Анализ решения ЗЛП с помощью теории двойственности

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

Виды анализа, выполняемого на основе математической модели, приведены на рис. 4.2.

Рис. 4.2

Поясним некоторые вопросы. На этапе постановки задачи производится анализ с целью ответить на вопросы: «Что будет, если…?» и (или) «Что надо, чтобы …?». Анализ с целью ответа на первый вопрос называется вариантным анализом, на второй – решением по заказу.

Вариантный анализ бывает нескольких видов.

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

Под структурным анализом понимают решение задачи оптимизации при различной структуре ограничений.

Многокритериальный анализ – это решение задачи по разным ЦФ.

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

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

Кроме анализа, выполняемого на этапе постановки задачи, мощным средством, помогающим принять решение, является анализ полученного оптимального плана.

Пример 2.8. Фабрика выпускает продукцию двух видов: П₁ и П₂. Продукция обоих видов поступает в оптовую продажу. Дляпроизводства этой продукции используются три исходных продукта: А, В, С. Максимально возможные суточные запасы этих продуктов составляют 6, 8 и 5 т соответственно. Расходы продуктов (сырья) А, В, С на 1 тыс. изделий П₁ и П₂ приведены в таблице.

Исходный продукт	Расход исходных продуктов на 1 тыс. изделий (т)	Максимально возможный запас (т)
П1	П2
А
В
С		0,8

Изучение рынка сбыта показало, что суточный спрос на изделия П₂ не превышает спроса на изделия П₁ более, чем на 1 тыс. шт. Кроме того, установлено, что спрос на изделия П₂ не превышает 2 тыс. шт. в сутки.

Оптовая цена 1 тыс. изделий П₁ равна 3 тыс. руб., 1 тыс. изделий П₂ – 2 тыс. руб. Какое количество изделий (в тыс. шт.) должна производить фабрика ежесуточно, чтобы доход от реализации был максимальным?

Математическая модель этой задачи (в канонической форме):

= 3Х₁ + 2Х₂ + 0S₁ + 0S₂ + 0S₃ + 0S₄ + 0S₅ ® max;

Х₁ + 2Х₂ + S₁ = 6;

2Х₁ + Х₂ + S₂ = 8;

Х₁ + 0,8Х₂ + S₃ = 5;

–Х₁ + Х₂ + S₄ = 1;

Х₂ + S₅ = 2;

Х₁ ³ 0, Х₂ ³ 0 S_j ³ 0; j = 1...5.

Исходная и оптимальная симплекс-таблицы решения задачи симплекс-методом имеют вид

s	`N(s)	`CN(s)	x1	x2	x3	x4	x5	x6	x7	`b
			-1	4/5
		Dj(0)	-3	-2						f=0
					2/3 -1/3 -2/10 -1 -2/3	-1/3 2/3 -4/10 1/3				4/3 10/3 6/10 2/3
		Dj(2)			1/3	4/3				38/3

Двойственная к ней имеет вид:

= 6Y₁ + 8Y₂ + 5Y₃ + Y₄ + 2Y₅ + 0Y₆ + 0Y₇ ® min;

Y₁ + 2Y₂ + Y₃ – Y₄ – Y₆ = 3;

2Y₁ + Y₂ + 0,8Y₃ + Y₄ + Y₅ – Y₇ = 2;

Y_i ³ 0; i = 1...7.

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

= и =

На основании второй теоремы двойственности

max = min , т.е.

max = .

Из этой формулы следует, что двойственная переменная является коэффициентом при b_i и, следовательно, показывает, как изменится целевая функция при изменении запаса i-го продукта (ресурса) на 1. В литературе двойственные переменные принято называть двойственными оценками, или теневыми ценами.

Анализируя вектор , придем к таким выводам. При увеличении запаса продукта А на 1 т доход от реализации продукции увеличится на 1/3 тысяч рублей, а при увеличении запаса продукции В на 1 т доход увеличится на 4/3 тысячи рублей. Изменение же запаса С или изменение в соотношениях спроса не приведут к изменению дохода. Продукты А и В при этом являются дефицитными, а продукт С – не дефицитным.

Последний вывод можно было получить, рассуждая иначе. Если некоторый продукт используется не полностью, то есть имеется резерв, − значит дополнительная переменная в ограничении для данного продута будет больше нуля. В нашей задаче это дополнительные переменные: S₃* = 3/5 т (резерв для продукта С); S₄* = 3 т (резерв в разности спроса) и S₅* = 2/3 т (резерв спроса на продукцию П₂). Очевидно, что если бы запас продукта С был равен не 5, а 6 т, то резерв был бы равен не 3, а 4 т. При этом непроизошло бы увеличения значения ЦФ. Следовательно, для третьего ограничения исходной задачи соответствующая двойственная переменная У₃* = 0. Аналогично, У₄* = 0, У₅* = 0, что и подтверждается вектором .

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

Выясним теперь смысл дополнительных двойственных переменных. В нашей задаче обе основных переменных Х₁* и Х₂*вошли воптимальный план, поэтому дополнительные переменные У₆* и У₇* равны нулю. Это следует из теоремы 4 (о дополнительной нежесткости). Если бы какая-то из основных переменных исходной задачи оказалась равной нулю (данная продукция нерентабельна), то положительное значение соответствующей дополнительной переменной двойственной задачи указало бы, на сколько уменьшится ЦФ при принудительном выпуске единицы данной продукции.

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

С₁ = 3 + С_1.

Тогда в оптимальной таблице решения исходной задачи симплекс-разности будут иметь вид:

= 0; = 0; = = 1/3 -1/3 С₁;

= -0 = 4/3 + 2/3 С₁;

= 0; = 0 = 0

Полученный план останется оптимальным при условии ,
то есть

Решая эту систему неравенств, получим:

–2 £ С₁ £ 1.

Это условие определяет пределы изменения С₁, при которых сохраняется полученный оптимальный план. Если от пределов изменения приращения С₁ перейти к пределам изменения самой величины С₁ то получим:

min С₁ = 3 + min С₁ = 3 – 2 = 1

max С₁ = 3 + max С₁ = 3 + 1 = 4.

Таким образом, при изменении С₁ в пределах

1£ С₁ £ 4

будет по-прежнему выгодно выпускать продукцию П₁ в количестве 3 тыс. шт. При этом значение ЦФ будет

f () = 4/3×2 + 10/3 (3 + С₁) = 38/3 + 10/3 С_1.

Если выполнить аналогичные преобразования с С₂, то получим:

–1/2 ≤ С₂ ≤ 4,

откуда

3/2 С₂ 6

пределы изменения С₂, при которых будет выгодно выпускать продукцию П₂ в количестве 1 тыс. шт. Полученные пределы изменения С_j – это, кроме того, пределы справедливости дополнительных двойственных оценок.

Рассмотрим влияние на полученное решение изменения запасов продуктов (ресурсов). Пусть запас исходного продукта А равен (6 + А). Вектор свободных членов
= имеет вид:

= А

Тогда в оптимальной симплекс-таблице (см. на преобразование вектора ) вектор свободных членов примет вид:

= А =

Решение = будет допустимым, если все элементы вектора будут неотрицательны:

откуда

–2 ≤ А ≤ 1.

Перейдя к пределам изменения А, получим:

4 ≤ A ≤ 7.

Найденные пределы показывают границы, в которых может изменяться запас продукта А, чтобы номенклатура выпускаемой продукции (структура оптимального плана) осталась без изменений. Это означает, что при изменении запаса продукта А в найденных пределах оптимальным, то есть обеспечивающим наибольшую прибыль, является выпуск и продукции П₁, и продукции П₂, только в других количествах. Продукцию П₁ необходимо будет выпускать в таком количестве:

= 10/3 – 1/ А;

продукции П₂ – в количестве

= 4/3 + 2/3 А,

при этом доход будет

f () = 38/3 + 1/3 А.

Следовательно, если увеличить запас продукта А на 1 т ( А = 1), то для обеспечения максимизации прибыли выпуск продукции П₁целесообразно уменьшить до = 3 т, а выпуск продукции П₂ – увеличить до = 13 т. Доход от реализации продукции станет равным

f () = 13 тыс. руб.

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