Диссертация (1150576), страница 2
Текст из файла (страница 2)
П. Маслова [22–28] в восьмидесятых годах XX века в Москве [29].В настоящее время в тропической математике существуют различные направления развития. Помимо применения чисто алгебраических методов, как,например, в работах Н. К. Кривулина [30–32] и С. Н. Сергеева в [33–35], суще-7ствует и геометрический подход, связанный с изучением тропической геометрии, применяемый Г. Б. Михалкиным [36–38] и М. Э. Казаряном [39].Существует широкий класс задач оптимизации, в которых целевая функцияи ограничения выражаются при помощи операций максимума и минимума, атакже арифметических операций.
К этому классу относятся, например, некоторые задачи размещения [40–43] и сетевого планирования [6, 44–46]. Решениетаких задач часто сопряжено с определенными трудностями, которые могутбыть связаны, в частности, с нелинейностью и негладкостью целевой функциии ограничений.Во многих случаях решение подобных задач можно упростить путем ихпредставления на языке тропической математики и использования ее результатов [47–49]. Тропическая (идемпотентная) математика охватывает область,связанную с изучением теории полуколец с идемпотентным сложением и ееприложениями [22, 32, 40, 45, 50, 51]. Одним из направлений развития этой области является разработка вычислительных методов и алгоритмов решения задачоптимизации, которые могут быть сформулированы в терминах тропическойматематики (задач тропической оптимизации).Изучению задач тропической оптимизации посвящен ряд исследований,опубликованных за последние несколько десятилетий.
К числу таких публикаций относятся ранние работы [6, 44, 45], которые положили начало развитиюэтого направления, а также недавние работы [31, 42, 46, 52–58].Существует класс задач оптимизации, которые формулируются в терминахтропической математики, состоят в минимизации нелинейных функционалов,и могут иметь ограничения в виде линейных векторных неравенств [30]. Решение некоторых таких задач опирается на экстремальное свойство спектральногорадиуса матрицы и связано с его вычислением [31, 52, 54, 59].Также имеется ряд практических задач (см., например, [8, 44, 60–62]), которые сводятся к наилучшему приближенному решению в смысле метрики Чебышева векторного уравнения = , где и обозначают заданные матрицу ивектор, – неизвестный вектор, а произведение матрицы на вектор понимаетсяв смысле тропической математики.Проблема чебышевской аппроксимации для решения рассматриваемогоуравнения сводится к задаче нахождения векторов , на которых достигает-8ся минимум в задачеmin ()− ⊕ − ,где матричные и векторные операции понимаются в смысле идемпотентной алгебры.Исследованию задачи посвящен ряд работ, опубликованных в различное время, включая работы [40, 44, 60–62].
Представленные в этих работах результатыобычно сводятся к нахождению одного из решений и не позволяют определитьвсе множество решений задачи. Поэтому представляет интерес разработка методов получения всех решений в явном виде в компактной векторной форме ипостроение вычислительных процедур поиска всех решений.Цели и задачи работы. Целью диссертации является исследование рядазадач тропической оптимизации для получение их полного решения в явномвиде, разработка эффективных методов для численного нахождения соответствующих решений, а также реализация этих методов при решении прикладныхзадач, возникающих при математическом моделировании задач сетевого планирования. Для достижения указанной цели необходимо было сформулировать ирешить следующие задачи:1.
Решить задачу с псевдоквадратичной целевой функцией и линейнымиограничениями на множестве допустимых значений с использованием аппарата тропической математики для нахождения полного решения в явном виде в простой аналитической форме и представлении его в форметеоремы.2. Реализовать численный метод, позволяющий найти решение этой задачиза полиномиальное по размерности задачи время.3. Разработать математическую модель задачи планирования мероприятийпо ликвидации последствий аварии с радиоактивным загрязнением местности, для решения которой может быть использована доказанная теорема и разработанный вычислительный метод.4. Использовать аппарат идемпотентной математики и технику разреженияматриц для нахождения полного множества решений расширенной задачи псевдочебышевской аппроксимации (которая при некоторых условиях9становится чебышевской) в тропическом векторном пространстве, а такжереализовать численный метод получения этого множества.5.
Исследовать тропическое линейное векторное неравенство и разработатьметод нахождения множества всех его решений.Соответствие диссертации паспорту специальности. Содержаниедиссертационного исследования соответствует следующим пунктам паспортаспециальности 01.01.07 – «Вычислительная математика»: создание алгоритмовчисленного решения задач алгебры, анализа, дифференциальных и интегральных уравнений, математической физики, теории вероятностей и статистики,типичных для приложений математики к различным областям науки и техники (пункт 1); разработка теории численных методов, анализ и обоснованиеалгоритмов, вопросы повышения их эффективности (пункт 2); реализация численных методов в решении прикладных задач, возникающих при математическом моделировании естественнонаучных и научно-технических проблем, соответствие выбранных алгоритмов специфике рассматриваемых задач (пункт 4).Научная новизна.
В диссертации обобщен ряд задач тропической оптимизации с псевдоквадратичной целевой функцией, решение которых получаетсяприменением разработанного точного конечношагового численного метода, вкотором количество шагов известно заранее, а шаги представляют собой применение простых матрично-векторных операций. Полученные результаты обеспечивают дальнейшее развитие теории численных методов задач тропическойоптимизации.Найдено новое применение полученных результатов в реализации численных методов в решении прикладной задачи планирования операции по ликвидации последствий радиационной аварии при наличии ограничений на срокивыполнения работ.Впервые получено полное решение задачи с псевдочебышевской метрикой,для которой был разработан точный численный метод получения множествавсех решений.
Предложен конечношаговый алгоритм, который используетсядля построения общего решения, представленного в компактной матричновекторной форме.10Все основные результаты, выносимые на защиту, являются новыми и получены автором лично или при его определяющем участии.Теоретическая и практическая ценность работы. Результаты работы имеют теоретическую ценность и могут быть использованы для решенияреальных задач сетевого планирования. В частности, как было показано в главе 2, с их помощью можно оптимальным образом наметить план действий поликвидации последствий чрезвычайной ситуации антропогенной природы.Результатом работы стало получение полного решения для двух задач тропической оптимизации, которые могут быть использованы в комбинации с другими задачами и ограничениями.
Матрично-векторная форма решений предполагает естественное распараллеливание вычислений.Для задачи с псевдоквадратичной целевой функцией и линейными ограничениями решение записано в простой аналитической форме в удобном виде,что делает возможным проведение дальнейшего аналитического исследованияматематическими методами.Методология и методы исследования. В работе применяются инструменты линейной алгебры, общей теории чисел, теории экстремальных задач,математического моделирования, а также методы оптимизации, теории сложности вычислений, компьютерного моделирования, построения математическихмоделей сложных систем и идемпотентной математики. Программирование велось на языке высокого уровня (R).Положения, выносимые на защиту:– Полностью решена задача с псевдоквадратичной целевой функцией и линейными ограничениями, решение получено в явном виде в простой аналитической форме с использованием матрично-векторных операций.– Разработан точный конечношаговый численный метод построения решения этой задачи с полиномиальной по размерности задачи сложностью, где все шаги представляют собой выполнение простых матричновекторных операций.– Представлена математическая модель задачи сетевого планирования мероприятий по ликвидации чрезвычайной ситуации, которая решается путем применения разработанного численного метода.11– Решена расширенная задача псевдочебышевской аппроксимации в тропическом векторном пространстве с использованием разрежения матрицызадачи.
Разработан точный численный метод нахождения множества всехрешений задачи, а также процедуры, позволяющие уменьшить вычислительную сложность этого метода. Предложен конечношаговый алгоритм,который используется для построения общего решения, представленногов компактной векторной форме.– Получены результаты исследования линейного векторного неравенства,построена схема нахождения множества всех решений неравенства. Предложены варианты использования схемы как в линейной, так и в нелинейной задачах оптимизации в случаях, когда присутствуют ограничения намножество допустимых значений в форме рассматриваемого неравенства.Степень достоверности изложенных в работе теоретических результатов обеспечивается их строгим математическим доказательством.
Кроме того,достоверность результатов подтверждается сравнением с ранее известными результатами. В работе приводятся полные доказательства для теорем, доказанных диссертантом; для прочих использованных утверждений приведены ссылкина доказательства.Апробация результатов. Результаты данной работы докладывались намеждународной конференции International Scientific Conference «MathematicalModeling» (Borovets, Bulgaria – 2017); на I Международной научнопрактической конференции «Теоретические и прикладные вопросы комплексной безопасности» (Санкт-Петербург, Россия – 2018); на семинарах кафедрыстатистического моделирования Санкт-Петербургского государственного университета, семинаре «Стохастическая оптимизация в информатике» СПбГУ исеминаре СПбГУ и СПб ЭМИ по тропической математике и смежным вопросам.Результаты работы использовались при создании рабочего прототипа на хакатоне «EdHack: Chatbots and AI», проводившегося в рамках Международнойконференции по новым образовательным технологиям EdCrunch (Москва, Россия – 2016).Результаты диссертационной работы были получены при поддержке грантовРоссийского гуманитарного научного фонда РГНФ (№16-02-00059 – «Развитие12моделей и методов тропической математики в прикладных задачах экономикии управления» и №13-02-00338 – «Модели и методы тропической математикив прикладных задачах экономики и управления»), а также гранта Российскогофонда фундаментальных исследований РФФИ №18-010-00723А – «Разработкамоделей и методов тропической математики для прикладных задач экономикии управления».Публикации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
