12.2. Теорема Форда и Фалкерсона

Величина каждого потока от входа к выходу не превосходит пропускной способности минимального разреза, разделяющего вход и выход сети. При этом существует максимальный поток, величина которого равна пропускной способности минимального разреза.

Все известные алгоритмы построения максимального потока основаны на последовательном увеличении потока.

Дуга (U,V) является допустимой, если для нее выполняется одно из условий:

1. направление дуги совпадает с направлением потока и значение потока по этой дуге меньше её пропускной способности f(U,V)<C(U,V)

2. направление дуги противоположно направлению потока и по ней проходит некоторый нулевой поток f(U,V)>0

Дуги, для которых выполняется условие 1), называются увеличивающими или согласованными дугами. Дуги, для которых выполняется условие 2) называются уменьшающими или несогласованными дугами.

Увеличивающей цепью называется простая цепь, соединяющая исток и сток сети, все дуги которой являются допустимыми.

Знание увеличивающей цепи позволяет увеличить поток по ней на величину = { (e)}, где (e)=

При этом по каждой увеличивающей дуге поток увеличивается на , а по каждой уменьшающей дуге уменьшается на .

Такое изменение потока по каждой дуге в сумме компенсируется для каждой вершины сети, отличной от истока и стока, т.е. для любой вершины сети vV\{s,t} по прежнему будет выполняться div(f,v)=0.

12.3. Алгоритм построения максимального потока

Шаг 1. Задать начальное значение потока, если оно не задано. Удобно задавать начальное значение потока равным нулю. Перейти на шаг 2.

Шаг 2. Построить увеличивающую цепь от истока к стоку сети. Если увеличивающей цепи не существует, то максимальный поток построен, его значение: (t)=div(f,s), в противном случае перейти на шаг 3.

Шаг 3. Вдоль построенной цепи увеличить значение потока на величину . Перейти на шаг 2.

На основании теоремы Форда-Фалкерсона доказательством того, что построенный поток максимальный, будет существование разреза, величина которого равна значению построенного потока.

При моделировании реальных задач могут использоваться сети с неориентированными дугами. Использование при расчетах неориентированных сетей предоставляет дополнительные возможности при выборе оптимального решения.

А именно, максимальное значение потока для сети с фиксированной ориентацией может увеличиться при изменении направлений некоторых дуг сети.

По неориентированному ребру поток может идти в любую сторону. Следовательно, для того чтобы построить максимальный поток для неориентированной сети, нужно каждое ребро заменить двумя противоположно направленными дугами, имеющими ту же пропускную способность, что и исходное ребро.

Для полученной ориентированной сети максимальный поток определяется по алгоритму, указанному выше.

В общем случае для неориентированной сети максимальный поток не меньше, чем для фиксированной сети с той же структурой.

13. Сетевое планирование и управление

13.1. Элементы сетевого графика

Сетевое планирование и управление (СПУ) – это совокупность методов, использующих сетевую модель для решения задач упорядочения и координации комплекса взаимосвязанных работ. Сетевая модель чаще всего представляется сетевым графиком – ориентированным ацикличным графом, изображенным на плоскости.

В сетевом графике дуги соответствуют работам комплекса, а вершины – событиям.

Работа в СПУ – это протяженный во времени процесс, требующий затрат ресурсов для его осуществления.

Ожидание – протяженный во времени процесс, не требующий затрат труда. Например, естественная сушка материалов.

Фиктивная работа – логическая связь между событиями, не требующая затрат труда, ресурсов и времени.

Ожидания и фиктивные работы на сетевых графиках обыч-

но изображаются пунктирными линиями.

События – это момент завершения какого-либо процесса, отражающего отдельные этапы выполнения комплекса работ. События на сетевом графике (графе) изображаются кружками (вершинами графа).

Различают следующие разновидности событий:

1. Исходное событие – результат, в отношении которого условно предполагается, что он не имеет предшествующих работ.

2. Завершающее событие – результат, являющейся конечной целью всего комплекса работ.

3. Начальное событие – событие, непосредственно предшествующее данной конкретной работе.

4. Конечное событие – событие, непосредственно следующее за данной работой.

Путь сетевого графика – любая последовательность работ, связывающая таким образом два события, что конечное событие каждой работы совпадает с начальным событием следующей работы. Каждый путь характеризуется своей продолжительностью, которая равна сумме продолжительностей составляющих его работ.

Пути, связывающие исходные и завершающие события называются полными, а все другие пути – неполными.

Полный путь, имеющий наибольшую продолжительность называется критическим путем.

Работы и события, лежащие на критическим пути называются соответственно критическими работами и критическими событиями. Полная продолжительность выполнения всего комплекса работ, отображенного сетевым графиком, равна продолжительности критического пути.