3548_matematicheskoe_programmirovanie
.pdfСетевой график с найденными числовыми характеристика ми изображен на рис. 2.
4
Рис. 2.
Теперь, зная T f и I f , вычисляем резервы времени. Напри
мер, вычисляем полный резерв времени работы (3, 5). Максимально допустимое время, на которое можно увели
чить продолжительность или отложить начало выполнения работы (i, j) так, чтобы это не вызвало задержки выполнения всего проекта, называется полным резервом времени этой ра
боты и обозначается Ry : Ry = Т" - T f -ty.
Для работы (3, 5) имеем: R35 = Г5П- Tf - 135 = 34 -10 -18 = 6.
Аналогично вычисляются остальные резервы времени.
4. Анализ сетевого графика. Так как структура связей сете вого графика с измененными длительностями работ не изме нялась, правильная нумерация остается прежней (рис. 3).
30
4
Рис. 3
Аналогично находим T f и Tf и вычисляем все резервы
времени. Теперь критическое время равно 50, а критический путь имеет следующий вид: (1, 3), (3, 5), (5,6).
Таким образом, в измененном сетевом графике критиче ский путь имеет только одну общую работу (5, 6) с критиче ским путем исходного сетевого графика. Причем его длина уменьшилась на 2 часа по сравнению с предыдущим.
Для примера проанализируем работу (3, 5). В исходном се тевом графике полный резерв времени R ^ = 6. Значит, можно увеличить продолжительность или отложить начало ее вы полнения на 6 часов, не вызывая задержки выполнения всего проекта. В сетевом графике с измененными длительностями эта работа уже является критической, полный резерв ее вре мени равен нулю. Поэтому любая задержка ее выполнения вызовет такую же задержку выполнения всего проекта.
31
5. ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ В СЕТИ
Задание для самостоятельного решения
Сеть задана матрицей D =|]б/(/| пропускных способностей
дуг ( dy = 0 означает, что в сети отсутствует дуга, ведущая из
вершины i в вершину j). Требуется по матрице D построить сеть и найти в ней максимальный поток из вершины 1 в вер шину 7, определив при этом минимальный разрез.
|
|
|
|
|
|
В а р и а н т ы |
|
|
|
|
|
|
|
|
0 |
10 |
4 |
13 |
0 |
0 |
0 |
0 |
2 |
8 |
0 |
0 |
0 |
|
0 |
10 |
0 |
0 |
0 |
6 |
0 |
0 |
2 |
0 |
7 |
0 |
15 |
0 |
|
5 |
4 |
5 |
0 |
7 |
2 |
5 |
0 |
0 |
7 |
0 |
0 |
8 |
3 |
|
0 |
13 |
0 |
7 |
0 |
0 |
1 |
0 |
6 |
0 |
6 |
0 |
0 |
10 |
|
0 |
0 |
6 |
0 |
0 |
0 |
10 |
7 |
0 |
15 |
8 |
0 |
0 |
4 |
|
1 |
0 |
0 |
5 |
1 |
0 |
0 |
12 |
0 |
0 |
3 |
10 |
4 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
5 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
12 |
16 |
0 |
0 |
0" |
0 |
20 |
15 |
7 |
0 |
0 |
0 |
|
10 |
0 |
5 |
0 |
0 |
0 |
9 |
20 |
0 |
0 |
0 |
7 |
0 |
|
9 |
12 |
5 |
0 |
7 |
3 |
8 |
0 |
15 |
5 |
0 |
11 |
3 |
6 |
|
0 |
16 |
0 |
7 |
0 |
0 |
5 |
0 |
7 |
0 |
11 |
0 |
0 |
12 |
0 |
|
0 |
10 |
3 |
0 |
0 |
13 |
4 |
0 |
7 |
3 |
0 |
0 |
4 |
|
9 |
0 |
0 |
8 |
5 |
13 |
0 |
0 |
0 |
0 |
6 |
12 |
4 |
0 |
|
0 |
0 9 0 0 4 0 |
о; |
0 9 0 0 9 0 |
0 |
32
|
' 0 |
20 |
25 |
8 |
0 |
0 |
0N |
/ 0 |
7 |
16 |
20 |
0 |
0 |
0" |
|
|
20 |
0 |
7 |
|
0 |
15 |
0 |
0 |
7 |
0 |
9 |
0 |
4 |
0 |
6 |
|
25 |
7 |
0 |
|
8 |
0 |
9 |
0 |
16 |
9 |
0 |
3 |
11 |
2 |
0 |
5. |
8 |
0 |
8 |
|
0 |
6 |
10 |
0 |
20 |
0 |
3 |
0 |
8 |
0 |
0 |
|
0 |
15 |
0 |
|
6 |
0 |
9 |
0 |
0 |
4 |
11 |
8 |
0 |
9 |
0 |
|
0 |
0 |
9 |
|
10 |
9 |
0 |
0 |
0 |
0 |
2 |
10 |
9 |
0 |
0 |
|
|
5 0 |
0 0 0 |
0, |
vO |
6 0 |
0 10 0 o, |
||||||||
|
' 0 |
20 |
0 |
12 |
0 |
0 |
0 |
0 |
0 |
19 |
13 |
0 |
0 |
o' |
|
|
20 |
0 |
9 |
0 |
0 |
6 |
0 |
7 |
0 |
10 |
0 |
8 |
0 |
0 |
|
|
10 |
9 |
0 |
|
0 |
7 |
11 |
0 |
19 |
10 |
0 |
3 |
10 |
0 |
0 |
|
12 |
0 |
5 |
0 |
0 |
8 |
0 |
13 |
0 |
3 |
0 |
0 |
9 |
0 |
|
|
0 |
6 |
7 |
|
0 |
0 |
4 |
9 |
0 |
8 |
10 |
0 |
0 |
15 |
0 |
|
0 |
0 |
11 |
8 |
4 |
0 |
0 |
0 |
0 |
6 |
9 |
15 |
0 |
0 |
|
|
v 0 |
3 |
0 |
|
0 |
9 |
0 |
0 |
0 |
7 |
0 |
0 |
7 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
12 |
19 |
|
0 |
0 |
0 |
0" |
'0 |
7 |
13 |
15 |
0 |
0 |
0 |
|
12 |
0 |
10 |
|
0 |
4 |
0 |
0 |
7 |
0 |
10 |
0 |
0 |
0 |
12 |
|
19 |
10 |
0 |
|
9 |
0 |
10 |
0 |
13 |
10 |
0 |
12 |
3 |
6 |
0 |
|
6 |
0 |
9 |
|
0 |
0 |
12 |
0 |
15 |
0 |
12 |
0 |
0 |
7 |
0 |
|
0 |
4 |
6 |
|
0 |
0 |
10 |
2 |
0 |
0 |
3 |
0 |
0 |
4 |
8 |
|
0 |
0 |
10 |
|
12 |
10 |
0 |
0 |
0 |
0 |
6 |
7 |
4 |
0 |
0 |
|
0 |
9 |
0 |
|
0 |
9 |
0 |
0, |
|
12 |
0 |
0 |
8 |
0 |
0 |
33
5.1. Алгоритм Форда - построения максимального потока в сети
Методические указания к решению задания
Начальный. Выбираем некоторый поток {х(/} в сети G (V,U)
(например, ху = 0 для всех дуг (/,_/) е U).
1. Общая итерация. Ш аг 1. Источник s получает метку (л,+). Шаг 2. Для всех дуг (л1, у), выходящих из вершины s, соот ветствующие вершины j получают метку л,+, если х,у < dv. Для дуг (/, s), входящих в вершину ,у, соответствующие вершины /
получают метку (s'), если х„> 0.
Шаг к. Просматриваем все вершины, помеченные на (£-1)-м шаге. Для каждой такой вершины к, соответствующие им вер шины j, для которых хк]< dkj, получают метку (к+), для всех дуг (г, к), входящих в вершину к, соответствующих им вершины /, для которых х,к > 0, получают метку (к ').
Алгоритм заканчивает работу одним из двух состояний: а) после некоторого шага мы не можем пометить ни одной вер шины, сток / остался непомеченным. Это означает, что имею щийся поток является максимальным, а (R, R ), где R - множе ство помеченных, R - множество непомеченных вершин, обра зует минимальный разрез; б) сток t оказался помеченным. Двигаясь от стока t к вершине, номер которой указан в ее метке
итак далее, мы придем к источнику.
2.В найденном увеличивающем пути обозначим через Р+ множество прямых, а через F - множество обратных дуг пути
ивычислим величину
е, = m in (^ -X y )> 0 и е2 = m inxy>0. |
(15) |
Oj)eP+
34
Полагаем е = min(ej,s2) - Увеличиваем поток вдоль пути Р
на величину е , полагая |
|
|
х(/ = Ху+ S , |
если (/' J) е Р+ |
|
Xij = Ху— 8 , |
если (г,У) е Р \ |
(16) |
Ху = ху для остальных дуг сети.
Переходим к шагу 1.
Рассмотрим пример. На рис. 4 изображена сеть. Первое число в скобках указывает пропускную способность дуги, второе - дуговой поток.
Найдем увеличивающий путь.
Общая итерация: Шаг 1. Источник s получает пометку (s ). Ш аг 2. Так как xsl = 1 < dsX = 2, то вершина 1 получает
метку (s+). Вершина 2 получает метку (5 '), т.к. Х21 - 1 > 0. Вершина 5 не может быть помечена, т.к. х,,5 = ds5 (дуга (.?, 5) - насыщенная).
35
Шаг 3. Соседними вершинами с вновь помеченными явля ются вершины 3 и 4. Вершина 3 не может быть помечена, так как *13 = d\3. Вершина 4 получает пометку (2'), т.к. х42 = 7 > 0.
Шаг 4. Соседними с помеченной вершиной 4 являются вершины t и 5. Вершина ( не может быть помечена, т.к. xt4 = 0. Вершина 5 получает пометку (4), т.к. х54=У > 0.
Шаг 5. Помечаем вершину t меткой (5+), x5l = 1 < d5t~ 3. Увеличивающий путь: s - 2 - 4 - 5 - t , причем на этом пути
дуга (5, /) является прямой, а дуги (2, .у); (4, 2); (5, 4) - обрат ными.
Увеличим поток вдоль этого пути по формулам (15)—(16). Находим
4 = |
m in {dst - * 5 / ) = 2, |
£ 2 = m in |
( % 2 ^ 24>^45) = in in ( l;l;l) = l, |
(u h P ~ |
|
т.е.
с = min(s j ,£ 2) = 1.
Полагаем
^ 2 s = X2S ~ 1 - 0, X42 = x42 -1 = 0,
^ 5 4 = X54 -1 = 0, X'St = x5t +1 = 2.
Величина суммарного потока в сети равна 3.
Общая итерация 1. Для нового потока ищем увеличиваю щий путь методом расстановки пометок. Пометить удается только вершины 5 и 1. Следовательно, увеличивающего пути нет, и построенный поток является максимальным. Мини мальный разрез (R, R , гдеR = {S; 1}, R = {2; 3; 4\ 5; /} состоит из дуг (R, R ) = {(1, 3); (s, 5); (2,.v); (2,1)} и обладает пропуск ной способностью С (R, R ) ~ d\^ + dss = 3.
36
На рис. 5 минимальный разрез показан пунктирной линией.
(s+)
5.2. Решение задачи о максимальном потоке
с помощью ЭВМ
Сеть задана матрицей D = |а^| пропускных способностей
дуг ( dy = О означает, что в сети отсутствует дуга, ведущая из
вершины i в вершину /'). Требуется по матрице D построить сеть и найти в ней максимальный поток из вершины 1 в вер шину 10, определив при этом минимальный разрез.
37
В а р и а н т ы
0 |
10 |
4 |
13 |
0 |
|
0 |
0 |
0 |
0 |
0 ' |
|
10 |
0 |
0 |
0 |
|
6 |
|
0 |
15 |
0 |
0 |
0 |
4 |
5 |
0 |
7 |
|
2 |
|
5 |
0 |
0 |
0 |
0 |
13 |
0 |
7 |
0 |
|
0 |
|
1 |
0 |
0 |
6 |
0 |
0 |
6 |
0 |
0 |
|
0 |
|
10 |
3 |
7 |
0 |
0 |
0 |
0 |
5 |
1 |
0 |
|
0 |
0 |
12 |
4 |
0 |
|
0 |
0 |
0 |
0 |
|
0 |
|
0 |
0 |
5 |
0 |
9 |
0 |
0 |
0 |
0 |
|
7 |
|
12 |
5 |
0 |
9 |
7 |
0 |
0 |
0 |
6 |
|
0 |
|
4 |
0 |
9 |
0 |
11 |
0 |
0 |
0 |
0 |
0 |
0 |
9 |
7 11 |
о , |
|||
'о |
2 |
8 0 |
|
0 |
0 0 0 0 |
o ' |
|||||
2 |
0 |
7 |
0 |
|
15 |
0 |
5 |
0 |
0 |
0 |
|
0 |
7 |
0 |
0 |
|
8 |
3 |
0 |
0 |
0 |
0 |
|
6 |
0 |
6 |
0 |
|
0 |
10 |
0 |
0 |
2 |
0 |
|
0 |
15 |
8 |
0 |
|
0 |
4 |
1 |
5 |
0 |
0 |
|
0 |
0 |
3 |
10 |
4 |
0 |
0 |
4 |
11 |
0 |
||
0 |
5 |
0 |
0 |
|
1 |
0 |
0 |
9 |
0 |
0 |
|
0 |
0 |
0 |
0 |
|
5 |
4 |
9 |
0 |
0 |
6 |
|
0 |
0 |
0 |
2 |
|
0 |
11 |
0 |
7 |
0 |
12 |
|
,0 |
0 0 |
0 |
|
0 |
0 4 6 12 |
o j |
|||||
0 |
0 |
12 |
16 |
0 |
0 |
0 |
0 |
0 |
0 |
||
0 |
0 |
5 |
0 |
|
0 |
0 |
9 |
0 |
0 |
0 |
|
2 |
5 |
0 |
7 |
|
3 |
8 |
0 |
0 |
0 |
0 |
|
6 |
0 |
7 |
0 |
|
0 |
5 |
0 |
0 |
0 |
0 |
|
0 |
10 |
3 |
0 |
|
0 |
13 |
4 |
8 |
0 |
0 |
|
0 |
0 |
8 |
5 |
13 |
0 |
0 |
7 |
2 |
0 |
||
0 |
9 |
0 |
0 |
4 |
0 |
0 |
10 |
0 |
12 |
||
0 |
0 |
0 |
0 |
8 |
7 |
10 |
0 |
9 |
13 |
||
0 |
0 |
0 |
6 |
0 |
2 |
0 |
9 |
0 |
11 |
||
0 |
0 |
0 |
0 |
0 |
0 |
12 |
13 |
11 |
0 |
38
0 |
20 |
15 |
7 |
0 |
|
0 |
0 |
0 |
0 |
0 " |
20 |
0 |
0 |
0 |
7 |
|
0 |
9 |
0 |
0 |
0 |
15 |
5 |
0 |
11 |
3 |
6 |
0 |
0 |
0 |
0 |
|
7 |
0 |
11 |
0 |
0 |
|
12 |
0 |
0 |
8 |
0 |
0 |
7 |
3 |
0 |
0 |
|
4 |
9 |
6 |
0 |
0 |
0 |
0 |
6 |
12 |
4 |
|
0 |
0 |
10 |
12 |
0 |
0 |
9 |
0 |
0 |
9 |
0 |
0 |
5 |
0 |
10 |
|
0 |
0 |
0 |
0 |
6 |
|
7 |
5 |
0 |
9 |
0 |
0 |
0 |
0 |
8 |
0 |
2 |
0 |
9 |
0 |
20 |
|
0 |
0 |
0 |
0 0 |
0 10 15 20 |
o j |
|||||
0 |
20 |
25 |
8 |
0 |
0 |
0 |
0 |
0 |
0 N |
|
20 |
0 |
7 |
0 |
15 |
0 |
0 |
0 |
0 |
0 |
|
25 |
7 |
0 |
8 |
0 |
9 |
0 |
0 |
0 |
0 |
|
8 |
0 |
8 |
0 |
6 |
10 |
0 |
0 |
13 |
0 |
|
0 |
15 |
0 |
6 |
0 |
9 |
0 |
7 |
0 |
0 |
|
0 |
0 |
9 |
10 |
9 |
0 |
0 |
12 |
0 |
0 |
|
0 |
5 |
0 |
0 |
8 |
0 |
0 |
10 |
0 |
0 |
|
0 |
0 |
0 |
0 |
7 |
12 |
10 |
0 |
3 |
15 |
|
0 |
0 |
0 |
13 |
0 |
9 |
0 |
3 |
0 |
17 |
|
0 |
0 |
0 |
0 |
0 |
0 |
3 15 |
17 |
o ; |
||
r 0 |
7 |
16 |
20 |
0 |
|
0 |
0 |
0 |
0 |
0 |
7 |
0 |
9 |
0 |
4 |
|
0 |
6 |
0 |
0 |
0 |
16 |
9 |
0 |
3 |
11 |
2 |
0 |
0 |
0 |
0 |
|
20 |
0 |
3 |
0 |
8 |
|
0 |
0 |
0 |
10 |
0 |
0 |
4 |
11 |
8 |
0 |
|
9 |
0 |
12 |
0 |
0 |
0 |
0 |
2 |
10 |
9 |
|
0 |
0 |
0 |
12 |
0 |
0 |
6 |
0 |
0 |
10 |
0 |
0 |
15 |
0 |
12 |
|
0 |
0 |
0 |
0 |
12 |
10 |
15 |
0 |
10 |
25 |
|
0 |
0 |
0 |
10 |
0 |
|
12 |
0 |
10 |
0 |
13 |
, o |
0 0 |
0 |
0 |
|
0 12 0 13 0 |
39