Введение в линейное программирование. Палий И.А. - 69 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Шаг 4. Найдена увеличивающая цепь, по которой из источника в сток
можно переслать дополнительные единицы потока. Восстановить эту
увеличивающую цепь, ориентируясь по меткам вершин, начиная с
вершины t. Увеличить потоки на всех прямых дугах этой цепи на E
t
,
уменьшить потоки на всех обратных дугах этой цепи на E
t
, где E
t
– вторая
часть метки вершины t.
Шаг 5. Стереть все пометки, кроме метки источника, и возвратиться к
шагу 2.
Шаг 6. В транспортной сети построен максимальный поток.
Множество дуг, ведущих из помеченных вершин в непомеченные,
образует минимальный разрез. Конец.
Пример Найдем максимальный поток в сети, показанной на рисунке
9.2. Для уменьшения количества итераций начнем с ненулевого
допустимого потока (рис. 9.5).
Рис. 9.5. Транспортная сеть с начальным потоком величины 7
Шаг 1. Метим источник меткой (0, ∞).
Шаг 2. Из вершины s можно пометить вершину V
2
меткой
(s
+
, min(∞; 4 − 3)) = (s
+
, 1) и вершину V
3
меткой (s
+
, min(∞; 2 − 1)) = (s
+
, 1).
Из вершины V
2
помечается вершина V
1
меткой (V
2
+
, min(1; 5 − 0)) = (V
2
+
, 1).
Из вершины V
1
метится вершина t меткой (V
1
+
, min(1; 6 − 3)) = (V
1
+
, 1) (рис.
9.6).
Шаг 3. Найдена увеличивающая цепь. Вершина t помечена от вершины
V
1
, вершина V
1
– от вершины V
2
, а вершина V
2
– от вершины s. Причем все
вершины помечены по прямым дугам.
5
S
t
V
3
V
1
V
2
4(3)
3(3)
1(1)
6(3)
2
3(3)
2(2)
2(1)

Страницы