Тема № 3. Использование свойств двойственных оценок задачи линейного программирования

Модель оптимального годового производственного планирования с критерием максимизации прибыли можно записать следующим образом:

Для этой задачи можно записать двойственную задачу:

Переменные называются двойственными оценками (ценами ресурсов, теневыми ценами).

Взаимосвязь между исходной и двойственной задачами:

1. Количество переменных в двойственной задаче соответствует количеству ограничений в исходной задаче.

2. Количество ограничений в двойственной задаче соответствует количеству переменных в исходной задаче.

3. Матрица коэффициентов при переменных в ограничениях двойственной задачи является транспонированной по отношению к матрице исходной задачи.

Для исходной и двойственной задачи выполняются следующие свойства:

1. Значения целевых функций для оптимального плана совпадают:

.

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

,

тогда является дефицитным ресурсом;

,

тогда является недефицитным ресурсом.

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

;

.

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

Пример 3.1. На предприятии производится два вида продукции на оборудовании, установленном в трех цехах. Известны нормы использования оборудования для производства единицы продукции в каждом цехе, количество установленного оборудования в каждом цехе, прибыль от производства единицы продукции каждого вида. Построить экономико-математическую модель задачи для определения оптимального плана производства продукции по критерию максимизации прибыли, составить двойственную задачу, найти значение двойственных оценок, провести их анализ. Данные задачи сведены в таблицу:

Номер цеха	Нормы использования оборудования для производства единицы продукции, шт.		Количество установленного оборудования, шт.
	1 вида	2 вида
1	4	7	56
2	5	4	40
3	6	-	24
Прибыль на ед. продукции, руб.	3	1

Экономико-математическая модель задачи выглядит следующим образом:

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

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

1. Арендная организация минимизировала расходы на аренду;

2. Организация, которая сдает в аренду оборудование, получила бы не меньше прибыли, чем, если бы она изготавливала на этом оборудовании продукцию.

Обозначим

- арендная плата за использование единицы оборудования в первом цехе;

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

- арендная плата за использование оборудования первого цеха. Аналогично для второго и третьего цехов.

В качестве критерия оптимальности используется минимизация общей арендной платы за использование оборудования:

- арендная плата за оборудование, которое установлено в первом цехе и используется для производства 1 вида продукции;

- арендная плата за оборудование, которое установлено во втором цехе и используется для производства 1 вида продукции;

- арендная плата за оборудование, которое установлено в третьем цехе и используется для производства 1 вида продукции.

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

.

Рассуждая аналогично, получаем ограничение для 2^го вида продукции. Тогда двойственная задача записывается следующим образом:

Заметим, что формально двойственную задачу можно записать, если транспонировать матрицу исходной задачи:

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