2.3. анализ решения злп с помощью теории двойственности

2.3. анализ решения злп с помощью теории двойственности

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

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

Виды анализа

1

При постановке задачи

После получения оптимального решения

Вариантный анализ

Решения по заказу

Анализ решения

Параметрический

Анализ устойчивости

Структурный

Анализ пределов

Многокритериальный

При условных исходных данных

Рис.2.2.

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

Вариантный анализ бывает следующих видов:

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

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

Многокритериальный анализ это решение задачи по разным целевым функциям;

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

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

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

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

Исходный продукт

А В

С

Расход исходных продуктов

на 1 тыс. изделий (т)

1

2

П1 І П "

2 1

0,8

Максимально возможный запас (т)

6 8

5

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

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

Математическая модель этой задачи (в канонической форме) -/ (x)= 3Хі +2 Х2 +0 Si +0 S2 +0 S3 +0 S4 +0 S5 -> max Хі + 2Х2 + Si = 6 2Хі + Х2 + S2 = 8 Хі+0,8Х2 + S3 =5 -Хі + Х2 + S4 =і Х2 + S5 =2 Хі > 0, Х2 > 0 Sj > 0 ; j=L..5.

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

g (у) = 6Y1 +8 Y2 +5 Y3 + Y4 +2 Y5 +0 Y6 +0 Y7 -> min Y1 +2 Y2 + Y3 Y4 Y6 =3 2Y1 + Y2 + Y3 + Y4 + Y5 -0 Y7 =2 Yi > 0; i=L..7

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

X

(ЮІ3 ^ 4/3

0

0 3/5

3

2/3

и

Y"

(і/3 Ї

4/3 0 0 0 0 0

На основании второй теоремы двойственности max f (x)=min g (y), т.е.

m

max f (x) = £ by

і=і

Из этой формулы следует, что двойственная переменная у*

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

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

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

0, У5* = 0, что и подтверждается вектором Y .

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

Выясним теперь смысл дополнительных двойственных переменных. В нашей задаче обе основных переменных Хі* и Х2* вошли в оптимальный план, поэтому дополнительные переменные У6* и У7* равны нулю. Это следует из теоремы IV (о дополнительной нежесткости). Если бы какая-то из основных переменных исходной задачи оказалась равной нулю (данная продукция нерентабельна), то положительное значение соответствующей дополнительной переменной двойственной задачи указало бы, насколько уменьшится целевая функция при принудительном выпуске единицы данной продукции.

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

С = 3 + А С

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

А2)=0; А(22)=0; А(32) =

2

І I 3 + АС

0 0 0

( 2/3 -1/3 | | -1/5 -1

2/3JJ

=1/3 -1/3 АС1;

А(2):

2 ^ II 3 + АС,

0 0

W 0

(-1/3 Yl

2/3 -2/5 1

1/3 JJ

-0=4/3+2/3 А С

д(2)=0; А(б2)=0 А(72)=0

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

(2) — Г1/3 1/3АС > 0

условии А(2) > 0; j = 1,7 , то есть <! 1

J j [4/3 + 2/3АС1 > 0

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

-2 < А С1 < 1

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

min С1 = 3 max А С1 = 3 2=1.

max С1 = 3 + max А С1 =3 +1=4

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

будет по-прежнему выгодно выпускать продукцию П1. При этом значение целевой функции будет

f (Т) = 4/3*2 + 10/3 (3+ А С ) = 38/3 + 10/3 А С

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

-1/2 < А С2 < 4,

откуда

3/2 < А С2 < б

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

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

А А). Вектор свободных членов b(0) = Xn <0) имеет вид:

b

(0)

Гб^ (1ї 0

0

I

I

+

АА

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

( 4/3 } 10/3 3/5

3 2/3

+

( 4/3 + 2/3АЛ^ 10/3 1/3АЛ

-1/5 А А= 3/5 1/5АЛ

-1 3 -АЛ

2/3J [ 2/3 2/3АЛ_

(2)

Решение Xn<2) = b(2) будет допустимым, если все элементы вектора

будут неотрицательны.

f4/3 + 2/3АЛ> 0

10/31/3АЛ> 0 3/5 1/5АЛ> 0

3 АЛ > 0

2/3 2/3АЛ> 0

Откуда

-2 < А А < 1.

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

4 < A < 7.

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

х; =10/3 -1/А А; продукции П2 в количестве

XI =4/3+2/3 А А,

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

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

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

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

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