Реферат: Применение метода ветвей и границ для задач календарного планирования

III этап. Решаем задачу 2 симплексным методом. Получим Z_max = 14/3 при X₃ ^* = (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X₃ ^* ) = 14/3 > Z₀ = 0, по-прежнему сохраняется Z₀ = 0, ибо план нецелочисленный. Так как х₂ ^* — дробное число, из области решений исключаем полосу 0 < x₂ < 1 и задачу 2 разбиваем на две задачи 4 и 5.

Задача 4

Z=3x₁ +x₂ →max

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

4x_l + Зх₂ < 18

x₁ + 2x₂ £ 6

0 £x₁ £ 4

0 £x₂ £0

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

Задача 5

Z=3x₁ +x₂ →max

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

4x_l + Зх₂ < 18

x₁ + 2x₂ £ 6

0£x₁ £4

1£x₂ £ 4

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

Список задач: 4 и 5. Значение Z₀ = 0.

IV этап. Решаем задачу 4 симплексным методом.

Получим Z_max = 12 при X₄ ^* = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z₀ ; Z₀ = Z(X₄ ^* ) = 12, ибо план Х₄ ^* целочисленный.

V этап. Решаем задачу 5 симплексным методом.

Получим Z_max = 12,25 при X₅ ^* = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z ₀ не меняется, т.е. Z₀ = 12, ибо план X₅ ^* нецелочисленный. Так как х₁ ^* — дробное, из области решений исключаем полосу 3<x₁ <4, и задача 5 разбивается на две задачи: 6 и 7.

Задача 6

Z=3x₁ +x₂ →max

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

4x_l + Зх₂ < 18

x₁ + 2x₂ £ 6

0 £x₁ £ 3

1 £x₂ £ 4

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