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

Пример 5. Для примера 4 составить двойственную задачу. Оценить дефицитность каждого вида ресурсов, используемых для производства продукции. Оценки, приписываемые каждому виду ресурсов, должны быть такими, чтобы оценка всех используемых ресурсов была минимальной, а суммарная оценка ресурсов на производство единицы продукции каждого вида - не меньше цены единицы продукции данного вида.

Решение. Обозначим через y₁ - двойственную оценку дефицитности трудовых ресурсов, через y₂ – ресурсов сырья, y₃ - оборудования. Тогда прямая и двойственная задачи формулируются:

прямая задача

двойственная задача

Решение прямой задачи дает оптимальный план производства продукции П₁, П₂, П₃, П₄, а решение двойственной задачи - оптимальную систему оценок ресурсов, используемых для производства этой продукции:

Двойственные оценки ресурсов y_i ^* – это оценочные коэффициенты D_j дополнительных переменных х₅, х₆, х₇ в последней симплексной таблице (таблица 2.9).

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

Трудовые ресурсы и оборудование используются полностью. Полному использованию этих ресурсов соответствуют полученные оптимальные оценки y₁, y₃, отличные от нуля. Значит, ресурсы сырья недоиспользуются (на х₆ =26 ед.).

Увеличение количества трудовых ресурсов на 1 ед. приведет к тому, что появится возможность найти новый оптимальный план производства продукции, при котором общая прибыль возрастет на 20 д. е. и станет равной 1320 + 20 = 1340 д. е. Анализ полученных оптимальных значений новой прямой задачи показывает, что это увеличение общей прибыли достигается за счет увеличения производства продукции П₁ на 1, 67 ед. (5/3) и сокращения выпуска продукции П₃ на 0, 67 ед. (2/3) (таблица 2.9). Вследствие этого использование ресурса сырья увеличивается на 7, 33 ед. (22/3).

Точно так же увеличение на 1 ед. количества оборудования позволит перейти к новому оптимальному плану производства, при котором прибыль возрастет на 10 д. е. и составит 1330 д. е., что достигается за счет уменьшения выпуска продукции П₁ на 0, 17 ед. и увеличения выпуска продукции П₃ на 0, 17 ед., причем объем используемого ресурса сырья уменьшается на 0, 33 ед.

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

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

2.4. Симплексный метод с искусственным базисом
(М-метод)

Пример 6. Решить задачу линейного программирования:

Домножив неравенство на (-1), получим: .

Приведем задачу к каноническому виду, перейдя к задаче на максимум:

Для нахождения исходного опорного плана переходим к М-задаче:

Дальнейшее решение проводим в симплексных таблицах (таблица 2.10).

Таблица 2.10

ci	БП	- 10					- M	- M	bi
x1	x2	x3	x4	x5	z1	z2
- M	z1		- 1	- 1
- M	z2				- 1
	x5	- 1	- 2
	Dj	-3M+10	- 5	M	M				- 5M
- 10	х1		-1/2	-1/2					3/2
- M	z2		3/2	1/2	-1				1/2
	x5		-5/2	-1/2					5/2
	Dj		-3М/2	-М/2+5	М				-М/2-15
- 10	х1			-1/3	-1/3				5/3
- 5	х2			1/3	-2/3				1/3
	x5				-5/3				10/3
	Dj								-15

В третьей симплекс-таблице получен опорный план исходной задачи ЛП.

Поскольку все оценки , то это решение является и оптимальным, т.е. х₁ =5/3, х₂ =1/3 (основные переменные), х₃ =0, х₄ =0, х₅ =10/3 (дополнительные переменные), при этом