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

0 £x₂ £ 4

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

Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z₀ = 0.

II этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплекс-методом.

Получим, что условия задачи 3 противоречивы.

III этап. Решаем задачу 2 симплекс-методом. Получим Z_max = 12 2/3 при X₃ ^* = (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X₃ ^* ) = 12 2/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 симплекс-методом.

Получим Zmax = 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