ВУЗ:
Составители:
Рубрика:
Основная задача о максимальном потоке из s в t состоит в
нахождении такого множества потоков по дугам, чтобы величина v была
максимальной. Эта задача и её варианты возникают во многих
приложениях.
Задача максимизации выражения (9.3) при условиях (9.1) − (9.2) −
это задача линейного программирования. Дадим сначала
содержательное описание двойственной задачи. Затем опишем
алгоритм построения максимального потока. Далее построим модель
двойственной задачи и применим условия дополняющей
нежесткости, чтобы доказать, что поток действительно максимален.
Одновременно доказывается оптимальность найденного решения
двойственной задачи.
9.2. Разрезы
Разобьем множество V вершин транспортной сети на два
непересекающихся подмножества
R
и R :
,VRR =U
,∅=RR I
так,
чтобы s∈R, a .
R
t
∈ Тогда разрезом, отделяющим s от t, называется
совокупность всех дуг транспортной сети вида (V
i
, V
j
), где V
i
∈R,
.RV
j
∈
Будем обозначать разрез символом
).,( RR
Рис. 9.2. Пример транспортной сети
s
t
V
3
V
1
V
2
4
3
1
6
5
2
3
2
2
Страницы
- « первая
- ‹ предыдущая
- …
- 60
- 61
- 62
- 63
- 64
- …
- следующая ›
- последняя »
