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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

v
*
= 4 + 5 + 2 +2 = 3 + 6 + 4 = 13
Рис. 9.12. Увеличение потока вдоль увеличивающей цепи
Таблица 9.3
)1,(
+
s
Дуги минимального разреза и вершины множества R показаны на рис.
9.13 жирными линиями. Пропускная способность минимального разреза
равна сумме 5 + 2 + 2 +3 + + 1 =13 =
*
v
В дальнейшем мы будем решать подобные задачи для более простого
случая, когда пропускные способности дуг двудольного графа так велики,
что их можно положить равными ∞. Тогда вместо символа ∞ в правом
верхнем углу допустимой клетки будем писать знак «x» – признак
допустимости. Шаг 2 упростится и будет таким:
Шаг 2. Пометить каждый непомеченный столбец
j, содержащий
допустимую клетку в помеченной строке i, меткой (i
+
, Е
i
).
Как и в случае задачи о наибольшем паросочетании, доказывается, что
при исходе б) шага 4 непомеченные строки и помеченные столбцы
покрывают все допустимые клетки. В минимальный разрез входят,
очевидно, только дуги с конечной пропускной способностью, т.е.
имеющие вид (s, i), (j, t). Кроме того, ясно, что минимальный разрез
j
i
1 3
3
2 6
6
3 4
4
1 5
4
3
3
1
1
2 5
5
3
3
4
2
3 2
2
1
1
1
1
4 2
2
3 2
2
1
3(2)+1 3(2)+1
(s
+
, 1)
(1
+
, 1) (2
+
, 1)
(2
−
, 1)
2
s
1
2
t
5(3)+1 3(2)+1
4(3)
−
1
(1
+
, 1)

Страницы