Двойственность и двойственные оценки при оптимальном планировании

Рассмотрим отношение приращения дохода  к приращению i-го ресурса       ;  

 Тогда по определению частной  производной функции 

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

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

Пусть L*- максимальное значение дохода в задаче (I),

Тогда, изменяя i-й ресурс на единицу, получим новое значение максимального дохода по формуле

или более общий вид

    

Двойственные переменные

называются оценками (теневыми ценами, ценностями) соответствующих ресурсов i=1,..., m, и характеризуют меру эффективности использования соответствующих ресурсов.

1.6 Экономическая интерпретация ограничений двойственной задачи.

Рассмотрим j-е ограничение задачи (II)   

Вектор   является j-м столбцом матрицы А и характеризует технологический процесс производства j-й продукции, а именно,  - это количество i-го ресурса i=1,..., m, необходимого для производства единицы j-й продукции.  Поскольку     - оценка единицы i-го ресурса, i=1,..., m, то сумма

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

характеризующая j- ограничение задачи (II), будет представлять собой приведенные издержки j-й продукции. Приведенные издержки характеризуют экономическую эффективность производства j-й продукции. Если приведенные издержки равны нулю, то производство j-й продукции эффективно, при ненулевых издержках

производство j-й продукции убыточно.

1.7  Экономическая интерпретация теорем двойственности

Рассмотрим экономическую интерпретацию основного неравенства двойственности. Так как  - прибыль от реализации единицы продукции, а     - количество произведенной j-й продукции, то     характеризует суммарную прибыль от реализации произведенной продукции. Так как  - количество i-го ресурса, а  - ценность единицы ресурса, то характеризует суммарную ценность всех ресурсов. Тогда из соотношения

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

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

Большой практический интерес представляет экономическая интерпретация второй теоремы двойственности, а также ее следствия  о дополняющей нежесткости.

1. Если суммарная оценка   i-го ресурса положительна

то этот ресурс в соответствии с оптимальным планом  х* используется полностью:           

2. Если i-й ресурс используется  не полностью 

то его оптимальная оценка нулевая    и i-е ограничение несущественно.  

3. Если в соответствии с оптимальным  планом х* j-я продукция производится   то это производство эффективно, так как цена единицы j-й продукции   равна затратам на ее производство в единицах

4. Если производство j-й продукции убыточно (приведенные издержки ненулевые

то в соответствии с оптимальным планом эта продукция не производится 

 

Глава II  Практическая часть

2.1 Словесная модель задачи

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

Тип сырья	Нормы сырья на одно изделие			Запасы ресурсов
	I	II	III
Труд	3	6	4	2000
Сырье 1	20	15	20	15000
Сырье 2	10	15	20	7400
Оборудование	0	3	5	1500
Цена	6	10	9

Требуется

Сформулировать прямую оптимизационную задачу на максимум выручки от реализации готовой продукции, получить оптимальный план выпуска продукции;

Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности;.

Пояснить нулевые значения переменных в оптимальном плане.

На основе свойств двойственных переменных в оптимальном плане:

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

Определить, как изменятся выручка и план выпуска продукции  при увеличении запасов сырья  I вида на 24

Оценить целесообразность включения в план изделия 4-го вида ценой 11 ед., на изготовление которого расходуется по 8, 4, 20 и 6 единиц сырья соответственно.

 

 

2.2 Математическая модель задачи

Составим экономико-математическую модель задачи. Для этого введем переменные:

Пусть

- количество выпущенной продукции  I вида

- продукции II вида

- продукции III вида.

Целевая функция, характеризующая максимум прибыли от реализации продукции:

F=

Составим систему ограничений по запасу ресурсов:

2.3 Решение  прямой задачи симплексным  методом

 

Решим прямую задачу линейного программирования   симплексным методом

 

Преобразуем математическую модель к каноническому виду:

Введем дополнительные переменные :

Применим симплекс-метод:

1) Разрешим систему уравнений  относительно некоторого базиса  и запишем соответствующее базисное  решение, которое является радиус-вектором  угловой точки ОДР.

:

Б0(0,0,0,2400,15000,1500) FБ0=0

Из целевой функции видно, что её наибольшее уменьшение будет если x2 будет уменьшаться, так как при х2 наибольший по модулю отрицательный коэффициент.

Возьмём x2 в качестве базисной переменной

     

Выразим x2 из 1-го уравнения, тогда  x4 выходит из базиса

Итак,

Б1(0;333,33;0;0;10000;2400;500) FБ0=-10000/3

Из целевой функции  видно, что её наибольшее уменьшение будет если x3 будет уменьшаться

Возьмём x3 в качестве базисной переменной

Выразим из 4-го уравнения , тогда выходит из базиса

         Б2(0;     FБ2=-33500/9

Из целевой функции  видно, что её наибольшее уменьшение будет если x1 будет уменьшаться

Возьмём x1 в качестве базисной переменной

Выразим из 3-го уравнения , тогда выходит из базиса

 Б3(     FБ3=-106220/27

Из целевой функции  видно, что её наибольшее уменьшение будет если x7 будет уменьшаться

Возьмём x7 в качестве базисной переменной

Выразим из 1-го уравнения, тогда выходит из базиса

Итак, Б4(520;0;110;0;2400;0,950) FБ4=4110

Т.к. все коэффициенты в целевой функции положительны, то найденное решение является оптимальным и симплекс-метод прекращает работу.

Возвращаясь к исходному условию задачи, получим:

Оптимальное решение:

2.4 Решение задачи средствами MS Excel

Составим компьютерную модель задачи.

1. Введем все необходимые данные в таблицу:

 

2. Решение: пропишем все необходимые формулы для подсчета:

3)  Теперь электронная модель сформирована и можно решать задачу. Для этого нужно открыть окно «Поиск решений» указать  целевую функцию и систему ограничений и нажмем «Выполнить». и нажать «выполнить». Если электронная модель сформирована правильно, то будет получено сообщение, что задача решена. Результат решения находится на листе EXCEL и в трех отчетах: Результаты, Устойчивость, Пределы

4. Получим результаты:

 

 

 

2.5 Двойственная задача. Решение двойственной задачи

 

Сформулируем двойственную задачу и найдем ее оптимальный план:

Имеем

При ограничениях:

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

Z=2000y1+15000y2+7400y3+1500y4 => min

При ограничениях:

y1 ≥ 0

y2 ≥ 0

y3 ≥ 0

y4 ≥ 0

Подставим  ; ;      в ограничение задачи

Из второй теоремы двойственности   (т.к в 2-ой и 4-ой строках не выполняется строгого равенстра «<»);

т.к >0; и >0, то ограничения запишем как равенства; 
Итак

       

т.к =0 ,и то ( ) будет иметь вид :

 

Решая её, получим 

 Подставим найденные значения  в целевую функцию двойственной задачи.

Проверим выполняется ли условие F( )=G( )

Итак, Fmax=Zmin, значит это условие выполняется,

 Подставим оптимальное решение Y(1.5;0;3/20;0) в систему ограничений

 Так как Y2=0 и Y4=0 рассмотрим 1-е и 3-е уравнение первоначальной системы. Во втором ограничении равенство не выполняется, значит Х2 =0

Откуда

Итак, max функции (т.е max общей стоимости выпускаемой продукции) равен 4110 при выпуске:

520 единиц продукции 1-го вида

0 единиц продукции 2-го вида

110 единиц продукции 3-го вида

Ответ: Максимум прибыли от общей стоимости выпускаемой продукции составляет 4110 д.ед., при 520 единицах продукции 1-го вида и 110 единицах продукции 3-го вида

 

 

Глава III Аналитическая часть

3.1 Анализ использования ресурсов в оптимальном плане

 

В оптимальном плане прямой задачи имеем х2=0, потому что затраты на выпуск этого изделия превышает их цену на 1,25 единиц.

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

По двойственным оценкам сделаем вывод, что сырьё №2 недефицитно, остро дефицитный ресурс №1, т.к. у1=1,5, и менее дефицитный ресурс №3, т.к. у3=0,15

И если мы увеличим количество первого ресурса, то у нас должна увеличиться и прибыль. Для определения проверим используя двойственную задачу

Z=2024*1,5+7400*3/20=4146(ден.ед) Т.е прибыль  увеличится на 46 единиц, поэтому  этот проект будет выгодным.

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

Рассмотрим эффективность включения в план изделия IV –го вида с ценой 11 ед, и затратами 8,4,20 и 6 ед каждого ресурса

8*у1+4у2+20у3+6у4-11=8*1,5+0+20*0,15+0-11=4 получили, что данный проект невыгодный.

Проверим решение новой задачи средствами Ms Excel, получим что наш оптимальный план не изменился, а значит включение в план 4-го вида изделия нецелесообразно.

 Отчет по устойчивости

В отчете по результатам отображается решение двойственной задачи в столбце «Теневая цена». Как мы видим из данного отчета решение двойственной задачи составляет у1=1,5;у2=0,15, что совпадает с нашим решением, полученным с помощью двойственных оценок.