ВУЗ:
Составители:
Рубрика:
10
5
C =
6
C =
Вычисляем оценки: 15015)(
5
=
+
=
Ω
ξ
, 18315)(
6
=
+
=
Ω
ξ
. Дальнейшему ветв -
лению подлежит множество
5
Ω
.
Делим
5
Ω
на подмножества
7
Ω
и
8
Ω
по паре
)
7
,
8
(
)
,
(
=
r
q
. Рассчитав матрицы
7
C
и
8
C , определяем
16115)(
7
=
+
=
Ω
ξ
,
17215)(
8
=
+
=
Ω
ξ
. Минимальную
оценку 16 имеет три подмножества:
43
,
Ω
Ω
и
7
Ω
.
Выберем для дальнейшего ветвления
3
Ω
. Делим его на подмножества
9
Ω
и
10
Ω
по паре
)
1
,
6
(
)
,
(
=
r
q
. Получим 16)(
9
=
Ω
ξ
, 18)(
10
=
Ω
ξ
.
Далее делим
9
Ω
на подмножества
11
Ω
и
12
Ω
по паре
)
6
,
7
(
)
,
(
=
r
q
. Вычисляем
16)(
11
=
Ω
ξ
, 19)(
12
=
Ω
ξ
.
Делим
11
Ω
по паре
)
5
,
3
(
)
,
(
=
r
q
на
13
Ω
и
14
Ω
. При этом получаем матрицу
13
C
размера 2
×
2. В результате выписываем допустимую точку
=
)(
ij
x
со значением целевой функции
16
=
L
.
Соответствующий маршрут: 1-2-3-5-4-8-7-5-1
Меняем рекорд:
16
=
R
, и подмножества
1412108764
,,,,,,
Ω
Ω
Ω
Ω
Ω
Ω
Ω
выбрасы -
ваются из рассмотрения как неперспективные (их оценки превышают или рав-
ны рекордному значению ). Так как больше подмножеств для ветвления не ос-
№
1 3 4 5 6
7
8
α
1 +
∞
1
0
2 2
0
5 0
2
0
+
∞
0
1 1 3
0
0
4 2 1 +
∞
0
1 5 1 0
5 2
0
1 +
∞
2 1 2 0
6 1 8 5 3 +
∞
0
4 0
7 0
6 4 2
0
+
∞
0
0
8 6 7 2 8 2
0
+
∞
0
β
0 0 0 0 0 0 0
0
№
1 2 3 4 5 6
7
8
α
1 +
∞
0
1
0
2 2
0
5 0
2
0
+
∞
+
∞
0
1 1 3
0
5
3
0
+
∞
+
∞
1
0
1 3 5 0
4 2 2 1 +
∞
0
1 5 1 0
5 2 1
0
1 +
∞
2 1 2 0
6 1 4 8 5 3 +
∞
0
4 0
7 0
3 6 4 2
0
+
∞
0
0
8 6 5 7 2 8 2
0
+
∞
0
β
0 3 0 0 0 0 0 0
3
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
10
№ 1 3 4 5 6 7 8 α
1 +∞ 1 0 2 2 0 5 0
2 0 +∞ 0 1 1 3 0 0
4 2 1 +∞ 0 1 5 1 0
C5 = 5 2 0 1 +∞ 2 1 2 0
6 1 8 5 3 +∞ 0 4 0
7 0 6 4 2 0 +∞ 0 0
8 6 7 2 8 2 0 +∞ 0
β 0 0 0 0 0 0 0 0
№ 1 2 3 4 5 6 7 8 α
1 +∞ 0 1 0 2 2 0 5 0
2 0 +∞ +∞ 0 1 1 3 0 5
3 0 +∞ +∞ 1 0 1 3 5 0
C6 = 4 2 2 1 +∞ 0 1 5 1 0
5 2 1 0 1 +∞ 2 1 2 0
6 1 4 8 5 3 +∞ 0 4 0
7 0 3 6 4 2 0 +∞ 0 0
8 6 5 7 2 8 2 0 +∞ 0
β 0 3 0 0 0 0 0 0 3
Вычисляем оценки: ξ (Ω 5 ) =15 +0 =15 , ξ (Ω 6 ) =15 +3 =18 . Дальнейшему ветв-
лению подлежит множество Ω 5 .
Делим Ω 5 на подмножества Ω 7 и Ω 8 по паре ( q, r ) =(8,7) . Рассчитав матрицы
C7 и C8 , определяем ξ (Ω 7 ) =15 +1 =16 , ξ (Ω 8 ) =15 +2 =17 . Минимальную
оценку 16 имеет три подмножества: Ω 3 ,Ω 4 и Ω7 .
Выберем для дальнейшего ветвления Ω 3 . Делим его на подмножества Ω 9 и Ω10
по паре ( q, r ) =(6,1) . Получим ξ (Ω 9 ) =16 , ξ (Ω10 ) =18 .
Далее делим Ω 9 на подмножества Ω11 и Ω12 по паре ( q, r ) =(7,6) . Вычисляем
ξ (Ω11 ) =16 , ξ (Ω12 ) =19 .
Делим Ω11 по паре ( q, r ) =(3,5) на Ω13 и Ω14 . При этом получаем матрицу C13
размера 2 ×2. В результате выписываем допустимую точку
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
( xij ) = со значением целевой функции L =16 .
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
Соответствующий маршрут: 1-2-3-5-4-8-7-5-1
Меняем рекорд: R =16 , и подмножества Ω 4 , Ω 6 , Ω 7 , Ω 8 , Ω10 , Ω12 , Ω14 выбрасы-
ваются из рассмотрения как неперспективные (их оценки превышают или рав-
ны рекордному значению). Так как больше подмножеств для ветвления не ос-
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
