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

--PAGE_BREAK--Решить задачу
Z = Зх1 + х2 — max

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

<img width=«23» height=«158» src=«ref-1_253595425-569.coolpic» v:shapes="_x0000_s1034">4xl + Зх2 < 18,

x1+ 2x2£6,

0 £x1£5,

0 £x2£4,

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

Решение. За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. Z= Z(0; 0) = 0.

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










--PAGE_BREAK--