ВУЗ:
Составители:
Рубрика:
9
2
C
=
Считаем оценки:
14410)(
1
=
+
=
Ω
ξ
,
15510)(
2
=
+
=
Ω
ξ
.
Выберем стратегию “по минимуму оценки” . В таком случае дальнейшему ветв -
лению подлежит множество
1
Ω
. Для каждого нулевого элемента матрицы
1
C считаем
1
ij
S : ,0
1
78
1
71
1
57
1
54
1
52
1
25
1
21
1
17
1
14
1
12
========== SSSSSSSSSS
,1
1
78
1
76
1
67
1
45
==== SSSS ,2
87
=
S . Имеем
1
87
2}2,1,0max{ S== . Следовательно ,
)
7
,
8
(
)
,
(
=
r
q
.
Формируем множества
3
Ω
и
4
Ω
, добавляя соответственно условия 1
87
=
x и
0
87
=
x . Вычисляем матрицы
3
C и
4
C .
3
C =
4
C =
Вычисляем оценки: 16214)(
3
=
+
=
Ω
ξ
, 16214)(
4
=
+
=
Ω
ξ
.
В соответствии со стратегией дальнейшему ветвлению подлежит множество
2
Ω
, так как оно имеет наименьшую оценку 15)(
2
=
Ω
ξ
. Аналогично для всех
нулевых элементов матрицы
2
C считаем
2
ij
S и определяем , что
)
2
,
3
(
)
,
(
=
r
q
.
Формируем множества
5
Ω
и
6
Ω
, добавляя соответственно условия
1
32
=
x
и
0
32
=
x . Матрицы
5
C и
6
C имеют вид:
№
1 2 3 4 5 6
7
8
α
1 +
∞
3 1
0
2 2
0
5 0
2
0
+
∞
+
∞
0
1 1 3
0
5
3
0 0
+
∞
1
0
1 3 5 0
4 2 5 1 +
∞
0
1 5 1 0
5 2 4
0
1 +
∞
2 1 2 0
6 1 7 8 5 3 +
∞
0
4 0
7 0
6 6 4 2
0
+
∞
0
0
8 6 8 7 2 8 2
0
+
∞
0
β
0 0 0 0 0 0 0 0
5
№
1 2 4 5 6 8
α
1 +
∞
0 0
2 2 4 0
2
0
+
∞
1
0
1 4 0
4 2 2 +
∞
0
1
0
0
5 1
0 0
+
∞
1
0
0
6
0
3 4 2 +
∞
2 1
7
0
3 4 2
0
+
∞
0
β
0 0 0 0 0 1
2
№
1 2 4 5 6 7 8
α
1 +
∞
0 0
2 2
0
5 0
3
0
+
∞
1
0
1 3 5 0
4 2 2 +
∞
0
1 5 1 0
5 1
0 0
+
∞
1
0
1 0
6 1 4 5 3 +
∞
0
4 0
7
0
3 4 2
0
+
∞
0
0
8 4 3
0
6
0
+
∞
+
∞
2
β
0 0 0 0 0 0 0
2
9
№ 1 2 3 4 5 6 7 8 α
1 +∞ 3 1 0 2 2 0 5 0
2 0 +∞ +∞ 0 1 1 3 0 5
3 0 0 +∞ 1 0 1 3 5 0
C2 = 4 2 5 1 +∞ 0 1 5 1 0
5 2 4 0 1 +∞ 2 1 2 0
6 1 7 8 5 3 +∞ 0 4 0
7 0 6 6 4 2 0 +∞ 0 0
8 6 8 7 2 8 2 0 +∞ 0
β 0 0 0 0 0 0 0 0 5
Считаем оценки: ξ (Ω1 ) =10 +4 =14 , ξ (Ω 2 ) =10 +5 =15 .
Выберем стратегию “по минимуму оценки”. В таком случае дальнейшему ветв-
лению подлежит множество Ω1 . Для каждого нулевого элемента матрицы
C1 считаем S ij1 : 1
S12 =S14
1
=S17
1
=S 21
1
=S 25
1
=S 52
1
=S 54
1
=S 57
1
=S 71
1
=S 78
1
=0,
1
S 45 =S 67
1
=S 761
=S 78
1
=1, S87 =2, . Имеем max{0,1,2} =2 =S 87
1
. Следовательно,
( q, r ) =(8,7) .
Формируем множества Ω 3 и Ω 4 , добавляя соответственно условия x87 =1 и
x87 =0 . Вычисляем матрицы C3 и C 4 .
№ 1 2 4 5 6 8 α
1 +∞ 0 0 2 2 4 0
C3 = 2 0 +∞ 1 0 1 4 0
4 2 2 +∞ 0 1 0 0
5 1 0 0 +∞ 1 0 0
6 0 3 4 2 +∞ 2 1
7 0 3 4 2 0 +∞ 0
β 0 0 0 0 0 1 2
№ 1 2 4 5 6 7 8 α
1 +∞ 0 0 2 2 0 5 0
3 0 +∞ 1 0 1 3 5 0
4 2 2 +∞ 0 1 5 1 0
C4 = 5 1 0 0 +∞ 1 0 1 0
6 1 4 5 3 +∞ 0 4 0
7 0 3 4 2 0 +∞ 0 0
8 4 3 0 6 0 +∞ +∞ 2
β 0 0 0 0 0 0 0 2
Вычисляем оценки: ξ (Ω 3 ) =14 +2 =16 , ξ (Ω 4 ) =14 +2 =16 .
В соответствии со стратегией дальнейшему ветвлению подлежит множество
Ω 2 , так как оно имеет наименьшую оценку ξ (Ω 2 ) =15 . Аналогично для всех
нулевых элементов матрицы C2 считаем S ij2 и определяем, что ( q, r ) =(3,2) .
Формируем множества Ω 5 и Ω 6 , добавляя соответственно условия x32 =1 и
x32 =0 . Матрицы C5 и C6 имеют вид:
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
