Введение к работе
Актуальность темы. Целочисленное программирование (ЦП) представляет собой одно из активно развивающихся направлений дискретной оптимизации. К моделям ЦП сводятся многие прикладные задачи, возникающие в экономике, управлении, проектировании и других областях. Значительная часть методов решения задач ЦП основана на сведении исходной задачи ЦП к последовательности задач непрерывной оптимизации. К таким- методам относятся методы отсечения, ветвей и границ (типа метода Лэнд и Дойг), декомпозиции (с отсечениями Бендерса), алгоритмы леребора L-классов и некоторые другие [3,4,7]. Характерными особенностями этих методов являются исполь-' зование релаксационных мноясеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации.
Для исследования задач ЦП, построения и анализа алгоритмов рассматриваемого типа А.А.Колоколовым был предложен метод регулярных разбиений, получивший развитие в [1-4,6] и других работах.
В соответствии с этим подходом исходное евклидово пространство, а, следовательно, и допустимая область непрерывной задачи, связанной с задачей ЦП, разбивается определенным образом на классы эквивалентности. С помощью регулярных разбиений введены и исследованы новые классы отсечений, построены оценки числа итераций (отсечений), изучена структура некоторых задач ЦП, разработаны алгоритмы решения задач ЦП, проведены экспериментальные исследования. Многие из указанных результатов получены с помощью .^-разбиения. В связи с этим представляется целесообразным дальнейшее развитие и применение рассматриваемого подхода к различным классам задач ЦП.
Цель работы. Исследование ряда классов задач ЦП с использованием регулярных разбиений, построение и анализ алгоритмов их ре-
шения, основанных на методе перебора L-классов и отсечениях, исследование свойств кубических разбиений, изучение возможностей их применения.
Научная новизна. В работе получил свое дальнейшее развитие и применение метод регулярных разбиений. На его основе проведен анализ задач о покрытии и упаковке, предложены и исследованы алгоритмы решения ряда задач ЦП.
Основные результаты диссертации заключаются в следующем:
1. Проведен анализ задач о покрытии и упаковке множества:
получены нижние оценки и точное значение мощности Х-накрытий для семейства задач о покрытии, предложенных Э.Балашем;
построены и исследованы задачи о покрытии и упаковке блочно-диагонального вида с L-накрытиями, мощность которых растет экспоненциально с увеличением числа переменных задачи;
получены оценки числа итераций при решении этих задач некоторыми алгоритмами отсечения и методом Лэнд и Дойг.
-
Разработаны и исследованы алгоритмы перебора L-классов для точного и приближенного решения задач о покрытии множества. Создано программное обеспечение, проведены экспериментальные исследования.
-
Предложено и изучено с использованием L-разбпения многопараметрическое семейство контрпримеров для некоторых вариантов прямых алгоритмов отсечения, на основе которых получены оценки числа их итераций; разработаны модификации указанных алгоритмов, учитывающие возможность неточности псходных данных, проведены экспериментальные исследования прямых алгоритмов.
-
Изучены вопросы использования систем правильных линейных неравенств для исключения элементов кубических разбиений релаксационных множеств задач ЦП. Дана классификация кубических раз-
биений на основе индекса разбиения, исследована регулярность ряда известных отсечений (1-го алгоритма Гоморн, вполне регулярных, 2-алгоритма и др.) относительно кубических разбиений.
Методы исследования. При выполнении работы использовались теория и методы линейного программирования, дискретной оптимизации, методология применения современной вычислительной техники в экспериментальных исследованиях.
Практическая значимость. Полученные в диссертации результаты служат основой для построения новых алгоритмов решения задач ЦП, могут быть использованы в научных исследованиях и учебном процессе. Разработанный пакет программ применим для решения прикладных задач.
Апробация работы. Результаты работы докладывались на III Всесоюзной школе "Дискретная оптимизация и компьютеры" (Ташта-гол, 1987), 10 Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Усть-Нарва, 1988), 6 Всесоюзной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989), IV Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989), III Всесоюзном семинаре "Дискретная математика и ее приложения" (Москва, 1990), 7 Всесоюзной конференции "Математическое программирование и приложения" (Свердловск, 1991), XI международной Байкальской школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 1998), а также на семинарах в Институте математики пм. С.Л.Соболева СО РАН, в Институте информационных технологий и прикладной математики СО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [10-19].
Структура и объем работы. Диссертация состоит из введения, трех глав, списка литературы (95 наименований). В каждой главе использована своя нумерация параграфов, утверждений, лемм, теорем, примеров и формул. Общий объем диссертации - 124 страницы.
