Материал: Методы оптимизации. методические указания для организации самостоятельной работы по курсу «Высшая математика». Пантелеев И.Н
C64 = min(C64 , C62 + C24 ) = min( ¥,2 + ¥) = ¥;
C65 = min(C65 ,C62 + C25 ) = min(3,2 + 6) = 3;
C66 = 0.
Матрица, полученная после второй итерации, имеет вид
|
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
C12 = min( C12 ,C13 + C32 ) = min(1,4 + 3) = 1;
C13 = min( C13 ,C13 + C33 ) = 4;
C14 = min( C14 ,C13 + C34 ) = min( ¥,4 + 5) = 9; C15 = min( C15 , C13 + C35 ) = min( 7,4 +1) = 5; C16 = min( C16 ,C13 + C36 ) = min(3,4 + 3) = 3.
Для второй строки получим
C23 = min(C23 ,C23 + C33 ) = 3;
C24 |
= min(C24 ,C23 |
+ C34 ) = min( ¥,3 + 5) = 8; |
C25 |
= min(C25 , C23 |
+ C34 ) = min( 6,3 +1) = 4. |
Приведем теперь расчет элементов, которые меняют свои |
||
значения |
|
|
C34 |
= min(C34 ,C33 |
+ C34 ) = min(5,5) = 5; |
C41 |
= min( C41 , C13 |
+ C31 ) = min( ¥,5 + 4) = 9; |
C42 |
= min(C42 ,C43 |
+ C32 ) = min( ¥,5 + 3) = 8; |
C43 |
= min(C43 ,C43 |
+ C33 ) = 5; |
C46 |
= min(C46 ,C43 |
+ C36 ) = min( ¥,5 + 3) = 8; |
C51 |
= min( C51 , C53 + C31 ) = min( 7,1 + 4) = 5; |
|
C52 |
= min(C52 ,C53 |
+ C32 ) = min( 6,1 + 3) = 4; |
19
|
C64 = min(C64 , C63 |
+ C34 ) = min(¥,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 |
8 |
|
5 |
|
5 |
4 |
1 |
1 |
0 |
3 |
|
6 |
|
3 |
2 |
3 |
4 |
3 |
0 |
|
Приведем расчет для k= 5 только тех элементов, которые
меняются |
|
|
|
|
|
|||
C14 |
= min( C14 , C15 |
+ C54 ) = min( 9,5 +1) = 6; |
|
|
||||
C24 |
= min( C24 ,C15 |
+ C54 ) = min(8,4 +1) = 5; |
|
|
||||
C34 = min(C34 , C35 |
+ C54 ) = min( 5,1 +1) = 2; |
|
|
|||||
C41 = min( C41 ,C45 |
+ C51 ) = min(9,1 + 5) = 6; |
|
|
|||||
C42 |
= min( C42 ,C45 |
+ C52 ) = min(8,1 + 4) = 5; |
|
|
||||
C46 |
= min( C46 ,C45 |
+ C56 ) = min(8,1 + 3) = 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. Для сети, представленной на рис. 3, найти кратчайшие пути от вершины а1 до остальных.
Решение. Результаты расчетов приведены в таблице.
20
k |
p |
l1 |
l2 |
l 3 |
l 4 |
l 5 |
|
l 6 |
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
¥ |
¥ |
¥ |
¥ |
¥ |
|
2 |
2 |
0 |
1 |
¥ |
¥ |
¥ |
5 |
|
3 |
6 |
0 |
1 |
4 |
¥ |
7 |
|
3 |
4 |
3 |
0 |
1 |
4 |
¥ |
6 |
3 |
|
5 |
4 |
0 |
1 |
4 |
9 |
5 |
3 |
|
6 |
5 |
0 |
1 |
4 |
6 |
5 |
3 |
|
В первом столбце дается номер итерации, во втором — номер вершины, получающей на данной итерации постоянную пометку, а в остальных — величины пометок для каждой вершины. Столбец выделяется жирными линиями, начиная с той итерации, на которой пометка соответствующей вершины стала постоянной. Рассмотрим порядок расчета.
1. |
На |
первой |
итерации |
пометка |
первой |
вершин |
||||
постоянная |
и |
равнаl1 = 0 , |
пометки |
остальных |
вершин |
|||||
временные и равны li = ¥. |
|
|
|
|
|
|
||||
2. |
Соседями |
вершины а1 является |
а2 |
и а6 . |
Временные |
|||||
пометки этих вершин равны |
|
|
|
|
|
|
||||
l2¢ = min( ¥,0 +1) = 1; |
l6¢ = min( ¥,0 + 5) = 5. |
|
|
|
||||||
Выбираем минимальную из них l2¢ = 1; p = 2; l p |
= 1. |
|
||||||||
3. |
На |
третьей итерации соседями |
вершиныа2 являются |
|||||||
вершины a3 , a5 , a6 . Временные пометки этих вершин |
|
|
||||||||
l2¢ = min( ¥,1 + 3) = 4; |
l5¢ = min( ¥,1 + 6) = 7; |
|
|
|
||||||
l6¢ = min(5,1 + 2) = 3. |
|
|
|
|
|
|
|
|||
Минимальная |
из |
нихl6¢ |
становится |
постояннойl6 |
= 3, |
|||||
p = 6. |
|
|
|
|
|
|
|
|
|
|
4. |
Соседями |
вершины а6 являются |
a3 , a5 . Временные |
|||||||
пометки этих вершин l3¢ = min( 4,3 + 3) = 4; |
l5¢ = min( 7,3 + 3) = 6. |
|||||||||
Минимальная из них l3¢ |
становится постоянной l3 = 4, |
p = 3. |
||||||||
21
5. На пятой итерации соседями |
вершиныa3 |
являются |
||
вершины a4 , a5 . Найдем временные пометки этих вершин |
||||
l4¢ = min( ¥,4 + 5) = 9; l5¢ = min( 6,4 +1) |
= 5. |
|
||
Минимальная из |
них l5¢ = 5 становится постоянной l5 = 5, |
|||
p = 5. |
|
|
|
|
6. Вершина a5 |
соседствует с |
вершинойa4 , |
временная |
|
пометка которой l4¢ = min(9,5 +1) = 6, |
p5 |
= 4. |
|
|
Таким образом, кратчайшие пути от первой вершины ко всем остальным приведены в вершинах выделенных столбцов и совпадают с первой строкой матрицы алгоритма Флойда предыдущей задачи.
5. АЛГОРИТМЫ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ПОТОКА
1°. Пусть |
в |
сети |
имеется |
единственный |
источникa |
||
|
|
|
|
|
|
|
0 |
единственный сток an . Обозначим положительным числом bij |
|||||||
пропускную |
способность дуги |
от ai к a j , |
а |
за b ji - |
|||
пропускную способность дуги от a j |
к ai ,причем выполнение |
||||||
равенства |
bij = b ji |
не |
обязательно. Потоком |
в |
сетииз |
||
источника |
a0 |
в |
сток an |
называется |
множество |
||
неотрицательных чисел xij |
, поставленных в соответствие дугам |
||||||
|
|
|
|
ì-u, j = 0, |
|
|
|
сети, таких, что å xij - å x jk = |
ï |
j ¹ 0, n, |
|
|
|||
í0, |
|
|
|||||
|
|
i |
k |
ï |
j = n, |
|
|
|
|
|
|
îu, |
|
|
|
где 0 £ xij £ bij ; число u ³ 0 называется величиной потока.
2°. Пусть начальные пропускные способности дуг заданы. Выберем некоторый начальный поток, например, нулевой.
Алгоритм работает следующим образом.
22
1. Выберем путь из a0 в an положительной пропускной способности q , гдеq - минимальная величина из пропускных способностей .дуг Источник a0 считается вначале
помеченным, но не просмотренным, а все остальные узлы не помеченными.
2. Выбрать любой помеченный, но не просмотренный узел
ai .
3. Всем узлам a j , для которых bij ³ 0 , приписать пометки
( i, j ) и |
считать |
их |
помеченными. Считать |
узел a0 |
просмотренным. Если при этом сток an оказался помеченным, то по пометкам легко восстановить искомый путь изa0 в an .
В противном случае следует перейти к шагу 2. Если это невозможно, то искомого пути не существует.
4. Пусть (a0 , ai1 ), (ai1 , ai2 ), …, (aim -1 , aim ) — найденный путь. Тогда для каждой дуги (aik , aik +1 ) ^), входящей в этот
путь, следует выполнить операторы:
xi i |
k +1 |
:= xi i |
+q; bi i |
:= bi i |
-q; |
k |
k k +1 |
k k +1 |
k k +1 |
||
bi i |
:= bi i |
+q; u := u +q. |
|
||
k +1 k |
k +1 k |
|
|
|
|
Далее переходим к шагу1. Если пути положительной пропускной способности не существует, то полученный поток является максимальным.
5.1. В областиимеется семь городов, соединенных дорогами. Граф задачи показан на рис.4.
Рис. 4
23