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

*=13,5,Х1*=(3;0,5;0;1;0;2,5).

Приложение 2

Решение задачи z = 4х1 + х2 +1 ® max при ограничениях:

с помощью табличного процессора Microsoft Excel.

Приложение 3

В качестве примера применения метода ветвей и границ приведем поиск оптимального значения функции Z = Зх1 + х2 ® max при ограничениях:

xl + Зх2 < 18,

x1 + 2x2 £ 6,

£ x1 £ 5,

£ x2 £ 4,

х1, x2 - целые числа.

Решение

За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. Z0 = Z (0; 0) = 0.этап. Решая задачу симплекс-методом, получим Zmax = 13,5 при Х1* = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента х1* дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение х1*, т.е. 4 < х1 < 5. Поэтому задача 1 разбивается на две задачи 2 и 3.

Задача 2

Z=3x1+x2→max

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

xl + Зх2 < 18

x1 + 2x2 £ 6

£ x1 £ 4

£ x2 £ 4

х1, x2 - целые числа.

Задача 3

Z=3x1+x2→max

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

xl + Зх2 < 18

x1 + 2x2 £ 6

£ x1 £ 5

£ x2 £ 4

х1, x2 - целые числа.

Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z0= 0.этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплекс-методом.

Получим, что условия задачи 3 противоречивы.этап. Решаем задачу 2 симплекс-методом. Получим Zmax = 12 2/3 при X3*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X3*) = 12 2/3 > Z0 = 0, по-прежнему сохраняется Z0 = 0, ибо план нецелочисленный. Так как х2* - дробное число, из области решений исключаем полосу 0 < x2 < 1 и задачу 2 разбиваем на две задачи 4 и 5.

Задача 4

Z=3x1+x2→max

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

xl + Зх2 < 18

x1 + 2x2 £ 6

£ x1 £ 4

£ x2 £ 0

х1, x2 - целые числа.

Задача 5

Z=3x1+x2→max

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

xl + Зх2 < 18

x1 + 2x2 £ 6

£ x1 £ 4

£ x2 £ 4

х1, x2 - целые числа.

Список задач: 4 и 5. Значение Z0 = 0.этап. Решаем задачу 4 симплекс-методом.

Получим Zmax = 12 при X4* = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z0; Z0 = Z(X4*) = 12, ибо план Х4* целочисленный.этап. Решаем задачу 5 симплекс-методом.

Получим Zmax = 12,25 при X5* = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z 0 не меняется, т.е. Z0 = 12, ибо план X5* нецелочисленный. Так как х1* - дробное, из области решений исключаем полосу 3<x1<4, и задача 5 разбивается на две задачи: 6 и 7.

Задача 6

Z=3x1+x2→max

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

xl + Зх2 < 18

x1 + 2x2 £ 6

£ x1 £ 3

£ x2 £ 4

х1, x2 - целые числа.

Задача 7

Z=3x1+x2→max

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

xl + Зх2 < 18

x1 + 2x2 £ 6

£ x1 £ 4

£ x2 £ 4

х1, x2 - целые числа.

Список задач: 6 и 7. Значение Z0 = 12.этап. Решаем одну из задач списка, например задачу 7, симплекс-методом. Получим, что условия задачи 7 противоречивы.этап. Решаем задачу 6 симплекс-методом. Получим Zmax = 10,5 ,при X6* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как, Z(X6*) = 10,5 < Z0 = 12, то задача исключается из списка.

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