Введение к работе
Актуальность темы. Исследование и решение многих задач, возникающих в экономике, планировании, технике и других областях, ввиду их сложности осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного линейного программирования (ЦЛП). Условие целочисленности позволяет учесть такие факторы, как неделимость объектов, дискретность процессов, наличие альтернатив, фиксированные доплаты и ряд других. Значительный интерес к задачам целочисленного программирования обусловлен их А/'Р-трудностью.
Актуальность исследования задач ЦЛП связана также с тем, что модели и методы целочисленного программирования широко используются для анализа и решения различных классов задач дискретной оптимизации, например, планирования производства, оптимального размещения, оптимизации на графах, развозки продукции, о покрытии, задач с логическими ограничениями.
В настоящее время проблематика целочисленного программирования является достаточно широкой и включает исследование структуры и сложности решения задач, разработку и применение методов ветвей и границ, отсечения, декомпозиции, полиэдрального подхода, приближенных и гибридных алгоритмов, изучение устойчивости задач и алгоритмов, многокритериальные постановки и ряд других. Представляет большой интерес исследование и решение задач ЦЛП с интервальными исходными данными. Во многих алгоритмах используется аппарат непрерывной оптимизации.
Значительный вклад в развитие этих направлений внесли работы известных учёных - А. Е. Бахтина, В. Л. Вереснева, В. П. Булатова, Э. X. Ги-мади, В. Т. Дементьева, В. А. Емеличева, И. И. Ерёмина, Г. И. Забиняко,
A. А. Корбута, Н. Н. Кузюрина, В. К. Леонтьева, В. Д. Мазурова, Э. А. Муха-
чёвой, В. К. Попкова, И. В. Сергиенко, И. X. Сигала, Ю. Ю. Финкелыптейна,
М. Ю. Хачая, Ю. Ю. Червака, В. Н. Шевченко, Ж. Бендерса, Ф. Гловера,
Р. Гомори, Р. Джерослоу, А. Дойг, Э. Лэнд, Дж. Немхаузера, А. Схрейвера,
B. Хватала, Д. Эдмондса, Р. Юнга и других.
В области целочисленного программирования широкое применение получил подход, предложенный А. А. Колоколовым, основанный на использовании регулярных разбиений евклидова пространства, в том числеL - разбиения. С использованием этого подхода были построены оценки числа итераций для ряда алгоритмов, введены новые классы отсечений, получены результаты по устойчивости задач и алгоритмов дискретной оптимизации, исследована L - структура задач. Предложен метод перебора L - классов, на основе которого были разработаны алгоритмы решения задачи о покрытии множества, задачи о рюкзаке, задач выполнимости и максимальной выполнимости.
С теоретической точки зрения указанные алгоритмы по некоторым на-
правлениям исследованы недостаточно. В частности, актуальными являются вопросы получения оценок числа итераций, построения семейств трудных задач, устойчивости алгоритмов при малых колебаниях исходных данных, поиск унимодулярных преобразований пространства, позволяющих улучшать Х-структуру задачи и повышать эффективность алгоритмов.
Целью диссертации является разработка, теоретическое и экспериментальное исследование алгоритмов целочисленного линейного программирования с использованием L - разбиения. Для достижения поставленной цели решались следующие задачи:
Построить семейства задач целочисленного линейного программирования для исследования алгоритмов, основанных на использовании релаксационных множеств задач.
Получить оценки числа итераций для алгоритмов отсечения, ветвей и границ, перебора L - классов на базе предложенных семейств. Найти унимодулярные преобразования, упрощающие структуру задач и повышающие эффективность алгоритмов.
Исследовать устойчивость первого алгоритма Гомори при малых изменениях релаксационного множества задачи ЦЛП. Предложить унимодулярные преобразования, улучшающие поведение алгоритма.
Разработать алгоритмы перебора L - классов для решения дискретной задачи планирования производства в стандартной и интервальной постановках.
Создать программное обеспечение, провести экспериментальные исследования рассматриваемых алгоритмов.
Методы исследования. Обоснованность и достоверность научных положений, результатов и выводов, содержащихся в диссертационной работе, основывается на фундаментальных положениях математического моделирования, дискретной оптимизации, целочисленного линейного программирования, применении компьютерных технологий и подтверждаются результатами численного эксперимента.
Научная новизна. Проведено исследование ряда известных алгоритмов ЦЛП на основе построенных специальных семейств задач. Показано, что число итераций этих алгоритмов экспоненциально зависит от длины входа задач, предложены унимодулярные преобразования, повышающие их эффективность. Разработаны и апробированы алгоритмы для дискретной задачи планирования производства с интервальными данными.
Основные результаты диссертации заключаются в следующем.
1. Для анализа двойственых алгоритмов отсечения, алгоритмов ветвей и границ и перебора Х-классов предложены и исследованы семейства задач ЦЛП. Показано, что решение этих задач требует экспоненциального
от длины входа числа итераций указанных алгоритмов, приведены унимодулярные преобразования, упрощающие структуру задач и повышающие эффективность алгоритмов.
Доказано, что первый алгоритм Гомори не является устойчивым при малых изменениях релаксационного множества задачи ЦЛП. Найдены унимодулярные преобразования пространства, улучшающие поведение алгоритма на построенных семействах задач.
Разработаны алгоритмы перебора L-классов для решения дискретной задачи планирования производства в стандартной и интервальной постановках. Приведены унимодулярные преобразования, ускоряющие процесс перебора Х-классов.
Создано программное обеспечение, в котором реализованы рассматриваемые алгоритмы, проведены экспериментальные исследования, в том числе на тестовых задачах из известной электронной библиотеки OR-Library, показавшие перспективность предложенных алгоритмов.
Практическая ценность. Разработанные алгоритмы перебора L - классов для решения задачи планирования производства в стандартной и интервальной постановках применимы в условиях достаточно большой размерности задач. Предложенные унимодулярные преобразования позволяют повысить эффективность работы алгоритмов. Полученные результаты используются при тестировании алгоритмов, в научных исследованиях и учебном процессе в ОмГУ.
Апробация работы. Результаты диссертации докладывались на XXIX Региональной научной студенческой конференции ОмГУ <Молодежь третьего тысячелетия> (Омск, 2005), III Всероссийской конференции <Проблемы оптимизации и экономические приложения> (Омск, 2006), XIII Всероссийской конференции <Математическое программирование и приложения» (Екатеринбург, 2007), IV Всероссийской научной молодежной конференции <Под знаком Сигма> (Омск, 2007), Российской конференции <Дискретная оптимизация и исследование операций» (Владивосток, 2007), VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (Омск, 2007), XIV Байкальской международной школе-семинаре (Иркутск-Северобайкальск, 2008), а также на научных семинарах в Омском филиале Института математики им. С.Л. Соболева СО РАН, Омском государственном университете им. Ф. М. Достоевского (2005-2010) и Институте вычислительной математики и математической геофизики СО РАН.
Публикации. Основные результаты диссертации опубликованы в 10 научных работах [1-10], три из них - в изданиях из списка ВАК.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы (101 наименование). Объем диссертации - 112 страниц.
