Алгоритм Форда – построения максимального потока в сети.

Начальный. Выбираем некоторый поток в сети G (V,U) (например x_{i j}= 0 для всех дуг (i,j)Î U).

Общая итерация 1. Применяем алгоритм нахождения увеличивающего пути из источника s в сток t. Если такого пути нет, то построенный поток яв­ляется максимальным. Алгоритм заканчивает работу. Если увеличивающий путь найден, то переходим к 2.

2. В найденном увеличивающем пути обозначим через P⁺ множество прямых, а P ^- - множество обратных дуг пути и вычисляем величину ₁ = (d_ij – x_ij) > 0 и _{2 =} . Полагаем q = min ( ₁, ₂). Увеличиваем поток вдоль пути P на величину , полагая

 

x_ij^’ = x_ij+ , если (i,j) Î P⁺

x_ij^’ = x_ij – , если (i, j) Î P^- (23)

x_ij^’ = x_ij для остальных дуг пути.

 

Переходим к 1.

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

 

Рис.1.

 

Найдем увеличивающий путь.

Общая итерация: Шаг 1. Источник s получает пометку (s⁺).

Шаг 2. Так как = 1< = 2, то вершина 1 получает метку (s⁺). Вер­шина 2 получает метку (s^-), т.к. x₂₁ = 1 > 0. Вершина 5 не может быть помечена, т.к. (дуга (s, 5) – насыщенная).

Шаг 3. Соседними вершинами с вновь помеченными являются вершины 3 и 4. Вершина 3 помечена не может быть, так как x₁₃ = d₁₃.. Вершина 4 получает пометку (2^-), т.к. х₄₂ = 1 > 0.

Шаг 4. Соседними с помеченной вершиной 4 являются вершины t и 5. Вершина t помечена не может быть, т.к. х_t4 = 0. Вершина 5 получает пометку (4 ^-), т.к. x₅₄=1>0.

Шаг 5. Помечаем вершину t с меткой (5 ⁺), x₅₁=1 < d₅₁=3.

Увеличивающий путь: s – 2 – 4 – 5 - t, причем на этом пути дуга (5, t) является прямой, а дуги (2, s); (4, 2); (5, 4) обратными.

Увеличим поток вдоль этого пути по формулам (23).

Находим

e ₁

e ₂ =

т.е. e = min(e ₁,e ₂) = 1.

Полагаем

_2S = x_2S – 1 = 0, ₄₂ = x₄₂ –1 =0, ₅₄ = x₅₄ – 1 = 0, _5t = x_{5 t}+1 = 2.

Величина суммарного потока в сети равна 3.

Общая итерация 1. Для нового потока ищем увеличивающий путь мето­дом расстановки пометок. Пометить удается только вершины s и 1. Следова­тельно, увеличивающего пути нет, и построенный поток является максималь­ным. Минимальный разрез (R,, , где R = {1; 2}, = {2; 3; 4; 5; t} состоит из дуг (R, ) = {(1, 3); (s, 5); (s,2); (1,2)} и обладает пропускной способностью

C (R, ) = d₁₃ + d_S5 = 3.

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

 

 

Рис. 2

 

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 6. Сеть задана матрицей пропускных способ­ностей дуг (d_ij = 0 означает, что в сети отсутствует дуга, ведущая из вершины 1 в вершину j). Требуется по матрице D построить сеть и найти в ней максимальный поток из вершины 1 в вершину 10, опреде­лив при этом минимальный разрез.

Вариант 1	Вариант 2
Вариант 3	Вариант 4
Вариант 5	Вариант 6

Вариант 7	Вариант 8
Вариант 9	Вариант 10

 

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

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

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

Полученные данные удобно заносить в таблицу. В таблице 1 приведены данные для проекта, состоящего из девяти работ.

Таблица 1

 

№ работы
Предшествующие работы	-	-		1, 2	1, 2	3, 4	3, 4		7, 5
Продолжительность работы

 

 

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

Рис. 3.

 

Предварительно следует упростить полученную сеть. Можно удалить некоторые дуги-связи, а начало и конец удаляемой дуги объединить в одну вер-шину. На рис. 2 изображена сеть, полученная после упрощения сети, изобра-женной на рис. 1.

Рис. 4.

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

После построения сетевого графика все его вершины нумеруются так, что нумерация является правильной.