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

отзыв научного руководителя на диссертационную работу Сорокина Владимира Николаевича «Разработка методов и алгоритмов решения многомерных минимаксных задач тропической оптимизации», представленную на соискание ученой степени кандидата физико-математических наук по специальности 01.01.07 — Вычислительная математика Диссертационное исследование посвящено развитию теории и разработке алгоритмов методов решения задач оптимизации, которые формулируются в терминах тропической (идемпотентной) математики и состоят в минимизации функций, заданных на пространствах векторов над полуполями с идемпотентным сложением.

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

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

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

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

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

Оформление диссертации отвечает установленным требованиям. Структура и содержание работы соответствуют поставленным целям и задачам исследования. Основные научные результаты опубликованы в журналах, рекомендованных ВАК РФ, и в других изданиях. Результаты апробированы на научных конференциях. Исследования проводились в рамках научных проектов, поддержанных фондами РФФИ и РГНФ. Считаю, что диссертация «Разработка методов и алгоритмов решения многомерных минимаксных задач тропической оптимизации», отвечает требованиям, предъявляемым к кандидатским диссертациям Положением о присуждении ученых степеней, а ее автор, Сорокин Владимир Николаевич„заслуживает присуждения ему ученой степени кандидата физико-математических наук по специальности 01.01,07 Вычислительная математика. Научный руководитель: профессор кафедры статистического моделирования СПбГУ, доктор физико;,~айтемфг1я~еских наук, доце 29 марта 2ф3:-Ё ~-й Г, ФФ )' .

~к)ю улин .