Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 86 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

88
Продолжение табл. 36
10 1 1,
4,2,3,1 10+120=130 1 1,4,2,6,5,3,1 10+228=238
11 1 1,5,2,3,1 66+490=556 2 1,2,4,6,5,3,1 22+448=470
12 1 1,6,2,3,1 54+230=284 3 1,2,6,4,5,3,1 30 – 8=22
13 2 1,2,4,3,1 22+95=117 4 1,2,6,5,4,3,1 72+205=277
14 2 1,2,5,3,1 84+40=124 5 1,2,6,5,3,4,1 78 – 5=73
15 2 1,2,6,3,1 24+40=64
16 3 1,2,3,4,1 72 – 5=67
17 3 1,2,3,5,1 138+21=159
18 3 1,2,3,6,1 306+12=318
5t
=
, ∅=
5
G
2681,3,5,4,6,2,1
5
=Э
5.7. Решение тестового примера обобщенной задачи коммивояжера
модифицированным методом расширения цикла
Модифицированный метод расширения цикла подробно описан в
подразделе 4.3, поэтому в решении тестового примера интерес
представляют прежде всего конечные результаты расчетов как основные
характеристики сравниваемых методов. Процесс решения
модифицированным методом расширения цикла представлен в табл. 37.
На первом шаге процесса в начальный цикл вошло два элемента, при
этом включаемый элемент
2
=
γ
соединен с границами интервалов
посредством кратчайших маршрутов
2;1 и 1,6,2 , взятых из табл. 31 (или
табл. 35). Маршруту
1,6,2,1 соответствует наименьшее значение
удельных энергозатрат
1
ε
(1;2) = 14,5, вычисленное по формулам (4.17),
(4.1). Ближайшее к нему значение
1
ε
(1;4) = 19 принадлежит варианту
1,4,1 (табл. 37, строка 3), для которого условия доминирования (4.33) не
выполняются. Недоминируемый вариант
1,6,2,1 берется в качестве
исходного для второго шага процесса (табл. 37, 2
=
t
). На втором шаге
согласно второму необходимому условию оптимальности улучшен
маршрут, записанный в строке 11, путем удаления элемента 6
=
j
,
отмеченного справа точкой.
Участок
1,,5 6 не является кратчайшим. Его замена на 1;5, который
также, не являясь кратчайшим, все-таки уменьшит длину на 3 ед. (табл. 31,
30). Если вместо
1;5 записать кратчайший маршрут 1,4,5 (табл. 31), то
длина участка уменьшится на 6 ед., что уменьшит и энергозатраты.
Из графы 7 видно, что минимальные удельные энергозатраты
соответствуют маршруту
1,4,6,2,1, и он должен быть выбран как
начальный для очередного (3
=
t
) шага процесса. Однако число шагов
может быть уменьшено, если использовать
принцип доминирования (4.33).

Страницы