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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

11
талось, то найденная точка является оптимальным решением . Однако оно мо-
жет быть не единственным, так как подмножества
74
,
Ω
Ω
так же имеют оценку
16. Чтобы выяснить, существуют ли другие решения, нужно осуществлять
дальнейшее ветвление этих множеств .
Дерево вариантов в рассмотренном примере имеет вид
1
23
=
x 0
23
=
x
1
87
=
x
0
87
=
x
1
32
=
x
0
32
=
x
1
61
=
x 0
61
=
x 1
87
=
x 0
87
=
x
1
76
=
x 0
76
=
x
1
35
=
x 0
35
=
x
УПРАЖНЕНИЯ
1. Предложите другие стратегии ветвления в задаче коммивояжера.
2. Решите задачу коммивояжера с матрицей :
a) b)
С= C= C=
Ответ: 1-4-6-7-3-5-2-1, L=126. Ответ: 4-3-5-6-2-1-4, L=63.
c) d)
С= С= С= С=
Ответ: 3-1-6-5-4-2-3, L=39. Ответ: 2-1-5-3-4-6-2, L=26.
+
∞
3 93 13 33 9 57
4 +
∞
77 42 21 16 34
45 17 +
∞
36 16 28 25
39 90 80 +
∞
56 7 91
28 46 88 33 +
∞
25 57
3 88 18 46 92 +
∞
7
44 26 33 27 84 39 +
∞
+
∞
14 9 8 10 6
10 +
∞
7 4 11 5
11 10 +
∞
10 20 11
12 4 4 +
∞
9 4
13 10 9 7 +
∞
10
11 9 8 3 4 +
∞
+
∞
4 10 13 4 8
2 +
∞
9 7 6 7
8 5 +
∞
5 5 9
5 8 5 +
∞
7 10
6 4 4 9 +
∞
4
5 1 4 8 3 +
∞
+
∞
27 43 16 30 26
7 +
∞
16 1 30 25
20 13 +
∞
35 5 0
21 16 25 +
∞
18 18
12 46 27 48 +
∞
5
23 5 5 9 5 +
∞
10
14
15
16
16
15
18
16
18
16
17
16
19
16
17
                                                         11
талось, то найденная точка является оптимальным решением. Однако оно мо-
жет быть не единственным, так как подмножества Ω 4 ,Ω 7 так же имеют оценку
16. Чтобы выяснить, существуют ли другие решения, нужно осуществлять
дальнейшее ветвление этих множеств.
Дерево вариантов в рассмотренном примере имеет вид


                                                               x23 =1         10     x23 =0

                                                       14                                     15
                                           x87 =1              x87 =0                x32 =1            x32 =0

                                      16                       16                     15                18
                         x61 =1               x61 =0                      x87 =1              x87 =0

                         16                   18                         16                   17
              x76 =1               x76 =0

               16                   19
     x35 =1            x35 =0

       16                17


                                            УПРАЖНЕНИЯ

1. Предложите другие стратегии ветвления в задаче коммивояжера.
2. Решите задачу коммивояжера с матрицей:
a)                                        b)
       +∞     3     93        13    33      9       57                         +∞      27      43      16    30   26
       4      +∞    77        42    21      16      34                         7       +∞      16      1     30   25
С=     45     17    +∞        36    16      28      25        C= C=            20      13      +∞      35    5    0
       39     90    80        +∞    56      7       91                         21      16      25      +∞    18   18
       28     46    88        33    +∞      25      57                         12      46      27      48    +∞   5
       3      88    18        46    92      +∞      7                          23      5       5       9     5    +∞
       44     26    33        27    84      39      +∞

        Ответ: 1-4-6-7-3-5-2-1, L=126.                                             Ответ: 4-3-5-6-2-1-4, L=63.
c)                                                                  d)
      +∞      14    9     8        10       6                                  +∞      4       10      13    4    8
      10      +∞    7     4        11       5                                  2       +∞      9       7     6    7
С=    11      10    +∞    10       20       11
                                               С= С=                 С=        8       5       +∞      5     5    9
      12      4     4     +∞       9        4                                  5       8       5       +∞    7    10
      13      10    9     7        +∞       10                                 6       4       4       9     +∞   4
      11      9     8     3        4        +∞                                 5       1       4       8     3    +∞

        Ответ: 3-1-6-5-4-2-3, L=39.                                                Ответ: 2-1-5-3-4-6-2, L=26.

Страницы