Рассмотрим пару двойственных задач. Задачу об оптимальном плане выпуска продукции (1) и задачу определения оптимальных оценок ресурсов (2).

З.1. (1) (1`)

(2) (2`)

(3) (3`)

Решим задачу (1) симплекс методом и найдем ее оптимальное решение и максимальное значение целевой функции и найдем решение двойственной задачи и минимальное значение целевой функции .

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

1.Как влияет на максимальное значение целевой функции «малое» изменение какого-либо i-того ресурса.

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

3.Как оценить целесообразность выпуска какого-либо вида продукции.

На 1 и 3 вопросы можно дать ответы решив задачу заново с измененной информацией, но этого делать не надо. Ответ на эти вопросы можно получить используя имеющуюся информацию решения задачи

1.Как влияет на максимальное значение целевой функции «малое» изменение какого-либо i-того ресурса.

Обозначим через вектор ресурсов исходной задачи (1):

, а максимальное значение целевой функции полученное при решении этой задачи через . Изменим объем i-го ресурса на . Вектор изменения ресурса обозначим = . Новый вектор ресурсов . Пусть при этом новом векторе ресурсов план будет допустимым планом. При этом новом векторе ресурсов значение целевой функции изменяется на величину . Найдем отношение и перейдем к пределу .

Если , , то при увеличении i-того ресурса на и при неизменных всех остальных ресурсах максимальная прибыль увеличится на .

Если , , то уменьшится на .

Если i-ый ресурс недефицитный, то его оценка , следовательно «малое» изменение недефицитного ресурса на максимальное значение целевой функции не влияет.

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

Обозначим исходный вектор ресурсов через . Изменим объем ресурса вида Р на величину , тогда вектор изменения ресурсов =. Новый вектор ресурсов будет равен или =. Решим исходную задачу (1) симплексным методом и в последней оптимальной симплексной таблице, в последнем столбце, получим преобразованный по формулам полного исключения неизвестных вектор, который обозначим через . Если одновременно в симплексных таблицах преобразовывать , то в последней симплексной таблице получим преобразованный вектор . Можно показать (4).

Вывод формулы (4):

Известно, что при решении ЗЛП симплексным методом правые части ограничений на каждом шаге преобразуются по формулам:

; ; (*)

где r – разрешающая строка, а s – разрешающий столбец. Если правая часть состоит из суммы двух векторов:

= и ,

т.е. =, то применяя формулы (*), получим:

;

Т.о., чтобы преобразовать вектор по формулам (*), достаточно преобразовать векторы в векторы и найти выражение . В нашем случае .

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

Век	A1	…	An	E1	…	Ep	…	Em	B
БП	X1	…	Xn	Xn+1	…	Xn+p	…	Xn+m	bi
Хn+1	a11	…	a1n	1	…	0	…	0	b1
Хn+2	a22	…	a2n	0	…	0	…	0	b2
…	…	…	…	…	…	…	…	…	…
Хn+p	ap1	…	apn	0	…	1	…	0	bp
…	…	…	…	…	…	…	…	…	…
Хn+m	am1	…	amn	0	…	0	…	1	bm
Z	1	…	n	0	…	0	…	0	0

Решив задачу симплексным методом мы получим:

Век				E`1		E`p	…	E`m	B`
БП	X1	…	Xn	Xn+1	…	Xn+p	…	Xn+m	С.Ч.
Xi1		b`1
Xi2	b`2
…	…
Xim	b`m
Z	D`1	…	D`n	D`n+1	…	D`n+p	…	D`n+m	Q

В этой таблице все оценки D`j>=0; j=1…m+n; b`i>=0; i=1…m. БП Хi1…Хim. Решение задачи X*i1=b`1,…, X*im =b`m и Zmax=Q. и . Все остальные свободные переменные равны нулю. И тогда в оптимальном базисе задачи (1): +=. Для того, чтобы оптимальный базис задачи (1) оставался оптимальным и для , необходимо чтобы значения БП: Хi1,…,Xim были неотрицательны, то есть Xi1=b`1+Dbp*q1>=0,…,Xim=b`m+Dbp*qm>=0, то есть необходимо решить следующую систему неравенств b`i+Dbp*qi>=0, где i=1,…,m. Решив эту систему неравенств мы найдем:

Т.о. номенклатура выпускаемой продукции и состав БП в оптимальном плане задачи (1) не изменится, если . При изменении i-того ресурса на величину Dbi: . Интервал () наз. Интервалом устойчивости оценки y*i. Если объем i-того ресурса менять в этом интервале, а объемы всех остальных ресурсов не менять, то в оптимальном плане задачи (1) сохраняется состав БП, т.е. номенклатура выпускаемой продукции, т.е. оценки всех ресурсов не меняются. Если объем i-того ресурса изменяется за пределами интервала устойчивости оценок, то состав bp меняется, а из-за этого изменяется оценки Z строки и следовательно изменяется значение оценок y*i. Изменение максимальной прибыли DZmax при изменении i-того ресурса на малую величину Dbi можно определять по формуле: DZmax=Dbi· y*i, если Dbi принадлежит интервалу .

3.Как оценить целесообразность выпуска какого-либо вида продукции.

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

Если , то такой вид продукции выпускать не выгодно. Пусть теперь имеется новый s-тый вид продукции с нормами затрат ресурсов на ед. продукции a_is ,i=1,…,m и прибылью от ед. продукции с_s. Тогда стоимость всех ресурсов в оптимальных оценках, идущих на изготовление ед. продукции вида s будет равна:

И если эта величина будет < прибыли, то тогда данный вид продукции выпускать целесообразно, а если больше прибыли — не целесообразно. Т.о. двойственные оценки y*i формируют показатель . Если Dj>0 то j–тый вид продукции выпускать невыгодно. А если Dj<0 то j–тый вид продукции выпускать выгодно. А для тех видов продукции, которые выпускаются Dj=0.

Ответ на третий вопрос.

Согласно второй теореме двойственности оптимальное решение и должны удовлетворять условиям:

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

если стоимость всех ресурсов идущих на изготовление единицы продукции вида j больше прибыли от реализации единицы этой продукции, то такой вид продукции выпускать невыгодно, то

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

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

Если , то j-й вид продукции выпускать невыгодно, а если — то выгодно.