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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

13
7
7
.
x
0
(2)
(1)
(3)
5
x
2
x
1
Шаг 2. Решение оценочной задачи на множестве
0
Ω
. Если полученная точка
0
x
целочисленная, то решение найдено . Останов.
Шаг 3. Выбор индекса
j
, такого что координата
j
k
x - не целая .
Шаг 4. Ветвление
21
kkk
Ω
∪
Ω
=
Ω
.
Шаг 5. Решение оценочных задач линейного программирования и вычисление
оценок )(
2
k
Ω
ξ
и )(
1
k
Ω
ξ
. Если какая- то из полученных оптимальных точек це-
лочисленная , то переход к шагу 7.
Шаг 6. Выбор перспективного множества
s
Ω
в соответствии со стратегией .
Положить
.
s
k
=
Переход к шагу 2.
Шаг 7. Возможная смена рекорда и сокращение перебора за счет отбрасывания
неперспективных множеств .
Шаг 8. Проверка критерия оптимальности . Если он выполнен , останов. Иначе
переход к шагу 6.
Пример.
Ζ∈≥
≤−
≤+
≤+
Ω
→
−
−
.,,0,
)3(,554
)2(,7
)1(,38112
min
2121
21
21
21
0
21
xxxx
xx
xx
xx
xx
Полагаем R=
∞
+
.
Решаем исходную задачу без требования целочисленности . Графическая иллю -
страция решения приведена на рисунке. Оптимальной точкой является
)2,4(
9
5
9
4
0
=x
, 7)()(
0
0
−==Ω x ϕξ .
Так как точка не целочисленная , осуществляем ветвление (например, по пер-
вой координате ): ,
210
Ω
∪
Ω
=
Ω
}4,{
101
≤
Ω
∈
=
Ω
xx , }5,{
102
≥
Ω
∈
=
Ω
xx .
Решаем две задачи линейного программирования , заключающиеся в миними-
зации функции
)
(
x
ϕ
на множествах
1
Ω
и
2
Ω
без требования целочисленности .
Получаем
)2,4(
11
8
1
=x
,
6)(
1
−
=
Ω
ξ
,
=
Ω
2
Ø . Полагаем
+∞
=
Ω
)(
2
ξ
.
Так как целочисленного решения опять не получено , осуществляем ветвления
множества
1
Ω
:
}2,{
213
≤
Ω
∈
=
Ω
xx
,
}3,{
214
≥
Ω
∈
=
Ω
xx
.
Решаем оценочные задачи на множествах
3
Ω
и
4
Ω
. Получаем )2,3(
4
3
3
=x ,
5)(
3
−
=
Ω
ξ
,
)3,2(
2
1
4
=x
, 5)(
4
−
=
Ω
ξ
.
Воспользуемся стратегией одностороннего обхода и выберем для дальнейшего
ветвления множество
3
Ω
. Получим : ,
653
Ω
∪
Ω
=
Ω
}3,{
135
≤
Ω
∈
=
Ω
xx ,
}4,{
136
≥
Ω
∈
=
Ω
xx . 
                                           13
Шаг 2. Решение оценочной задачи на множестве Ω 0 . Если полученная точка
x 0 целочисленная, то решение найдено. Останов.
Шаг 3. Выбор индекса j , такого что координата xkj - не целая.
Шаг 4. Ветвление Ω k =Ω k1 ∪ Ω k2 .
Шаг 5. Решение оценочных задач линейного программирования и вычисление
оценок ξ (Ω k2 ) и ξ (Ω k1 ) . Если какая-то из полученных оптимальных точек це-
лочисленная, то переход к шагу 7.
Шаг 6. Выбор перспективного множества Ω s в соответствии со стратегией.
Положить k =s. Переход к шагу 2.
Шаг 7. Возможная смена рекорда и сокращение перебора за счет отбрасывания
неперспективных множеств.
Шаг 8. Проверка критерия оптимальности. Если он выполнен, останов. Иначе
переход к шагу 6.
                                                 x2
Пример.
                                              7 (2)
       −x1 −x2 → min
    � 2 x1 +11x2 ≤38, (1)                                            (3)

Ω0 �
     � x +x ≤7,
      � 1   2

    � 4 x1 −5 x2 ≤5,
                      ( 2)
                             (3)
                                                3
                                                               .   x0      (1)

     �� x1 , x2 ≥0, x1 , x2 ∈Ζ.
                                                                                 x1
                                                              5     7
Полагаем R= +∞ .
Решаем исходную задачу без требования целочисленности. Графическая иллю-
страция решения приведена на рисунке. Оптимальной точкой является
x 0 =(4 94 ,2 95 ) , ξ (Ω 0 ) =ϕ ( x 0 ) =−7 .
Так как точка не целочисленная, осуществляем ветвление (например, по пер-
вой координате): Ω 0 =Ω1 ∪ Ω 2 , Ω1 ={x ∈Ω 0 , x1 ≤4} , Ω 2 ={x ∈Ω 0 , x1 ≥5} .
Решаем две задачи линейного программирования, заключающиеся в миними-
зации функции ϕ (x) на множествах Ω1 и Ω 2 без требования целочисленности.
Получаем x1 =( 4,2 118 ) , ξ (Ω1 ) =−6 , Ω 2 = Ø. Полагаем ξ (Ω 2 ) =+∞ .
Так как целочисленного решения опять не получено, осуществляем ветвления
множества Ω1 : Ω 3 ={x ∈Ω1 , x2 ≤2} , Ω 4 ={x ∈Ω1 , x2 ≥3} .
Решаем оценочные задачи на множествах Ω 3 и Ω 4 . Получаем x 3 =(3 34 ,2) ,
ξ (Ω 3 ) =−5 , x 4 =(2 12 ,3) , ξ (Ω 4 ) =−5 .
Воспользуемся стратегией одностороннего обхода и выберем для дальнейшего
ветвления множество                Ω 3 . Получим: Ω 3 =Ω 5 ∪ Ω 6 , Ω 5 ={x ∈Ω 3 , x1 ≤3} ,
Ω 6 ={x ∈Ω 3 , x1 ≥4} .

Страницы