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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

37
Это условие будет выполнено, если элементы с
ij
являются
минимальными в строках или столбцах матрицы с или, в противном
случае,
будут заменены кратчайшими маршрутами
0
ij
μ
, например:
=
1,3,6,5,4,2,1L с
12
+с
24
+с
45
+с
56
+с
63
+с
31
=6+1+12+5+16+22 = 62. (3.5)
Три выделенных элемента не являются минимальными ни в столбцах,
ни в строках матрицы
с. Найденные для них кратчайшие маршруты и их
длины соответственно равны:
115,2,4 =L ,
63
163;6 cL
=
=
, 191,2,4,6,3
=
L . (3.6)
Заменяя соответствующие дуги в (3.5) на кратчайшие маршруты (3.6),
получим улучшенное решение, в котором включенные элементы выделены
жирным шрифтом:
,4,2,1L 2,3,6,5, 6,4,2 581,
=
. В новом решении
некоторые элементы содержатся более одного раза, а значит, могут быть
удалены. Если повторяющийся элемент совместно с двумя смежными с
ним не образует кратчайший маршрут, то он удаляется (
второе
необходимое условие оптимальности
). Согласно этому условию элемент
4=
j
удаляется, так как маршрут 2,4,2 не является кратчайшим (табл. 14;
2=
k
).
Совместно с 4=
j
удаляется и одна из двух оказавшихся рядом двоек.
Окончательно получим
556,4,2,11,2,5,6,3,
=
L .
Рассмотрим возможность модификации метода расширения цикла для
дальнейшего снижения его средней погрешности и уменьшения объема
вычислений, а главное – для расширения его общности.
Таблица 13. || c
ij
||
j
i
1 2 3 4 5 6
1 6 13 27 18 25
2 10 20 1 9 23
3 22 28 15 8 3
4 19 2 30 12 17
5 14 11 26 29 5
6 24 7 16 4 21

Страницы