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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

97
Для оценки
2
3,5
π
согласно (6.4) из табл. 40 имеем
i
max
2
3,5
=
π
{ max {
5
17,13,2,
=i
20
}}; max {
2
3,,22,12
=i
23
}23}23;20max{ =
=
,
1
I
i∈ . (6.5)
Игнорируя в матрице
c элементы 23
2
3,5
=<
π
ij
c , от пункта
5
A
строится маршрут по новой оценке:
=
0
3,5
μ
3,4,2,5,
5 2 4 3 ►
.23
0
3,5
=
π
(6.6)
3,6,4,2,5
0
3,5
=
′
μ
,
Поскольку концевой элемент полученного маршрута (
3
2
=j ) совпал с
заданным )3(
=
l
, то решение получено и записано в табл. 41, где в
совмещенной матрице помещены и другие оптимальные решения
nlk ,1,( = ).
В оптимальности решения можно убедиться, проверив
невозможность построения маршрута от
5
A
до
3
A
при ближайшей
(завышенной по сравнению с
2
3,5
π
) оценке 24
,
=
lk
π
(элементы 24≥
ij
с в
табл. 40 выделены шрифтом).
Рассмотренный метод определения улучшенной оценки позволил
вместо пяти итераций обойтись одной.
Таблица 40.
c = ||
ij
с ||, 1
=
ϕ
j
i
1 2 3 4 5 6
1 1 16 5 22 9
2 12 22 23
27
3
3 23 18 14
24 29
4 4 8
30
7
25
5 20
28
2 13 17
6 6 15
26
11 19
28
23
25
26
30
6

Страницы