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

 

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

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

Z = 100 х₁ + 50 x₂

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

7х₁+ 2х₂ 700,

2х₁ + 4х₂ 480,

2х₁ + 2х₂ 300,

x₁ 0, x₂ 0.

 

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

 

A

B

C

 

Рис. 4.3.

 

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

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

Из рис. 4.3 видно, что в этом случае наибольшее (оптимальное) значение целевой функции будет достигаться в новой точке B, поскольку чем дальше линия уровня расположена от начала координат, тем большие значения принимает Z. Следовательно, увеличение данного ресурса привело, во-первых, к новой точке оптимума (новой оптимальной производственной программе), а во-вторых, к увеличению значения целевой функции (дохода). Значит ли это, что если увеличивать запас ресурса 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

 

Решение

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

Z = 3 x₁ + 2 x₂ (4.1)

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

x₁ +3 x₂ 6 (4.2)

2x₁ + x₂ 8

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

x₁ 0, x₂ 0. (4.3)

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

x_1opt = 3.6 т

x_2opt = 0.8 т

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

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

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

 

л

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

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

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

у₁ + 2 у₂ 3

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

3у₁ + у₂ 2

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

y₁ 0, y₂ 0.

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

Z* = 6у₁ + 8 у₂.

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

Z* = 6 у₁ + 8 у₂ => min (4.4)

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

у₁ + 2 у₂ 3. (4.5)

3у₁ + у₂ 2

y₁ 0, y₂ 0. (4.6)

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

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

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

При этом

Z*_min = 6y₁+ 8у₂ = 12,4 тыс. руб.

 

Y₂

Y1

y1opt = 0,2 y2opt = 1,4

 

Рис.4.7.

 

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

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

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

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

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

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

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

Табл. 4.2.

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

 

	Исходная задача	Двойственная задача
Переменные решения	х1,х2	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

 

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

Теорема

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

 

Z_max = Z*_min (4.8)

 

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

Так как

Z*_min = b₁y₁ + b₂y₂ +…….+b_my_m

где b₁, b₂,……,b_m – запасы ресурсов, которыми располагает производитель, а y₁, y₂, ……..,y_m – теневые цены этих ресурсов, то, с учетом (4,8) получаем формулу, устанавливающую взаимосвязь оптимального значения целевой функции (оптимального решения) с запасами ресурсов и их теневыми ценами.

 

Поскольку

Z_max = Z*_min = b₁y₁ + b₂y₂ +…….+b_my_m

 

то

Z_max = b₁y₁ + b₂y₂ +…….+ b_my_m (4.9)

 

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

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

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

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

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

Z_max = b₁ y₁

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

 

y_i = (4.10)

 

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

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

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

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

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

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