§3. Как распорядиться запасами сырья: произвести из него продукцию или выгодно продать? Двойственные задачи линейного программирования

Начнем с рассмотрения очень простых задач А₁ и А₂.

З а д а ч а А₁. Имеется 200 единиц сырья. Из него можно изготавливать некоторые детали. Пусть для изготовления одной детали требуется 5 единиц сырья. Детали реализуются по цене 7 условных единиц. Требуется определить, сколько деталей можно изготовить из сырья и какова будет стоимость всей реализованной продукции.

Р е ш е н и е. Хотя эта задача решается устно и без всякой теории линейного программирования, мы решим ее «по науке».

Обозначим через x₁ число изготовляемых деталей, b₁ = 200 – количество сырья, a₁ = 5 – затраты сырья на изготовление одной детали,

c₁ = 7 - цена реализации готового изделия.

Получаем задачу ЛП стандартной формы:

,

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

Решим задачу графически:

Вектор здесь имеет одну координату, т.е. является просто числом на оси (Ох₁).

Точка максимума х₁ = 40

.

О т в е т: ,.

Рассмотрим теперь другую задачу, связанную с задачей А₁.

З а д а ч а В₁: Пусть в условиях задачи А сырье решено продать. По какой минимальной цене следует продавать сырье, чтобы продавать его было выгоднее, чем производить из него продукцию?

Р е ш е н и е: Введем обозначения: у₁ – цена единицы сырья. Будем также использовать обозначения задачи А₁.

Цена у₁ ≥ 0 и должна удовлетворять соотношению 5у₁ ≥ 7, так как сырье, нужное для изготовления детали, должно стоить не менее самой детали. Ограничениям у₁ ≥ 0 и 5у₁ ≥ 7 удовлетворяют все достаточно большие значения цены у₁. Нас интересуют такая цена, при которой будет минимальная выручка от продажи сырья g(у₁) = 200 у₁ (→ min). Получили задачу ЛП стандартной формы.

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

Решим задачу B₁ графически:

Точка минимума .

Вектор нормали целевой функции – число. Область допустимых плановD_y: .

.

О т в е т: ;.

Обратите внимание на равенство:

.

Это не случайное совпадение!

Итак, сырье следует продавать по цене 1,4 ден. eд.

Задачи А₁ и В₁ приоткрывают дверь в страну, которая носит название теории двойственности в линейном программировании. Знание этой теории будет полезно тем, кто хочет разобраться в таких экономических понятиях, как цена, стоимость и т.д. Однако следует заметить, что цена у₁ здесь есть некоторая мера ценности единицы сырья с точки зрения данного производства.

Рассмотрим теперь более содержательные задачи.

З а д а ч а А₂: Имеется два вида сырья S₁ и S₂ в количествах 800 и 140 единиц соответственно. Из этого сырья можно изготовить три вида продукции: Р₁, Р₂ и Р₃. Затраты сырья на изготовление одной единицы продукции даны в таблице:

Продукция	Р1	Р2	Р3
Сырье
S1	4	2	5
S2	2	6	5

Цена реализации готовых изделий Р₁, Р₂ и Р₃соответственно 8, 14 и 10 денежных единиц. Требуется найти оптимальный план производства продукции из имеющегося сырья.

Р е ш е н и е: Составим математическую модель в виде задачи ЛП.

Обозначим через х₁, х₂ и х₃ план производства изделий вида Р₁, Р₂ и Р₃. Нужно найти максимум целевой функции

,

стоимости всей произведенной продукции, при ограничениях

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

Приведем графическое решение этой задачи, хотя не все моменты здесь можно изобразить на чертеже, так как переменных три. Вместо линий уровня здесь пришлось бы изображать плоскости уровня; перпендикулярные вектору нормали целевой функции. Но мы их не изображаем.

Плоскость (АВС) является границей полуплоскости, заданной неравенством

.

Координаты точек А(200; 0; 0), В(0; 400; 0) и С(0; 0; 160) получены из уравнения плоскости

.

приравниванием к нулю двух соответствующих координат. Областью допустимых планов является выпуклый многогранник с вершинами в точках ОАСLEK.

Вектор нормали – вектор (8; 14; 10) функциипоказывает направление ее возрастания. Самой «дальней» в этом направлении будет точкаК. Ее координаты находим из уравнений плоскостей (АВС) и (DGE).

Эти плоскости пересекаются по прямой (К). Для нахождения точки К следует взять х₃ = 0.

Получим систему линейных уравнений:

Она имеет решение х₁ = 100, х₂ = 200. Добавляя сюда х₃ = 0, получаем оптимальный план задачи линейного программирования .

Вычислим значение целевой функции:

.

О т в е т: ,.

Найденный ответ означает следующее.

Мы должны производить из имеющегося сырья 100 единиц продукции Р₁ и 200 единиц продукции Р2. Продукцию Р₃ производить не будем. Выручка от реализации готовой продукции составит 3600 условных денежных единиц.

Допустим теперь, что у производителя продукции имеется альтернативная возможность – продать все сырье.

З а д а ч а В₂: Допустим, что выполняются условия задачи А₂. По каким ценам следует продавать сырье, чтобы реализовать его было выгоднее, чем производить из него продукцию?

Р е ш е н и е: Обозначим через у₁ и у₂ цены на единицу сырья видов S₁ и S₂. Вектор цен задает точку на плоскости. Если ценыу_i очень большие, то производителя они устроят, но не обязательно сырье купят по этим ценам. Производителя интересуют такие комбинации цен, при которых сырье выгоднее продать. При этом он хочет знать, какой доход он получит от продажи сырья.

В одной единице готовой продукции Р₁ содержится 4 единицы сырья S₁ по цене у₁ и 2 единицы сырья S₂ по цене у₂. Общая стоимость сырья, заключенного в одном готовом изделии Р₁, равна 4у₁ + 2у₂. Эта величина должна быть не меньше, чем цена готового изделия - 8. В противном случае выгоднее из данного сырья изготовить продукцию.

Получили первое ограничение:

.

По аналогичной причине должны выполняться два другие неравенства, соответствующие второму и третьему видам продукции:

Добавляя условия не отрицательности цен у₁ ≥ 0, получаем систему неравенств, которая задает область допустимых цен:

Если производитель найдет покупателя, согласного купить сырье по ценам, которые входят в область допустимых цен, то сырье выгоднее продать, не производя из него продукции. При этом производителя продукции будет интересовать гарантированный доход, который ему может дать продажа сырья. Гарантированный доход соответствует минимуму целевой функции.

.

Решим графически полученную задачу:

(l1)	,
(l2)	,
(l3)	.

Вектор нормали целевой функции сонаправлен с векторомна чертеже. Точкой минимума будут точкаВ, которая является точкой пересечения прямых l₁ и l₂. Ее координаты находим из системы:

Найдем значение целевой функции:

.

Заметим, что .

Задачи А и В взаимно определяют друг друга. Зная одну из задач, можно записать и другую задачу.

Сравним задачи А₂ и В₂.

А	В

В задаче В в некотором смысле «все по другому» по сравнению с задачей А.

В задаче А целевая функция максимизируется, неравенства имеют вид ## ≤ ##, а в задаче В целевая функция минимизируется, неравенства вида ## ≥ ##.

Свободные члены в неравенствах и коэффициенты в целевых функциях в задачах А и В меняются ролями.

Если сравнить коэффициенты при неизвестных, то они образуют две матрицы

у которых меняются ролями строки и столбцы.