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

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

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

Таблица 1.2.1

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

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

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

,

, (1.2.1)

,

.

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

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

Суммарная прибыль F составит 2х₁ руб. от реализации продукции Р₁ и 3х₂ руб. — от реализации продукции Р₂, т.е.

(1.2.3)

Итак, экономико-математическая модель задачи: найти такой план выпуска продукции Х = (х₁, х₂), удовлетворяющий системе (1.2.1) и условию (1.2.2), при котором функция (1.2.3) принимает максимальное значение:

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

(I)

(II)

(III)

(IV)

х₁³0, х₂³0 (V,VI)

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

Рис. 1.2.1

Очевидно, что при F=0 линия уровня 2х₁+3х₂=0 проходит через начало координат (строить ее не обязательно). Зададим, например, F = 6 и построим линию уровня 2х₁ + 3х₂ = 6. Ее расположение указывает на направление возрастания линейной функции (вектор ). Так как рассматриваемая задача — на отыскание максимума, то оптимальное решение — в угловой точке С, находящейся на пересечении прямых I и II, т.е. координаты точки С определяются решением системы уравнений

,

,

откуда х₁ =6, х₂ = 4, т.е. С (6;4).

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

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