Исследование и решение минимаксных и минисуммных задач размещения на сетях

• Автор: Филимонов, Дмитрий Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Омск
• Количество страниц: 94 с. : ил.

Глава 1. Полиномиальные алгоритмы решения задач на деревьях с ограничениями на максимальные расстояния

1.1 Постановка задач

1.2 Алгоритмы решения непрерывной минимаксной

задачи

1.3 Решение дискретной минимаксной задачи

1.4 Минисуммная задача размещения

Глава 2. Алгоритмы ветвей и границ решения задач

размещения на произвольных сетях

♦ 2.1 Сложность минимаксных и минисуммных задач

2.2 Эквивалентная задача математического

программирования
2.3 Дискретная минимаксная задача размещения ... '51
2.4 Решение минисуммной задачи размещения
2.5 Вычислительный эксперимент
Глава 3. Эвристические алгоритмы решения задач
размещения на произвольных сетях
3.1 Алгоритмы последовательного одиночного
размещения

3.2 Генетические алгоритмы
3.3 Алгоритмы поиска с запретами
3.4 Вычислительный эксперимент
Заключение
Список использованной литературы

Значительное число работ в области исследования операций посвящено решению проблем планировки и расположения объектов. Задачи размещения имеют обширную сферу практического применения, поскольку область, в которой производится размещение, может иметь различную структуру, и термин ’’объект” может трактоваться достаточно широко. Такие задачи возникают при размещении различных пунктов обслуживания, например, больниц, магазинов, пожарных депо, формировании генеральных планов предприятий [5,17], проектировании печатных плат [1,6], конструировании летательных аппаратов [49] и выполнении других работ.
Следует отметить, что изучение задач размещения объектов началось в 17 веке, когда Ферма сформулировал задачу, известную ныне как задача Вебера [27,82,98]: даны три точки на плоскости, требуется найти четвертую точку, такую, что сумма расстояний от нее до трех фиксированных точек минимальна. Задача была решена геометрически Торичелли в 1640 году. В 1750 году Симпсон обобщил задачу в направлении учета произвольных весов связей между объектами. В 1909 году Вебер использовал подобную модель для определения оптимального размещения фабрики при известных точках расположения ресурсов и потребителей продукта.
Среди задач размещения можно выделить два больших класса: задачи размещения взаимосвязанных объектов и задачи размещения-распределения (задачи размещения предприятий). К первому классу относятся задачи с заранее заданной структурой связей между объеквершинами сети Т. Отметим, что в этой системе
тп(п — 1)/2 + п(п — 1)(п — 2)/2 + ш(ш — 1)п/2
ограничений. Таким образом, систему AZ > d с экспоненциальным числом ограничений можно заменить системой aZ > Ö с полиномиальным потия числом ограничений, при этом не изменяя число переменных. Итак, задача (РМ) сведена к задаче МП с полиномиальным числом переменных и ограничений.
Используя указанную методику, нами построены задачи ЛИ, эквивалентные (1.1),(1.3)-(1.4) и (1.2)-(1.4). Введем дополнительную переменную z, которая равна значению целевой функции (1.1). Тогда минимаксная задача эквивалентна следующей задаче MMLP:
л —> min
VjkPjk - z < 0, j,k 6 J, j < к, Wijqij — z < 0, i 6 I, j E J, Pjk bjki j, к G J, j
Qij — ^ij * i j G t/j
Qsk TPjk Qsj ^0, s £ I•, j^k £ Jj j Pjr +Prk - Pjk > 0, j, к G J, j < k, r 6 J, Г Ф j, k,
Qsj Ф Qtj ^ ^ ) ? 5, £ £ /, e <
Pjfc > 0, j, А £ J, j < k,
Qij >0, ie /, i € J.