5. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

В данном разделе вводится важное понятие теории линейного программирования  - понятие двойственности. Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой задачи, которая применима к любой форме представления прямой задачи. В основу такого подхода положен тот факт, что использование симплекс-метода требует приведения любой ЗЛП к каноническому виду.

5.1. ОПРЕДЕЛЕНИЕ И ЭКОНОМИЧЕСКИЙ СМЫСЛ ДВОЙСТВЕННОЙ ЗЛП

Пусть прямая задача записана в каноническом виде:

Задачей, двойственной к ЗЛП (5.1)-(5.3), называется следующая ЗЛП

 не ограничены в знаке,  i=1..m                      (5.6)

Из приведенного определения следует, что двойственная ЗЛП строится по следующим правилам:

1) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, т.е. число переменных двойственной задачи равно числу ограничений прямой задачи.

2) Каждой переменной прямой задачи соответствует ограничение двойственной задачи, т.е. число ограничений двойственной задачи равно числу переменных прямой задачи.

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

4) Вектор  целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а вектор  правой части прямой задачи - вектором целевой функции двойственной задачи.

5) Если целевая функция прямой задачи максимизируется, то целевая функция двойственной задачи минимизируется, а ограничения имеют вид , и наоборот.

Прямая задача                                Двойственная задача

Пример 1   Пусть прямая задача записана в виде основной ЗЛП:

Max (`c,`x),

`Ax £`b                  (5.9)   

`x £`0

Приведем задачу (5.9) к канонической форме:

(5.10)

Тогда двойственная задача (ДЗ) будет иметь вид:

           (5.11)

.

Пример 2.

Прямая задача:

Прямая задача в каноническом виде:

S₁  0

Двойственная задача:

- не ограничены в знаке.

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

у₂ - не ограничена в знаке.

Пример 3.                   Прямая задача

min( 5X₁ - 2X₂ )

-   X₁ +   X₂  -3

2 X₁ + 3X₂   5

X_1,2  0

Прямая задача в канонической форме

min( 5X₁ - 2X₂ + 0 S₁ + 0 S₂)

- X₁ +   X₂  - S₁ = -3

2 X₁ + 3X₂ + S₂ =  5

Двойственная задача

max( - 3 У₁ +5 У₂ )

- У₁ + 2 У₂   5

У₁ + 3 У₂  -2

- У₁ + 0 У₂  0

0 У₁ + У₂  0

У_1,2  не ограничены в знаке.

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

max( - 3 У₁ +5 У₂ )

- У₁ + 2 У₂   5

У₁ + 3 У₂ -2

У₁  0 , У₂    0

Пример 4.    Прямая задача

max( 5X₁ + 6X₂ )

X₁ +  2X₂   5

- X₁ +  5X₂  3

4X₁ +  7X₂  8

X₁  не ограничена в знаке,  X₂  0

Прямая задача в канонической форме

max( 5- -5 + 6X₂ + 0 S₁ + 0 S₂)

+ 2X₂  = 5

-  + 5X₂ - S₁ =3

4+ 7X₂ + S₂ =8

Двойственная задача

min( 5 У₁ +3 У₂ + 8 У₃)

У₁ - 2 У₂ + 4 У₃   5

- У₁ +   У₂ - 4 У₃ -5

2 У₁ + 5 У₂ +7 У₃  6

0 У₁ -     У₂ +0 У₃  0

0 У₁ +  0У₂ +   У₃  0

У_1,2,3 - не ограничены в знаке

Заметим, что первое и второе ограничения двойственной задачи можно заменить одним ограничением в виде равенства, избыточные ограничения на У₂ и У₃  можно отбросить. Окончательно получаем:

min( 5 У₁ +3 У₂ + 8 У₃)

У₁ - 2 У₂ + 4 У₃   = 5

2 У₁ + 5 У₂ +7 У₃  6

У₁  не ограничена в знаке

У₂   0 , У₃ 0

Очевидно, что задача, двойственная к двойственной, совпадает с прямой.

5.2. ОСНОВНЫЕ ПОЛОЖЕНИЯ ТЕОРИИ ДВОЙСТВЕННОСТИ

Прямая задача                        Двойственная задача

 - не ограничен в знаке

Теорема 1. Пусть  - планы соответственно прямой и двойственной ЗЛП, тогда

                                (5.12)

Теорема 2. Пусть - планы соответственно прямой и двойственной ЗЛП и , тогда - решения соответственно прямой и двойственной задач.

Теорема 3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойственная (прямая) ЗЛП имеет решение, причем

                            (5.13)

Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

Теорема 4. Планы  соответственно прямой и двойственной ЗЛП являются оптимальными тогда и только тогда, когда

                                  (5.14)

Условия (2.14) называются условиями дополнительной нежесткости.

Замечание 1. Для основной ЗЛП и двойственной к ней ЗЛП условия нежесткости имеют вид:

(5.15)              

Замечание 2. Если прямая ЗЛП записана не в канонической форме, то условия дополнительной нежесткости для этой ЗЛП и двойственной к ней ЗЛП могут быть записаны в следующем виде:

если х_j^* > 0, то

если  то y_i^* = 0,

если y_i^*  > 0, то                                          (5.16)

если , то х_j^* = 0.

Получение оптимального плана двойственной задачи на основании теоремы 4

Пример 5. Рассмотрим задачу:

                                      (5.17)

Ее решение . Найдем решение задачи, двойственной к (5.17), используя теорему 4. Запишем двойственную к (5.17) задачу:

                         (5.18)

Применяем соотношение (2.16). Так как х₁^*=3/2 > 0, то 3у₁^*+4у₂^*+у₃^*=2. Далее, так как 3х₁^*+х₂^*=9/2+0 > 3, то у₁^*=0, и так как х₁^*+2х₂^*=3/2+0 < 3, то у₃^*=0. Итак, имеем:

3у₁^*+4у₂^*+у₃^*=2, у₁^*=у₃^*=0,

т.е. вектор  является решением задачи (5.18) на основании теоремы 4. Вычислим , что соответствует утверждению теоремы 3.

Пример 6.  Найти решение прямой и двойственной задачи.

Прямая задача. max = 5 Х1 +12Х2 +4 Х3 Х1 +2 Х2 +3Х3 10 2Х1   -  Х2 +3Х3  = 8 Х2,3 0 Х1  - не ограничена в знаке

Двойственная задача. min=10Y1+8 Y2 Y1 +2 Y2  =  5       (а)                        2 Y1 -    Y2  12 (б) Y1  + 3 Y2 4      (в) Y1  0                 (г) У2 - не ограничена в знаке.

Двойственная задача содержит две переменные, т.е. ее можно решать графически (рис.5.1)

Рис.5.1

Как видно из рис.5.1, область допустимых решений - планов двойственной ЗЛП - Q представляет собой отрезок АВ, лежащий на прямой Y₁ +2 Y₂ = 5, так как первое ограничение задается в виде равенства. Передвигая линию уровня функции 10 Y₁ +8 Y₂ = const в направлении, противоположном вектору =(10,8), получаем точку А, в которой достигается минимум функции . Находим координаты точки А, которая является пересечением двух прямых:

Y₁ +2 Y₂  =  5

2 Y₁ -  Y₂  = 12,

откуда  =29/5; =-2/5 и =54 .

Ипользуя теорему 4, находим решение исходной задачи. Так как >0  и <0, то оба ограничения прямой задачи имеют вид строгих равенств.

Х₁ +2 Х₂ +3Х₃  = 10            (5.19)

2Х₁  -  Х₂ +3Х₃ = 8

Так как третье ограничение двойственной задачи выполняется в виде строгого неравенства (29/5 - 6/5 = 24/5 > 4) , то  =0. Решая систему (5.19), получаем:

= 26/5; = 12/5; =0; f() = 54,8.

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

Пусть прямая задача имеет вид основной ЗЛП

(5.20)

  , .

Двойственная к ней ЗЛП имеет вид

                              (5.21)

.

Предположим, что ЗЛП (5.20) имеет решение. Решения обеих задач могут быть записаны в виде:

= = ;   =,

где ==(, … , )

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

, ,                                    (5.22)

откуда следует, что i -я компонента  решения двойственной ЗЛП есть (n + i)-я симплекс-разность матрицы , определяющей оптимальный план исходной  ЗЛП, а j-я симплекс-разность матрицы () равна разности между левой и правой частью ограничений двойственной ЗЛП:

= .     (5.23)

Пример 7. Решить следующую ЗЛП:

max ( 4Х₁  +   Х₂ + 2Х₃  +3 Х₄ )

Х₁  +  2 Х₂  +3Х₃  -  Х₅ +  Х₇ =50

-3Х₂ +3Х₃  +  Х₄ +5Х₅  + 4Х₇ =40                  (5.24)

4 Х₂  +  Х₅ + Х₆ - ½ Х₇ =24

.

Найти решение задачи двойственной к ЗЛП (2.24).

Так как расширенная матрица

=

системы линейных уравнений (5.24) является К-матрицей, то ЗЛП (5.24) можно решить симплекс-методом. Результаты решения приведены в таблице.

`N^(^s)	`C`N^(s)	`X`N^(s)	4	1	2	4	0	0	0	q^(s)
			`a1^(s)	`a2^(s)	`a3^(s)	`a4^(s)	`a5^(s)	`a6^(s)	`a7^(s)
1         4         50    4         3         10    6         0         24			1 2         3         0           -1        0          1   0          -3          1         1            2        0          4   0           4         0         0            1        1        -1/2							25   -   6
Dj^(0)	f(`x)=230		0	-2	3	0	2	0	6
1         4         38    4         3         28    2         1          6			1          0           3         0         -3/2     -1/2      5/4   0          0          1         1         11/4      3/4      29/8   0          1          0        0          1/4      1/8        -1/8
Dj^(1)	f(`x)=242		0	0	13	0	5/2	1/2	63/4

На первой итерации получен оптимальный план ЗЛП (5.24).

= (1, 4, 2); = (38, 28, 6),

 = ( 38, 6, 0, 28, 0, 0, 0);    f() = 242.

Запишем задачу, двойственную к (2.24)

min(50Y₁+10Y₂+24Y₃)                            

Y₁   4                                                   (5.25)

                                  2 Y₁ - 3 Y₂ + 3 Y₃   1

                                  3 Y₁ +   Y₂ + 4 Y₃   1

                                         Y₂3                                              (5.26)       

                                    -Y₁ +2 Y₂ +  Y₃   0

                                                 Y₃  0

                                     Y₁ + 4 Y₂ - ½ Y₃   0

 не ограничены в знаке.        (5.27)

Ограничения (5.27) являются избыточными, следовательно, их можно отбросить.

Находим решение ЗЛП (5.25) по формуле

== (4, 3, 1) = (4, 3, 1/2),

или (2.22):

= (0+4, 0+3, ½ +0) = (4, 3, 1/2)

= 50*4 + 10*3 + 24* ½  =242

5.3. АНАЛИЗ РЕШЕНИЯ ЗЛП С ПОМОЩЬЮ ТЕОРИИ ДВОЙСТВЕННОСТИ

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

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

Рис.5.2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Х₁ + 2Х₂ + S₁  =  6

2Х₁ +  Х₂ + S₂   = 8

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

-Х₁ +  Х₂ + S₄    =1

Х₂  + S₅   =2

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

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

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

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

Y₁ +2 Y₂ + Y₃ - Y₄  - Y₆ =3

2Y₁ + Y₂ + Y₃ + Y₄  + Y₅ -0 Y₇ =2

Y_i 0; i=1…7

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

= и = 

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

max =min , т.е.

мax =

Из этой формулы следует, что двойственная переменная   является коэффициентом при  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, что и подтверждается вектором .

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

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

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

С₁ = 3 + С₁

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

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

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

=0; =0; =0

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

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

-2С₁1

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

min С₁ = 3 -  max С₁  = 3 - 2=1.

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

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

1 С₁  4

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

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

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

-1/2 С₂  4,

откуда

3/2 С₂  6

- пределы изменения С₂, при которых будет выгодно выпускать продукцию П₂. Полученные пределы изменения С_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 тыс.руб

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

5.4. АНАЛИЗ РЕШЕНИЯ ЗЛП НА ОСНОВЕ ОТЧЁТОВ MS EXCEL

Рассмотрим следующую ЗЛП:

 =7,5х₁+3х₂+6х₃+12х₄®max

2х₁+х₂+0,5х₃+4х₄ £ 2400

х₁+5х₂+3х₃ £  1200

3х₁+6х₃+х₄ £  2000

x_1,2,3,4 ³0

Начнём с отчёта результатов. Приведём его вид:

Единственное, что здесь следует прокомментировать, это статус ресурсов. Т.к. все ограничения на ресурсы являются связанными, то это говорит о том, что все ресурсы были использованы. Другими словами, все ресурсы являются дефицитными.

Рассмотрим отчёт по устойчивости:

Нормированная стоимость (часто, редуцированная стоимость, от английского: cost reduction – уменьшение затрат) представляет собой дополнительные двойственные переменные. Они показывают, насколько по модулю уменьшится целевая функция при принудительном выпуске единицы данной продукции. В нашем примере нормированная стоимость по продукту А не равна нулю. Следовательно, если мы будем принудительно выпускать единицу продукта А, то целевая функция уменьшится на 0,062. Другими словами, выпуск продукта А является нерентабельным (неприбыльным).

Допустимое увеличение показывает, насколько максимально можно увеличить коэффициент целевой функции (цену продукта), чтобы структура оптимального плана осталась прежней. Допустимое уменьшение, наоборот, показывает, насколько можно максимально уменьшить коэффициент ЦФ, чтобы осталась прежней структура оптимального плана. Например, в нашей задаче, чтобы  выпуск продукта А оставался нерентабельным, максимально допустимое увеличение его цены составляет приблизительно 0.06. Допустимое же уменьшение представляет собой огромное число. Это понятно, т.к., ещё больше уменьшив цену нерентабельного продукта, сделать его рентабельным невозможно.

Теневая цена в отчётах Excel представляет собой двойственные переменные. Они показывают, как изменится целевая функция при изменения запаса ресурса на единицу. Понятно, что если ресурс использован полностью, то теневая цена этого ресурса положительна. Например, если мы увеличим запас ресурса I на единицу, то ЦФ возрастёт на 2,628 (ресурс I является самым приоритетным). Допустимое увеличение и уменьшение показывают границы, в которых могут изменяться ресурсы, чтобы структура оптимального решения, т.е. номенклатура выпускаемой продукции, остались без изменений.

Рассмотрим последний отчёт – отчёт по пределам:

В отчёте указаны значения ЦФ при выпуске данного типа продукции на нижнем и верхнем пределах. Так, значение ЦФ 6971,901 соответствует тому, что продукт С не выпускается.

Отчёты Excel обеспечивают всей необходимой информацией для проведения полного анализа линейной модели.

Домашнее задание №15

Решить с помощью MS Excel соответствующий вариант из домашнего задания №8. К ответам на вопросы приложить распечатку отчетов.