Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


При помощи метода Гомори можно добиться целочисленности всех переменных задачи, т.е. произвести полное отсечение.


В приведенном примере достаточно добиться целочисленности переменных x1 и x2, поэтому совершим неполное отсечение.


Условие отсечения для k строки базиса:


[akl} xi + Н2} Х2 + … + {akn} xn > {xk},    (29)


где {xk} > 0, {xk} = Xk — entire(xk); entire(xk) € Z; entire(xk) < Xk.


Для этого составим условие отсечения по первой и второй строкам, соответствующим нецелочисленным базисным переменным x1= /14 и x2=    /14.


Можно составить условие отсечения сразу по двум строкам, однако на практике для упрощения вычислений строят отсечения последовательно для каждого компонента базиса, начиная с того компонента, у которого большая дробная часть.


В рассматриваемом примере дробные части нецелочисленных базисных переменных таковы:


{x1} = С/м} = 4/14,


{x2}    =    {2000/14}    = 12/14 .


Построим отсечение по второй строке, соответствующей переменной x2 с наибольшей дробной частью:


{1} x1 + {0} x2 + {-2} x3 + {-12/14} x4 + {5/14} x5 + {0} x6 > {2000/14},


0x +    0*x2 +    0’x3 +    2/14 x4 +    5/14 x5 +    0-x6    > 12/14,


/14 x4 +    /14 x5    > /14.


Полученное отсечение (29) добавим к системе ограничений задачи. Получим новую задачу линейного программирования:


max(40x1 + 30x2 + 35x3),


x1    — 2x3 + 10/14 x43/14 x5    = 200/14,


x2 + 4×3 — 12/14 x4 + 5/14 x5    = 200°/14,


2×3 — 20/14 x4 — 1/14 x5 + x6 = 1000/14 ,


/14 x4 + /14 x5    > /14; x1-6 > °.

Скачать в pdf «Экстремальные модели менеджмента и экономики»