Дискретная оптимизация - 8 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

8
Шаг 7. Получение допустимого маршрута , возможная смена рекорда и сокра-
щение перебора.
Шаг 8. Проверка критерия оптимальности . Если он выполнен, то останов.
Иначе переход к шагу 6.
Замечание. В момент получения матрицы 2
×
2 определяется замыкающая пара
городов для образования допустимого маршрута .
Пример.
Рассмотрим задачу коммивояжера с
8
=
n
и матрицей расстояний
С =
Положим R=
∞
+
. Осуществив операцию приведения, получаем матрицу
0
C .
0
C =
В последнем столбце и нижней строке записаны приводящие константы . Их
сумма S=10, то есть 10)(
0
=
Ω
ξ
. Для каждого нулевого элемента матрицы
0
C считаем
0
ij
S : ,0
0
71
0
35
0
31
0
17
==== SSSS ,1
0
78
0
76
0
67
0
53
0
45
0
14
====== SSSSSS
,2
0
87
=S 3
0
32
=S , 5
0
23
=S . Имеем
0
23
5}5,3,2,1,0max{ S== . Следовательно ,
)
3
,
2
(
)
,
(
=
r
q
. Формируем множества
1
Ω
и
2
Ω
, добавляя соответственно условия
1
23
=
x и 0
23
=
x . Вычисляем матрицы
1
C и
2
C .
1
C =
+
5 3 2 4 5 2 7
7 +
1 6 7 8 9 6
3 2 +
3 2 4 5 7
4 6 2 +
1 3 6 2
4 5 1 2 +
4 2 3
3 8 9 6 4 +
∞
1 5
1 6 6 4 2 1 +
0
7 8 7 2 8 3 0 +
№
1 2 3 4 5 6
7
8
α
1 +
∞
3 1
0
2 2
0
5 2
2 5 +
0
5 6 6 8 5 1
3
0 0
+
1
0
1 3 5 2
4 2 5 1 +
0 1 5 1 1
5 2 4
0
1 +
2 1 2 1
6 1 7 8 5 3 +
0
4 1
7 0
6 6 4 2
0
+
0
0
8 6 8 7 2 8 2
0
+
0
β
1 0 0 0 0 1 0 0
10
№
1 2 4 5 6 7 8
α
1 +
0 0
2 6
0
5 0
2
0
+
1
0
1 3 5 0
4 2 2 +
0
1 5 1 0
5 1
0 0
+
1
0
1 1
6 1 4 5 3 +
0
4 0
7
0
3 4 2
0
+
0
0
8 6 5 2 8 2
0
+
0
β
0 3 0 0 0 0 0
4 
                                              8
Шаг 7. Получение допустимого маршрута, возможная смена рекорда и сокра-
щение перебора.
Шаг 8. Проверка критерия оптимальности. Если он выполнен, то останов.
Иначе переход к шагу 6.
Замечание. В момент получения матрицы 2 ×2 определяется замыкающая пара
городов для образования допустимого маршрута.

Пример. Рассмотрим задачу коммивояжера с n =8 и матрицей расстояний

        +∞   5       3      2    4     5     2    7
        7    +∞      1      6    7     8     9    6
        3    2       +∞     3    2     4     5    7
        4    6       2      +∞   1     3     6    2
С=      4    5       1      2    +∞    4     2    3
        3    8       9      6    4     +∞    1    5
        1    6       6      4    2     1     +∞   0
        7    8       7      2    8     3     0    +∞

Положим R= +∞ . Осуществив операцию приведения, получаем матрицу C0 .

         №   1       2      3    4     5    6     7     8     α
         1   +∞      3      1    0     2    2     0     5     2
         2   5       +∞     0    5     6    6     8     5     1
         3   0       0      +∞   1     0    1     3     5     2
C0 =     4   2       5      1    +∞    0    1     5     1     1
         5   2       4      0    1     +∞   2     1     2     1
         6   1       7      8    5     3    +∞    0     4     1
         7   0       6      6    4     2    0     +∞    0     0
         8   6       8      7    2     8    2     0     +∞    0
         β   1       0      0    0     0    1     0     0     10


В последнем столбце и нижней строке записаны приводящие константы. Их
сумма S=10, то есть ξ (Ω 0 ) =10 . Для каждого нулевого элемента матрицы
C0 считаем S ij0 :        S170 =S 31
                                  0
                                     =S 35
                                        0
                                           =S 71
                                              0
                                                 =0,   S140 =S 45
                                                               0
                                                                  =S 53
                                                                     0
                                                                        =S 67
                                                                           0
                                                                              =S 76
                                                                                 0
                                                                                    =S 78
                                                                                       0
                                                                                          =1,
S870
      =2,        0
              S 32 =3 , S 23
                          0
                             =5 . Имеем max{0,1,2,3,5} =5 =S 23
                                                             0
                                                                . Следовательно,
( q, r ) =(2,3) . Формируем множества Ω1 и Ω 2 , добавляя соответственно условия
x23 =1 и x23 =0 . Вычисляем матрицы C1 и C2 .
        №    1    2       4      5    6     7     8    α
        1    +∞   0       0      2    6     0     5    0
        2    0    +∞      1      0    1     3     5    0
        4    2    2       +∞     0    1     5     1    0
C1 =    5    1    0       0      +∞   1     0     1    1
        6    1    4       5      3    +∞    0     4    0
        7    0    3       4      2    0     +∞    0    0
        8    6    5       2      8    2     0     +∞   0
        β    0    3       0      0    0     0     0    4

Страницы