Введение к работе
Актуальность темы. Модели и методы оптимизации являются мощным инструментом повышения эффективности функционирования технических, социально-экономических и других систем. Эти модели традиционно разделяются на статические и динамические. В статических моделях описание развития процесса го времени не производится. Динамические же модели такое описание дают.
Среди моделей оптимизации наибольшее применение получили линейные модели. Наиболее распространенной статической моделью оптимизации является задача линейного программирования в конечномерном пространстве. При этом часть, а возможно и все переменные этой задачи могут быть подчинены дополнительному условии целочис-лешости.
Существует большое число разнообразных линейных динамических моделей оптимизации. К ним относятся задачи линейного динамического программирования как в непрерывном, так и в дискретном времени, различные задачи теории расписаний, календарного и сетевого планирования. Как и раньше, часть, а возможно и все неизвестные функции этих задач могут принимать только целочисленные значения.
Метод штрафных функций является одним из наиболее популярных методов решения экстремальных задач. Он позволяет "мягко" учитывать некоторые из ограничений, заменять задачи со сложными системами ограничений задачами с простыми системами ограничений или вовсе без них, решать задачи с несовместными системами ограничений. Обычно он используется для получения приближенных решений. Его вариант - метод точных штрафных функций позволяет находить оптимальные решения уже при конечных значениях штрафных коэффициентов, что значительно ослабляет проблему плохой обусловленности, характерную для метода штрафных функций. Поэтому этот вариант может быть использован для получения точных решений.
Цель работы. Целью настоящей диссертационной работы является развитие теоретического и вычислительного аспектов метода точных штрафных функций для линейных статических ж динамических задач оптимизации с целочисленными переменными и неизвестными функция-
ми.
Метода исследования! В качестве методов исследования использованы аппарат выпуклого и математического анализа, теория линейного и целочисленного линейного программирования.
Научная новизна. Научная новизна диссертационной работы заключается в применении метода точных штрафных функций в общем виде и с использованием слабо двойственных задач к задачам оптимизации с целочисленными переменными и функциями.
В рамках этого подхода в терминах существования решений слабо двойственных задач, удовлетворяющих соответствующим ограничениям, получены необходимые и достаточные условия применимости метода точных штрафных функций к задачам смешанного целочисленного линейного программирования, достаточные условия существования оптимальных решений задач оптимизации точных штрафных функций, достаточные условия совпадения множеств этих решений с множествами оптимальных решений исходных задач смешанного целочисленного линейного программирования.
Кроме того разработана общая схема метода решения задач оптимизации точных штрафных функций, в котором штрафные коэффициенты являются произведениями множителей, определяемых последовательно на соответствующих итерациях. Установлена эквивалентность этого метода соответсвувдему улучшенному варианту метода последовательной оптимизации. Выведены формулы, предназначенные для вычисления начальных значений штрафных коэффициентов.
Сформулирована общая и простая постановка задачи линейного динамического программирования со свертками. Показана возможность описания с помощью сверток широкого класса ограничений.и задач теории расписаний, календарного и сетевого планирования. Для данной постановки развиты теоретический и вычислительный аспекты метода точных штрафных функционалов.
Практическая ценность. Для практической проверки полученных е диссертации результатов было разработано программное обеспечение. Оно реализует метод ограниченных ветвей и границ и использует пакет нелинейной и линейной оптимизации Омега. О помощью этого программного обеспечения был успешно решен ряд задач планирования дискретного производства с реальными данными.
Разработанные в диссертации методы могут быть использованы
для решения практических задач смешанного целочисленного линейного программирования и календарного планирования большой размерности в тех случаях, когда не требуется жесткого выполнения всех ограничений, когда эти задачи могут не иметь допустимых решений или когда достаточно найти приближенное решение.
Апробация работы. Результаты настоящей диссертации докладывались на Всесоюзном рабочем совещании по численным методам решения экономических задач (г. Звенигород, Московская обл., 1976 г.), Всесоюзном семинаре "Методы дискретной оптимизации в АСУ" (г. Алушта, 1983 г.), Всесоюзном семинаре "Дискретная оптимизация: методы и приложения" (г. Севастополь, 1984 г.), Всесоюзной конференции "Методы математического программирования и программное обеспечение" (г. Свердловск, 1989 г.), Международной конференции по проблемам управления (г. Москва, 1999 г.), на научных семинарах Вычислительного центра РАН, Института проблем управления РАН, Института системного анализа РАН, Международного научно-исследовательского института проблем управления, Московского государственного университета. Центрального экономико-математического института РАН.
Публикации. По теме диссертации опубликовано 20 научных работ. Все результаты диссертационной работы получены автором лично.
Структура и объеи работы. Диссертационная работа состоит из введения, шести глав, заключения, списка литературы из 167 наименований, приложения и двух таблиц. Текст диссертации без списка литературы, приложения и таблиц составляет 272 страницы машинописного текста, общий объем - 296 страниц.
