Двойственная задача линейного программирования

1.4.1 Пример прямой и двойственной задачи линейного программирования

Обратимся к задаче рационального использования ресурсов. Пусть для осуществления l технологических процессов T₁,…,T_l  предприятию требуется m ресурсов S₁,…, S_m. Запасы ресурсов каждого вида ограничены и равны b₁,…,b_m.

Известен расход ресурсов {a_ij}, i= , j=  на единицу продукции по каждому технологическому процессу и стоимость единицы продукции каждого типа c_j, j= . Тогда, как нам известно, задача определения такого плана выпуска продукции x_j, при котором доход от ее реализации будет максимальным, является задачей линейного программирования:

            ;                             (1.37)

                   ;                    (1.38)

             x_j  0, j =

и ее решение может быть найдено симплекс-методом.

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

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

 Ясно, что варьируя план выпуска продукции, мы тем самым варьируем теневые цены используемых ресурсов, а потому ставится задача нахождения оптимальных теневых цен, которые соответствуют максимальному доходу предприятия, то есть оптимальному распределению ресурсов. Оптимальные теневые цены называют объективно обусловленными или оптимальными оценками. Построим математическую модель для определения оптимальных теневых цен.

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

                     .                    (1.39)

Оптимальными теневыми ценами естественно считать такие, которые минимизируют общую теневую стоимость ресурсов, то есть величину

                        g^*= b_i y_i  min.                    (1.40)

Задача нахождения минимума целевой функции (1.40) при условиях (1.39) представляет собой задачу линейного программирования и называется двойственной по отношению к задаче (1.37)–(1.38).

 1.4.2 Общая формулировка прямой и двойственной задачи

 Дадим достаточно общее определение двойственной задачи по отношению к прямой, заданной в виде:

                    f = c₁x₁ + c₂x₂ + …+ c_nx_n  max                   (1.41)    

при условиях

                                          a₁₁ x₁ + a₁₂ x₂  +…+  a_1n x_n < R₁ > b₁   

                                           a₂₁x₁ + a₂₂ x₂ +…+  a_2n x_n < R₂ > b₂

                                          . . . . . . . . . . . . .                                   (1.42)

                                          a_m1 x₁ + a_m2 x₂ +…+ a_mn x_n < R_m > b_m

                                          x₁  0, x₂  0 ,…, x_n  0,

где: R1,R2, …, R_n – операция отношения вида либо =, либо ≤ одновременно.

Очевидно, что любую задачу линейного программирования можно представить в одной из двух указанных форм. Тогда двойственной по отношению к задаче (1.41)−(1.42) будем называть задачу:

                                        f ^*=b₁y₁+b₂y₂+…+b_my_m  min                      (1.43)

при условиях

                                  a₁₁y₁ + a₂₁y₂ +…+ a_m1y_m  c₁

                               a₁₂y₁ + a₂₂y₂ +…+ a_m2y_m  c₂

                              ……………………………                                  (1.44)

                              a_1ny₁ + a_2ny₂ +…+ a_mny_m    c_n

и, если в прямой задаче R_i ( ), i= , то

                               y₁  0, y₂  0,…, y_n  0 .                              (1.45)

Сформулируем правила построения двойственной задачи:

а) целевая функция исходной задачи (1.41)−(1.42) задается на максимум, а целевая функция двойственной задачи (1.43)−(1.45) – на минимум;

б) матрица системы сильных ограничений двойственной задачи получится из матрицы системы ограничений прямой задачи транспонированием;

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

г) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены системы сильных ограничений прямой задачи, а правыми частями системы сильных ограничений двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи. Отметим, что если все R_i≡( ) и, следовательно, в двойственной задаче выполнены условия (1.45) – переменные неотрицательны, то пара задач (1.41)–(1.42) и (1.43)–(1.45) называется симметричной.

1.4.3 Свойства двойственной задачи

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

ТЕОРЕМА 1.2. Значение целевой функции задачи (1.41)–(1.42) при любом допустимом плане x не превышает значения целевой функции задачи (1.43)–(1.45) при любом ее допустимом плане y: f( ) f ^*(y).

 Если для каких-нибудь x и узначения целевых функций совпадают, т.е. f( ) = f ^*(y), то . x- оптимальное решение (1.41)–(1.42),y– оптимальное решение (1.43)–(1.45).

Доказательство. Пусть x=(x₁,x₂,…,x_n) – допустимое решение задачи (1.41)–(1.42), у=(y₁,y₂,….,y_m) – допустимое решение задачи (1.43)–(1.45). Подставим решение x в ограничения (1.42), умножим первое равенство на y₁, второе на y₂,…, m–е на y_m и сложим полученные равенства:

Перегруппируем слагаемые в левой части:

.     (1.46)

Так как y – допустимое решение задачи (1.43)–(1.45), то для любого j (j=1,2,…,n) , имеем:

Заменяя в (1.46) суммы, заключенные в скобки, соответствующими c_j и учитывая, что x_j ≥ 0 , получаем:

,

или, что тоже самое f(x)≤f ^*(y). Первая часть теоремы доказана.

Пусть для каких-нибудь x,y имеем: (c,x^′)>(b^T,y). Допустим от противного, что x не является оптимальным решением задачи (1.41)–(1.42). Это значит, что есть такое другое допустимое решение x^′задачи (1.41)–(1.42), что

(c,x^′) > (c,x) = (b^T,y),

а это противоречит первой части данной теоремы. Следовательно, при нашем условии x– оптимальное решение задачи (1.41)–(1.42). Аналогично показывается, что y - оптимальное решение задачи (1.43)–(1.45).Теорема доказана.

ТЕОРЕМА 1.3. Если одна из пар двойственных задач (1.41)–(1.42) или (1.43)–(1.45) имеет оптимальное решение, то и другая также имеет оптимальное решение, причем их оптимумы совпадают (max f=min f ^*).

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

Доказательство. Ввиду взаимной двойственности задач (1.41)–(1.42) и (1.43)–(1.45) достаточно провести доказательство, принимая за исходную одну из задач. Пусть, например, задача (1.41)–(1.42) имеет оптимальные решения, и  – одно из них, найденное симплекс-методом, и – его базис. Тогда на последней итерации имеем  (j=1,2,…,n) так что z_j ≥ c_j, j=1,2,…,n, или, в векторной форме

.           (1.47)

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

,

где – матрица, обратная к базисной матрице , A –матрица системы ограничений-уравнений задачи (1.42): .Следовательно, из (1.47) имеем:

                         (1.48)

Введем обозначение:

Тогда неравенство (1.48) принимает вид

Оно означает, что вектор  является допустимым решением задачи (1.43)-(1.45).

Докажем, что y– оптимальное решение задачи (1.43) – (1.45). Имеем:

.

Таким образом, значение целевой функции задачи (1.43) –(1.45) при её допустимом решении y совпадает с значением целевой функции задачи (1.41)–(1.42) при её допустимом решении . Согласно теореме 1.2 это означает, что y оптимальное решение задачи (1.43)–(1.45). Первая часть теоремы доказана.

Докажем вторую её часть. Пусть известно, что целевая функция, например, задачи (1.41)–(1.42) не ограничена сверху на допустимом множестве. Допустим, от противного, что задача (1.43)–(1.45) имеет при этом допустимое решение, и пусть y – одно из них. Ввиду неограниченности целевой функции задачи (1.41)–(1.42) найдётся такое допустимое её решение x, для которого значение целевой функции будет больше числа (b,y):

,

что противоречит теореме 1.2. Теорема доказана.

При доказательстве первой части теоремы мы установили следующее: если B – базисная матрица оптимального опорного решения канонической задачи (1.41)–(1.42), то

– оптимальное решение двойственной к (1.41)–(1.42) задачи (1.43)-(1.45).  Этим фактом мы будем пользоваться в дальнейшем.

Рассмотрим, в качестве примера, следующую задачу и двойственную к ней.

       f =5x₁+10x₂ max                      f ^*=96y₁+144y₂+48y₃ min

                                    4x₁ + 3x₂  96                                4y₁ + 5y₂ + y₃  5                                           

                                    5x₁ + 8x₂  144                              3y₁ + 8y₂ + 4y₃  10                                                    

                                     x₁ + 4x₂  48                                   y₁  0, y₂  0, y₃  0.

         x₁  0,  x₂  0.

Оптимальное решение прямой задачи, приведенное в последней симплекс таблице: x^T=(16,8,8,0,0) получено в базисе ₃, ₁, ₂. Найдем матрицы B,

                             1 4 3                                               12 –13 17                       

                   B =   0 5 8 ;                = (1/12) 0  4 –8 ;       

                             0 1 4                                               0 –1 5                                                

                              y^* = c_B = (0, 5/6, 5/6);

                                                           max f = f (x^*) = 160 = min f  ^*(y^*).

В том случае, когда среди векторов ₁, ₂, …, _n прямой задачи(1.41)−(1.42) имеется m – единичных

( , ,…, ), решение двойственной задачи может быть найдено проще, а именно, компоненты вектора

                                y_k=α_jk+c_jk, k = ;

                                y^*=(y₁,…, y_m)^T,

где α_jk – элементы строки оценок в последней симплекс-таблице решения прямой задачи, а c_jk – соответствующие коэффициенты целевой функции прямой задачи.

Рассмотрев предыдущий пример, можем убедиться, что поскольку в исходной задаче векторы ₃, ₄, ₅ - единичные, то:  

                                                              y₁ = α₃ + c₃ = 0 + 0 = 0

                                                            y₂ = α₄ + c₄ = 5/6 + 0 = 5/6

                                                            y₃ = α₅ + c₅ = 5/6 + 0 = 5/6

.                                                            y^*= (0; 5/6; 5/6).

1.4.4 Анализ чувствительности

Нас будет интересовать вопрос: какое воздействие окажут изменения, вносимые в те или иные параметры задачи линейного программирования, на ее решение, на решение двойственной задачи, на оптимальные значения целевой функции ? А именно, изучим:

а) воздействие дополнительного количества дефицитного ресурса;

б) воздействие дополнительного количества недефицитного ресурса;

в) воздействие изменений в коэффициентах целевой функции.

Для наглядности исследований рассмотрим прямую и двойственную задачи линейного программирования и их геометрическое решение (рисунок 1.5).

Пример 1.5.

                         f  = 2x₁ + 3x₂  max                                 f  ^*= 4y₁ + 2y₂  min

                              x₁ + x₂  4                                               y₁ – y₂    2     

                            –x₁ + x₂  2                                               y₁ + y₂  3

                              x₁ 0, x₂  0                                          y₁ 0, y₁ 0

               x₂                                                                 y₂

                                                                                                            f ^*= 4y₁ + 2 y₂ =c₀ =11

                 M(1,3)                                                                        

                               f = 2x₁ + 3x₂ = 11                              M(2.5;0.5)           

                                                                                            x₁                                                                                            y₁

                                         f ^* = (4 +∆b₁) y₁ + (2 + ∆b₂) y₂ = c₁

Рисунок 1.5 - Решение задачи линейного

программирования геометрическим способом.

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

Таблица 1.6 – Заключительная симплекс-таблица

Базис	cB	bопорн.		c 1	c2	c3	c4
				2	3	0	0
				1	2	3	4
1	2	1		1	0	1/2	–1/2
2	3	3		0	1	1/2	1/2
		f = 11	αj	0	0	2,5	0,5
						y1	y2

Очевидно, что значение целевой функции задачи линейного программирования f = f (b₁, b₂ ,…, b_m) зависит, вообще говоря, от запасов ресурсов. Изменение ресурсов b_i на малую величину ∆b_i, i = 1,2,...,m ведет к изменению значения max f =min f ^*, но изменение min f ^*происходит, при малых ∆b_i, не за счет изменения точки, в которой достигается min f ^* (допустимая область двойственной задачи вообще не изменится при изменении b_i), а за счет изменения наклона поверхности (линии) уровня целевой функции f ^*, коэффициенты которой зависят от b_i+∆b_i.

Следует отметить, что при больших изменениях b_i, i= или даже некоторых из них, оптимальное решение двойственной задачи может перейти в другую угловую точку. Нас будет интересовать в каких пределах изменение запасов b_i на величину ∆b_i не влечет изменения двойственных оценок (теневых цен). Множество таких значений ∆b_i будем называть областью устойчивости решения двойственной задачи.

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

В рассмотренном примере увеличение ∆b₂ на величину большую 2, то есть b₂+∆b₂>4, при фиксированном b₁=4, перемещает оптимальное решение двойственной задачи в точку y₁=3, y₂=0 и min f ^*= max f =12. Таким образом, увеличение на 1 единицу произошло за счет увеличения ресурса b₂ на величину ≥2. Причем, начиная со значения b₂=4, этот ресурс перестает быть дефицитным. При 0<∆b₂<2 и ∆b₁>0 точка минимума f ^* не меняется, а значение целевой функции f ^* увеличивается, а следовательно, увеличивается и значение целевой функции прямой задачи. Это и есть область устойчивости двойственных оценок дефицитных ресурсов. Здесь же отметим, что если b₁=4, b₂>4, то уменьшая недефицитный ресурс b₂ на величину ∆b₂<0, мы при b₂+∆b₂<4 добьемся того, что оптимальное решение двойственной задачи будет достигаться в точке (2,5; 0,5) и ресурс y₂ станет дефицитным, но значение min f ^*= max f  уменьшится.

В общем случае рассмотрим иной подход к изучению влияния ∆b_i на область устойчивости двойственных оценок. Пусть B– матрица векторов исходной задачи, составляющих базис, в котором решение прямой задачи оптимально. Тогда последняя симплекс-таблица 1.7 формально может быть получена так:

Таблица 1.7 – Итоговая симплекс-таблица

Базис	cB	Опорное решение	c1	c2	…	cn
			A1	A2	…	An
…	...	b	A1	A2	…	An
Оценка			α1	α2	…	αn

Очевидно, что изменения запасов ресурсов на величины ∆b_i не окажет влияния ни на разложения векторов ₁ ,…, _n по базису, ни на значения A_j, а стало быть и на значения двойственных оценок, если только          ( +∆ ), будет оставаться допустимым опорным решением задачи линейного программирования, т.е. его компоненты будут оставаться неотрицательными. Условия неотрицательности компонент вектора ( +∆ ) позволит определить область устойчивости двойственных оценок и выяснить порознь влияние дополнительного количества дефицитных и недефицитных ресурсов. В рассматриваемом примере

                 ,   , .

Оптимальное опорное решение (значения базисных переменных):

.

Пусть мы внесли изменения в вектор правых частей (увеличили запасы ресурсов)

,

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

при условиях:

                                                                     1 + (1/2)∆b₁ –(1/2)∆b₂  0

                                                                     3 + (1/2)∆b₁ + (1/2)∆b₂  0

                                         ∆b₁  0, ∆b₂  0.

Область устойчивости двойственных оценок в этом случае нетрудно изобразить геометрически (рисунок 1.6).

Рисунок 1.6 – Область устойчивости

Итак, область устойчивости: ∆b₁ – любое неотрицательное и ∆b₂ может принимать значения 0 ∆b₂≤2+∆b₁. В частности, при ∆b₁ = 0, 0≤∆b₂≤2 .

 В задачах большей размерности мы сможем, вообще говоря, лишь проверять попадают ли компоненты вектора  (b+∆b) в область устойчивости.

Обратимся к вопросу влияния вариации коэффициентов целевой функции (c₁,…,c_n) прямой задачи на оптимальное решение. В частности нас интересует вопрос устойчивости решения прямой задачи относительно вариации коэффициентов целевой функции. Легко видеть, что вариация c₁,…,c_n не оказывает влияния на допустимую область задачи линейного программирования и нас интересует область изменения ∆c₁, ∆c₂,…, ∆c_n , в которой точка достижения оптимального решения не изменится. Очевидно, что если рассматривать в качестве прямой задачи двойственную, то решение проблемы будет аналогично рассмотренному выше (роль b₁,…,b_m будут играть c₁,…, c_n). Например, в рассмотренном примере базисом оптимального решения двойственной задачи будут естественно векторы A₁=(1,1)^T и A₂=(−1,1)^T. Оптимальное опорное решение (значение базисных переменных)

.

Для изучения устойчивости внесем изменения в вектор цен

с + ∆c = (2 + 3∆c₁ + ∆c₂).

Найдем оптимальное опорное решение новой двойственной задачи (значение базисных переменных).

  .

Потребуем:                   

5/2 + (1/2)∆c₁ + (1/2)∆c₂  0

1/2 − (1/2)∆c₁ + (1/2)∆c₂  0

∆c₁ 0, ∆c₂ 0,

что определяет область устойчивости решения прямой задачи относительно вариации коэффициентов (см. рисунок 1.7). 

                                                                                    ∆c₂                     

                                                                        Область

                                                              устойчивости

                                  -5           -1   1                    ∆c₁

                                                               -5

Рисунок 1.7 − Область устойчивости

1.4.5 Экономическая интерпретация двойственных задач

Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере.

Для производства продукции двух видов А и В используются ресурсы трех видов I,II,III. Запасы ресурсов – b_i, затраты ресурсов a_ij на производство единицы продукции каждого вида и цена c_j единицы продукции приведены в таблице 1.8.

Таблица 1.8 – Таблица выпускаемой продукции

Требуется так спланировать производство, чтобы прибыль от реализации продукции была максимальной. Оценить теневые цены ресурсов и произвести анализ решения двойственной задачи. Обозначим  план выпуска продукции А, В, С, y_i – теневые цены ресурсов I,II,III типа. Тогда прямая и двойственная задачи имеют вид:

f = 2x₁ + x₂  max               f ^* = 10y₁ + 30y₂ + 8y₃  min

x₁ + x₂  10                            y₁ + 2y₂ + y₃  2

2x₁ + 4x₂  30                        y₁ + 4y₂ + 0y₃  1

x₁  8                                      y₁  0

x₁  0                                      y₂  0

x₃  0                                      y₃  0.

Решение прямой и двойственной задач приведено в заключительной симплекс-таблице 1.9.

 Таблица 1.9 – Симплекс-таблица

Оптимальный план производства продукции вида А: x₁=8; вида В: x₂=2; f_max=18. Ресурсы типа I и III имеют теневые цены, большие нуля, поэтому дефицитны и в оптимальном плане используются полностью, что легко проверить по 1-му и 3-му ограничениям прямой задачи.

Ресурс II типа имеет теневую цену равную нулю, является недефицитным и в оптимальном плане недоиспользуется в объеме 6 ед., что легко вычисляется из 2-го ограничения прямой задачи. Увеличение запасов дефицитного ресурса I типа ведет к увеличению прибыли от дополнительно произведенной продукции на одну единицу за счет следующих изменений в плане выпуска продукции: выпуск продукции вида В увеличивается на одну единицу, выпуск продукции вида А остается на прежнем уровне, а использование ресурса II типа увеличивается на 4 единицы (результаты получены из компонент столбца A₃ и легко проверяются непосредственной проверкой). По аналогии при увеличении запасов дефицитного ресурса III типа на одну единицу прибыль от реализации дополнительно произведенной по новому оптимальному плану продукции также возрастает на одну единицу, при этом, как видно из последнего столбца симплекс – таблицы 1.9 необходимо увеличить выпуск продукции вида А на одну единицу и одновременно выпуск продукции вида В сократить на одну единицу. Использование ресурса II типа уменьшится еще на 2 единицы.