Нахождение решения двойственных задач

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

,

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

Оптимальный план прямой задачи можно записать в виде:

,

где - обратная матрица к матрице, составленной из компонент векторов, вошедших в оптимальный план.

Подставим оптимальный план в выражение

.

Тогда

,

где С_Б –вектор, состоящий из коэффициентов целевой функции при базисных переменных оптимального решения.

Тогда оптимальный план двойственной задачи равен

.

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

Таким образом, если найти оптимальное решения прямой задачи симплексным методом, то, используя последнюю симплекс–таблицу, можно определить и , и с помощью соотношения найти оптимальное решение двойственной задачи.

Соответствие между переменными прямой и двойственной задач в симплекс-таблице

переменные прямой задачи	основные	дополнительные
переменные двойственной задачи	дополнительные	основные

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

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

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

Свойства двойственных оценок:

1. Оценка ресурса показывает, на сколько изменится оптимальное значение целевой функции (значение целевой функции на оптимальном плане), если объем соответствующего ресурса увеличить на единицу.

2. Ресурс называется дефицитным для данного оптимального плана, если он полностью используется в производстве, согласно этому плану.

Экономическую интерпретацию двойственных оценок рассмотрим на примере.

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

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

Вид сырья	Нормы затрат сырья (кг) на единицу продукции
	А	В	С
I	4	2	1
II	3	1	3
III	1	2	5
Цена единицы продукции (руб.)	10	14	12

Решение. Предположим, что производится x₁ изделий А, х₂ изделий В и х₃ изделий С. Для определения оптимального плана производства нужно решить следующую задачу

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

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

Как видно, задачи образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий А, В и С, а решение двойственной — оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой-либо одной из них. Так как система ограничений исходной задачи содержит лишь неравенства вида «≤», то лучше сначала найти решение этой задачи. оптимальное решение приведено в симплексной таблице.

Б	СБ	B	10	14	12	0	0	0
			a1	a2	a3	a4	a5	a6
a2	14	82	19/8	1	0	5/8	0	-1/8
a5	0	80	23/8	0	0	1/8	1	-5/8
a3	12	16	-3/4	0	1	-¼	0	¼
		1340	57/4	0	0	23/4	0	5/4
						y1*	у2*	y3*

Из этой таблицы видно, что оптимальным планом производства изделий является такой план, при котором изготовляется 82 изделия В и 16 изделий С, при этом остается неиспользованным 80кг сырья II вида, а максимальную прибыль равна руб., т.е. . Из таблицы также видно, что оптимальным решением двойственной задачи является .

Переменные y₁^* и y₂^* обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье I и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

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

Так, увеличение количества сырья 1 вида на 1кг приведет к тому, что появится возможность найти новый оптимальный план производства, при котором общая стоимость произведенной продукции возрастет на 5,75 руб. и станет равной 1340+5,75 = 1345,75 руб. При этом числа, стоящие в столбце вектора a₄ оптимальной таблицы, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида увеличится на 1/8 кг.

Точно так же увеличение на 1кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий B на 1/8 ед., причем объем используемого сырья II вида уменьшится на 5/8 кг.

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

.

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

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

Первое ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия вида А, выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий В и С, равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.

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