4. Понятие разреза. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке.

Пусть дана некоторая сеть. Разобьём множество вершин сети на два непересекающихся множества А и В так, чтобы исток Iпопал в А, а стокS– в В. В этом случае на сети задан разрез. Совокупность ребер (i,j), начальные вершины которых принадлежат А, а конечные – В, называется разрезом сети (А/B).

Пропускной способностью разреза называют сумму пропускных способностей всех рёбер разреза R(A/B) = r_ij.

Сумма всех потоков x_ijпо всем рёбрам разреза называется потоком через разрез

X(A/B) =x_ij.

Теорема Форда-Фалкерсона:на любой сети максимальная величина потока равна

минимальной пропускной способности разреза.

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

Алгоритм решения задачи о максимальном потоке.

1. Построить начальный поток Х=(чем больше величина выбранного потока, тем быстрее решается задача).

2. На основе заданной сети строится новая сеть:

а) каждая дуга, для которой остаётся в новой сети с первоначальнойr_ij;

б) каждая дуга для которой заменяется на две:

- одна дуга того же направления с пропускной способностью r_ij-;

- вторая дуга противоположенного направления с пропускной способностью .

3. Если в новой сети можно найти ненулевой поток из IвS, то этот поток прибавляет-

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

Если же в новой сети отсутствуют ненулевые потоки из IвS, то максимальный

поток сети построен.

Пример.

5. Элементы сетевого планирования.

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

Пример.

Составление сетевого графика требует выполнения определённых организационных и формальных правил.

Организационные правила:

1) составляется подробный перечень всех работ от отправного момента до целевого

результата;

2) определяется продолжительность всех работ;

3) устанавливаются технологические связи между всеми промежуточными событиями и

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

предшествующие и все последующие работы.

Формальные правила:

1) сетевой график должен иметь только одно исходное событие – исток и только одно

завершающее – сток;

2) любые два события должны быть связанны не более чем одной работой и, наоборот,

каждая работа должна заключаться между двумя событиями;

3) сеть не должна иметь контуров, петель, изолированных участков, не связанных

работами с её остальной частью;

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

Замечание:для выполнения формальных правил и учёта ряда технологических процессов вводят фиктивные события и работы. В частности.

1. Если комплекс работ начинается с нескольких работ, не имеющих предшествующих (нарушается п. 1 формальных правил), вводится фиктивный «исток» с дугами к указанным работам.

2. Если два события связанны параллельными дугами (нарушается п.2 формальных правил), вводится фиктивное событие, на которое замыкается одна из работ.

3. Если следует учесть зависимость событий, не связанных реальными работами

(различные работы aиbвыполняются на одном оборудовании), то вводится

фиктивная работа c:

В случаях 1) - 3) фиктивные работы не имеют протяжённости во времени.

4. Если технологический процесс требует естественного дозревания, брожения,

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

следующее событие без учёта этих процессов начаться не может, то вводится

фиктивная работа, имеющая протяжённость во времени.

К основным параметрам сетевого графика относятся:

1. продолжительностьt* критического пути, т.е. наиболее протяжённого во времени пути от истока к истоку;

2. резервы времени событий R(i),определяющие предельно допустимые задержки событийi, не приводящие к изменениюt*;

3. полный резерв времени промежуточной работы R_ij,определяющий максимальный запас времени, на который можно задержать начало работы или увеличить её продолжительность, не изменяяt*;

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

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

Если события iдают начало работам, продолжающимсяt_ijед. времени и завершающимся событиемj, то ожидаемый (ранний) срокt_iнаступленияj-ого события равен

, (1)

(1-е событие – «исток»),

где t_i– ожидаемый (ранний) срокi– го события (i<j).

Наиболее поздний срок наступления i– го события

T_i = min(T_j – t_ij), i =

T_n=t_n=t* (n-ecoбытие – «сток») (2)

Т=

Резерв времени наступления i-го события

(3)

Свободный резерв времени работы (i,j)

(4)

Полный резерв времени работы (i,j)

(5)

Расчёты параметров сетевого графика проводят в 5 этапов, изображая события кружками с четырьмя секторами, которые заполняются по ходу выполнения этапов:

1. находят все t_iпо формулам (1), при этом перемещаются по сетевому графику согласно номерам событий слева направо;

2. находят T_iпо формулам (2), при этом перемещаются по сетевому графику от стока влево по мере убывания номеров событий;

3. определяю R_i по формуле (3)

4. выделяют критический путь;

5. вычисляют все остальные параметры.

Пример.

Замечания:

1. Резерв времени наступления события R_iпозволяет варьировать сроки готовности событияiв пределахt_iT_i.

2. Свободные резервы времени работ с учётом их значений можно использовать (отсрочить начало или затянуть окончание) по всем некритическим работам сети одновременно, не изменив t*.

3. Полные резервы времени использовать одновременно удаётся не всегда.