Алгоритм нахождения максимального потока

 

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

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

Шаг 1. Найти цепь, соединяющую s с t, по которой поток принимает положительное значение в направлении s→ t. Если такой цепи не существует, перейти к шагу 3. В противном случае перейти к шагу 2.

Шаг 2. Пусть c^-_ij — пропускные способности дуг цепи (s, t) в направлении s→t(t→s) и q=min{c^-_ij}>0

Матрицу пропускных способностей C_ij можно изменить следующим образом:

(а) вычесть q из всех c^-_ij;

(б) прибавить q ко всем c⁺_ij. При этом общая пропускная способность сети не изменится. Перейти к шагу 1.

Операция (а) дает возможность использовать остатки пропускных способностей дуг выбранной цепи в направлении s→t. Операция (б) восстанавливает исходные пропускные способности сети, поскольку уменьшение пропускной способности дуги в одном направлении можно рассматривать как увеличение ее пропускной способности в противоположном направлении.

Шаг 3. Найти максимальный поток в сети. Пусть С=||с_ij|| — исходная матрица пропускных способностей, и пусть С*=||с^*_ij|| — последняя матрица, получившаяся в результате модификации исходной матрицы (шаги 1 и 2).

Оптимальный поток X=||x_ij|| в дугах задается как

.

Максимальный поток из s в t равен

.

 

Тестовый пример

 

Рассмотрим сеть с указанными на рис.5.1 пропускными способностями.

Рис.5.1. Граф сети

 

Соответствующая матрица пропускных способностей С приведена в табл. 5.1. В качестве исходной цепи можно выбрать s→1→4→t.

Таким образом, ячейки (s, 1), (1, 4) и (4, t) помечаются знаком (-), а ячейки (1, s), (4, 1) и (t, 4) - знаком (+). Для данной цепи максимальный поток определяется как q=min{c_s1, c₁₄, c_4t}=min{10, 5,13}=5.

Матрица С в табл. 5.1 корректируется путем вычитания q=5 из всех элементов, помеченных знаком (-), и сложения со всеми элементами, имеющими знак (+). Результаты приведены в табл. 5.2.

 

Табл. 5.1.Цепь (s→1→4→t),q=5 Табл. 5.2. Цепь s→3→2→t), q=10

	s					t
s
t

	s					t
s
t

 

Результаты последующих итераций приведены в табл. 5.3-5.6.

 

Табл. 5.3. q=5 Табл. 5.4. q=3 Цепь (s→1→3→4→t) Цепь (s→1→3→4→t)

	s					t
s
t

	s					t
s
t

 

Табл.5.5. Цепь (s→3→t), q=2 Табл. 5.6. Нет стока

	s					t
s
t

	s					t
s
t

Из табл. 5.6 следует, что между s и t нельзя построить цепей с положительным потоком, поскольку все элементы в столбце t равны нулю. Таким образом, табл. 5.6 дает матрицу C^*. В табл. 5.1 (матрица С) и табл.5.6 (матрица С^*) приведены данные, характеризующие оптимальный поток, которые используются для вычисления Х=C-C* с заменой отрицательных величин нулями.

В табл. 5.7 дана матрица X, а табл. 5.8 приведена рядом для удобства сравнений исходной матрицы и матрицы потоков.

 

Таблица 5.7. Таблица 5.8.

Матрица оптимального потока Исходная матрица

	s					t
s
t

	s					t
s
t

 

.

 

 

Из табл. 5.8 видно, что z=10+12+3=10+2+13=25. Сумма всех q(=5+10+5+3+2=25) также дает максимальный поток. В табл.5.8 показана исходная матрица с отметкой узлов, через которые происходит сток.

 

Практическая работа №6

 

КАЛЕНДАРНОЕ ПЛАНИРОВАНИЕ

Цель работы: Изучение теоретических и практических приёмов работы с календарным планом..

Сетевое планирование и управление (СПУ) программами включает три основных этапа: структурное планирование, календарное планирование и оперативное управление.

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

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

Заключительным этапом является оперативное управление процессом реализации программы. Этот этап включает использование сетевой модели и календарного графика для составления периодических отчетов о ходе выполнения программы. Сетевая модель подвергается анализу и в случае необходимости корректируется. В этом случае разрабатывается новый календарный план выполнения остальной части программы.