Введение к работе
Актуальность темы. Задачи оптимального размещения объектов имеют много практических приложений. Их необходимо решать при проектировании планов предприятий, расстановке технологического оборудования в цехах, размещении элементов на печатных платах, определении мест расположения пунктов обслуживания и выполнении многих других работ.
По признаку наличия фиксированных связей между объектами в задачах размещения можно выделить два класса - размещение взаимосвязанных объектов и размещение-распределение. В задачах первого класса требуется найти позиции для расположения объектов с заранее заданными связями между ними. Наиболее известные представители этого класса - это квадратичная задача о назначениях и задача Вебера. Они рассматривались в работах Ахмедова И.С, Демиденко В.М., Забудского Г.Г., Иорданского М.А., Метельского И.И., Панюкова А.В., Сергеева СИ., Сигала И.Х., Трубина В.А., Burkard R.E., Qela Е., Finke С и других. Во втором классе задач связи между объектами изначально не фиксированы, а устанавливаются в процессе их решения. К ним относятся, в частности, простейшая задача размещения, задача о р-медиане, задача о р-центре, задача размещения с предпочтениями клиентов. Значительный вклад в развитие этого направления внесли Берес-нев В.Л., Гимади Э.Х., Колоколов А.А., Кочетов Ю.А., Кристофидес И. и другие.
Актуальными в настоящее время является исследование задач оптимизации на сетях и различных дискретных структурах. Данному направлению, в частности, посвящены работы Ерзина А.И., Кристофидеса И., Кузьмина О.В., Попкова В.К. В диссертации изучается дискретная задача размещения взаимосвязанных объектов - квадратичная задача о назначениях (КЗН), сформулированная в терминах теории графов. Она А^Р-трудна в общей постановке.
КЗН является базовой математической моделью при решении многих прикладных проблем: проектировании компьютерных материнских плат с учетом соблюдения температурного режима; проектировании планов предприятий и расстановке (компоновке) технологического оборудования в цехах; размещении лечебных подразделений на заданной территории и других. Она представляет собой обобщение многих известных задач оптимизации, в частности, задачи коммивояжера, поэтому ее исследование представляет интерес с математической точки зрения.
Точные методы решения КЗН (например, алгоритмы ветвей и границ) слабо применимы на практике. В задачах с числом объектов более 20
не гарантировано нахождение точного решения за приемлемое время. Для
приближенного решения КЗН большой размерности применяются известные эвристические алгоритмы: муравьиной колонии, имитации отжига, поиска с запретами, генетические и ряд других. В частных случаях предложены точные алгоритмы и приближенные алгоритмы с оценками. Разработаны, например, полиномиальные алгоритмы решения задач нумерации вершин графов различной структуры (КЗН на сети, представляющей собой цепь).
Недостаточно исследована КЗН в терминах теории графов на сетях более общей структуры, чем цепь, - в частности, на древовидных сетях. Интерес представляет как разработка полиномиальных алгоритмов решения задачи для специальных структур связей между объектами, так и эффективных алгоритмов для более общих графов связей, в том числе, с применением параллельных вычислений.
Целью диссертации является разработка и анализ эффективных алгоритмов решения КЗН в теоретико-графовой постановке для различных структур связей между объектами.
С учетом поставленной цели решались следующие задачи:
сформулировать задачу оптимального размещения взаимосвязанного технологического оборудования нефтехимического предприятия в виде модели КЗН;
разработать полиномиальные алгоритмы решения КЗН для специальных структур связей между объектами и сетей, на которых производится размещение;
построить эффективные алгоритмы решения задачи для общих структур связей между объектами;
создать программное обеспечение и провести экспериментальное исследование предложенных алгоритмов, в том числе, с применением известных программных продуктов.
Методы исследования. Обоснованность и достоверность научных положений, результатов и выводов, содержащихся в диссертационной работе, основываются на фундаментальных положениях математического моделирования, дискретной оптимизации, целочисленного и динамического программирования, применении современных компьютерных технологий.
Научная новизна. Разработаны новые полиномиальные алгоритмы решения КЗН с минисуммным и минимаксным критериями на древовидных сетях для специальных структур связей между объектами. Предложены параллельный алгоритм динамического программирования и алгоритм поиска
приближенного решения для общих структур связей в задачах с минисумм-ным критерием.
Основные результаты диссертации заключаются в следующем.
Проведено исследование КЗН с минисуммным критерием в теоретико-графовой постановке, которая является математической моделью размещения взаимосвязанного технологического оборудования. Структура связей представляет собой граф, позиции для размещения - узлы сети. Построены полиномиальные алгоритмы решения задачи на древовидной сети для случаев, когда структура связей представляет собой цепь или цикл с равными весами ребер.
Разработан полиномиальный алгоритм решения КЗН с минимаксным критерием для размещения объектов со структурой связей в виде цепи на древовидной сети в случае ребер одинакового веса.
Предложен параллельный алгоритм динамического программирования решения КЗН с минисуммным критерием для графа связей общей структуры с произвольными весами ребер на древовидной сети с равными
весами.
Разработан алгоритм поиска приближенного решения КЗН с минисуммным критерием для графа связей и сети общего вида с произвольными весами ребер.
Создан программный комплекс с реализацией предложенных параллельного алгоритма динамического программирования и алгоритма поиска приближенного решения. Проведено экспериментальное исследование эффективности параллельного алгоритма в зависимости от характеристик сети и конфигурации ЭВМ. Выполнено сравнение его работы с результатами решения задачи программным пакетом IBM ILOG CPLEX. Проведен вычислительный эксперимент по анализу работы алгоритма поиска приближенного решения.
Практическая ценность. Полученные в диссертации результаты представляют ценность в области развития методов математического моделирования и дискретного программирования. Предложенные алгоритмы применимы для решения прикладных задач, в частности, при разработке систем автоматизированного проектирования. Программный комплекс может быть использован в научных исследованиях в Омском филиале Учреждения Российской академии наук Института математики им. С.Л. Соболева Сибирского отделения РАН, Омском государственном университете им. Ф.М. Досто-
евского, Учреждении Российской академии наук Институте вычислительной математики и математической геофизики Сибирского отделения РАН.
Апробация работы. Результаты диссертации докладывались на IV Всероссийской конференции "Проблемы оптимизации и экономические приложения" (г. Омск, 2009), VII Международной научно-технической конференции "Динамика систем, механизмов и машин" (г. Омск, 2009), Российской конференции "Дискретная оптимизация и исследование операций" (Республика Алтай, 2010), Международной конференции "Operations Research 2010" (г. Мюнхен, Германия, 2010), 8 Международной конференции "Интеллектуализация обработки информации ИОИ-2010" (г. Пафос, Республика Кипр, 2010), XIV Всероссийской конференции "Математическое программирование и приложения" (г. Екатеринбург, 2011), XXXV Региональной научно-практической студенческой конференции "Молодежь третьего тысячелетия" (г. Омск, 2011), Международной конференции "Operations Research 2011" (г. Цюрих, Швейцария, 2011), Международной конференции "Optimization and Applications OPTIMA-2011" (г. Петровац, Черногория, 2011), а также на научных семинарах в Омском филиале Учреждения Российской академии наук Института математики им. С.Л. Соболева Сибирского отделения РАН (2009-2011).
Публикации. Основные результаты работы опубликованы в 11 научных работах [1-11], две из них - в изданиях из списка ВАК.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы (95 наименований). Объем диссертации - 103 страницы.
