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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

9.5. Алгоритм Форда–Фалкерсона для транспортной сети,
имеющей вид двудольного графа
Если транспортная сеть после удаления из нее источника и стока
вместе с инцидентными им дугами представляет собой ориентированный
двудольный граф, ее можно компактно представить в виде таблицы так же,
как при решении задачи о наибольшем паросочетании. Только вместо
единиц в допустимых клетках будем записывать пропускные способности
дуг и проставлять эти
числа в правом верхнем углу, а в центре будем
проставлять величину потока по данной дуге, если она больше нуля. В
клетках крайнего левого столбца запишем номера вершин из множества V
a
в левом верхнем углу, а в правом верхнем углу запишем пропускные
способности дуг (s, V
i
), V
1
∈ V
a
. В центре клетки проставим ненулевые
потоки по этим дугам.
В клетках верхней строки, где раньше записывались номера вершин из
множества V
b
, перенесем эти номера в левый верхний угол. Пропускные
способности дуг (V
j
, t), V
j
∈ V
b
запишем в правом верхнем углу, в центре
клетки запишем ненулевые потоки по этим дугам. Положим, что все дуги
двудольного графа начинаются в вершинах множества V
a
и кончаются в
вершинах множества V
b
.
Пример транспортной сети приведен на рис. 9.11. Соответствующая ей
таблица – табл. 9.1.
Рис. 9.11. Пример транспортной сети
3
1(1)
1(1)
1(1)
2(2)
2(2)
2(2)
6(4)
6(6)
3(2)
3(2)
3(2)
4(3)
5(5)
5(3)
4
33
1
s
1
2 2
t

Страницы