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

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

Интервал [ , ] называется интервалом свободы, а его длина R(i) = - . называется резервом времени события i.

 

Сетевые методы планирования

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

Термин работа используется в широком смысле:

1) действительная работа (возведение стен, окраска труб и т.д.);

2) ожидание (процесс сушки, отвердения бетона и т.д.);

3) зависимость или фиктивная работа - логическая связь между двумя или несколькими работами.

Работы видов 1) и 2) имеют известную положительную длительность. Работы вида 3) имеют нулевую длительность.

Событие - момент завершения какого-либо процесса, отдельного этапа выполнения проекта.

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

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

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

Составим и исследуем сетевой график. Для исследования сетевого графика будем применять метод критического пути. Перейдем к составлению сетевого графика. Нам понадобится упорядочить вершины графа. Для упорядочения вершин применяется метод разбивки графа на слои.

Разбить все вершины ориентированного связного графа без контуров на слои означает, что множество вершин графа нужно разбить на подмножества S⁽¹⁾, S⁽²⁾,...,S^(k), называемые слоями, удовлетворяющие следующим условиям:

1) все элементы данного слоя S⁽ⁱ⁾ не имеют предков в следующих слоях S⁽ⁱ⁺¹⁾, S⁽ⁱ⁺²⁾,..., S^(k), элементы первого слоя не имеют предков, а элементы последнего потомков;

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

Разбиение на такие слои всегда существует.

Первый метод разбивки на слои. Составим матрицу смежности. Затем вычислим столбец V0, каждый элемент которого есть сумма по соответствующей строке элементов матрицы смежности. Вектор Vo содержит некоторое число нулей, это означает, что эти вершины не имеют потомков, они образуют слой 0. Далее вычислим столбец V1, вычитая из столбца V0 столбец матрицы смежности, соответствующий вершине, вошедшей в нулевой слой. Те же операции проделываем для остальных слоев

Поиск критического пути. Вычислим ожидаемое время выполнения событий - (максимальное время). Расчеты осуществляются от слоя к слою. Теперь, двигаясь назад из завершающей вершины, находим дуги, на которых получилось время . Эти дуги составят критический путь или критические пути, если их несколько.

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

Резервы времени событий.

Для каждого события i есть два граничных срока:
время - ожидаемое время наступления события i;
время - предельное время наступления события i.

Для критических событий имеет место равенство = , для некритических ³ .

Интервал [ , ] называется интервалом свободы, а его длина R(i) = - . называется резервом времени события i.

Резервы времени работ.

Полным резервом (i,j) работы (i,j) называется максимально возможная величина, на которую можно увеличить время выполнения данной работы при условии, что событие i наступило в ожи­даемое время , а срок выполнения всего проекта не изменится
(i,j)= - - t (i,j).

Пусть событие i наступило в ожидаемое время . Тогда свободным резервом R_c(i,j) работы (i,j) называется часть полного резерва, на которую можно увеличить продолжительность работы, не из­меняя при этом раннего срока ее конечного события j. R_c(i,j) = - - t (i,j).

Независимым резервом R_н(i,j) работы (i,j) назы­вается величина, на которую возможна задержка работы (i,j) при условии, что начальное событие i наступает в предельно позднее время , а конеч­ное событие j в наиболее раннее время , т.е. R _н(i,j) = max{0; - - t (i,j)}.

Частным резервом R₁(i,j) работы (i,j) называется часть полного резерва, на которую можно увеличить продолжительность работы (i,j) при условии, что начальное и конечное события наступают в свои самые поздние сроки и . R₁(i,j) = - - t (i,j)