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

Задача 1. (об использовании ресурсов).

Для изготовления двух видов продукции р₁ и р₂ используют четыре вида ресурсов s₁, s₂, s₃, s₄. запасы ресурсов, затрачиваемых на производство единицы продукции, приведены в таблице 1.

Таблица 1

Прибыль, получаемая от единицы продукции р₁ и р₂ – соответственно 2 и 3 руб. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Геометрический метод решения.Составим экономико-математическую модель задачи. Обозначим - число единиц продукции соответственно и , запланированных к производству. Для их изготовления потребуется единиц ресурса , единиц ресурса s₂, единиц ресурса и единиц ресурса . Так как потребление ресурсов s₁, s₂, s₃, s₄ не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

,

, (4)

,

.

по смыслу задачи переменные

х₁³0, х₂³0 (5)

суммарная прибыль f составит руб. от реализации продукции и руб. - от реализации продукции р₂, т.е.

(6)

итак, экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (4) и условию (5), при котором функция (6) принимает максимальное значение:

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

(i)

(ii)

(iii)

(iv)

(v,vi)

Изобразим многоугольник решений на рис. 1

Рис. 1.

Очевидно, что при линия уровня проходит через начало координат (строить ее не обязательно). Зададим, например, и построим линию уровня . Ее расположение указывает на направление возрастания линейной функции (вектор ). Так как рассматриваемая задача - на отыскание максимума, то оптимальное решение - в угловой точке с, находящейся на пересечении прямых i и ii, т.е. координаты точки с определяются решением системы уравнений

откуда , т.е. С (6;4).

Максимум (максимальное значение) линейной функции равен .

Итак, при оптимальном решении , т.е. максимальная прибыль в 24 руб. может быть достигнyта при производстве 6 единиц продукции р₁ и 4 единиц продукции р₂.