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

Задача 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 единиц продукции р₂.