3.4. Основные теоремы двойственности

Первая теорема двойственности.

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

Экономическая интерпретация теоремы такова: если разрешима задача определения оптимального плана производства, то разрешима и задача определения оценок ресурсов. Чтобы план производства и вектор оценок ресурсов были оптимальны, необходимо и достаточно, чтобы доход и суммарная оценка ресурсов совпадали. Несовпадение – это сигнал о том, что система находится в нестабильном состоянии, поскольку стоимость потребляемых ресурсов превышает получаемый доход. Таким образом, двойственные оценки выступают как инструмент балансировки затрат и результатов. Второе утверждение теоремы можно интерпретировать так: предположим что ресурсов недостаточно для обеспечения заданного плана производства, тогда для его выполнения пришлось бы приобретать ресурсы по любой (формально неограниченной) цене.

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

Содержательный смысл оценок переменных прямой задачи в том, что они показывают, на сколько уменьшится целевая функция, если соответствующая переменная увеличится на единицу. Значит оценки переменных x₄, x₅, x₆ это и есть оптимальные значения переменных двойственной задачи, т. е. двойственные оценки.

Например, если на последней итерации (при получении оптимального решения) оценка , то эта величина есть отклонение функционала от оптимального значения при присвоении переменной х₆ единичного значения. Но это равносильно уменьшению третьего ресурса на единицу (достаточно посмотреть на третью строку нулевой итерации), т. е. это цена третьего ресурса.

Таблица 3.3

Номер итера- ции	БП
				9	6	7	0	0	0
0		0	180	6	2	5	1	0	0
		0	60	0	2	4	0	1	0
		0	120	5	2	5	0	0	1
	Оценки
			0	–9	–6	–7	0	0	0
2		0	48	1	0	–1/5	1	1/5	–6/5
		6	30	0	1	2	0	1/2	0
		9	12	0	0	1/5	0	–1/5	1/5
	Оценки
			288	0	0	6,8	0	1,2	1,8
Соответствующие переменные двойственной задачи

Следовательно, значения – это оценки соответствующих ресурсов. Первый ресурс недефицитный (ранее было отмечено, что величину этого ресурса можно уменьшить на 48 единиц без изменения прибыли), а наиболее дефицитным является третий ресурс.

Если подставить найденные цены ресурсов в математическую модель двойственной задачи, то целевая функция должна получить значение 288, как и при решении прямой задачи. Действительно, имеем:

180 · 0 + 60 · 1,2 + 120 · 1,8 = 72 + 216 = 288.

Оценки переменных x₁, x₂, x₃ – это значения свободных переменных двойственной задачи, которые можно истолковать так: если вместо продажи части ресурсов по оптимальным двойственным ценам произвести по единице каждого из возможных видов продукции, то производство третьего вида продукции повлечет указанный убыток, а производство первых двух видов прибыль не изменит.

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

Теорема о дополняющей нежесткости.

Для того чтобы планы и у^* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

Эти условия означают, что, если после оптимизации какая-либо переменная одной из задач положительна, то соответствующее ограничение двойственной задачи должно обращаться в строгое равенство.

Величина представляет суммарную стоимость всех ресурсов, используемых для производства единицы продукции, которая и должна равняться доходу от ее реализации , если планы оптимальны. Разности часто называют приведенной стоимостью (приведенными издержками) j-го вида деятельности.

Величина – это неиспользованное количество i-го ресурса, которое для оптимального плана производства может быть положительным только для недефицитных (используемых не полностью ресурсов), которым соответствует нулевое значение двойственной оценки .

Теорема об оценках.

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

Экономический смысл очевиден – единичный прирост ресурса (при оптимальном его использовании) позволяет увеличить доход на величину, равную теневой цене этого ресурса.

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

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

50