Введение к работе
Актуальность темы. Математическими моделями многих задач планирования и управления производством являются модели дискретной (целочисленной) оптимизации.Точные алгоритмы решения задач дискретной оптимизации (ДО) базируется на таких общих подходах как 1) методы последовательного анализа вариантов (включая динамическое программирование), 2)методы ветвей и границ, 3)методы отсечений, 4)методы построения последовательности решений, 5)методы, использующие обобщенные функции (множители) Ла-гранжа. Отметим, что среди перечисленных, подходы 1), 2) и 4) позволяют в принципе строить двусторонние алгоритмы. Приближенные алгоритмы базируются, в основном, на схемах локальной и субградиентной оптимизации. Несмотря на успехи в решении отдельных классов (главным образом линейных) задач ДО с несколькими сотнями переменных, в общем случае нельзя быть уверенным в решении произвольных задач с 30-40 целочисленными переменными, поэтому разработка новых универсальных подходов по-прежнему актуальна. Особенно это относится к подходам, позволяющим в рамках единой теоретической схемы строить двусторонние алгоритмы решения задач ДО.
Определенные новые возможности для решения широкого класса задач оптимизации, в том числе и задач дискретной (представляемых в виде многошаговых процессов с одно- и многомерным аргументом), предоставляются используемыми здесь достаточными условиями оптимальности В.Ф. Кротова, ядром которых является задание разрешающей функции ЧчІ,У ) .Реализация тех или иных условий оптимальности для заданной функции 44t,o) позволяет строить в основном двусторонние алгоритмы решения задач ДО, осуществляющие приближение по функционалу как "сверху",так и "снизу". Конкретизация вида функции ЦЧ'ЦУ) (линейный, нелинейный) позволяет получить алгоритмы различной степени "силы" (и, соответственно, сложности). Помимо перечисленных "методологических" свойств функции ЧІ'цЧ") с ее помощью часто удается учесть специфику конкретной рассматриваемой задачи, в силу чего как показывает опыт разработки алгоритмов, включая численный эксперимент, последние обладают определенной новизной и эффективностью. Вместе с тем подход, связанный с заданием функции тлі.,") позволяет исполь-
зовать и полезные идеи, полученные' ранее с помощью других подходов .
Большинство рассмотренных в диссертации алгоритмов осуществляет приближение "снизу" по функционалу. Основой алгоритмов этой группы является дальнейшая конкретизация способов построения функции
№,9) -элементарная операция (ЭО) улучшения функции 4^(t,4) ,
с помощью которой последовательно увеличивается значение определенной нижней границы исходного функционала - (.-функционала. В работе проводится дальнейшее развитие идей, основанных на реализации ЭО, особенно в применении к многоиндексным задачам ДО. Определенная идейная общность последнего подхода прослеживается с подходами 2), 3), 4) и особенно 5), то есть с методами, использувщими в той или иной степени следующую универсальную идею: расширение множества допустимых решений за счет отбрасывания части ограничений исходной задачи или введения функционалов-минорант, решение задачи оптимизации на расширенном множестве и затем аппроксимация допустимыми решениями решения на расширенном множестве.
Б диссертации на основе единой теоретической базы (достаточных условий оптимальности) исследуются следующие задачи математического программирования: общая задача выпуклого непрерывного (включая линейную) программирования с двусторонними ограничениями; линейные задачи назначения и распределения, являющиеся частными случаями транспортной задачи; симметричная, обобщенная и триплапарная задачи назначения; многомерная задача о ранце с сепарабелышм функционалом; задачи оптимального резервирования и целочисленного целераспределения; задачи коммивояжера и квадратичного назначения. Последние, как известно, являются в'настоящее время "полигоном" для проверки эффективности новых общих методов решения соответственно для линейных и нелинейных задач целочисленного программирования.
Вместе с тем развиваемый в диссертации подход можно использовать не только для решения перечисленных выше классов статических задач ДО, но и динамических, а также многошаговых задач оптимального управления с одно- и многомерным аргументом с ограничениями на управление (на все или только часть) топологи-
*)Кротов В.Ф. Вычислительные алгоритмы решения и оптимизации управляемых систем уравнений, I II.-Изв. АН СССР,Сер. Техническая кибернетика, 1975, N5, с.3-15; 1975, N6,с. 3-ІЗ.
чесного характера (несвязность множества ограничений на управление, в том числе целочисленность и т.д.).
Цель и задачи исследования - создание нового подхода для решения широкого класса задач ДО (и некоторых специальных задач теории оптимального управления) на основе единой теоретической базы - достаточных условий оптимальности, и разработка на его основе новых, главным образом двусторонних алгоритмов решения этих задач.
Метод исследования. В работе используются современные достижения в области дискретной оптимизации, включая теорию сложности решения таких задач, теории выпуклого и линейного программирования, теории оптимального управления.
Научная новизна. Результаты диссертационной работы можно классифицировать как направление в теории оптимизации, связанное с разработкой нового подхода и новых численных методов решения задач ДО и некоторых специальных задач теории оптимального управления.
В диссертации получены следующие основные результаты: 1 .Доказана теорема о достаточных условиях оптимальности для многошаговых процессов управления с многомерным аргументом, частным случаем которых являются статические многоиндексные задачи ДО (теорема 1.2).
2.Для решения задач оптимизации выделенного класса впервые использована разрешающая функция ЧЧ"ЦУ) , нелинейная по исходным переменным, позволяющая строить для одноиндексных задач ДО двусторонние алгоритмы (теоремы 6.2 и 6.3 для многомерной задачи о ранце с линейными связями и сепарабельным функционалом) .
3.Развит (особенно это касается многоиндексных задач ДО) специальный вариант субградиентного метода, связанный с нахождением за полиномиальное число операций квазиградиентов для решения встречающихся задач двойственного типа. 4.Разработаны новые точные и приближенные алгоритмы решения широкого класса задач ДО, среди которых и такие традиционно--трудные, как задачи коммивояжера и квадратичного назначения. В частности более "резкие", чем у существующих алгоритмов новые нижние границы, требующие полиномиальное число операций, получены для следующих задач:
-обобщенная задача назначения с границей лучшей, чем для одной из релаксаций Росса-Соланда (теорема 2.1);
-трипланарная задача назначения с границей лучшей, чем доставляемой алгоритмом В. Иванова (теорема 3.4); -задача коммивояжера с границей, полученной независимо и более "резкой", чем доставляемая Процедурами Ограничений 1-3 в алгоритме Балаша-Кристофидеса (теоремы 4.1,4.4 и 4.2); -квадратичная задача назначения с границей лучшей, чем доставляемой алгоритмом Гаветта-ПлайтераСтеорема 5.1 и лемма 5.2); -задача о многомерном ранце с линейными связями и сепарабель-ным функционалом с границей более "резкой", чем доставляемой схемой обобщенных множителей Лагранжа(теорема 6.1); -точный алгоритм решения линейной задачи назначения с оценкой 0(n )+0(Rn ) числа операций (теорема 3.3).
Практическая ценность.На основе предложенных методов и алгоритмов , а также с помощью других известных в ДО подходов решен ряд сложных задач, встретившихся в практической деятельности ряда организаций..
Первая группа задач связана с проблемой проектирования, создания и функционирования реальной информационно-вычислительной сети. Разработанный комплекс алгоритмов и программ (последние частью выполнены под научным руководством автора Мотусом О.А.) внедрен в ВИНИТИ ГКНТ и АН СССР с годовым экономическим эффектом 35 тыс. руб. в год. Имеется акт о внедрении.
Вторая группа задач - с созданием системы автоматизированного проектирования двусторонних печатных плат повышенной плотности. Разработанный комплекс алгоритмов и программ (последние частью выполнены под научным руководством автора Герасимовым А.Л.) внедрены в НИИ радиотехники Министерства радиопромышленности. Имеется акт о внедрении.
Третья группа задач - с решением ряда задач оптимального распределения ресурсов, встретившихся в практике отраслевого планирования. Первая из этой группы задач - об оптималььном целочисленном распределении неоднородных средств, вторая - об оптимальном резервировании. Разработанные алгоритмы и программы внедрены в НИИ экономики, планирования и управления Министерства авиационной промышленности. Имеется акт о внедрении.
Кроме того, ряд алгоритмов,разработанных в диссертации, использовался в учебном процессе Московского экономико-статистического института MB и ССО СССР на кафедре Экономической кибернетики.
Апробация. Результаты диссертации докладывались на V Все-
союзном совещании-семинаре по управлении, большими системами (Алма-Ата 1978г.), на IX, XIII, XIV Всесоюзном семинаре "Системные исследования ГАСНТИ" (Ереван 1979г, Тбилиси 1982г., Минск 1983г.), на VIII и XI Всесоюзных совещаниях по проблемам управления (Таллин 1980г., Ташкент 1989г.), на 1,11,111 Всесопзном совещании "Методы и программы решения оптимизационных задач на сетях и графах" (Новосибирск 1980г.,1982г, Ташкент 1984г.), Республиканском семинаре по дискретной оптимизации (Киев 1987г.), Всесоюзной школе-семинаре "Дискретная оптимизация и компьютеризация" (Таштагол 1987г.), 8-й Всесоюзной конференции по теоретической кибернетике (Горький 1988г.).Всесопзном семинаре "Дискретная оптимизация и исследование операций" (Новосибирск 1990г.), Международной конференции по методам оптимизации и их приложениям (Иркутск 1989г.), а также на ряде научных семинаров в Московском экономико-статистическом институте MB и ССО СССР под руководством проф. Кротова В.Ф. (1975-1984).семинарах в ИПУ АН СССР (1980,1988), ВЦ АН СССР (1988,1990), ЯК АН УССР (1987), Московском авиационном институте MB и ССО СССР (1989).
Публикации. По теме диссертации опубликовано 52 работы.
Объем и структура работы.Работа состоит из введения, 6 глав, заключения, списка литературы из 2.97 наименований и четырех приложений, содержащих результаты численного эксперимента по результатам внедрения разработанных в диссертации алгоритмов,и документов, отражающих внедрение результатов работы. Общий объем работы страниц 2$>2> страниц основного текста, страниц приложений, вклпчая 5 рисунков и 20 таблиц.