Анализ решения задачи о планировании производства мороженого на основе теории двойственности

Таким образом, задача (1.7) – (1.9) может быть записана в следующей канонической форме:

 

                                                                               (1.10)

 

Дополнительные  переменные y_i ( ) представляют собой остатки ресурсов каждого вида. Если в оптимальном решении какой-либо ресурс будет использован полностью, то ограничение исходной задачи (1.3.2) будет выполнено в виде равенства и y_i=0. Такое ограничение в отчетах Exсel называется связанным. Ресурс, который использован полностью, считается дефицитным.

1.5  Двойственность в линейном программировании

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

1. Она имеет столько переменных, сколько ограничений в исходной задаче;
2. Правые части ограничений исходной задачи становятся коэффициентами целевой функции в двойственной задаче;
3. Если исходная задача на максимум, то двойственная задача – на минимум, и наоборот;
4. Матрица коэффициентов при переменных в ограничениях транспонируется;
5. Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений в двойственной задаче;
6. Если ограничения исходной задачи имеют вид , то двойственной - и наоборот;
7. На переменные двойственной задачи наложено условие неотрицательности _{[6, c 31]}.

 

В таблице 2 приведена двойственная задача к рассматриваемой задаче планирования производства продукции.

 

Таблица 2- Исходная и двойственная задачи

Исходная задача	Двойственная задача
	(1.11)              (1.12) .                     (1.13)

Рассмотрим экономический смысл двойственной задачи. Допустим, что у предприятия есть возможность реализации всех своих ресурсов некоторой организации вместо того, чтобы организовывать свое производство. Необходимо установить прикидочные цены на ресурсы. Обозначим - цена единицы ресурса i-го вида (где ). Эти цены должны быть установлены исходя из несовпадающих интересов предприятия и покупающей организации.

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

F_Д=b₁×z₁+ b₂×z₂+…+ b_m×z_m®min

 

 

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

   ( ).

 

 

 

 

В результате получим  систему ограничений по каждому виду  продукции (1.12). По смыслу цена неотрицательна, поэтому в двойственную задачу включаются ограничения неотрицательности (1.13).

В отчетах Excel, получаемых с помощью надстройки “Поиск решения” оптимальное значение двойственной переменной называется теневой ценой. Теневая цена - это оценка значимости ресурса, вытекающая из конкретных условий задачи, а не реальная цена на рынке _{[7, c 33]}.

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

Если существует единственное решение исходной задачи, то существует и единственное решение двойственной задачи, причем значения целевых функций на оптимальных решениях совпадают:

max F=min F_Д .

Это означает, что  предприятию безразлично, производить  ли продукцию по оптимальному плану X^* и получить максимальную прибыль, либо продать ресурсы по оптимальным ценам Z^* и получить такую же сумму. Для всех других (неоптимальных) планов X и Z прибыль от выпуска продукции всегда меньше внутренней стоимости затраченных ресурсов: F<F_Д, а величина F_Д-F характеризует производственные потери.

Следствие (теорема  об оценках).

Двойственная  оценка z_i^* (теневая цена) показывает, как изменится целевая функция исходной задачи при изменении ресурса b_i на единицу:

Таким образом, по теневым ценам можно судить о том, насколько целесообразно изыскивать резервы для увеличения количества i-го ресурса: если соответствующая теневая цена равна нулю, то увеличение количества этого ресурса никак не повлияет на рост прибыли. С другой стороны, чем  больше теневая цена, тем больше увеличится прибыль при увеличении количества этого ресурса на одну единицу. Поэтому тот ресурс, который имеет большую теневую цену, считается более дефицитным _{[3, c 25]}.

Однако эта  теорема справедлива  только тогда, когда при изменении количества ресурса b_i значения переменных z_i^* в оптимальном плане двойственной задачи остаются неизменными. Это выполняется в пределах устойчивости оптимального решения, т.е. когда структура решения не изменяется. Пределы устойчивости при изменении правых частей ограничений указаны во второй таблице отчета по устойчивости (рис. 8).

 

 

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

Ограничения двойственной задачи можно также привести к  виду равенства, введя дополнительные переменные v_j, которые вычитаются из левых частей ограничений:

 

                                                                       (1.14)

 

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

 

                                       

 

 

 

 

Таким образом, v_j – это разница между той суммой, что могли бы получить, продавая ресурсы, необходимые для производства единицы продукции типа j, и прибылью, которая будет получена, если из этих ресурсов произвести и продать продукцию _{[1, c 35]}.

v_j=0, если оценка затрат ресурсов равна прибыли, т.е. потерь при производстве нет.

v_j>0, если оценка затрат ресурсов больше прибыли от единицы продукции. В этом случае производить этот вид продукции невыгодно.

В отчетах Excel  оптимальное значение дополнительной двойственной переменной называется нормированной стоимостью.

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

Пусть, например, продукция вида j не вошла в оптимальный план производства, т.е. =0. Однако существует некоторое плановое задание, предписывающее выпуск этого вида продукции в количестве T_j единиц. Тогда при выпуске этого невыгодного вида продукции на него будут оттянуты ресурсы, и выгодной продукции будет выпущено меньше. Целевая функция (общая прибыль) уменьшится, причем это уменьшение можно количественно измерить:

.

1.8 Вторая теорема двойственности (теорема о дополняющей

нежесткости)

Оптимальные решения  исходной и двойственной задач связаны  соотношениями:

Эта теорема  означает, что между переменными  исходной и двойственной задач существует взаимосвязь, которая заключается в том, что одна переменная из пары должна быть нулевой _{[3, c 29]}.

Рассмотрим  связь  (остаток ресурса i-го вида) и (теневая цена ресурса i-го вида).

Если  , то имеется остаток ресурса i-го вида, т.е. ресурс не дефицитен. Увеличение количества этого ресурса не позволит нарастить объемы производства, т.е. не вызовет увеличение прибыли. Увеличится только остаток этого ресурса. Поскольку теневая цена показывает, на сколько возрастает прибыль, она должна быть равна нулю:  .

Если  , то i - й ресурс  является дефицитным, и следовательно, использован полностью. Остаток этого ресурса равен нулю: .

Рассмотрим  связь  (оптимальный объем производства продукции j-го типа) и (потери при производстве  единицы продукции j-го типа).

Если  , то продукция типа j является невыгодной, и не должна входить в оптимальный план производства:

Если  , т.е. согласно оптимальному плану этот вид продукции должен быть произведен в каком-то количестве, он является выгодным. Поэтому соответствующие потери равны нулю: _{[1, c 38].}

 

2 ПОСТАНОВКА ЗАДАЧИ

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

 

Таблица 3- Исходные данные

Ресурсы	Норма расхода  ресурса  на 1 т мороженого				Общее количество ресурсов
	сливочного I вида	сливочного II вида	пломбира I вида	пломбира II вида
Молоко  натуральное, кг	550	0	620	0	64100
Молоко сухое, кг	40	30	20	20	4800
Молоко сухое  обезжиренное, кг	30	40	30	30	5200
Масло сливочное, кг	86	110	150	52	22360
Сахар, кг	160	92	158	128	26240
Молоко  сгущенное, кг	0	0	0	50	800
Молоко  сгущенное обезжиренное, кг	0	158	30	50	7910
Затраты оборудования (машино/ч)	4,5	4,5	4,5	4,5	720
Прибыль от реализации 1 т мороженого, ден. ед.	315	278	573	370

 

Вопросы:

1. Какое количество мороженого каждого вида следует производить? Какая будет получена прибыль?
2. Полностью ли задействовано оборудование в оптимальном плане производства?  Имеются ли остатки сырья какого-либо вида?
3. Какое управленческое решение принесет большую прибыль: дополнительно ввести в производство 100 кг молока сгущенного, или увеличить количество молока натурального на 200 кг?
4. К чему приведет плановое задание по выпуску 1 т сливочного мороженого 1 вида?

 

3 РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО  ПРОГРАММИРОВАНИЯ

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

1) Введем переменные. Нужно найти план производства, т.е. количество мороженого каждого вида, которое следует производить. Таким образом, будет 4 переменных:

x₁- количество сливочного мороженого I вида;

x₂ –количество сливочного мороженого  II вида;

x₃ –количество мороженого пломбир I вида;

x₄ –количество мороженого пломбир II вида.

2) Запишем целевую функцию. Она должна выражать собой критерий оптимальности (т.е. тот показатель, который в задаче должен достигнуть максимума или минимума). В нашей задаче указано, что должна быть максимальна прибыль. Поэтому целевая функция должна представлять собой формулу расчета прибыли.  Прибыль от единицы сливочного мороженого I вида составляет 315 денежных единиц, а поскольку мы собираемся выпускать x₁ мороженого данного вида, прибыль составит 315x₁ ден.ед. Аналогично прибыль от сливочного мороженого  II вида равна 278x₂ , и т.д. Общая прибыль от всех видов мороженого равна сумме:

F=315x₁+178x₂+573x₃+370x₄ → max

3) Запишем систему ограничений. Очевидно, что расход каждого вида ресурса не должен превышать его запас. Расход молока натурального   на производство сливочного мороженого I вида равен 550x₁, на сливочное мороженое  II вида – 0x₂, и т.д. Общий расход молока натурального выражается с помощью формулы: 550х₁+0х₂+620х₃+0х₄, а запас равен 64100. Поэтому имеем неравенство: . Аналогично записываются другие ограничения.

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Здесь x_j – количество выпускаемой продукции j-го типа (j= ).  Целевая функция представляет собой общую прибыль от производства мороженого всех видов. Ограничения отражают конечность запасов ресурсов на предприятии. Неотрицательность переменных следует из их смысла.