基于Lagrange函數的線性規劃對偶問題研究

向彥寧，李永玲

(重慶師范大學 數學學院，重慶　401331)

基于Lagrange函數的線性規劃對偶問題研究

向彥寧，李永玲

(重慶師范大學 數學學院，重慶401331)

摘要：運用非線性規劃的Lagrange對偶原理，對線性規劃的弱對偶、強對偶進行了證明，并通過極小-極大對偶性Lagrange函數詳細證明了線性規劃在不同的約束條件下的對偶形式。

關鍵詞：非線性規劃；線性規劃；Lagrange對偶；對偶問題

線性規劃問題通常被定義為：在滿足一定的約束條件下，求得目標函數的最優值。通常考慮如下形式的線性規劃問題(LP)[1]：

(1)

其中x=(x1，x2，…，xn)t，A=(aij)m×n，b=(b1，b2，…，bm)t，c=(c1，c2，…，cn)t。

定義其對偶問題(DP)為[1]：

(2)

其中y=(y1，y2，…，ym)t為列向量。問題(2)為原問題(1)的對偶問題，問題(1)與問題(2)是一對對稱的對偶規劃問題。

在線性規劃理論中，線性規劃的對偶問題是非常重要的部分，但在一般的文獻和高校教材中[1-5]，線性規劃的對偶問題是求最大值、最小值，約束條件為等式和不等式，變量是大于等于零或者是任意的，因此對于不同約束條件形式的對偶證明比較繁瑣。

本文在第2節中給出了非線性規劃的Lagrange對偶；在第3節中證明了線性規劃原問題(1)的對偶性質(強弱定理)；第4節詳細證明了線性規劃在不同約束條件下的對偶。

1預備知識

考慮下面的非線性規劃問題(NLP)[9]：

(3)

其中函數f:Rn→R，g:Rn→Rm，h:Rn→Rl是向量函數，則Lagrange對偶問題(NDP)為[9]：

其中θ(u，v)=inf{f(x)+utg(x)+vth(x):x∈X}。

注：Lagrange對偶函數θ對某些向量(u，v)可取值為-∞，與不等式約束g(x)≤0相應的Lagrange乘子u是非負的，與等式約束h(x)=0相應的Lagrange乘子v不受符號影響。

引理1設X是Rn的非空，α:Rn→R和g:Rn→Rm，h:Rn→Rl是凸的向量函數。如果下面的組1無解，則組2有解(u0，u，v)；如果u0>0，相反的結論成立[9]。

組1α(x)<0，g(x)≤0，h(x)=0，對于某個x∈X。

組2u0α(x)+utg(x)+vth(x)≥0，對任意的x∈X，(u0，u)≥0，(u0，u，v)≠0。

2線性規劃的對偶性質

在本節中通過非線性規劃的Lagrange對偶來研究原問題(1)與對偶問題(2)之間的關系。原問題(1)可變形為：

(4)

其中x=(x1，x2，…，xn)t，A=(aij)m×n，b=(b1，b2，…，bm)t，c=(c1，c2，…，cn)t。按照非線性規劃的對偶原理引入Lagrange乘子u≥0，其Lagrange對偶問題為：

(5)

以下將非線性的 Lagrange對偶方法用在文獻[10]上，更加簡單地證明了線性規劃的強、弱定理。

定理1弱對偶性定理

注：原問題的可行解的目標函數值是對偶問題目標函數值的上界。

推論2如果inf{ctx|Ax-b≤0，x≥0}=-∞，則對任何u≥0，θ(u)=-∞。

定理2強對偶性定理

min{ctx:Ax≤b，x≥0}=max{θ(u):u≥0}

(6)

證明設K=inf{ctx:Ax-b≤0，-x≤0}，如果k=-∞，由定理1的推論2得maxθ(u)=-∞，故式(6)成立。現假設K為有限值，則考慮系統：

(7)

按照K的定義，ctx≥K，所以式(7)無解。由引理1，必存在(a0，a)≥0，a0，a不能同時為0，a=(a1，a2)，使得

(8)

3線性規劃在不同的約束條件下的對偶形式

本節先引入極小極大對偶性Lagrange函數[6]：

設x∈X?Rn，y∈Y?Rn，X，Y是非空集合，則極小極大對偶性Lagrange函數為

接下來考慮不同約束條件下的線性規劃問題LP和DP。

注：“!≥”表示不大于等于。因為向量b-Ax=(c1，c2，…，cm)t≥0，表示每個ci≥0(i=1，2，…，m)，b-Ax=(c1，c2，…，cm)t!≥0表示?ci<0，故“!≥”不等于“<”。

1) 約束條件為Ax≤b，x≥0的原、對偶問題：

(9)

(10)

(11)

(12)

其中y=(y1，y2，…，ym)t為列向量。通過極小極大對偶性Lagrange函數得出式(9)與(10)等價，式(11)與(12)等價，又因為式(9)與(11)為一對Lagrange對偶，所以式(10)與(12)是一對對稱的對偶規劃問題。式(10)剛好就是為原問題(1)，式(12)為原問題的對偶問題(2)。

2) 約束條件為Ax=b，x≥0的原問題LP:

(13)

(14)

(15)

(16)

由上面極小極大對偶性得到問題(13)與問題(14)等價，問題(15)與問題(16)等價。又因為問題(13)與問題(15)為一對Lagrange對偶，所以問題(14)與問題(16)是一對對稱的對偶規劃問題。

同樣按照極小極大對偶性Lagrange函數原理可以得到如表1所示的另外4種情形。

表1　另外4種情形

參考文獻：

[1]運籌學教材編寫組.運籌學[M].3版.北京：清華大學出版社，2005.

[2]劉云志,郭嗣琮.含直覺模糊彈性約束的模糊線性規劃求解[J]. 系統工程理論與實踐,2013(8):2027-2032.

[3]吳東華,夏洪山.基于多目標模糊線性規劃求解方法的飛機排班問題研究[J].計算機科學，2012(1)：234-238.

[4]盛仲飆 .基于Matlab的線性規劃問題求解[J]. 計算機與數字工程,2012(10):26-27,80.

[5]劉年磊,毛國柱,趙林.基于強化區間線性規劃方法的流域環境系統管理優化[J]. 天津大學學報,2012(1):21-28.

[6]李師正，李剛.非線性規劃的對偶原理[J].山東科學，1999，12(2):1-7.

[7]李師正，李剛.帶有等式約束的非線性規劃的對偶問題[J].山東科學，1999，12(3):1-5.

[8]張立衛.錐約束優化[M].北京:科學出版社，2010.

[9]Bazaraa M S，Sherali H D，Shetty C M.Nonlinear programming:theory and algorithms[M].[S.l.]:John Wiley & Sons，2013.

[10]盧開澄.線性規劃[M].北京:清華大學出版社，2009.

(責任編輯陳艷)

收稿日期：2014-12-24

基金項目：國家自然科學基金資助項目(11431004)

作者簡介：向彥寧(1990—),男,重慶萬州人,碩士研究生,主要從事運籌學和控制優化研究。

doi:10.3969/j.issn.1674-8425(z).2015.07.021

中圖分類號：O174

文獻標識碼：A

文章編號：1674-8425(2015)07-0116-04

DualProblemResearchofLagrangeFunction
BasedonLinearProgramming

XIANGYan-ning,LIYong-ling

(SchoolofMathematicalSciences，ChongqingNormalUniversity，Chongqing401331,China)

Abstract:Using the Lagrange principle of duality for nonlinear programming, linear programming duality of weak and strong duality was proved, and using the min-max Lagrange duality function, we proved that there is dual under different constraints in linear programming.

Key words:nonlinear programming; linear programming; Lagrange duality; dual problem

引用格式：向彥寧，李永玲.基于Lagrange函數的線性規劃對偶問題研究[J].重慶理工大學學報：自然科學版，2015(7):116-119.

Citationformat：XIANGYan-ning,LIYong-ling.DualProblemResearchofLagrangeFunctionBasedonLinearProgramming[J].JournalofChongqingUniversityofTechnology:NaturalScience，2015(7):116-119.