О методах решения робастных задач комбинаторной оптимизации

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