Задача коммивояжера
Обычно эта задача формулируется следующим образом. Коммивояжер должен побывать в ряде городов. Известны расстояния между каждой парой городов (время или стоимость проезда). Необходимо выбрать кратчайший маршрут, проходящий один раз через каждый город. Если расстояние между городами не зависит от направления движения, то задача называется симметричной. Если стоимость проезда меняется при изменении направления движения, задача называется несимметричной.
Для задачи коммивояжера при необходимости посещения только двух городов выбора нет. При посещении трех городов и заданном начальном пункте возможны 2 маршрута. Если городов четыре, то имеется 6 маршрутов, а при одиннадцати городах — более 3,5 млн допустимых маршрутов. В общем случае при n городах имеется (n -1)! маршрутов.
К подобному типу задач сводится множество реальных ситуаций. Например, выбор очередности обработки разнородных изделий, маршрута автотранспорта, задачи выбора маршрута в сетях систем связи.
Пример. Пусть имеется 5 пунктов, соединенных между собой дорогами так, что из любого пункта можно проехать в любой другой пункт. Известно время перевозки из пункта i в пункт j (табл. 7.1).
Таблица 7.1 Время переезда, ед.
№ маршрута из пункта i № маршрута в пункт j
1 2 3 4 5
1 0 10 25 25 10
2 1 0 10 15 2
3 8 9 0 20 10
4 14 10 24 0 15
5 10 8 25 27 0
Требуется найти маршрут с наименьшей продолжительностью, начинающийся в данном пункте, проходящий через все пункты и заканчивающийся в пункте выезда.
Решение. Введем обозначения: i и j — номера пунктов выезда и въезда; t. — время переезда из пункта i в пункт j. В общем случае t. может быть не равно времени переезда в обратном направлении — t. Ф j (например, когда один пункт на вершине горы, а другой — у ее подножия). В ведем булевы переменные:
[1, если из пункта i торговец переедет в пункт j; j [0, если не поедет.
Составим модель (рис. 7.1). Из пункта 1 можно выехать в любой из пунктов: 2, или 5, или 3, или 4, или остаться в пункте 1. Но при этом можно выехать только в одном-единственном направлении. Это условие можно записать так:
Sn + ^ + ^3 + ^4 + ^5 = 1,
Рис. 7.1
или
= 1
j=i
или для произвольного (любого) i-го пункта
YSj = 1 (i = 1...5).
j=i
Эти зависимости обеспечивают выполнение условия, согласно которому из каждого пункта выезд производится только один раз и только в одном направлении.
Условие въезда в пункт 1 аналогично условию выезда из пункта 1. Требование минимальной продолжительности маршрута запишется в виде целевой функции:
min L = tnSn + t12^12 + + tu5u + ^^ + + t22S22 + ... + t55S55,
где tj берутся из исходной таблицы, а <5j — искомые переменные.
(7.7)
(7.8)
(7.9) (7.10)
Математическую постановку задачи можно сформулировать в виде:
5 5
min L=YYjj;
i=1 j=1
5
YSj = 1 (i = 1... 5);
j=1 5
= 1 (j = 1... 5);
i=1
Sj = [0; 1] , (i, j = 1...5).
В результате решения системы получим следующие значения (рис. 7.2): Й150 = Й520 = Й230 = Й340 = V = 1, остальные й ° = 0;
min L = 10 + 8 + 10 +20 + 14 = 62.
Рис. 7.2
(7.11)
(7.12)
(7.13)
(7.14)
Переходя от частной постановки к общей, задачу коммивояжера можно сформулировать так:
n n
min L = YYtjSij;
i=1 j=1
5
YSj = 1 (i = 1... n);
j=1 5
YSj = 1 (j = 1... n);
i=1
Sj = [0; 1] (i, j = 1... n).
7.12. Распределение капитальных вложений
Пусть известны возможные значения эффективности (например, прирост прибыли, выпуск продукции и др.) на каждом из четырех предприятий отрасли в результате расширения действующих мощностей (табл. 7.2).
Требуется составить план распределения ограниченных капиталовложений по этим предприятиям (К = 200 ден. ед.), максимизирующий общий прирост выпуска при заданной номенклатуре и структуре отраслевого плана производства продукции.
Таблица 7.2
Возможные значения эффективности предприятий в результате расширения
действующих мощностей
Капиталовложения (x), ед. Прирост выпуска продукции i-го предприятия g,(x), ед./год
1 2 3 4
0 0 0 0 0
50 25 30 36 28
100 60 70 64 56
150 100 90 95 110
200 140 122 130 142
Решение. Данная задача может быть решена методом динамического программирования. Обозначим: gi(x) — прирост выпуска продукции на i-м предприятии при x единиц капиталовложений на реконструкцию или расширение активной части его основных фондов; F(K) — максимально возможный прирост выпуска продукции при распределении суммы К между четырьмя предприятиями.
Тогда, согласно основному функциональному уравнению Беллмана:
Ft(K) = max[ g4(x) + F3(K - x)];(7.15)
0< x
] = [36 + 0] = 36,
0
Похожие рефераты:
