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

УТВЕРЖДАЮ Проректор по научной работе Санкт-Петербургского государственного морского технического университета (СПбГМТУ), д.т.н, доцент Д. В. Никущенко ОТЗЫВ ведущей организации на диссертацию Сорокина Владимира Николаевича «Разработка методов и алгоритмов решения многомерных минимаксных задач тропической оптимизации», представленной на соискание ученой степени кандидата физико-математических наук по специальности 01.01.07 — Вычислительная математика Основные результаты исследовании н их новизна Диссертационная работа Сорокина В.Н. посвящена вопросам развития вычислительных методов решения и разработки приложений задач оптимизации, сформулированных в терминах тропической математики. Начало исследованиям в области тропической (идемпотентной) математики, которая изучает алгебраические системы с идемпотентным сложением, было положено в 1960-х годах в трудах Н.

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

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

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

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

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

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

Исследования по теме диссертации проводились в рамках научных проектов, поддержанных научными фондами РФФИ и РГНФ. Рекомендации по использованию результатов и выводов работы Предложенные в работе методы и вычислительные алгоритмы решения задач тропической оптимизации будут полезны при решении многих прикладных задач, возникающих при математическом моделировании естественнонаучных и научно-технических проблем, включая задачи сетевого планирования, размещения объектов и принятия решений. Разработанные программные средства могут быть использованы при численном решении перечисленных выше и других прикладных задач. Результаты диссертационной работы найдут применение в научной и учебной работе в исследовательских и учебных учреждениях, включая Санкт-Петербургский государственный морской технический университет, Санкт-Петербургский политехнический университет Петра Великого, Московский государственный университет, Санкт-Петербургский государственный университет, Липецкий государственный технический университет, Институт проблем управления им.

В. А. Трапезникова РАН, Санкт-Петербургский институт информатики и автоматизации РАН и др. Замечания по диссертации и автореферату 1. Во введении на стр.14 при описании результатов главы3 не понятно о каких семействах решений задачи, которые могут содержаться в других семействах решений идет речь. Автор, по-видимому, имел в виду подмножества семейства решений, которые могут содержаться в других подмножествах. См. также текст в первом абзаце подраздела «Процедуры построения полного решения» на стр. 65. 2. На стр.25 при использовании леммы 1 для решения неравенств следовало бы пояснить, почему условие этой леммы (регулярность матрицы) оказывается выполненным.

См. также применение леммы на стр. 27. 3. На стр. 30 указано, что для полученного в работе решения в явном виде можно точно определить число операций, необходимых для его вычисления, а не ограничиваться оценкой сложности вычислений. Однако затем приводится только оценка вычислительной сложности решений, а число операций не подсчитывается. Не вполне ясно, как получена оценка 2" для порядка общего числа слагаемых матричных сумм. 4. В численном примере решения двумерной задачи с ограничениями на стр, 38 получен результат, в котором у матрицы, генерирующей множество решений, оба столбца являются коллинеарными в тропическом смысле.

В этом случае параметрическую запись решения следовало бы упростить, оставив один столбец и сократив число параметров до одного (о возможности такого упрощения свидетельствует также приведенная на рис. 1.4. графическая иллюстрация решения в виде отрезка прямой). 5. При формулировке леммы 3 на стр. 45 одновременно используются обозначения обычного и тропического нулей. Представляется, что в контексте рассматриваемой прикладной задачи условие, в котором используется тропический нуль, будет всегда выполнено, и его из формулировки утверждения можно исключить. Кроме того, ссылка в формулировке на задачу (2.6) является ошибочной.

Должна быть указана ссылка (2.7). 6. На стр. 45 в начале подраздела «2.3 Численный пример» упоминается «следствие 3», которое отсутствует в тексте. По-видимому, имеется ввиду «лемма3». Аналогично, на стр.46 вместо «следствия 2.6» должна быть также указана «лемма 3». 7. На стр. 56 указана ошибочная ссылка на лемму 1.4, которая в тексте отсутствует. См. также ссылку на лемму 1.4 на стр. 67. 8. Описание на стр.

68 алгоритма 1 (для которого почему-то использован латинский заголовок А18ог1йтп1) слишком схематичное и не содержит многих деталей, необходимых для полного понимания его работы. 9. При описании выпуклого конуса и его граней на стр. 76 не ясно, о какой гиперплоскости (в обычном или тропическом смысле) говорится. Не вполне ясно, что понимается под 1/2~ частью пространства или гиперплоскости. Перечисленные замечания, однако, носят редакционный характер и не снижают ценности проведенного исследования. Общая оценка диссертации В целом диссертация Сорокина В. Н.

представляет собой завершенную научно-квалификационную работу. Совокупность научных и практических результатов, представленных в диссертации, можно рассматривать как решение актуальной задачи разработки и исследования новых вычислительных методов решения задач тропической оптимизации, а также их практического применения в решении практических задач планирования и управления. Диссертация соответствует критериям п, 9 (абзац 2) раздела 11 Положения о порядке присуждения ученых степеней, а также пп.