Введение к работе
Актуальность темы. Исследование многих задач оптимизации, разработка и анализ методов их решения осуществляется на основе математического моделирования, в том числе с использованием аппарата целочисленного программирования (ЦП). Особый интерес к задачам ЦП обусловлен их большой теоретической значимостью и широким кругом приложений в экономике, планировании, управлении, теории информации и других отраслях. В настоящее время модели и методы целочисленного программирования применяются для анализа и решения различных задач дискретной оптимизации, например, оптимального размещения, о покрытии, оптимизации на графах, о рюкзаке, задач проектирования, поэтому их построение и изучение являются перспективными [1-5,7-10,12,13].
Задача об упаковке множества занимает важное место в области дискретной оптимизации, ее математические модели используются при решении значительного числа практических задач, в частности, задачи формирования оптимального набора проектов, проблем оптимизации транспортных систем, поиска решения в комбинаторном аукционе и других. Некоторые из них описываются системами ограничений блочного типа [1,14]. При этом блоки обычно соответствуют отдельным объектам, подразделениям фирмы, частям одного устройства и т.п. Они могут быть объединены между собой ограничениями, отражающими использование общих ресурсов, обеспечение технологического процесса или периода планирования. Для задач об упаковке множества актуальными являются анализ их структуры и сложности, построение алгоритмов точного и приближенного решения, разработка декомпозиционных методов.
Для исследования задач целочисленного программирования, построения и анализа алгоритмов их решения А.А. Колоколовым предложен метод регулярных разбиений [8], получивший применение и развитие во многих работах [6,11,15]. В соответствии с этим подходом релаксационное множество задачи ЦП, разбивается определенным образом на классы эквивалентности. Наиболее изученным является одно из таких разбиений - L-разбиение, элементы которого называются L-классами. На его основе предложен алгоритм перебора L-классов [8], который может использоваться для решения многих задач целочисленного линейного программирования (ЦЛП), в том числе в сочетании с лексикографической оптимизацией [5].
В методах, основанных на применении релаксационных многогранников задач ЦП, в частности, алгоритмах отсечений, ветвей и границ, перебора L-классов и других требуется исключить множество точек, находящихся
между оптимальными решениями исходной и соответствующей ей непрерыв-
ной задач, которое называется дробным накрытием. Множество L-классов, входящих в дробное накрытие, образует L-накрытие задачи, поэтому изучение L-накрытий имеет большое значение для анализа сложности их решения и построения оценок числа итераций указанных алгоритмов.
Представляется целесообразным использование регулярных разбиений в сочетании с другими подходами для исследования и решения задач об упаковке множества.
Целью диссертации является исследование задач об упаковке множества, в том числе с системами ограничений блочной структуры, разработка и анализ алгоритмов их решения на основе L-разбиения и лексикографической оптимизации.
Для достижения поставленной цели решались следующие задачи:
-
исследовать математические модели ряда проблем, возникающих при проектировании сложных систем, в частности систем связи с использованием задач об упаковке множества;
-
провести анализ структуры и сложности задач об упаковке множества, включая постановки блочного типа на основе L-разбиения, выделить и изучить семейства задач с L-накрытиями экспоненциальной мощности;
-
построить и исследовать алгоритмы, основанные на переборе L-классов и лексикографической оптимизации для решения рассматриваемых задач;
-
pазработать научно-исследовательский вариант комплекса программ для задач об упаковке множества, в том числе с учетом ограничений блочного вида;
-
выполнить экспериментальные исследования предложенных алгоритмов.
Методы исследования. В работе используются фундаментальные положения математического моделирования, аппарат целочисленного программирования, в частности, метод регулярных разбиений и лексикографическая оптимизация, теория разработки программного обеспечения. Достоверность полученных научных результатов, основывается на строгих формулировках и доказательствах, подтверждается проведенными вычислительными экспериментами.
Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем. Проведен анализ задач об упаковке множества с системами ограничений блочной структуры, которые являются математическими моделями ряда проблем, возникающих при проектировании сложных систем, в том числе систем связи, построены семейства и подклассы NP-трудных задач с L-накрытиями экспоненциальной мощности. Разработаны алгоритмы перебора L-классов и лексикографической оптимизации для
решения указанных задач. Выполнено исследование предложенных алгоритмов, найдены нижние оценки числа их итераций.
Практическая значимость. Полученные в диссертации результаты имеют важное значение в области развития методов целочисленного программирования. Они нашли применение в лаборатории дискретной оптимизации Омского филиала ФГБУН Института математики им. С.Л. Соболева СО РАН в научных исследованиях, в частности для изучения структуры и сложности задач ЦП, при анализе, построении и тестировании алгоритмов, решении задач об упаковке множества на базе разработанного научно-исследовательского варианта комплекса программ. Кроме того, указанные результаты используются в учебном процессе на кафедре прикладной и вычислительной математики в Омском государственном университете им. Ф.М. Достоевского при подготовке специалистов по методам оптимизации и исследованию операций.
Апробация работы. Результаты диссертации докладывались и обсуждались на следующих конференциях: XXXIII научно-практической студенческой конференции «Молодежь III тысячелетия», (г. Омск, 2009), IV, V Всероссийских конференциях «Проблемы оптимизации и экономические приложения», (г. Омск, 2009, 2012), VII Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск, 2009), Российской конференции «Дискретная оптимизация и исследование операций», (Республика Алтай, 2010), XIV Всероссийской конференции «Математическое программирование и приложения», (г. Екатеринбург, 2011), XV Байкальской международной школе-семинаре «Методы оптимизации и их приложения», (г. Иркутск, 2011), Международной конференции «Optimization and Applications 0PTIMA-2011», (г. Петровац, Черногория, 2011), Международной конференции «Алгебра и линейная оптимизация», посвященной 100- летию С.Н.Черникова (г. Екатеринбург, 2012), на заседаниях научных семинаров лаборатории прикладных систем ФГБУН Института вычислительной математики и математической геофизики СО РАН (г. Новосибирск, 2013), «Математическое моделирование и дискретная оптимизация» Омского филиала ФГБУН Института математики им. С.Л. Соболева СО РАН и Института математики и информационных технологий ОмГУ им. Ф.М. Достоевского (г. Омск, 2009-2013).
Публикации. Основные результаты диссертации опубликованы в 11 научных работах, три из них - в журналах из списка ВАК.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы (144 наименования). Объем диссертации - 129 страниц.
