Графический метод решения ЗЛП

Графическим методом целесообразно решать ЗЛП, содержащие не более двух переменных x₁ и x₂. Данный метод основывается на возможности графического изображения области допустимых решений ЗЛП на листе бумаги. Алгоритм графического метода рассмотрим применительно к задаче.

Пример 6. Фабрика выпускает пряжу двух видов: П1 и П2. Продукция поступает в оптовую продажу. Для производства используется три вида сырья – шерсть, капрон и акрил. Максимально возможные суточные запасы этих материалов составляют 6, 8 и 5 тонн соответственно. Расходы сырья на партию пряжи и оптовые цены приведены в таблице:

Сырьё	Расход сырья на 1 партию пряжи	Запас, тонн
П1	П2
шерсть
капрон
акрил		0,8
оптовая цена партии, тыс.у.е.

Изучение рынка сбыта показало, что суточный спрос на пряжу П2 никогда не превышает спроса на пряжу П1 более чем на одну партию. Кроме того, установлено, что спрос на пряжу П2 никогда не превышает 2 партий.

Какое количество пряжи (в партиях) каждого вида должна производить фабрика, что бы доход от реализации продукции был максимальным?

Решение. Построение математической модели задачи начинается с обозначения переменных: X₁ – суточный объем производства пряжи П1; X₂ - суточный объем производства пряжи П2 в количестве партий.

Целевая функция должна представлять собой доход от продажи пряжи обои видов, произведенной за сутки: f = 3X₁ + 2X₂ тыс. у.е.

Ограничения накладываются на запасы сырья:

расход шерсти на производство пряжи П1 в количестве X₁ партий и пряжи П2 в количестве X₂ партий составит: 1X₁+2X₂ тонн и это количество не должно превысить запаса в 6 тонн. Получаем первое ограничение: X₁+2X₂ 6.

Аналогично накладываются ограничения по капрону: 2Х₁ + Х₂ 8 и акрилу: Х₁+0,8Х₂ 5.

Ограничения на величину спроса на продукцию имеют вид:

-Х₁ + Х₂ 1 (соотношение величины спроса на пряжу П1 и П2);

Х₂ 2 (максимальная величина спроса на пряжу П2).

Вводятся так же условия неотрицательности переменных, т. к. объемы производства не могут быть отрицательными: Х₁ 0, Х₂ 0.

В итоге, получаем следующую математическую модель задачи:

3Х₁ + 2Х₂ (1.16)

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

Х₁ + 2Х₂ 6 (а)

2Х₁ + Х₂ 8 (б)

D: Х₁+0,8Х₂ 5 (в) (1.17)

-Х₁ + Х₂ 1 (г)

Х₂ 2 (д)

Х₁ 0, Х₂ 0 (е)

Поскольку переменных в задаче только две, можно решить её с помощью графического метода.

Шаг 1. Строим область допустимых решений (1.17) - область D, т.е. геометрическое место точек, в котором одновременно удовлетворяются все ограничения ЗЛП. Каждое из неравенств (а)-(д) системы ограничений (1.17) задачи геометрически определяет полуплоскость соответственно с граничными прямыми:

Х₁ + 2Х₂ = 6 (а)

2Х₁ + Х₂= 8 (б)

Х₁+0,8Х₂= 5 (в)

-Х₁ + Х₂= 1 (г)

Х₂= 2 (д)

Каждая из прямых делит координатную плоскость на две полуплоскости. Чтобы определить, какая именно из двух полуплоскостей, ограниченных, например, прямой (а) Х₁ + 2Х₂ = 6, удовлетворяет соответствующему неравенству Х₁ + 2Х₂ 6, подставим в неравенство координаты произвольной точки, не лежащей на граничной прямой, например, координаты точки О(0,0). Если координаты «контрольной» точки удовлетворяют неравенству, то областью его решений является полуплоскость, содержащая эту точку. Если же координаты не удовлетворяют неравенству, то областью его решений является полуплоскость, не содержащая данную точку.

В нашем случае, получаем верное неравенство: 0+2*0 6, следовательно, решением неравенства (а) является полуплоскость, содержащая точку начала координат и лежащая ниже граничной прямой (а).

Условия неотрицательности переменных (е) ограничивают область допустимых решений первой четвертью. Области, в которых выполняются соответствующие ограничения (1.17) в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных (рис. 1.2).

Рис.1.2. Область допустимых решений D

Если система неравенств (1.17) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям.

Полученная таким образом область допустимых решений D - планов ЗЛП (рис. 1.2) есть многоугольник ABCDEF - замкнутое, ограниченное, выпуклое множество с шестью крайними или угловыми точками: A, B, C, D, E, F.

Шаг 2. Строим вектор-градиент линейной формы : . Обозначим его , т.к. частные производные линейной функции совпадают с коэффициентами при соответствующих переменных. В условиях данной задачи . Вектор градиент указывает направление наискорейшего роста функции .

Шаг 3. Строим прямую С₁Х₁ + С₂Х₂ = const - линию уровня функции , перпендикулярную вектору-градиенту :

3Х₁ + 2Х₂ = const (рис.1.3)

Рис.1.3. Вектор - градиент целевой функции и линия уровня

Шаг 4. В случае максимизации передвигают прямую 3Х₁ + 2Х₂ = const в направлении вектора до тех пор, пока она не покинет область D. Крайняя точка (или точки) области, в которой линия уровня покидает допустимую область, и является решением задачи (рис. 1.4).

Рис.1.4. Определение угловой точки области D, являющейся оптимальным решением.

Угловая точка С - точка максимума , С = лежит на пересечении прямых (а) и (б). Для определения ее координат решим систему уравнений:

Х₁ + 2Х₂ = 6

2Х₁ + Х₂ = 8.

Откуда Х^*₁ = 10/3; X^*₂ = 4/3 или = (10/3; 4/3).

Подставляя значения Х^*₁ и X^*₂ в функцию , найдем

max = = 3 ^. 10/3 + 2 ^. 4/3 = 38/3.

Ответ: фабрике необходимо производить пряжи первого вида 3 и 1/3 партий, а второго вида – 1 и 1/3 партий. При этом фабрика получит максимальный доход от реализации всей пряжи 12,67 тыс. у.е.