Введение к работе
Актуальность темы. В настоящее время резко возрос интерес исследователей к вопросам управления сложными объектами. Возникающие при этой проблемы невозможно всесторонне рассмотреть без привлечения формализованных методов решения, основой которых является теория решения экстремальных задач. Довольно большой раздел в этой теории занимают методы оптимизации.
Основным критерием эффективности при теоретическом анализе методов оптимизации, как правило, считается сходимость и скорость сходимости итерационных процессов. Однако, при практическом применении становится ясно, что сходимость алгоритма пусть даже за конечное число шагов не полностью отвечает критериям эффективности, даже для достаточно просто реализуемых алгоритмов.
Уже хорошо известны примеры задач линейного программирования, на которых стандартая реализация симплекс-метода работает экспоненциальное по входу число шагов, то есть метод может быть эквивалентен перебору всех вершин допустимого многогранника. Аналогичные результаты известны и для других задач.
Поэтому, в последние годы актуальное значение имеет разработка, изучение и модификации методов, которые решали бы, например, задачу линейного программирования за полиномиальное время.
К числу таких методов относятся так называемые методы "погружения-отсечения".
Теория полиномиальных алгоритмов является бурноразвивающейся и при этом можно выделить два направления - разработка новых методов и развитие существующих.
Данная работа относится ко второму направлению.
Цель работы. Развитие и модифицирование метода и алгоритма симплексных погружений, который является современным эффективным методом для решения задач выпуклого программирования, идейно близким к широко известным методам Л.Г. Хачияна, Н.Кармаркара и другим полиномиальным на классе задач линейного программирования методам. Получение оценок сокращения объема (скорости сходимости) метода при его модификациях. Тестирование "базового" и "модифицированного" алгоритмов.
Методы исследования. Для обоснования и доказательств основных
положений диссертации используются методы выпуклого анализа и математического программирования.
Научная новизна и практическая ценность результатов.
-
Разработана эффективная версия метода симплексных погружений, скотгасть сходимости которой в среднем лучттто чен в базовом иетоде. Приведено соответствующее теоретическое обоснование.
-
Предложена новая модификация метода симплексных погружений, основанная на одновременном введении нескольких отсекающих плоскостей. Исследована минимаксная задача специального вида для реализации этой модификации.
-
Предложена двухэтапная процедура для решения задач выпуклого программирования, комбинирующая модифицированный метод симплексных погружений с решением задачи минимизации выпуклой функции на параллелепипеде.
-
Проведенное тестирование метода показало, что рассмотренные в работе новые версии позволяют ускорить работу базового алгоритма в среднем в 1.4 раза.
-
Применение метода симплексных погружений для решения прикладных задач термодинамики позволило выявить неоднозначность решения на примере изомеризации гексана, что послужило дальнейшему развитию теории термодинамических химических цепей.
Апробация работы. Результаты работы докладывались на конференциях "Методы математического программирования и их приложения" (Екатеринбург, 1991, 1995), на международной конференции по исследованию операций (Берлин, 1994), на конференциях молодых ученых СЭИ СО РАН (Иркутск, 1991, 1994) на научных семинарах СЭИ СО РАН.
Структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы, содержащего 35 наименований. Она содержит 8 рисунков, 9 таблиц. Работа изложена на 74 страницах машинописного текста.
