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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

9. ТРАНСПОРТНАЯ ЗAДAЧA И ВEНГEРСКИЙ AЛГОРИТМ EЁ
РEШEНИЯ
Далее мы рассмотрим венгерский алгоритм решения ТЗ,
предложенный создателями теории потоков в транспортных сетях Фордом
и Фалкерсоном, которые обобщили алгоритм Куна решения ЗН.
Рассмотрим коротко теорию Форда и Фалкерсона, в частности, теорему
Форда-Фалкерсона о максимальном потоке и минимальном разрезе и
основанный на ней алгоритм отыскания максимального потока в
транспортной сети. Венгерский алгоритм двойственен по отношению к
методу потенциалов, описанному ранее. В этом алгоритме происходит
последовательное улучшение решения задачи, двойственной
транспортной. Одновременно с оптимальным решением двойственной
задачи получается и оптимальное решение ТЗ. Венгерский алгоритм
свободен от эффекта вырожденности; на каждой итерации целевая
функция двойственной задачи увеличивается на некоторое целое
положительное число.
9.1. Потоки в сетях
Рассмотрим ориентированный граф G=(V, E) с одним источником s
(вершиной, из которой дуги только выходят) и одним стоком t (вершиной,
в которую дуги только входят). Каждой дуге (V
i
, V
j
) графа G поставим в
соответствие положительное целое число r(V
i
, V
j
), называемое пропускной
способностью дуги. В этом случае говорят, что задана транспортная
сеть. Неотрицательные числа x(V
i
, V
j
), определенные на дугах (V
i
, V
j
),
называются потоками на дугах, если выполнены следующие условия:
∑x(V
i
, V
j
) − ∑x(V
k
, V
i
) =0,
tsV
i
,
≠
;
(V
i
, V
j
)
→
∈
i
V
E
; (V
k
, V
i
)
←
∈
i
V
E
; (9.1)
0≤ x(V
i
, V
j
) ≤ r(V
i
, V
j
) для всякой дуги (V
i
, V
j
) данного графа (9.2)
Через
→
i
V
E
обозначено множество дуг графа G, выходящих из
вершины V
i
, через
←
i
V
E
обозначено множество дуг графа G, входящих в
вершину V
i
.
Условие 9.1 называют уравнением сохранения потока. Оно означает,
что суммарный поток, втекающий во всякую вершину, отличную от

Страницы