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

• Автор: Лагздин, Артем Юрьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Омск
• Количество страниц: 103 с. : ил.

Оглавление
Введение
1 Задачи оптимального размещения взаимосвязанных объектов на сетях и методы их решения
1.1 Математические модели
1.2 Моделирование прикладных проблем и связь с известными
задачами оптимизации
1.3 Алгоритмы решения
2 Полиномиальные алгоритмы на древовидных сетях для специальных структур связей
2.1 Минисуммный критерий
2.2 Минимаксный критерий
3 Алгоритмы и их экспериментальное исследование для произвольных структур связей
3.1 Параллельный алгоритм динамического программирования на невзвешенной древовидной сети
3.2 Экспериментальное исследование параллельного алгоритма
3.3 Алгоритм поиска приближенного решения для произвольных сетей
Заключение

Литература
Приложение
Приложение

Введение
Задачи оптимального размещения объектов имеют много практических приложений. Их необходимо решать при проектировании генеральных планов предприятий, расстановке технологического оборудования в цехах, размещении элементов на печатных платах, определении мест расположения пунктов обслуживания и выполнении других работ.
Первые попытки анализа задач оптимального размещения относятся к XVII веку, когда Ферма сформулировал следующую задачу: найти точку на плоскости, сумма евклидовых расстояний от которой до трех фиксированных минимальна. В начале XX века ее обобщил Вебер, рассматривая произвольное число точек, которым приписаны веса. Более детальные исследования задач размещения связаны с появлением и развитием исследования операций.
По признаку наличия фиксированных связей между объектами задачи оптимального размещения можно разбить на два класса - размещение взаимосвязанных объектов и размещение-распределение [30]. В задачах первого класса требуется найти позиции для размещения объектов с заранее заданной структурой связей между ними. Наиболее известные представители этого класса - это квадратичная задача о назначениях и задача Вебера [4,12,14-16,25-27,42-44,47,48,50,51,54,57-59,61,63-77,79, 81,83,84,87-89,91,93,94]. Во втором классе задач связи между объектами изначально не фиксированы, а устанавливаются в процессе их решения. К ним относятся, в частности, простейшая задача размещения, задача

сопоставим каждому узлу кг £ У0(тг) поддерево гД(ж) = (Ц(тг),и7г)), обозначим ?7(ж) = |1К'('7г){&г}|- Функцию Г можно представить как сумму весов ребер сети Т с неотрицательными целыми коэффициентами
*'(*)= XI аФ)гШМз)), (2-1)
{7г(г),7г и)}еи
где г(7г(г),7г(у)) - вес ребра {7г(г),7гф')} £ С/, а(ж) £ Z+. Поясним данное представление. Для любого к — 1
р(п(Н),тт(к +1)) = г(тг(к),п(1)), (2.2)
{тг(*:))7г(г)}еСД.Л+1
где £Дд+1 С и - множество ребер кратчайшего пути между узлами ж (к) и 7г{к+ 1). Заменив в функции (1.5) выражение р(ж(к),ж(к + 1)) согласно (2.2) для всех к = 1
Заметим, что по построению, в размещении ж*, полученном алгоритмом Ате, справедливо а.ц{ж*) — 1 для всех ребер (тг*(г), 7г*(у)} £ и0(ж*) И ОьД7Г*) = 2 ДЛЯ всех ребер {тг*(з), 7Г*(£)} € {/;(7Г*), I — 1
Отметим некоторые свойства коэффициентов ац (ж) в зависимости от размещения тт. Произвольное ребро и = {тг(г), 7г(у)} £ II разбивает множество узлов V сети Т на два подмножества Ац(ж) = = {п(к) £ Уж(к) соединен с ж(г) цепью, не содержащей ребра
н} и (тг(г)} и А(ж) = {7г(£;) £ Уж(к) соединен с ж(у) цепью, не
содержащей ребра и} и {7г(Д} Имеет место
Лемма 2.1 Значение коэффициента (ж) для произвольного размещения ж цепи Ск на сети Т равно числу пар узлов {ж (к), ж (к + 1)} сети Т таких, что ж (к) и ж (к + 1) не принадлежат одновременно одному множеству Иу (ж) или А*-(ж), к = 1
Доказательство. Рассмотрим произвольную пару узлов {ж(к), 7г(/И-1)} сети Т. В случае, если ж(к),ж(к + 1) £ или