Материал: Методы оптимизации. методические указания для организации самостоятельной работы по курсу «Высшая математика». Пантелеев И.Н
|
|
|
|
bi |
|
|
x1 |
|
|
x2 |
|
x3 |
|
|
|
y4 |
|
x5 |
|
x6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L |
|
60 |
|
0 |
|
|
-1 |
-1 |
|
|
-1 |
0 |
-1 |
||||||
|
|
|
120 |
|
|
|
1 |
-1 |
-1 |
|
|
0 |
1 |
0 |
||||||
|
y1 |
|
-40 |
|
1 |
|
1 |
-1 |
-1 |
|
|
-1 |
0 |
-1 |
||||||
|
|
|
40 |
|
|
|
-1 |
-1 |
|
|
-1 |
1 |
-1 |
|||||||
|
y2 |
|
-80 |
|
0 |
|
1 |
-1 |
-1 |
|
|
0 |
-1 |
0 |
||||||
|
|
|
-40 |
|
|
|
-1 |
-1 |
|
|
0 |
-1 |
0 |
|||||||
|
y3 |
|
-40 |
|
-1 |
1 |
0 |
-1 |
|
|
0 |
0 |
-1 |
|||||||
|
|
|
40 |
|
|
|
0 |
|
|
0 |
0 |
1 |
||||||||
|
x4 |
|
60 |
|
1 |
|
1 |
0 |
1 |
|
|
-1 |
1 |
0 |
||||||
|
|
|
60 |
|
|
|
0 |
-1 |
|
|
-1 |
1 |
0 |
|||||||
|
Выберем разрешающий элемент и перепишем таблицу, |
|||||||||||||||||||
заменяя |
|
y3 « x3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bi |
|
|
|
x1 |
|
x2 |
|
y3 |
|
|
|
y4 |
|
x5 |
|
x6 |
|
L |
|
100 |
|
|
|
1 |
|
-1 |
|
-1 |
|
|
|
0 |
|
1 |
|
0 |
|
|
|
|
|
140 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
||
|
y1 |
|
-40 |
0 |
|
1 |
|
-1 |
|
0 |
|
|
|
-1 |
|
1 |
|
-1 |
||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
||
|
y2 |
|
-40 |
40 |
1 |
-1 |
|
-1 |
|
-1 |
1 |
|
0 |
|
-1 |
|
0 |
|||
|
|
|
|
|
|
|
|
|
|
0 |
|
-1 |
|
0 |
||||||
|
x3 |
|
40 |
40 |
|
1 |
|
0 |
|
-1 |
|
|
|
0 |
|
0 |
|
1 |
||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
x4 |
|
60 |
60 |
|
1 |
|
0 |
|
0 |
|
|
|
-1 |
|
1 |
|
0 |
||
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
||
|
Выберем разрешающий элемент и перепишем таблицу, |
|||||||||||||||||||
заменяя |
|
y2 « x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
14
|
bi |
|
x1 |
|
y2 |
y3 |
|
y4 |
|
x5 |
x6 |
|
|
|
|
|
|
|
|
|
|
|
|
L |
140 |
|
2 |
|
1 |
0 |
|
0 |
|
2 |
0 |
y1 |
0 |
|
2 |
|
1 |
1 |
|
-1 |
|
1 |
-1 |
x2 |
40 |
|
-1 |
- 1 |
- 1 |
|
0 |
|
-1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
40 |
|
1 |
|
0 |
-1 |
|
0 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
x4 |
60 |
|
1 |
|
0 |
0 |
|
- 1 |
|
1 |
0 |
Целевая |
функция |
Lmin =140 при |
x2 = 40, |
x3 |
= 40, |
||||||
x4 = 60, x1 = x5 = x6 =0. |
|
|
|
|
|
|
|
||||
4. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ
1°. Граф задается конечным множеством вершин или узлов ( a1 , a2 ,..., an ) и множеством дуг или ребер ( l1 , l2 ,...,lm ),
соединяющих некоторые или все вершины. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, а граф с такими ребрами называется
ориентированным графом. Если ребра графа не имеют ориентации, то граф называютнеориентированным. Каждая
дуга может быть задана упорядоченной парой вершин(ai a j ) ,
где ai - называется начальной, а a j — конечной вершиной дуги.
Сетью называется граф, каждой дуге которого поставлено в соответствие некоторое неотрицательное число. Эти числа могут выражать длину, пропускную способность, стоимость перевозки и т.п. Иногда сеть ассоциируется с транспортной сетью или сетью связи.
Путем в графе называют |
последовательность дуг |
или |
||
вершин, в |
которой каждая |
конечная вершина |
является |
|
начальной вершиной следующего ребра. Простым путем |
||||
называется |
путь, в котором каждая вершина обходится не |
|||
более одного раза. Если в простом пути ориентации |
дуг |
не |
||
15
совпадают, то такой путь называетсяпростой цепью. Граф, в котором каждая пара вершин соединена некоторой цепью, называется связным. Задача нахождения кратчайшего пути между двумя заданными вершинами представляет одну из главных задач теории сетей.
2°. Пусть требуется найти кратчайшие пути от одной вершины ко всем остальным вершинам сети.
Алгоритм Флойда. 1) Введем матрицу Cij , в которой
записаны длины всех дуг сети
ì0, если i=j
ï
С = íдлине дуги между вершинами ai и a j
ïî¥, если дуги между ai и a j нет.
Положим k = 1 .
2)Для всех i ¹ k и j ¹ k осуществить операцию
Cij := {Cij , Cik + Ckj }.
3)Если k = m, вычисления закончены, иначе перейти к п. 4.
4) k := k +1 и перейти к шагу 2.
Алгоритм применим и для отрицательных длин ребер.
3°. Алгоритм Дейкстры. Алгоритм позволяет найти
кратчайшие |
пути |
от |
заданной |
вершины |
до |
||
остальных. Обозначим: Сij - расстояние от узла ai до a j |
; |
||||||
li¢ — временная |
пометка |
для |
вершиныai , li |
— |
|||
постоянная пометка для вершины ai ; |
m — число вершин |
||||||
в сети. |
|
|
|
|
|
|
|
Полагаем: |
|
|
|
|
|
|
|
1. ls = 0, li |
= ¥ для i = 1,..., m; |
|
i ¹ s; |
k = 1; p = s. |
|
||
2. Для всех соседей вершины a p с временными пометками
16
изменить пометки по формуле
li¢ = min( li¢, l p + C pi ).
3. Для всех вершин, имеющих временные пометки, найти lr = min li¢.
4. Положить p = r, k := k +1. Если k = m , вычисления закончены, иначе перейти к шагу 2.
4.1. Пусть дана сеть (рис. 31.3). Найти кратчайшие пути между всеми узлами.
Рис. 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 =1 матрица не меняется, поэтому рассмотрим
случай, когда k = 2. |
|
|
C13 |
= min( C13 ,C12 |
+ C23 ) = min( ¥,1 + 3) = 4; |
C14 |
= min( C14 ,C12 |
+ C24 ) = min(¥,1 + ¥) = ¥; |
C15 |
= min(C15 , C12 |
+ C25 ) = min( ¥,1 + 6) = 7; |
C16 |
= min( C16 ,C12 |
+ C26 ) = min(5,1 + 2) = 3. |
Найдем элементы матрицы во второй строке матрицы |
||
C21 |
= min(C21 , C22 |
+ C21 ) = min(1,1) = 1; |
C22 |
= 0; |
|
17
C23 = min(C23 ,C22 + C23 ) = min(3,3) = 3;
C24 |
= min(C24 ,C22 |
+ C24 ) = min( ¥, ¥) = ¥; |
C25 |
= min(C25 , C22 |
+ C25 ) = min( 6,6) = 6; |
C26 |
= min(C26 ,C22 |
+ C26 ) = min( 2,2) = 2. |
Для третьей строки найдем |
||
C31 |
= min( C31 ,C32 |
+ C21 ) = min( ¥,3 +1) = 4; |
C32 |
= min(C32 ,C32 |
+ C22 ) = min(3,3) = 3; |
C33 = 0 ; |
|
|
C34 |
= min(C34 ,C32 |
+ C24 ) = min(5,3 + ¥) = 5; |
C35 |
= min(C35 ,C32 |
+ C25 ) = min(1,3 + 6) = 1; |
C36 |
= min(C36 ,C32 |
+ C26 ) = min(3,3 + 2) = 3; |
Для четвертой строки |
||
C41 |
= min(C41 , C42 |
+ C21 ) = min( ¥, ¥ +1) = ¥; |
C42 |
= min(C42 ,C42 |
+ C22 ) = ¥; |
C43 |
= min(C43 ,C42 |
+ C23 ) = min(5, ¥ + 3) = 5; |
C44 |
= 0; |
|
C45 |
= min(C45 , C42 |
+ C25 ) = min(1, ¥ + 6) = 1; |
C46 |
= min(C46 ,C42 |
+ C26 ) = min( ¥, ¥ + 2) = ¥. |
Пятая строка примет вид |
||
C51 |
= min( C51 , C52 |
+ C21 ) = min( ¥,6 +1) = 7; |
C52 |
= min(C52 ,C52 |
+ C22 ) = min( 6,6) = 6; |
C53 |
= min(C53 ,C52 |
+ C23 ) = min(1,6 + 3) = 1; |
C54 |
= min(C54 ,C52 |
+ C24 ) = min(1,6 + ¥) = 1; |
C55 |
= 0; |
|
C56 |
= min(C56 ,C52 |
+ C26 ) = min(3,6 + 2) = 3. |
Элементы шестой строки |
||
C61 |
= min(C61 , C62 |
+ C21 ) = min(5,2 +1) = 3; |
C62 |
= min(C62 , C62 |
+ C22 ) = min( 2,2) = 2; |
C63 |
= min(C63 ,C62 |
+ C23 ) = min(3,2 + 3) = 3; |
18