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

Лабораторная работа №2

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ

Вариант 2

 (ограничение запаса сырья А)                                                                        (8)               [pic 1]

 (ограничение запаса сырья В)                                                                        (9)               [pic 2]

(ограничение соотношения спроса на П1 и П2)                                                (10)[pic 3]

[pic 4]        (ограничение спроса на продукцию П2)                                                            (11)            

 (условие неотрицательности объемов производства  П1 и П2)                 (12)               [pic 5]

Доход от реализации [pic 6] единиц продукции П1 и [pic 7] единиц продукции П2 составит  (целевая функция задачи). Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значение.[pic 8]

Построим многоугольник решений (рис. 1). Для этого в системе координат на плоскости изобразим граничные прямые:

-  (L1);     - (L2); [pic 9][pic 10]

  - (L3); [pic 12] -  (L4).[pic 11]

Взяв какую-либо точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Полуплоскости, определяемые неравенствами, на рис. 1 показаны стрелками. Областью решений является многоугольник OABCD.

Для построения прямой   строим вектор-градиент [pic 14] и через точку О=(0;0) проводим прямую, перпендикулярную ему. Построенную прямую f(X)=0 перемещаем параллельно самой себе в направлении вектора [pic 16]. Из рис. 1 следует, что в точке В  функция принимает максимальное значение. Точка В лежит на пересечении прямых L4 и L1. Для определения ее координат решим систему уравнений:[pic 13][pic 15]

                      [pic 17]

Оптимальное решение задачи [pic 18]= 1,5 , [pic 19]=2. Подставляя значения [pic 20] и [pic 21] в целевую функцию, получим: f(X)=5*1.5 + 3*2=13,5. Полученное решение означает, что объем производства продукции П1 должен быть равен 1,5 ед.,  продукции П2 — 2 ед. Доход, получаемый в этом случае, составит:  f(X)=13,5 д. е.

Определить предельно допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение? На сколько можно снизить запас недефицитного ресурса при сохранении полученного оптимального решения?

 В данном случае сырье A и спрос на продукцию П2 являются дефицитными ресурсами. Рассмотрим ресурс - сырье A. На рис. 2 при увеличении запаса ресурса прямая L1 перемещается вверх, параллельно самой себе, до точки K, в которой пересекаются линии ограничений L2 и L4. В точке K ограничения (9) и (11) становятся связывающими; оптимальному решению при этом соответствует точка К, а пространством (допустимых) решений становится многоугольник АКЕD0. В точке К ограничение (8) (для A) становится избыточным, так как любой дальнейший рост запаса ресурса не влияет ни на пространство решений, ни на оптимальное решение.