ВУЗ:
Составители:
Рубрика:
137
2) (3,=
∗
x , 12=
∗
f .
11. Метод ветвей и границ
1. Решается задача L
0
:
()
,
2
1
6,0
0
= x ,13
0
=
ξ
−∞=Θ
0
(ветвление из 0-й вершины по
()
0
2
x ). Решается задача L
1
:
()
,6,
4
1
1
= x ,
4
1
12
1
=
ξ
−∞=Θ
1
; задача L
2
не имеет допустимых
решений: −∞=Θ
2
(ветвление из 1-й вершины по
()
1
1
x ). Решаются
задача L
3
:
()
()
,6,0
3
x = ,12
3
=
ξ
;12
3
=Θ задача L
4
:
()
,
2
1
4,1
4
= x
10
4
=
ξ
,
.12
4
=Θ В результате получаем
()
,6,0 x =
∗
.12=
∗
f
2. Решается задача L
0
: ,
5
4
1,
2
1
3
=
(0)
x
5
3
10
0
=
ξ
, −∞=Θ
0
(ветвление из 0-й вершины по
(0)
1
x ). Решаются задача L
1
:
2)(3,
(1)
=x , 10
1
=
î
, 10
1
=Θ ; задача L
2
:
=
5
1
14,
(2)
x , ,
5
2
10
2
=
ξ
10
2
=Θ (ветвление из 2-й вершины по
(2)
2
x ). Решается задача L
3
:
= 1,
6
1
4
(3)
x ,
3
1
10
3
=
ξ
, 10
3
=Θ ; задача L
4
не имеет допустимых
решений: 10
4
=Θ (ветвление из 3-й вершины по
(3)
1
x ). Решаются
задача L
5
: 1)(4,
(5)
=x , 10
5
=
ξ
, 10
5
=Θ ; задача L
6
: 0)(5,
(6)
=x ,
10
6
=
ξ
, 10
6
=Θ . В результате получаем
{}
0)(5,либо1),(4,либо2),(3,=
∗
x , .10=
∗
f
