Курсовая работа: Применение метода ветвей и границ для задач календарного планирования

4x_l + Зх₂ < 18

x₁ + 2x₂ £ 6

0 £x₁ £ 3

1 £x₂ £ 4

х₁ , x₂ — целые числа.

Задача 7

Z=3x₁ +x₂ →max

при ограничениях:

4x_l + Зх₂ < 18

x₁ + 2x₂ £ 6

4 £x₁ £ 4

1 £x₂ £ 4

х₁ , x₂ — целые числа.

Список задач: 6 и 7. Значение Z₀ = 12.

VI этап. Решаем одну из задач списка, например задачу 7, симплекс-методом. Получим, что условия задачи 7 противоречивы.

VII этап. Решаем задачу 6 симплекс-методом. Получим Z_{m a x} = 10,5 ,при X₆ ^* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как, Z(X₆ ^* ) = 10,5 < Z₀ = 12, то задача исключается из списка.

Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет X^* = Х₄ ^* = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Z_max = 12.

[1] «Оптимальным» будем называть план, оптимальный на данный момент решения.

[2] Естественно, без введения и вычисления переменных искусственного базиса.

[3] «о трех станкак».