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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

101
В ходе первой итерации был получен маршрут
1,0
,lk
μ
(1=
r
, 5=
k
, 3
=
l
,
см. (6.9)):
3,4,2,5
1,0
3,5
=
μ
, 23
1,0
3,5
=
π
.
Итерация
2=
r
начинается с получения остаточной матрицы
2
c после
пересчёта элементов матрицы
1
с
. Согласно (6.7) и табл. 40 имеем
52328
1,0
3,5
1
2,5
2
2,5
=−=−=
π
cс
, 02323
2
4,2
=−=c , 72330
2
3,4
=−=c .
В табл. 42 пересчитанные элементы выделены жирным шрифтом.
Элементы
2
, ji
c остаточной матрицы
2
c
записаны в клетках и сверху над
чертой в клетках табл. 42. Дальнейшие вычисления для 2=
r
записаны
справа от табл. 42.
На второй итерации (2=
r
) после двух шагов (рис. 6,
00
52 −
) найден
второй маршрут от
5
A
до
3
A
с пропускной способностью 17 ед.:
,3,6,5
2,0
3,5
=
μ
17
2,0
3,5
=
π
. (6.9)
На основании (6.9) и
2
с вычисляется новая остаточная матрица
3
с .
Изменившиеся согласно (6.7) элементы (
6,5
с ,
3,6
c ) записаны внизу клеток
курсивом (табл. 42).
Начальная оценка при остаточной матрице
3
с
не может быть больше
пропускной способности предыдущего маршрута:
1,0
,
,1
,
−
≤
r
lk
r
lk
ππ
, (6.10)
поэтому в строке 5==
k
i и в столбце 3
=
=
l
j
остаточной матрицы
3
c
выбираются ближайшие к пропускной способности предыдущего
оптимального маршрута
2,0
3,5
π
элементы
j
c
,5
,
3,i
c (но не большие её), и
больший из них назначается в качестве начальной оценки (1=
t
):
}
.1616;13max
3,1
3,5
==
π
Полученный при этом оптимальный маршрут
3,1,5
3,0
3,5
=
μ
и его

Страницы