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

На правах рукописиСорокин Владимир НиколаевичРазработка методов и алгоритмов решениямногомерных минимаксных задачтропической оптимизацииСпециальность 01.01.07 –вычислительная математикаАвторефератдиссертации на соискание учёной степеникандидата физико-математических наукСанкт-Петербург – 2018Работа выполнена на кафедре статистического моделированияСанкт-Петербургского государственного университета.Научный руководитель:Кривулин Николай Кимович,доктор физико-математических наук, доцентОфициальные оппоненты:Ерохин Владимир Иванович,доктор физико-математических наук, профессор,Военно-космическая академия имени А.

Ф. Мо­жайского, старший научный сотрудникНиколаев Дмитрий Александрович,кандидат физико-математических наук,Липецкий государственный технический универ­ситет, доцент кафедры прикладной математикиВедущая организация:Федеральное государственное бюджетное образо­вательное учреждение высшего образования«Санкт-Петербургский государственный мор­ской технический университет»»2018 г. вчасов на заседанииЗащита состоится «диссертационного совета Д 212.232.49 на базе Санкт-Петербургского государ­ственного университета по адресу: 198504, Санкт-Петербург, Старый Петер­гоф, Университетский пр., д. 28, ауд.

405.С диссертацией можно ознакомиться в Научной библиотеке им. М. Горько­го Санкт-Петербургского государственного университета по адресу: 199034,Санкт-Петербург, Университетская наб., 7-9 и на сайте:https://disser.spbu.ru/files/disser2/disser/KqM3N92JNH.pdf.Автореферат разослан «»2018 г.Ученый секретарь диссертационного совета,доктор физико-математических наукЮ. В. ЧуринОбщая характеристика работыТропическая (идемпотентная) математика пред­ставляет собой раздел прикладной математики, который изучает теорию по­луколец и полуполей с идемпотентным сложением, а также связанные с нимивычислительные задачи. За последнее время тропическая математика сталаодной из быстро развивающихся ветвей математической науки, роль которойв качестве инструмента эффективного решения задач в экономике, технике,управлении и других сферах человеческой деятельности постоянно растет.Существует несколько основных причин для объяснения возросшего ин­тереса к тропической математике.

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

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

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

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

Начало активногоразвития тропической математики относится к 1950-60 годам, вскоре послепубликаций работ Р. А. Канингхейм-Грина, Н. Н. Воробьева, И. В. Романов­ского и А. А. Корбута. Идемпотентный анализ в том смысле, в котором онпонимается сейчас, был разработан научным коллективом академика В. П.Маслова.Изучению задач тропической математики посвящен ряд исследований,опубликованных за последние несколько десятилетий, включая работы рос­сийских авторов С. Л.

Блюмина, В. Д. Матвеенко, Д. Ю. Григорьева, А. Э. Гу­термана, Г. Б. Михалкина, Н. К. Кривулина, С. Н. Сергеева, Я. Н. Шитоваи других. За рубежом существенный вклад в развитие этой области внеслиработы Д. С. Голана, Ф. Л. Бачелли, Г. Я. Олсдера, К. Циммерманна, У. Цим­мерманна, С. Гобера, П. Бутковича и Б. Хейдерготта.Существует широкий класс задач оптимизации, в которых целевая функ­ция и ограничения выражаются при помощи операций максимума и миниму­ма, а также арифметических операций.

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

Одним из направлений развития этой области является разработкавычислительных методов и алгоритмов решения задач оптимизации, которыемогут быть сформулированы в терминах тропической математики (задач тро­пической оптимизации).Существует класс задач оптимизации, которые формулируются в терми­нах тропической математики, состоят в минимизации нелинейных функцио­налов, и могут иметь ограничения в виде линейных векторных неравенств.Решение некоторых таких задач опирается на экстремальное свойство спек­трального радиуса матрицы и связано с его вычислением.

Изучению этогокласса задач посвящены работы Р. А. Канингхейм-Грина, П. Бутковича и4Н. К. Кривулина, в которых были найдены решения для задачи без ограни­чений со сложной целевой функцией, а также для задачи с более простойцелевой функцией при наличии линейных ограничений на множество допу­стимых значений. При этом результаты для задачи с целевой функцией наи­более общего вида с линейными ограничениями известны не были.Также имеется ряд практических задач, которые сводятся к наилучшемуприближенному решению в смысле метрики Чебышева и псевдочебышевскойметрики векторных уравнений, заданных на пространствах векторов над тро­пическими полуполями.Исследованию задачи посвящен ряд работ, опубликованных в различноевремя, включая работы Р.

А. Канингхейм-Грина, К. Циммерманна, П. Бутко­вича и Н. К. Кривулина. Представленные в этих работах результаты обычносводятся к нахождению одного из решений и не позволяют определить всемножество решений задачи. Поэтому представляет интерес разработка мето­дов получения всех решений в явном виде в компактной векторной форме ипостроение вычислительных процедур поиска всех решений.Цели и задачи диссертационной работы. Целью диссертации яв­ляется исследование ряда задач тропической оптимизации для полученияих полного решения в явном виде, разработка эффективных методов длячисленного нахождения соответствующих решений, а также реализация этихметодов при решении прикладных задач, возникающих при математическоммоделировании задач сетевого планирования.

Для достижения указанной це­ли необходимо было сформулировать и решить следующие задачи:1. Решить задачу с псевдоквадратичной целевой функцией и линейнымиограничениями на множестве допустимых значений с использованиемаппарата тропической математики для нахождения полного решения вявном виде в простой аналитической форме.2. Реализовать численный метод, позволяющий найти решение этой зада­чи за полиномиальное по размерности задачи время.3. Разработать математическую модель задачи планирования мероприя­тий по ликвидации последствий аварии с радиоактивным загрязнениемместности, для решения которой может быть использовано полученноерешение и разработанный вычислительный метод.4. Использовать аппарат идемпотентной математики и технику разреже­ния матриц для нахождения полного множества решений расширеннойзадачи псевдочебышевской аппроксимации в тропическом векторномпространстве, а также реализовать численный метод получения этогомножества.5.

Исследовать тропическое линейное векторное неравенство и разрабо­тать метод нахождения множества всех его решений.5Содержаниедиссертационного исследования соответствует следующим пунктам паспортаспециальности 01.01.07 – «Вычислительная математика»: создание алгорит­мов численного решения задач алгебры, анализа, дифференциальных и инте­гральных уравнений, математической физики, теории вероятностей и стати­стики, типичных для приложений математики к различным областям наукии техники (пункт 1); разработка теории численных методов, анализ и обос­нование алгоритмов, вопросы повышения их эффективности (пункт 2); реа­лизация численных методов в решении прикладных задач, возникающих приматематическом моделировании естественнонаучных и научно-техническихпроблем, соответствие выбранных алгоритмов специфике рассматриваемыхзадач (пункт 4).Научная новизна.