Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Построение и анализ алгоритмов решения квадратичной задачи о назначениях на сетях Лагздин, Артем Юрьевич

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Лагздин, Артем Юрьевич. Построение и анализ алгоритмов решения квадратичной задачи о назначениях на сетях : диссертация ... кандидата физико-математических наук : 05.13.18 / Лагздин Артем Юрьевич; [Место защиты: Ом. гос. ун-т им. Ф.М. Достоевского].- Омск, 2012.- 103 с.: ил. РГБ ОД, 61 12-1/602

Введение к работе

Актуальность темы. Задачи оптимального размещения объектов имеют много практических приложений. Их необходимо решать при проектировании планов предприятий, расстановке технологического оборудования в цехах, размещении элементов на печатных платах, определении мест расположения пунктов обслуживания и выполнении многих других работ.

По признаку наличия фиксированных связей между объектами в задачах размещения можно выделить два класса - размещение взаимосвязанных объектов и размещение-распределение. В задачах первого класса требуется найти позиции для расположения объектов с заранее заданными связями между ними. Наиболее известные представители этого класса - это квадратичная задача о назначениях и задача Вебера. Они рассматривались в работах Ахмедова И.С, Демиденко В.М., Забудского Г.Г., Иорданского М.А., Метельского И.И., Панюкова А.В., Сергеева СИ., Сигала И.Х., Трубина В.А., Burkard R.E., Qela Е., Finke С и других. Во втором классе задач связи между объектами изначально не фиксированы, а устанавливаются в процессе их решения. К ним относятся, в частности, простейшая задача размещения, задача о р-медиане, задача о р-центре, задача размещения с предпочтениями клиентов. Значительный вклад в развитие этого направления внесли Берес-нев В.Л., Гимади Э.Х., Колоколов А.А., Кочетов Ю.А., Кристофидес И. и другие.

Актуальными в настоящее время является исследование задач оптимизации на сетях и различных дискретных структурах. Данному направлению, в частности, посвящены работы Ерзина А.И., Кристофидеса И., Кузьмина О.В., Попкова В.К. В диссертации изучается дискретная задача размещения взаимосвязанных объектов - квадратичная задача о назначениях (КЗН), сформулированная в терминах теории графов. Она А^Р-трудна в общей постановке.

КЗН является базовой математической моделью при решении многих прикладных проблем: проектировании компьютерных материнских плат с учетом соблюдения температурного режима; проектировании планов предприятий и расстановке (компоновке) технологического оборудования в цехах; размещении лечебных подразделений на заданной территории и других. Она представляет собой обобщение многих известных задач оптимизации, в частности, задачи коммивояжера, поэтому ее исследование представляет интерес с математической точки зрения.

Точные методы решения КЗН (например, алгоритмы ветвей и границ) слабо применимы на практике. В задачах с числом объектов более 20

не гарантировано нахождение точного решения за приемлемое время. Для

приближенного решения КЗН большой размерности применяются известные эвристические алгоритмы: муравьиной колонии, имитации отжига, поиска с запретами, генетические и ряд других. В частных случаях предложены точные алгоритмы и приближенные алгоритмы с оценками. Разработаны, например, полиномиальные алгоритмы решения задач нумерации вершин графов различной структуры (КЗН на сети, представляющей собой цепь).

Недостаточно исследована КЗН в терминах теории графов на сетях более общей структуры, чем цепь, - в частности, на древовидных сетях. Интерес представляет как разработка полиномиальных алгоритмов решения задачи для специальных структур связей между объектами, так и эффективных алгоритмов для более общих графов связей, в том числе, с применением параллельных вычислений.

Целью диссертации является разработка и анализ эффективных алгоритмов решения КЗН в теоретико-графовой постановке для различных структур связей между объектами.

С учетом поставленной цели решались следующие задачи:

сформулировать задачу оптимального размещения взаимосвязанного технологического оборудования нефтехимического предприятия в виде модели КЗН;

разработать полиномиальные алгоритмы решения КЗН для специальных структур связей между объектами и сетей, на которых производится размещение;

построить эффективные алгоритмы решения задачи для общих структур связей между объектами;

создать программное обеспечение и провести экспериментальное исследование предложенных алгоритмов, в том числе, с применением известных программных продуктов.

Методы исследования. Обоснованность и достоверность научных положений, результатов и выводов, содержащихся в диссертационной работе, основываются на фундаментальных положениях математического моделирования, дискретной оптимизации, целочисленного и динамического программирования, применении современных компьютерных технологий.

Научная новизна. Разработаны новые полиномиальные алгоритмы решения КЗН с минисуммным и минимаксным критериями на древовидных сетях для специальных структур связей между объектами. Предложены параллельный алгоритм динамического программирования и алгоритм поиска

приближенного решения для общих структур связей в задачах с минисумм-ным критерием.

Основные результаты диссертации заключаются в следующем.

  1. Проведено исследование КЗН с минисуммным критерием в теоретико-графовой постановке, которая является математической моделью размещения взаимосвязанного технологического оборудования. Структура связей представляет собой граф, позиции для размещения - узлы сети. Построены полиномиальные алгоритмы решения задачи на древовидной сети для случаев, когда структура связей представляет собой цепь или цикл с равными весами ребер.

  2. Разработан полиномиальный алгоритм решения КЗН с минимаксным критерием для размещения объектов со структурой связей в виде цепи на древовидной сети в случае ребер одинакового веса.

  3. Предложен параллельный алгоритм динамического программирования решения КЗН с минисуммным критерием для графа связей общей структуры с произвольными весами ребер на древовидной сети с равными

весами.

  1. Разработан алгоритм поиска приближенного решения КЗН с минисуммным критерием для графа связей и сети общего вида с произвольными весами ребер.

  2. Создан программный комплекс с реализацией предложенных параллельного алгоритма динамического программирования и алгоритма поиска приближенного решения. Проведено экспериментальное исследование эффективности параллельного алгоритма в зависимости от характеристик сети и конфигурации ЭВМ. Выполнено сравнение его работы с результатами решения задачи программным пакетом 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 страницы.

Похожие диссертации на Построение и анализ алгоритмов решения квадратичной задачи о назначениях на сетях