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

Изначально величине потока присваивается значение 0: f (u, v) = 0 для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Дан граф G (V, E) с пропускной способностью c (u, v) и потоком f (u, v) = 0 для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:

· . Поток из u в v не превосходит пропускной способности.

· .

· для всех узлов u, кроме s и t. Поток не изменяется при прохождении через узел.

Остаточная сеть G_f (V, E_f) — сеть с пропускной способностью c_f (u, v) = c (u, v) − f (u, v) и без потока.

Вход Граф G с пропускной способностью c, источник s и сток t
Выход Максимальный поток f из s в t

1. для всех ребер

2. Пока есть путь P из s в t в G_f, такой что для всех ребер :

1. Найти

2. Для каждого ребра

1.

2.

 

Задача №4

Найти критический путь для данного проекта

Работа	Следование	Продолжительность
A	-
B	M, O
C	A
D	M, O
E	I, K
F	-
G	E
H	C
I	H
J	I, K
K	F
L	K, G
M	K, G
N	F
O	N

 

Задача №5.

Менеджер – координатор аудиторской фирмы должен распределить аудиторов для работы на следующий месяц. Есть заявки от 10 клиентов на 75 аудиторов. В четырех конторах фирмы работают 90 аудиторов. 15 аудиторов можно отправить на плановую учебу. Аудиторы различаются по квалификации и опыту работы. Прежде чем приступить к аудиту конкретной фирмы, они должны затратить определенное время на подготовку и консультации. Менеджер – координатор, учитывая опыт работы аудиторов каждой конторы, оценил время, необходимое в среднем аудитору каждой конторы для подготовки к аудиту конкретного клиента. Результаты приведены в таблице. Знаки вопроса в клетках таблицы означают, что аудиторы из этой конторы не имеют опыта аудита в отрасли, которой занимается клиент, и их нельзя посылать к нему. Распределить аудиторов так, чтобы суммарные временные затраты на подготовку были минимальны.

 

Конторы	Клиенты	Ресурсы
К 1	К 2	К 3	К 4	К 5	К 6	К 7	К 8	К 9	К 10
А 1
А 2
А 3
А 4		?							?
Заявки

 

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