Диссертация (Разработка методов и алгоритмов решения многомерных минимаксных задач тропической оптимизации)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиСорокин Владимир НиколаевичРАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВРЕШЕНИЯ МНОГОМЕРНЫХ МИНИМАКСНЫХЗАДАЧ ТРОПИЧЕСКОЙ ОПТИМИЗАЦИИСпециальность 01.01.07 —вычислительная математикаДиссертация на соискание учёной степеникандидата физико-математических наукНаучный руководитель:доктор физ.-мат.

наук, доцентКривулин Николай КимовичСанкт-Петербург — 20182ОглавлениеВведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 Задача с псевдоквадратичной целевой функцией и линейными ограничениями . . . . . . . . . . . . . . . . . . . . . . . .

. . . 151.1Элементы тропической математики . . . . . . . . . . . . . . . . .161.1.1Идемпотентное полуполе. . . . . . . . . . . . . . . . . . .161.1.2Алгебра матриц . . . . . . . . . . . . . . . . . . . . . . . . .171.2Линейные неравенства и их решения . . . . . . .

. . . . . . . . . .211.3Задачи тропической оптимизации . . . . . . . . . . . . . . . . . .221.4Задача оптимизации с ограничениями . . . . . . . . . . . . . . . .231.5Оценка вычислительной сложности . . . . . . . . . . . . . . . . .301.6Численные примеры . . . . .

. . . . . . . . . . . . . . . . . . . . .321.6.1Задача без ограничений . . . . . . . . . . . . . . . . . . . .321.6.2Задачи с ограничениями . . . . . . . . . . . . . . . . . . . .332 Практическое применение методов тропической оптимизациидля планирование работ по дезактивации .

. . . . . . . . . . . 402.1Задача ликвидатора . . . . . . . . . . . . . . . . . . . . . . . . . .412.2Решение задачи ликвидатора . . . . . . . . . . . . . . . . . . . . .442.3Численный пример . . . . . . . . . . . . . . . . . . . . . . . . . . .453 Задача псевдочебышевской аппроксимации в тропическомвекторном пространстве . . . . . . . . . . . . .

. . . . . . . . . . . 523.1Задачи тропической оптимизации . . . . . . . . . . . . . . . . . .533.2Предварительный анализ задачи . . . . . . . . . . . . . . . . . . .553.3Разрежение матрицы задачи . . . . . . . . . . . . . . . . . . . . .573.4Полное решение задачи . . . . . . . . . . . . . . . . . . . . . . . .613.5Процедуры построения полного решения . . . . . . . . . .

. . . .6533.6Алгоритм нахождения множества нижних границ . . . . . . . . .683.7Численный пример . . . . . . . . . . . . . . . . . . . . . . . . . . .694 Метод построения множества всех решений тропического линейного векторного неравенства . . . . . . . . . . . . . . . . . . . 754.14.24.3Метод нахождения решений неравенства . . . .

. . . . . . . . . .764.1.1Предварительная подготовка . . . . . . . . . . . . . . . . .764.1.2Общая идея . . . . . . . . . . . . . . . . . . . . . . . . . . .77Применение в задачах оптимизации . . . . . . . . . . . . . . . . .784.2.1Линейная задача оптимизации . . . . . . . . . . . . . . . .794.2.2Варианты работы с нелинейными задачами . . . . .

. . . .79Пример использования метода . . . . . . . . . . . . . . . . . . . .80Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86Список рисунков . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . 99А Программная реализация задачи с псевдоквадратичной целевой функцией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100Б Программная реализация расширенной задачи псевдочебышевской аппроксимации . . . . . . . . . . . . . . . . . . . . . . . 110В Схема поиска решений неравенства .

. . . . . . . . . . . . . . . 1204ВведениеАктуальность темы.Тропическая (идемпотентная) математика представляет собой раздел прикладной математики, который изучает теорию полуколец и полуполей с идемпотентным сложением, а также связанные с ними вычислительные задачи. Запоследнее время тропическая математика стала одной из быстро развивающихся ветвей математической науки, роль которой в качестве инструмента эффективного решения задач в экономике, технике, управлении и других сферах человеческой деятельности постоянно растет. Сильная взаимосвязь с нечеткой ибулевой логикой, дискретной математикой и методами оптимизации обеспечилией надежные позиции в задачах оптимального управления и принятия решений.Существует несколько основных причин для объяснения возросшего интереса к тропической математике. Во-первых, многие упомянутые задачи, в которыхцелевая функция в обычной математике является нелинейной и негладкой (исоответственно сложной для многих стандартных методов анализа), становятсялинейными при переходе на язык идемпотентной алгебры.

После этого решение таких задач может быть получено путем вычисления собственных чисел ивекторов матриц или решения линейных неравенств и уравнений. Во-вторых,многие вычислительные процедуры линейной алгебры, такие, например, какалгоритм Якоби и метод Гаусса-Зейделя имеют свои идемпотентные аналоги,которые позволяют строить эффективные вычислительные алгоритмы тропической математики. При этом открываются новые возможности для анализатаких задач, что во многих случаях приводит к упрощению как процедур ихчисленного решения, так и интерпретации полученных результатов.Помимо этого, эволюция многих динамических систем, играющих важнуюроль в практических задачах (например, системы и сети с очередями), можетбыть представлена в терминах линейных уравнений идемпотентной алгебры,5что обеспечивает основу для разработки новых подходов к численному (имитационному) моделированию таких систем.Тропическая математика имеет большое количество приложений к задачамоптимизации, включая задачи размещения, принятия решений, сетевого планирования и многим другим.

Значительная часть этих задач может быть решенас использованием точных конечношаговых вычислительных методов, таких какметоды линейного и смешанного целочисленного линейного программированияи т.п. В этих методах применяются итерационные процедуры, с помощью которых можно численно получить одно из решений, если решение существует,либо убедиться в отсутствии решений.В отличие от решений с помощью указанных процедур, решения на основеметодов тропической оптимизации во многих случаях предоставляют возможность нахождения всего множества решений в явном виде в простой матричновекторной форме, удобной как для аналитического исследования множества решений, так и для создания алгоритмов численного решения.

Полученное такимобразом множество решений может быть напрямую использовано в других задачах в качестве области допустимых значений, обеспечивая композицию решенийразличных задач. Прямые явные решения позволяют проводить дальнейшееисследование множества решений математическими методами, изучать влияние дополнительных ограничений, точно определять трудоемкость нахождениярешений, а также строить экономичные процедуры для последовательных ипараллельных вычислений. Эти решения обычно представляют значительныйинтерес, что делает тему настоящей работы, направленной на разработку, обоснование и исследование эффективности прямых точных методов решения задачтропической оптимизации и их приложений, весьма актуальной.Степень разработанности темы.Понятие полукольца, которое является центральным понятием тропическойматематики, по-видимому, как указывается в работах [1, 2], впервые было введено Г.

Вандивером в 1934 году в статье [3], хотя неявное использование присутствует уже в книге Р. Дедекинда [4] 1894 года и некоторых других работах. Вдальнейшем на протяжении длительного времени полукольца и их различныеаспекты исследовались многими математиками в связи с большим количествомтеоретических и прикладных вычислительных задач, в которых эти полукольца6возникали. Однако начало наиболее активного развития тропической математики относится к 1950-60 годам, вскоре после публикаций работ С. К. Клини [5]в 1956, Р. А.

Канингхейм-Грина [6] в 1962 и Н. Н. Воробьева [7–9] в 1963, 1967и 1970 годах.Если обратиться к истории развития тропической математики в России, тостатья [8] была одной из первых на этапе ее становления. Появлению этой статьи предшествовали как различные теоретические работы (например по теорииструктур [10] и -пространств [11]), так и многочисленные возникшие практические задачи вычислительной математики. Как указывает в ней Н. Н. Воробьев: «...к построению такой теории приводит и необходимость обобщения рядаконкретных фактов, встречавшихся в различных прикладных математическихтеориях.

Достаточно сослаться на статьи А. Г. Лунца [12] и Н. Г. Поварова [13]по теории релейно-контактных схем, а также А. Шимбела [14], Р. Беллмана и У.Каруша [15] и др., исследовавших вопросы путей в графе.» ( [8], стр. 42) Помимопроектирования контактных схем, подобные вычислительные задачи в том илиином виде возникли также во многих других областях народного хозяйства (см.например работу Л. В. Канторовича [16] 1942 года). В частности, «идеи экстремального гармонического анализа... в духе динамического программированияразбирает И.

В. Романовский [17, 18]» ( [8], стр. 42).Помимо работ Н. Н. Воробьева стоит отметить статьи А. А. Корбута [19,20], в которых проводятся дальнейшие исследование введенных в этих работах«экстремальных векторных пространств».Различные аспекты идемпотентной математики изучались также С. Н. Самборским. В частности, в работе [21] рассматривается вопрос существованиянетривиального спектра эндоморфизма над идемпотентным полумодулем, атакже исследуется асимптотическое поведение при итерациях и сходимость «рядов Неймана», проявляющихся при решении уравнений = ⊕ .Идемпотентный анализ в том смысле, в котором он понимается сейчас, былразработан научным коллективом академика В.