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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

130
Приложение 1
Определение пропускной способности сети
методом Форда-Фалкерсона и методом улучшения оценок
В работе [14, с. 549] приведен пример графа сети, который несмотря
на малый размер (п = 4) при определении пропускной способности сети из
пункта А
1
в пункт А
4
методом Форда-Фалкерсона может, в силу
специфики метода, потребовать при решении 2 000 000 (2
· 10
6
) итераций.
Данный пример представлен в графическом и матричном виде на рис. 1.
j = 1 2 3 4
10
6
10
6
1
10
6
10
6
Рис. 1. Представление графа сети
В [14] подробно рассматривается данный пример. Столь низкая
вычислительная эффективность обусловлена той особенностью метода,
что в ходе решения предусматривается возможность манипуляций с
отрицательными плотностями потоков и отрицательными пропускными
способностями. Получим решение данного примера методом улучшения
оценок (раздел 6).
Согласно 2° алгоритма (рис. 6) имеем начальную оценку сверху
искомой пропускной способности
оптимального маршрута
{
}
1
1,4
66 6
π = min 10 ;10 = 10
.
По начальной оценке
1
1,4
π (в матрице с игнорируется только элемент
c
2,3
=1) строятся маршруты из пункта А
1
в пункт А
4
:
A
2
A
3
A
1
A
4
10
6
10
6
10
6
10
6
С
2,3
=1
4
3
2
i = 1
=
c

Страницы