Автореферат (1150574), страница 2
Текст из файла (страница 2)
В диссертации обобщен ряд задач тропической оптимизации с псевдоквадратичной целевой функцией, решение которых получается применением разработанного точного конечношагового численногометода, в котором количество шагов известно заранее, а шаги представляют собой применение простых матрично-векторных операций. Полученныерезультаты обеспечивают дальнейшее развитие теории численных методовзадач тропической оптимизации.Найдено новое применение полученных результатов при разработке численных методов решения прикладной задачи планирования операции по ликвидации последствий радиационной аварии при наличии ограничений на сроки выполнения работ.Впервые получено полное решение задачи с псевдочебышевской метрикой, для которой был разработан точный численный метод получения множества всех решений.
Предложен конечношаговый алгоритм, который используется для построения общего решения, представленного в компактной матрично-векторной форме.Теоретическая и практическая значимость. Результаты работыимеют теоретическую ценность и могут быть использованы для решения реальных задач сетевого планирования.
В частности, как было показано в главе 2, с их помощью можно оптимальным образом наметить план действий поликвидации последствий чрезвычайной ситуации антропогенной природы.Результатом работы стало получение полных решений для двух задачтропической оптимизации, которые могут быть использованы в комбинациис другими задачами и ограничениями. Матрично-векторная форма решенийпредполагает естественное распараллеливание вычислений.Для задачи с псевдоквадратичной целевой функцией и линейными ограничениями решение записано в простой аналитической форме в удобном виде,что делает возможным проведение дальнейшего аналитического исследования множества решений математическими методами.Методология и методы исследования.
В работе применяются инструменты линейной алгебры, общей теории чисел, теории экстремальныхСоответствие диссертации паспорту специальности.6задач, математического моделирования, а также методы оптимизации, теории сложности вычислений, компьютерного моделирования, построения математических моделей сложных систем и идемпотентной математики. Программирование велось на языке высокого уровня R.Положения, выносимые на защиту.1. Полностью решена задача с псевдоквадратичной целевой функцией илинейными ограничениями, решение получено в явном виде в простойаналитической форме с использованием матрично-векторных операций.2.
Разработан точный конечношаговый численный метод построения решения этой задачи с полиномиальной по размерности задачи сложностью, где все шаги представляют собой выполнение простых матричновекторных операций.3. Представлена математическая модель задачи сетевого планированиямероприятий по ликвидации чрезвычайной ситуации, которая решаетсяпутем применения разработанного численного метода.4. Решена расширенная задача псевдочебышевской аппроксимации в тропическом векторном пространстве с использованием разрежения матрицы задачи. Разработан точный численный метод нахождения множества всех решений задачи, а также процедуры, позволяющие уменьшитьвычислительную сложность этого метода.
Предложен конечношаговыйалгоритм, который используется для построения общего решения, представленного в компактной векторной форме.5. Получены результаты исследования линейного векторного неравенства,построена схема нахождения множества всех решений неравенства. Предложены варианты использования схемы в задачах оптимизации в случаях, когда присутствуют ограничения на множество допустимых значений в форме рассматриваемого неравенства.Достоверностьизложенных в работе теоретических результатов обеспечивается их строгимматематическим доказательством. Кроме того, достоверность результатов подтверждается сравнением с ранее известными результатами. В работе приводятся полные доказательства для теорем, доказанных диссертантом; для прочих использованных утверждений приведены ссылки на доказательства.Результаты данной работы докладывались на международной конференции International Scientific Conference «Mathematical Modeling» (Borovets,Bulgaria – 2017); на I Международной научно-практической конференции«Теоретические и прикладные вопросы комплексной безопасности» (СанктПетербург, Россия – 2018); на семинарах кафедры статистического моделирования Санкт-Петербургского государственного университета, семинаре «СтоСтепень достоверности и апробация результатов.7хастическая оптимизация в информатике» СПбГУ и семинаре СПбГУ и СПбЭМИ по тропической математике и смежным вопросам.Результаты работы использовались при создании рабочего прототипана хакатоне «EdHack: Chatbots and AI», проводившегося в рамках Международной конференции по новым образовательным технологиям EdCrunch(Москва, Россия – 2016).Результаты диссертационной работы были получены при поддержке грантов Российского гуманитарного научного фонда (РГНФ) №16-02-00059 – «Развитие моделей и методов тропической математики в прикладных задачах экономики и управления» и №13-02-00338 – «Модели и методы тропической математики в прикладных задачах экономики и управления», а также гранта Российского фонда фундаментальных исследований (РФФИ) №18-010-00723А –«Разработка моделей и методов тропической математики для прикладныхзадач экономики и управления».Публикации.
Основные результаты работы представлены в 2 печатныхработах [1, 2], опубликованных в рецензируемых научных изданиях, рекомендованных ВАК при Минобрнауки России, переводы которых [3, 4] индексируются в международных библиографических базах Scopus и Web Of Science.Всего по результатам диссертации автором опубликовано 5 печатныхработ [1, 2, 5–7].В совместных работах с Кривулиным Н. К. [1, 2, 5, 6] соискателю принадлежит формулировка и доказательства теорем о решении задачи с псевдоквадратичной целевой функцией и линейными ограничениями, а такжерасширенной задачи псевдочебышевской аппроксимации в тропическом векторном пространстве, разработка алгоритмов и программных средств, проведение вычислительных экспериментов для верификации полученных результатов, соавтору принадлежат постановки задач и выбор методов решения.Личный вклад автора.
Все основные результаты, выносимые на защиту, являются новыми и получены автором лично или при его определяющемучастии.Структура и объем диссертации. Диссертация состоит из введения,четырех глав, заключения и трех приложений. Общий объём диссертациисоставляет 123 страниц. В тексте содержится 1 таблица и 5 рисунков. Библиография работы состоит из 103 наименований.Содержание работыВ первой главе приводятся основные понятия и результаты тропической математики, на которые опираются решения, представленные в остальной части работы. Затем проводится исследование задачи с псевдоквадратичной целевой функцией и линейными ограничениями.Рассмотрим набор ⟨X, ⊕, ⊙, 0, 1⟩, где X – непустое множество, на кото8ром определены операции сложения ⊕ и умножения ⊙.
Сложение идемпотентно: для любого ∈ X выполняется ⊕ = . Умножение дистрибутивноотносительно сложения и обратимо для всех элементов, кроме 0.Примеры идемпотентных полуполей на множестве вещественных чисел:Rmax,+ = ⟨R ∪ {−∞}, max, +, −∞, 0⟩, Rmin,+ = ⟨R ∪ {+∞}, min, +, +∞, 0⟩,Rmax,× = ⟨R+ ∪ {0}, max, ×, 0, 1⟩, Rmin,× = ⟨R+ ∪ {+∞}, min, ×, +∞, 1⟩, гдеR+ = { ∈ R| > 0}.Обозначим через X× множество матриц над X, состоящих из строки столбцов.
Матрица, все элементы которой равны 0, считается нулевой.Матрица, у которой нет нулевых строк (столбцов), называется регулярнойпо строкам (столбцам). Матрица, состоящая из одного столбца или строки,образует вектор. Множество вектор-столбцов размерности с элементами изX обозначается X . Вектор регулярен, если у него нет нулевых компонент.Матрично-векторные операции сложения и умножения вводятся аналогично операциям в стандартной алгебре с заменой соответствующих покомпонентных операций на ⊕ и ⊙.Мультипликативно сопряженным транспонированием ненулевой матрицы = ( ) будем называть преобразование, при котором она трансформи−−1руется в транспонированную матрицу − = (− ) с элементами = ,если ̸= 0, и − = 0 в противном случае.Рассмотрим квадратные матрицы из X× .
Обозначим через единичную матрицу, на главной диагонали которой стоят 1, а вне ее – 0. След квадратной матрицы = ( ) вычисляется по формуле tr = 11 ⊕ · · · ⊕ .Введем функцию, которая ставит в соответствие любой матрице ∈×Xскаляр по правилу Tr() = tr ⊕ · · · ⊕ tr .При условии, что Tr() ≤ 1, введем оператор, который сопоставляетматрице матрицу * = ⊕ ⊕ · · · ⊕ −1 .Скаляр является собственным числом матрицы , если существуетненулевой вектор такой, что = .Максимальное собственное число называется спектральным радиусомматрицы и вычисляется по формуле = tr() ⊕ · · · ⊕ tr1/ ( ).Вектор, все компоненты которого равны 1, обозначается 1 = (1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
