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

                                              14
Решаем оценочные задачи на множествах Ω 5 и Ω 6 . Получаем x 5 =(3,2) ,
ξ (Ω 5 ) =ϕ ( x 5 ) =−5 , Ω 6 = Ø.
Получено целочисленное решение. Происходит смена рекорда R=-5. Множест-
ва Ω 6 , Ω 4 и Ω 2 выбрасываем из рассмотрения как неперспективные (их оценки
превышают или равны рекордному значению).
Так как перспективных множеств для ветвления не осталось, то останов, полу-
чено оптимальное решение: x min =(3,2) , ϕ min =−5 .
Дерево вариантов в данной задаче имеет вид:

                                                             -7
                                                   x1 ≤4          x1 ≥5

                                             -6                            +∞
                                   x2 ≤2             x2 ≥3

                              -5                     -5
                      x1 ≤3          x1 ≥4

                       -5            +∞




                                   УПРАЖНЕНИЯ

1. Покажите, что любая задача целочисленного программирования может быть
эквивалентно переписана как задача с булевыми переменными.
2. Пользуясь определением оценки докажите, что задача с отброшенным усло-
вием целочисленности является оценочной к исходной.
3. Решить ЦЗЛП:
a) −2 x1 −3 x2 → min       b) −3 x1 −4 x2 → min       c) −x1 −4 x2 → min
  −x1 +3x2 ≤11,                    −x1 +5 x2 ≤15,                         −x1 +2 x2 ≤10,
  2 x1 +2 x2 ≤13,                  x1 +x2 ≤11 13 ,                        x1 +x2 ≤7 12 ,
  2 x1 −x2 ≤11,                    2 x1 −x2 ≤10,                          2 x1 −x2 ≤10,
   x1 , x2 ≥0, x1 , x2 ∈Ζ          x1 , x2 ≥0, x1 , x2 ∈Ζ                 x1 , x2 ≥0, x1 , x2 ∈Ζ
Ответ: x min =(2,4)            Ответ: x min =(7,4)                   Ответ: x min =(2,5)