ВУЗ:
Составители:
Рубрика:
85
5.5. Решение тестового примера обобщенной задачи коммивояжера
методом последовательного наращивания цикла
Для данного примера (табл. 34) дополнительной исходной
информацией является вектор веса доставляемых грузов, компоненты
которого записаны ниже табл. 34. Для решения обобщенной
задачи коммивояжера, минимизирующей энергозатраты методом
последовательного наращивания цикла, вычислена совмещенная матрица
кратчайший маршрут – энергозатраты – удельные энергозатраты
(табл. 35, формулы (4.1), (4.17)).
В первой строке (начало цикла в пункте
1
A ) минимальным удельным
энергозатратам 5
2,1
=
ε
соответствует начало цикла 2;1. Ближайшим по
удельным энергозатратам является маршрут
4;1, однако он не включает в
себя маршрут
2;1 (условия доминирования (4.33) не выполнены),
поэтому осуществляется переход к строке 2
=
i , в которой находится
очередной (недоминируемый) участок цикла
6;2. Продолжая процесс
далее,
получим решение
1,4,3,5,4,6,2,11,4,33;55;44;66;22;1
1
=
∪∪∪∪∪=
μ
. (5.8)
Такой маршрут (5.5) был получен ранее, как ближайший к
кратчайшему (табл. 32). Энергозатраты для полученного решения,
согласно (4.1), равны:
26342124422315246151,4,3,5,4,6,2,1
=
⋅
+
⋅
+
⋅
+
⋅
+⋅+⋅=Э , 42)(
1
=
μ
L .
Если доставку грузов реализовать по
принципу убывания веса, то
получим такое же решение (табл. 35):
j
: 6, 2, 3, 5, 4, 1,
1
μ
= ,1,4,3,5,4,6,2,11,4,33,5,4,66,2,1
=
∪∪
(
)
263
1
=
μ
Э .
Для сравнения оценим энергозатраты решения, соответствующего
циклу минимальной длины:
513411356325143123521,6,2,3,5,4,1
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅+⋅
=
Э ,
41
min
=L
.
Энергозатраты цикла минимальной длины почти вдвое больше, чем у
полученного решения.
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
