Автореферат (1150574)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

На правах рукописиСорокин Владимир НиколаевичРазработка методов и алгоритмов решениямногомерных минимаксных задачтропической оптимизацииСпециальность 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).Научная новизна.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации