Лекции.Орг


Поиск:




Анализ чувствительности оптимальных решений к изменениям в ограничениях




 

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

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

Z = 100 х1 + 50 x2

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

1+ 2х2 700,

1 +2 480,

1 +2 300,

x1 0, x2 0.

 

Область допустимых решений, соответствующая данной системе ограничений, показана на рис. 4.3.

 

A
B
C

 


Рис. 4.3.

 

Оптимальная точка, в которой достигается максимальное значение целевой функции (линия уровня Z = 11 500), расположена в вершине А. Заметим, что она лежит на пересечении граничных прямых, соответствующих первому и третьему ограничениям системы. Уравнения этих прямых: 7х1+ 2х2 = 700 и 2х1 +2 = 300.

Выясним, к каким изменениям в оптимальном решении приведет, например, увеличение ресурса 1 с 700 до 840 единиц при неизменности других ограничений. В этом случае уравнение новой граничной прямой 1* примет вид 7х1+ 2х2 = 840. Она будет параллельна исходной прямой 1, но расположена правее. Соответственно изменится и граница ОДР: к ней добавится некоторая область.

Из рис. 4.3 видно, что в этом случае наибольшее (оптимальное) значение целевой функции будет достигаться в новой точке B, поскольку чем дальше линия уровня расположена от начала координат, тем большие значения принимает Z. Следовательно, увеличение данного ресурса привело, во-первых, к новой точке оптимума (новой оптимальной производственной программе), а во-вторых, к увеличению значения целевой функции (дохода). Значит ли это, что если увеличивать запас ресурса 1 до бесконечности, то и доход будет бесконечно прирастать? Оказывается, нет. Как только граничные линии пересекутся с осью ОХ1 дальнейший прирост ресурса 1 ничего не даст и в игру вступят ограничения по другим ресурсам. Легко проверить, что после того, как значение ресурса превысит величину 1050, ОДР не будет изменяться (прирастать) и оптимальная угловая точка C не сможет перемещаться в область дальнейшего роста значений целевой функции. Предельное значение целевой функции в этом случае будет Z = 15 000. Следовательно, влияние запаса ресурса на доходность ограничено определенными границами, называемыми границами устойчивости.

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

Заметим, что увеличение ресурса 2 не приведет ни к изменению точки оптимума (оптимальной производственной программы), ни к изменению целевой функции (дохода). Этот ресурс избыточен (недефицитен) и, в принципе, его запас можно уменьшать, исполь­зуя высвобождающиеся средства для других целей. Однако снижать запас ресурса 2 без влияния на оптимум можно только до определенного предела. Действительно, при уменьшении ресурса 2 граничная прямая будет перемещаться вниз. Как следует из рис. 4.3, область допустимых решений при уменьшении запаса ресурса 2 будет изменяться (уменьшаться). Причем как только линия 2 пересечет точку A, все кардинально изменится. Точка оптимума перейдет в новую вершину D— точку пересечения граничных прямых 1 и 2. При этом оптимальное значение Z станет меньше, чем раньше, а ресурс 3 перейдет в разряд избыточных (недефицитных).

Таким образом, можно сделать следующие выводы.

• Увеличение (уменьшение) значений целевой функции в зависимости от изменений в правых частях ограничений происходит только в рамках определенного диапазона.

• При выходе за границы такого диапазона изменение правых частей ограничений не приводит к изменениям целевой функции.

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

 

Двойственность задач ЛП

 

Для количественной оценки вклада каждого из ресурсов в прирост (уменьшение) целевой функции используются специальные приемы. С их помощью определяют так называемые теневые (удельные) цены, показывающие, на какую величину изменится целевая функция при увеличении или уменьшении запаса каждого из ресурсов на единицу. Для знакомства с аналитическими методами, положенными в основу оценки чувствительности оптимальных решений к изменению правых частей ограничений, рассмотрим так называемую двойственную задачу линейного программирования.

Пример 4.1.

 

Фабрика производит 2 вида химических удобрений — А и Б. Для их производства необходимы компоненты 2-х типов, дневной расход которых на 1 тонну каждого из удобрений приведен в табл. 4.1. Рыночная цена 1 т удобрений А составляет 3 тыс. руб., удобрения Б — 2 тыс. руб. Требуется так спланировать производственную программу (выбрать объемы выпуска А и Б), чтобы доход от реализации был максимальным.

Табл. 4.1.

Ресурс Расход ресурса на единицу продукции Запасы ресурсов  
А (x1) Б (x2)
№1      
№2      

 

Решение

Обозначим через x1объем выпуска (в тоннах) удобрения А, а через x2 — объем выпуска (в тоннах) удобрения Б. Тогда доход от их реализации будет равен

Z = 3 x1 + 2 x2 (4.1)

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

x1 +3 x2 6 (4.2)

2x1 + x2 8

Кроме того, переменные неотрицательны:

x1 0, x2 0. (4.3)

Объединяя все сказанное, приходим к задаче линейного программирования: требуется максимизировать целевую функцию (4.1), если на переменные наложены ограничения (4.2) и (4.3). Решая задачу графоаналитическим методом, находим:

x1opt = 3.6 т

x2opt = 0.8 т

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

Zmax = 12,4 тыс. руб.

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

 

л
   
 

Для решения задачи обозначим гипотетические цены единицы каждого ресурса через у1, у2. Тогда, у1 — цена единицы ресурса № 1 (тыс. руб. за 1 т), у2— цена единицы ресурса № 2 (тыс. руб. за 1 т).

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

Так как в прямой задаче цена одной тонны продукта А была равна 3 тыс. руб., то и выручить от продажи ресурсов, затрачиваемых на производство А, нужно не менее 3 тыс. руб. Поскольку на производство единицы продукта А расходуется одна единица ресурса № 1 и две единицы ресурса №2 (табл. 4.1), то получаем первое ограничительное условие:

у1 + 2 у2 3

Рассуждая аналогично, получаем второе ограничительное условие:

1 + у2 2

Искомые цены не могут быть отрицательными, поэтому

y1 0, y2 0.

С позиции гипотетического покупателя-конкурента, целевая функция — это суммарная стоимость приобретаемых им ресурсов, которую необходимо минимизировать. Так как запасы ресурсов фабрики — 6 и 8 тонн, то их суммарная стоимость при ценах за единицу у1, у2 будет равна

Z* = 6у1 + 8 у2.

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

Z* = 6 у1 + 8 у2 => min (4.4)

при ограничениях

у1 + 2 у2 3. (4.5)

1 + у2 2

y1 0, y2 0. (4.6)

Решая эту задачу графоаналитическим методом (рис. 4.7), находим оптимальные гипотетические цены ресурсов:

y1opt = 0,2 тыс. руб. за тонну ресурса №1

y2opt = 1,4 тыс. руб. за тонну ресурса №2

При этом

Z*min = 6y1+ 8у2 = 12,4 тыс. руб.

 

Y2

Y1
y1opt = 0,2 y2opt = 1,4

 


Рис.4.7.

 

Заметим, что оптимальное (минимальное) значение целевой функции во второй задаче в точности совпало с оптимальным (максимальным) значением целевой функции исходной задаче

Zmax = 12,4 тыс. руб. Z*min = 12,4 тыс. руб. (4.7)

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

Найденные ylopt = 0,2 и y2opt =1,4 — это стоимости ресурсов с точки зрения их ценности для производителя. В теории линейного программирования их называют теневыми ценами (объективно обусловленными оценками, двойственными оценками).

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

Для этого вначале проанализируем особенности рассмотренных выше задач, из которых первую называют исходной (прямой), а вторую — двойственной по отношению к первой. Двойственная задача полностью основана на исходных данных прямой задачи и в отрыве от нее не имеет смысла.

Сравним обе задачи примера 4.1 (см. табл. 4.2).

Табл. 4.2.

Ресурс Расход ресурсов на единицу продукции аij Запасы ресурсов bi Теневые цены yj
А Б
№1       y1
№2       y2
Целевые коэффициенты        
Кол-во единиц продукции x1 x2    

 

  Исходная задача Двойственная задача
Переменные решения х12 y1,y2
Целевая функция Доход (максимизируется) Z = 3x1 + 2x2 max Издержки (минимизируются) Z* = 6y1 + 8y2 min
Ограничения x1 +3 x2 6 2x1 + x2 8 x1, x2 0 у1 + 2 у2 3 3у1 + у2 2 y1 0, y2 0.

 

Двойственные задачи составляются по следующим правилам.

1. В одной задаче ищется максимум целевой функции, в другой — минимум.

2. Коэффициенты целевой функции обратной задачи являются правыми частями ограничений исходной.

3. В обеих задачах переменные неотрицательны.

4. Все неравенства системы ограничений в задаче на максимум имеют знак «», в задаче на минимум – «».

5. Число переменных двойственной задачи равно числу ограничений исходной.

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

Табл. 4.3.

Исходная задача Двойственная задача
x1,x2,………,xn y1,y2,……,ym
Z = c1x1+c2x2+…..+cnxn max Z = b1y1+b2y2+…..+bmym min
a11x1+a12x2+….+a1nxn b1 ………………………………………….. am1x1+am2x2+……+amnxn bm x1 0, x2 0, ……., xn 0 a11y1+a21y2+….+am1ym c1 ………………………………………….. a1ny1+a2ny2+……+amnyn cn y1 0, y2 0, ……., ym 0

 

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

Теорема

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

 

Zmax = Z*min (4.8)

 

Именно такой результат был получен выше в примере 4.1. Выясним смысл этого равенства.

Так как

Z*min = b1y1 + b2y2 +…….+bmym

где b1, b2,……,bm – запасы ресурсов, которыми располагает производитель, а y1, y2, ……..,ym – теневые цены этих ресурсов, то, с учетом (4,8) получаем формулу, устанавливающую взаимосвязь оптимального значения целевой функции (оптимального решения) с запасами ресурсов и их теневыми ценами.

 

Поскольку

Zmax = Z*min = b1y1 + b2y2 +…….+bmym

 

то

Zmax = b1y1 + b2y2 +…….+ bmym (4.9)

 

Зная теневые цены, по формуле (4.9) легко оценить насколько возрастет или уменьшится оптимальное решение — значение Zmax,если запас какого-либо ресурса biувеличить или уменьшить на определенную величину. Иначе говоря, соотношение (4.9) дает возможность количественно оценить:

• влияние запаса каждого ресурса на целевую функцию;

• ценность каждого ресурса с точки зрения его вклада в доходность.

При проведении анализа на основе формулы (4.9) следует помнить, что изменять величину запасов можно только в некоторых допустимых границах, о которых говорилось выше — в разделе 4.3.

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

Zmax = b1 y1

Или, записав это равенство иначе, получаем:

 

yi = (4.10)

 

Смысл соотношения (4.10) в следующем.

Теневая цена показывает, на какую величину изменится максимальный доход (оптимальное значение целевой функции) при изменении запаса соответствующего ресурса на единицу.

Таким образом:

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

2. Теневые цены показывают, на какую величину изменится максимальный доход (оптимальное значение целевой функции) при изменении запаса соответствующего ресурса на единицу.

Полезность двойственной задачи не исчерпывается только соотношениями (4.9) и (4.10). Другие теоремы позволяют использовать ее для рационализации процедур решения исходной задачи в тех случаях, когда число ограничений значительно превышает число переменных. Впервые проблему двойственности сформулировал и исследовал академик Л. В. Канторович, удостоенный в 1975 году Нобелевской премии по экономике за выдающийся вклад в теорию оптимизации и линейного программирования.





Поделиться с друзьями:


Дата добавления: 2016-12-05; Мы поможем в написании ваших работ!; просмотров: 1281 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Два самых важных дня в твоей жизни: день, когда ты появился на свет, и день, когда понял, зачем. © Марк Твен
==> читать все изречения...

759 - | 699 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.009 с.