Введение к работе
Актуальность темы. Для решения многих задач, возникающих в планировании, управлении, проектировании и других областях, применяются модели и методы целочисленного программирования (ЦП), в которых учитываются такие факторы, как неделимость объектов, дискретность процессов, альтернативность выбора. Аппарат ЦП широко используется при исследовании различных классов задач дискретной оптимизации, в частности задач оптимального размещения, о покрытии, выполнимости логической формулы, задач с ресурсными ограничениями. Значительный интерес к задачам ЦП обусловлен их NP - трудностью.
Проблематика ЦП является достаточно разнообразной и включает, в том числе, исследование структуры и сложности задач, разработку и анализ методов их решения, многокритериальные постановки [1-21].
В настоящее время в целочисленном программировании активно развивается предложенный А.А. Колоколовым метод регулярных разбиений [9, 23], на основе которого исследована L - структура задач ЦП [31], построены алгоритмы и оценки числа итераций [8], введены новые классы отсечений [9], изучены вопросы устойчивости задач и алгоритмов дискретной оптимизации [4].
Многие методы решения задач ЦП основаны на использовании релаксационного множества задачи, которое определяется исходной системой ограничений без условия целочисленности переменных. При этом важную роль играют структура задачи и ее дробное накрытие, состоящее из точек, находящихся между лексикографически оптимальными решениями задачи ЦП и соответствующей непрерывной задачи. Регулярные разбиения позволяют оценивать " объем" дробного накрытия, характеризующего сложность решения задачи, и, таким образом, измерять эффективность алгоритмов. Как правило, мощные накрытия затрудняют процесс решения, поэтому перспективными представляются исследования, связанные с поиском методов улучшения структуры задач в терминах регулярных разбиений. Одним из таких направлений, показавших свою продуктивность и актуальность, является построение и исследование унимодулярных преобразований, с помощью которых исходная задача сводится к эквивалентной ей задаче ЦП. Применение унимо- дулярных преобразований сохраняет множество допустимых целочисленных точек, но может сделать структуру задачи более приемлемой для анализа и решения.
Несмотря на большое число результатов, полученных в области ЦП, с
теоретической точки зрения многие вопросы требуют дальнейшего исследо-
вання. Среди них следует отметить: выделение полиномиально разрешимых
случаев задач; построение семейств задач, трудных для решения некоторыми алгоритмами; получение оценок числа итераций; разработка и анализ новых, в том числе гибридных, алгоритмов.
Целью диссертации является исследование структуры и сложности задач ЦП, разработка и анализ алгоритмов их решения с использованием регулярных разбиений и унимодулярных преобразований.
Для достижения поставленной цели решались следующие задачи:
-
изучить возможности применения в ЦП различных линейных преобразований, в том числе унимодулярных, выделить классы таких преобразований, улучшающих L - структуру задач о рюкзаке;
-
построить семейства " трудных" задач целочисленного линейного программирования (ЦЛП) для алгоритмов лексикографического типа, предложить преобразования, существенно меняющие структуру этих задач и позволяющие ускорять процесс решения;
-
разработать варианты алгоритма перебора L - классов (LCE) с учетом специфики задач о рюкзаке, изучить их поведение с использованием свойств L - структуры задач булева программирования (БП);
-
исследовать z - алгоритм Вотякова А.А. для решения задач ЦЛП на основе регулярных разбиений;
-
провести экспериментальный анализ влияния унимодулярных преобразований пространства, применяемых к задачам ЦП, на эффективность алгоритмов.
Методы исследования. В работе использован математический аппарат дискретной оптимизации и целочисленного программирования, в частности, метод регулярных разбиений и унимодулярные преобразования. Обоснованность и достоверность полученных научных результатов базируются на строгих формулировках и доказательствах, подтверждаются проведенными вычислительными экспериментами.
Научная новизна. В диссертации продолжены исследования в направлении развития и применения метода регулярных разбиений в сочетании с унимодулярными преобразованиями для задач ЦЛП, анализа и разработки алгоритмов их решения, получены новые теоретические результаты. Выделен и изучен класс унимодулярных преобразований перестановочного типа, улучшающих структуру задачи о рюкзаке и некоторых ее обобщений, повышающих эффективность решения алгоритмов лексикографического перебора. Доказаны теоремы об " оптимальном" порядке переменных (с точки зрения мощности L - структуры задачи) для одномерной задачи о рюкзаке в целочисленной и булевой постановках. Для алгоритма перебора L - классов и метода ветвей и границ построены семейства задач ЦЛП с L - накрытиями экспоненциальной мощности, найдены унимодулярные преобразования, улучшающие их структуру. Проведен анализ алгоритма LCE для булевого варианта задачи о рюкзаке, предложена его модификация с учетом специфики задачи, получены новые оценки числа итераций. Исследован z - алгоритм Вотякова А.А. для решения задач ЦЛП, изучено его поведение относительно регулярных разбиений.
Практическая ценность. Полученные в диссертации результаты представляют ценность в области развития методов математической кибернетики, дискретной оптимизации и целочисленного программирования. Они нашли применение в лаборатории дискретной оптимизации Омского филиала Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева СО РАН в научных исследованиях, в частности для изучения структуры и сложности задач ЦП, при анализе, разработке и тестировании алгоритмов. Кроме того, указанные результаты используются в учебном процессе на кафедре прикладной и вычислительной математики в Омском государственном университете им. Ф.М. Достоевского при подготовке специалистов по методам оптимизации и исследованию операций.
Апробация работы. Результаты диссертации докладывались на IV и V Всероссийских конференциях "Проблемы оптимизации и экономические приложения" (Омск, 2009 и 2012), VII Международной научно-технической конференции "Динамика систем, механизмов и машин" (Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций' (Алтай, 2010), 8-й и 9-й Международных конференциях "Интеллектуализация обработки информации" (Кипр, 2010 и Черногория, 2012), XIV Всероссийской конференции " Математическое программирование и приложения " (Екатеринбург, 2011), XV Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2011), Международной конференции " Алгебра и линейная оптимизация", посвященной 100-летию С.Н. Черникова (Екатеринбург, 2012), на заседании научного семинара отдела математического программирования Института математики и механики им. Н.Н. Красовского УрО РАН (Екатеринбург, 2012), а также на заседаниях научного семинара"Математическое моделирование и дискретная оптимизация" Омского филиала Института математики им. С.Л. Соболева СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (Омск, 2009 - 2012).
Публикации. Основные результаты диссертации опубликованы в 11 научных работах [22-32], две из них — в журналах из списка ВАК [22,23].
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы (96 наименований). Объем диссертации — 101 страница.
