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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

102
пропускная способность
3,0
3,5
π
позволяют получить очередную остаточную
матрицу
4
с , записанную в табл. 43.
Примечание. Начальная оценка
4,1
3,5
π
может быть получена и
прежним способом (6.2), при этом, учитывая (6.10), оценку следует
улучшить:
min
,1
,
=
r
lk
π
{
1,0
,
,
;max;max
−
r
lk
r
il
i
r
jk
j
cc
π
}. (6.11)
Справа от табл. 43 записаны начальная оценка
4,1
3,5
π
, полученная двумя
способами, и построенный на её основе маршрут, оказавшийся
оптимальным,
4,0
3,5
μ
.
Полученные согласно (6.7) элементы остаточной матрицы
5
3,5
c
записаны в табл. 43, при этом элементы
4
ij
c , изменившие свои значения,
записаны жирным шрифтом (под чертой).
Для
5
c (5=
r
) начальная оценка (6.11) и оптимальный маршрут
записаны справа от табл. 43 (рис. 7).
Далее приведена динамика процесса решения.
Таблица 42
c
2
c
3
1 2
3
4 5 6
1 1 16 5 22 9
2 12 22
0
27 3
3 23 18 14 24 29
4 4 8
7
7 25
5
20
5
2 13
17
0
6 6 15
26
9
11 19
r = 2
t = 1 :
{
}
⇒== ,2026;20min
2,1
3,5
π
=> 5 → 1 ► => I
t,r
= I
1,2
= {5;1},
20
t = 2 :
{
}
⇒== 1716;17max
2,2
3,5
π
20 1►
=> 5 3►
3,6,5
2,0
3,5
=⇒
μ
,
.17
2,0
3,5
=
π
17 6 26
r = 3
t = 2 :
{
}
⇒<==
02
3,5
3,1
3,5
1616;13max
ππ
=
> 5 → 1 → 3 ►
.16 ,3,1,5
3,0
3,5
3,0
3,5
==⇒
πμ
20 16

Страницы