6.5. Определение ценности ресурсов

Одно из основных положений теории двойственности: ценность ресурса совпадает со значением соответствующей двойственной переменной. Основные сведения о двойственности в линейном программировании представлены в приложении А.

Построим задачу, двойственную к рассматриваемой.

Прямая задача:

z =	15 x1	+10 x2	+8 x3	+2 x4	+0 s1	+0 s2	+0 s3	+0 s4		(двойств. перемен.)
	x1	+ 4 x2	+ x3	+5 x4	+ s1				=70	(y1)
	3 x1	+ 2 x2	+3 x3	+5 x4		+ s2			=80	(y2)
	2 x1	+ 3 x2		+4 x4			- s3		=25	(y3)
	x1		+ x3	+ x 4				- s4	=10	(y4)
	2 x1	- x2	+ x3						=0	(y5)
	x1,	x2,	x3,	x4,	s1,	s2,	s3,	s4	0

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

min ω=70y₁ + 80y₂ + 25y₃ + 10y₄ +0 y₅

y₁ + 3 y₂ + 2 y₃ + y₄ + 2 y₅ ≥15 (x₁)

4 y₁ + 2 y₂ + 3 y₃ - y₅ ≥10 (x₂)

y₁ + 3 y₂ + + y₄ + y₅ ≥8 (x₃)

5 y₁ + 5 y₂ + 4 y₃ + y₄ ≥2 (x₄)

y₁ ≥0 (s₁)

y₂ ≥0 (s₂)

- y₃ ≥0 (s₃)

- y₄ ≥0 (s₄)

В оптимальной таблице прямой задачи (табл. 6.9) базисными являются переменные x₁, x₂, x₃, s₂, s_3. Значит, согласно соотношениям дополняющей нежесткости, соответствующие этим переменным ограничения-неравенства двойственной задачи в точке оптимума выполняются как равенства. Таким образом получаем следующую систему линейных уравнений.

x₁≠0 y₁ + 3y₂ + 2y₃ + y₄ + 2y₅ = 15 y₁ + y₄ + 2y₅=15 x₂≠0 4y₁ + 2y₂ + 3y₃ -y₅ = 10 4y₁ - y₅ =10

x₃≠0 y₁ + 3y₂ + y₄ + y₅ = 8 y₁ + y₄ + y₅ =8

s₂≠0 y₂ = 0

s₃≠0 -y₃ = 0

Решив полученную систему линейных уравнений, получим:

Основная теорема двойственности гласит: "Если прямая и двойственная задача имеют решения, то их значения совпадают". Убедимся в этом:

ω=70y₁+80y₂+25y₃+10y₄ = 704,25+10(-3,25) = 297,5--32,5 = 265  ω≡z.

Согласно теории двойственности двойственная переменная y_i (i=1,..,m) опре­деляет ценность i-го ресурса (оценку ресурса, shadow price, теневую цену) – величину, на которую изменится значение целевой функции при увеличении на единицу уровня запаса соответствующего ресурса (относительную ценность единицы допол­нительного ресурса).

Значит, статус и ценность ресурсов таковы (табл. 6.10):

Таблица 6.10

№ ресурса	Наименование	Статус	Ценность
1-й	Сахар	Дефицитный	4,25
2-й	Мука	Недефицитный	0
3-й	Дрожжи	Недефицитный	0
4-й	Требование выполнения обязательных поставок	Дефицитный	-3,25
5-й	Соотношение объемов выпечки ватрушек, сушек и пирожков	Дефицитный	7

Т.о., при изменении в некоторых пределах уровней запасов ресурсов, имеем:

• каждый дополнительный мешок сахара (первый ресурс) позволит увеличить суммарную прибыль пекарни на 4,25 единиц стоимости;

• изменение уровней запасов муки и сахара (второй и третий ресурсы) не приведут к изменению суммарной прибыли;

• каждая дополнительная партия обязательных поставок ватрушек, пирожков и сдобных булочек согласно договорам с постоянными клиентами (четвертый ресурс) уменьшит суммарную прибыль пекарни на 3,25 единиц стоимости;

• увеличение разности объемов выпечки ватрушек, сушек и пирожков 2 x ₁ - x₂ + x₃ (пятый ресурс) на одну партию привело бы к увеличению суммарной прибыли пекарни на 7 единиц стоимости.

Отметим, что полученные аналитическим путем значения ценности ресурсов полностью совпадают с результатами Excel (см. рис. 6.5 – столбец Теневая цена отчета по устойчивости).

6.6. Диапазоны устойчивости

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

6.6.1. Изменение компонент вектора ограничений

6.6.1.1. Недефицитные ресурсы

Теоретические положения

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

• уменьшаться (в случае знака ограничения “”)

• увеличиваться (в случае знака ограничения “”)

Пусть — значение соответствующей дополнительной переменной в точке оп­тиму­ма. Тогда решение остается допустимым и оптимальным в диапазоне ,

где для ограничения типа “”,

для ограничения типа “”.