Экономическая интерпретация двойственных задач

Двойственной задачи

Связь между решениями прямой и

Лемма 1. Если Х – некоторый план исходной задачи 4.17 – 4.20, а Y – произвольный план двойственной задачи 4.21 – 4.24, то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е.

f(x) £ F(Y).

Лемма 2. Если f(x*) = F(Y*) для некоторых планов Х* и Y* задач 1 – 4 и 5 – 8, то Х* - оптимальный план исходной задачи, Y* - оптимальный план двойственной задачи.

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

max f(x) = min F(Y).

Если целевая функция одной из пары двойственной задач не ограничена (для f(x) – сверху, для F(Y) – снизу), то другая задача вообще плана не имеет.

Пример. Для производства трех видов изделий А, В и С используются три различных вида сырья, запасы которого составляют соответственно 180, 210 и 244 кг. Нормы затрат сырья на единицу продукции и доход от реализации единицы продукции приведены в табл. 4.6.

Таблица 4.6

Вид сырья	Нормы затрат сырья, кг, на ед. продукции	Запасы сырья, кг
A	B	C
I
II
III
Доход ден.ед.				-

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

Решение. Предположим, что Х_j – количество продукции j–го вида, т.е. производится Х₁ изделий типа А,

Х₂ – типа В и Х₃ – типа С.

Для определения оптимального плана производства, необходимо решить следующую задачу: определить максимум целевой функции

f(x) = 10X₁ + 14X₂ + 12X₃ ® max (4.25)

при следующих условиях

Х₁, Х₂, Х₃ ³ 0. (4.27)

Припишем единице каждого из видов сырья, используемого для производства продукции, двойственную оценку, соответственно равные y₁, y₂ и y₃ (другие названия: объективно обусловленные оценки, теневые цены и т.п.). Тогда общая оценка сырья, используемого на производство всей продукции, должна быть минимальной:

F(Y) = 180y₁ + 210y₂ + 244y₃ ® min, (4.28)

а суммарные оценки сырья, используемого на производство единицы продукции каждого вида, должны компенсироваться доходом от реализации единицы продукции данного вида:

y₁, y₂, y₃ ³ 0. (4.30)

Задачи 4.25 – 4.27 и 4.28 – 4.30 образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий А, В и С, а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий.

Двойственные оценки можно интерпретировать как внутреннюю ценность, важность ресурсов. Тогда функцию цели двойственной задачи можно интерпретировать таким образом, что внутренняя ценность используемых ресурсов состоит в обеспечении оптимальной прибыли, но при этом затраты ресурсов должны быть минимальными. Систему ограничений двойственной задачи можно интерпретировать как то, что суммарная внутренняя ценность ресурсов, идущих на единицу продукции, определяется получением ожидаемого дохода. Если же затраты на ресурсы больше ожидаемого дохода, то данный вид продукции нерентабелен и выпускаться не будет:

= C_j если Х_j > 0;

> C_j если Х_j = 0.

Дата добавления: 2014-12-27