Черненко В.Д. Высшая математика в примерах и задачах (том 3)
Подождите немного. Документ загружается.
430
Л
Ух
\У1
Уз
1
^4
ь^
60
120
-40
-40
-80
-40
-40 ^.^
Г40
60
60
X,
' 1
1
1
0
1
"г^
1
1
X.
-1
-1
-1
0
0
)
-1
-1
-1
Го
0
Хз
1
-^
г
0
[-1
(3
"V
^4
-1
0
-1
-1
0
0
V
X,
0
1
0
1
-1
-1
0 .'^
1
0
1
1
гпава 31
Ч
-1
0
-1
-1
0 1
0
-'г^
0
0
Выберем разрешающий элемент и перепишем таблицу, за-
меняя ^3
<-^
^3
L
Ух
\У1
X,
^4
ь.
100
140
-40
0
1
40
40
40
60
60
X,
1
1
'[^
1
1
х^
-1
1
-1
1
Н)
0
0
0
0
Уъ
-1
0
-1^х^
-1
0
УА
0
-1
V
0
-1
X,
1
1
-1 ^^
0
1
ч
0
-1
°f^
1
0
Выберем разрешающий элемент и перепишем таблицу, за-
меняя у^
<->
^2
ЭПЕМЕНТЫ ТЕОРИИ ОПТИМИЗАиИИ
431
],
Ух
^2
J^3
^4
ь,
140
0
40
40
60
X,
2
2
-1
1
1
У2
1
1
-1
0
0
Уз
0
1
-1
-1
0
УА
0
-1
0
0
-1
X,
2
1
-1
1
1
^6
0
-1
0
1
0
Целевая функция
L^.^
=140 при ^2 = 40, х^ =
40,
х^
=
60,
31.4. Задача нахождения
кратчайшего пути
V. Граф задается конечным множеством вершин или узлов
{а^^а^у...,
^^) и множеством дуг ияиребер (/р А,...,
/^),
соединя-
ющих некоторые или все вершины. Если ребра ориентированы,
что обычно показывают стрелками, то они называются дугами,
а граф с такими ребрами называется
ориентированным
графом.
Если ребра графа не имеют ориентации, то граф называют нео-
риентированным. Каждая дуга может быть задана упорядочен-
ной парой вершин {ctidj), где а- называется начальной, а
а^
—
конечной вершиной дуги.
Сетыо
называется граф, каждой дуге которого поставлено
в соответствие некоторое неотрицательное число. Эти числа
могут выражать
длину,
пропускную способность, стоимость пе-
ревозки и
т.п.
Иногда сеть ассоциируется
с
транспортной сетью
или сетью связи.
432 Г пава 31
Путем
в графе называют последовательность дуг или вер-
шин, в которой каждая конечная вершина является начальной
вершиной следующего
ребра.
Простым путем
называется путь,
в
котором каждая вершина обходится
не более одного
раза.
Если
в
простом пути ориентации
дуг не
совпадают, то такой путь на-
зывается
простой
цепью.
Граф, в котором каждая пара вершин
соединена некоторой
цепью,
называется
связным.
Задача нахож-
дения кратчайшего пути между двумя заданными вершинами
представляет одну
из
главных задач теории сетей.
2°.
Пусть требуется найти кратчайшие пути от одной вер-
шины ко всем остальным вершинам сети.
Алгоритм
Флойда.
1)
Введем матрицу
С^у,
в которой запи-
саны длины всех дуг сети
с.
О, если
i =
/
длине
дуги между
вершинами
а.
и
а^
оо,
если дуги между
а.
и
UJ
нет.
Положим
fe
=
1.
2)
Для всех
i^i^k
и j^k осуществить операцию
C..:
=
min{Q..,
Q+QJ.
3)
Если k
=
m, вычисления
закончены,
иначе
перейти
к п.
4.
4)
fe:
= ^ +1 и перейти к шагу 2.
Алгоритм применим и для отрицательных длин ребер.
3°.
Алгоритм
Дейкстры.
Алгоритм позволяет найти крат-
чайшие пути от заданной вершины до всех остальных. Обозна-
чим:
С^.у—расстояние
от узла
щ
до а^; I'.—временная пометка для
вершины а., I.—постоянная пометка для вершины
а-\
т—число
вершин в сети.
Полагаем:
1.
4=0, (
=
^ для
/ =
1,...,
т;
i
Фз;
k-1; p^s.
ЭЛЕМЕНТЫ ТЕОРИИ ОПТИМИЗАиИИ
433
2.
Для всех соседей вершины
а^
с временными пометками
изменить пометки по формуле
/;
= min(^/;,/^+C^J.
3.
Для всех вершин, имеющих временные пометки, найти
/^ =minl',
4.
Положить р = г,
k:
=
k
+
l. Если k
=
m, вычисления закон-
чены, иначе перейти к шагу 2.
4.1.
Пусть дана сеть (рис. 31.3). Найти кратчайшие пути
между всеми узлами.
Рис. 31.3
Решение. Составим исходную матрицу
1
2
3
4
5
6
1
0
1
оо
оо
сх>
5
2
1
0
3
оо
6
2
3
ОО
3
0
5
1
3
4
ОО
оо
5
0
1
оо
5
ОО
6
1
1
0
3
6
5
2
3
ОО
3
0
при k
=
l матрица не меняется, поэтому рассмотрим слу-
чай, когда k
=
2'
Cj3 =
min(^C,3,
Cj2
+
С23 >)
=
min(^oo,
1
+ 3 j = 4;
434 Г
пава
31
Ci4 = min(^Ci4, Q2 + Q4
>>
= min(^oo,
1
+
oo^
= oo;
Cj5 = min(^Cj5, C,2 +
C25
J = min(^oo,
1
+ 6^ = 7;
Cj6 =
rmn(C^^,
Cj2 +
C26;
= min(^5,1 + 2; = 3.
Найдем элементы матрицы во второй строке матрицы
С^^
= min(^C2i,
С22
+ С2 J = min(^l, 1^ = 1;
С -О-
22 ~ *
С23 =
min(^C23 > ^11
+ Q3
>^"
min(^3,3^ = 3;
С24 = min('C24, С22 + С24
>)
= minf'oo, оо^ = oo;
С25 = min(^C25' Q2 + Qs
>^"
min(^6,6^ = 6;
C26 = min('C26' ^22 +
^26
>*
= min("2,2^ = 2.
Для третьей строки найдем
Сз1 = тт(^Сз1, Сз2 +
С21 ^
= min(^oo, 3
+1^
= 4;
С32 = тт(^Сз2,
Сз2
+^22^ = min(^3,3^ = 3;
Сзз=0;
Сз4 = тт('Сз4, Сз2 +
С24,)
= min(^5,3 +
00^
= 5;
С35 = тш(^Сз5' Q2 + ^5
>^
= min(^l, 3 + 6^ = 1;
С36 = тт('Сзб, Сз2 +^26^* = minp, 3-f 2; = 3.
Для четвертой строки
С41
= min(^C4i,
С42
+ Q J = min(^oo,
00
+1^
= 00;
C42 = min(^C42,
C42
+
C22 >)
= ^;
C43 = min(^C43' Q2 +
^23
>*
= min(^5,00 + 3 J = 5;
^44=0;
C45 = min('C45,
C42
+025^ = minn,
сю
+ 6 J = 1;
C46 = inin('C46, Q2 +
^26 >>
= min(^oo,
00
+ 2; = 00.
ЭПВМЕНТЫ ТЕОРИИ ОПТИМИЗАиИИ
435
Пятая строка примет вид
Cj,
= minf'Cj,,
С52
+Cj^)
=
min(^co,
в
+
\)
=
7;
C52
= minf
C52,
C52
+
C22 ^
= min(^6,6^ = 6;
C53
= minfC53,
C52
+
C23 ^
= minf'l,
6
+ 3 j = 1;
C54
= minfC54,
C52
+ C24 j = mm(\,
6
+
00;
= l;
Q,=0;
^56 = minf
C5,,
C52
+ C2 J = min(^3,6
+
2; = 3.
Элементы шестой строки
Q, = minf'Q,, Q2 +
C2,;
= min('5,2-\-\)
=
3;
Q2 = ^10(^^2, Q2 +^22^ = min(^2,2; = 2;
Q3 =
min('Q3,
Q2 +
C23;
= тш(Ъ,
2
+ З; = 3;
Сб4
= minf'C^, Q2 +
C24;
= minf'oo,
2
+
00;
=
00;
Q5 = minf'Qs, Q2 +
C25;
= minf'S,
2
+ 6; = 3;
Матрица, полученная после второй итерации, имеет вид
1
2
3
4
5
6
1
0
1
4
оо
7
3
2
1
0
3
оо
6
2
3
4
3
0
5
1
3
4
ОО
оо
5
0
1
оо
5
7
6
1
1
0
3
6
3
2
3
оо
3
0
Рассмотрим случай, когда k
= 3
436
Гпава 31
С,з=ттГС,з,С,з+Сзз; = 4;
Ci4 = тт('С,4, С,з
+Сз4>)
= minf'oo,
4
+ 5; = 9;
С,5 =
min(^Cj5,
Q3
+
С35 >)
= min(^7,4
+1^
= 5;
С,б = mini'C,^, С,з + Сз J = mini's,
4
+ 3; = 3.
Для второй строки получим
С2з=тт('С2з,С2з+Сзз>> = 3;
С24
=
min('C24,
С23
+^34^ = minf'oo,
3
+
5^
= 8;
С25
=
min('C25,
С23
+
Q5
>^
- minf^e,
3
+
1^
= 4.
Приведем теперь расчет элементов, которые меняют свои
значения
Сз4 = тш('Сз4,
Сзз
+
Сз4>>
= mini's, 5^ = 5;
С41
=
тт(С^^'
Qs + Qi
>>
= niinf'c»,
5
+ 4; = 9;
С42
=
min('C42,
C43
+
C32
j = mini'oo,
5
+ З; = 8;
C43
=
m\n(C^^,
C43
+
C33;
=
5,-
C46
=
rmn(C^,
C43
+ C3 J = minf'oo,
5
+ З; = 8;
C51
= min('C5i,
C53
+ C3 J = minf
7,1
+ 4J = 5;
C52
=
mm(C^^,
Q3
+
C32;
= mini'e,
1
+
3^
= 4;
C^ =
min('C64,
Q3
+
C34 J
= minf'oo,
3
+
5^
= 8.
Матрица, полученная после третьей итерации, будет
1
2
3
4
5
6
1
0
1
4
9
5
3
2
1
0
3
8
4
2
3
4
3
0
5
1
3
4
9
8
5
0
1
4
5
5
4
1
1
0
3
6
3
2
3
8
3
0
ЭЛЕМЕНТЫ ТЕОРИИ ОПТИМИЗАЦИИ
437
Приведем расчет для
/^
=
5
только тех элементов, которые
меняются
^4 = min('C,4,
С,5
+ С54
у)
= min('9,5
-h
I; = 6;
С24
=
min('C24,
С25
+
С54
j = min(^8,4
-h
i; = 5;
C34
=
1ШП('Сз4,
Сз5
+
C54 ^
= тт(Ъ,
1
+1^
= 2;
C41
=
min(^C4j,
C45
+ C5 J =
min(^9,1
+ 5 J = 6;
C42
=
min('C42,
C45
+
C52 ^
=
min(^8,1
+ 4 J = 5;
C46
=
min(^C46,
C45
+ C5 J =
min(^8,1
+ З; = 4.
Таким образом, кратчайшие пути между всеми узлами
1
2
3
4
5
6
1
0
1
4
6
5
3
2
1
0
3
5
4
2
3
4
3
0
2
1
3
4
6
5
2
0
1
4
5
5
4
1
1
0
3
6
3
2
3
4
3
0
4.2.
Для сети, представленной на рис. 31.3, найти кратчай-
шие пути от вершины
Oj
до остальных.
Решение. Результаты расчетов приведены в таблице.
k
1
2
3
4
5
6
Р
1
2
6
3
4
5
k
0
0
0
0
0
0
4
00
к
оо
4
4
4
4
пг~
оо
ОО
оо
оо
9
6
4
оо
оо
7
6
5
5
4
ОО
5
3
3
3
3
438 г пава 31
В первом столбце дается номер итерации, во втором — но-
мер вершины, получающей на данной итерации постоянную по-
метку, а
в
остальных — величины пометок для каждой вершины.
Столбец вьщеляется жирными линиями, начиная
с
той итерации,
на которой пометка соответствующей вершины стала постоян-
ной. Рассмотрим порядок расчета.
1.
На первой итерации пометка первой вершины постоянная
и
равна /j =
О,
пометки остальных вершин временные
и
равны
1.=оо,
2.
Соседями вершины
а^
являются 02 и а^. Временные по-
метки этих вершин равны
Выбираем минимальную из них /2=1, Р = 2, /р = 1.
3.
На третьей итерации соседями вершины «2 являются вер-
шины
а^,а^,а^.
Временные пометки этих вершин
/; = minf^oo,
1
+ 3; = 4; /; =
min(^oo,
1
+ 6; = 7;
/;=min(^5,l + 2; = 3.
Минимальная
из
них /^ становится постоянной /^
== 3
и р = 6.
4.
Соседями вершины а^ являются
ci^,ci^.
Временные помет-
ки этих вершин /з =
min(^4,3
+ 3 j = 4; /5 = тт(1,3 +
3^
=
6.
Ми-
нимальная из них /з становится постоянной /з = 4 и р =
3
.
5.
На пятой итерации соседями вершины а^ являются вер-
шины
а^,а^.
Найдем временные пометки этих вершин
/;=min(^oo,4
+
5; = 9; /; = min(^6,4
+
lj = 5.
Минимальная из них
1^
= 5
становится постоянной 4 =
5
и р = 5.
5.
Вершина а^ соседствует с вершиной а^, временная по-
метка которой /^ = min(^9,5 +
1^
= 6, Р5 = 4.
Таким образом, кратчайшие
пути
от первой вершины
ко
всем
остальным приведены в вершинах выделенных столбцов и со-
впадают с первой строкой матрицы алгоритма Флойда преды-
дущей задачи.
ЭПЕМЕНТЫ ТЕОРИИ ОПТИМИЗАЦИИ 439
31.5.
Алгоритмы определения
максимального потока
1°.
Пусть в сети имеется единственный источник а^ и един-
ственный сток
а„*5
Обозначим положительным числом
Ь..
про-
пускную способность дуги от а. к
fl^y,
а за
Ь-.^
— пропускную
способность дуги от а. к а., причем выполнение равенства
6,у =
Ьу^
не обязательно. Потоком в сети из источника а^ в сток
а^
называется множество неотрицательных чисел х.у, поставлен-
ных в соответствие дугам сети, таких, что
&/-Х^/.=
-t;, / =
0,
О, /
-t
О,
п,
где
О
<
X.J
<
b.j;
число v>0 называется величиной потока,
2°.
Пусть начальные пропускные способности дуг заданы.
Выберем некоторый начальный поток, например, нулевой. Ал-
горитм работает следующим образом.
1.
Выберем путь из а^ в а^ положительной пропускной
способности в, где в — минимальная величина из пропуск-
ных способностей дуг. Источник а^ считается вначале поме-
ченным, но не просмотренным, а все остальные узлы не
помеченными.
2.
Выбрать любой помеченный, но не просмотренный
узел а..
3.
Всем узлам а^, для которых
b.j
> О
, приписать пометки
(i,j) и считать их помеченными. Считать узел
UQ
просмотрен-
ным. Если при этом сток а^ оказался помеченным, то по по-
меткам легко восстановить искомый путь из а^ в а„. В
противном случае следует перейти к шагу 2. Если это невоз-
можно, то искомого пути не существует.