1.Задача оптимального плана производства и двойственная к ней – задача нахождения оптимальных оценок ресурсов.

Запишем мат. Модель задачи оптимального плана производства.

З.1)

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

Первая теорема двойственности :

1) Если одна из двойственных задач 1) — 3) или 1^{`</sup> ) — 3<sup>`} ) имеют оптимальное решение то и другая также имеет оптимальное решение причём Z_max = U_min т.е. и оптимальные планы и

2) Если одна из двойственных задач неразрешима из-за неограниченности целевой функции т.е. или то система ограничений другой задачи несовместна.

3) Если система ограничений одной из двойственных задач несовместна то либо система ограничений другой задачи тоже несовместна либо её целевая функция неограниченна.

Вторая теорема двойственности:

Для того чтобы два допустимых решения и пары двойственных задач 1)-3) или 1^{`</sup>)-3<sup>`}) были оптимальными необходимо и достаточно чтобы выполнялись условия:

Следствия из второй теоремы двойственности и их экономический смысл:

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

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

3.Если в оптимальном плане задачи 2) цена единицы i-го ресурса положительна т.е. Y_i>0 то такой ресурс в оптимальном плане производства расходуется полностью () такой ресурс называется дефицитным.

4.Если в оптимальном плане производства какой-то i-й ресурс использован не полностью т.е. имеется остаток () то оценка такого ресурса в оптимальном плане задачи 2 будет равна 0, это недефицитный ресурс. Равенство нулю такой оценки говорит о том, что неиспользованное количество ресурсов – остаток ресурсов вклада в прибыль не вносит.

Анализ устойчивости оптимального плана производства

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

Решим задачу (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) симплексным методом, приведем ее к стандартному виду и запишем условие в исходную симплексную таблицу.

В этой таблице все оценки 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.