基于Lagrange函數(shù)的線性規(guī)劃對偶問題研究

向彥寧，李永玲

(重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶　401331)

基于Lagrange函數(shù)的線性規(guī)劃對偶問題研究

向彥寧，李永玲

(重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶401331)

摘要：運(yùn)用非線性規(guī)劃的Lagrange對偶原理，對線性規(guī)劃的弱對偶、強(qiáng)對偶進(jìn)行了證明，并通過極小-極大對偶性Lagrange函數(shù)詳細(xì)證明了線性規(guī)劃在不同的約束條件下的對偶形式。

關(guān)鍵詞：非線性規(guī)劃；線性規(guī)劃；Lagrange對偶；對偶問題

線性規(guī)劃問題通常被定義為：在滿足一定的約束條件下，求得目標(biāo)函數(shù)的最優(yōu)值。通?？紤]如下形式的線性規(guī)劃問題(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)是一對對稱的對偶規(guī)劃問題。

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

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

1預(yù)備知識

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

(3)

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

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

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

引理1設(shè)X是Rn的非空，α:Rn→R和g:Rn→Rm，h:Rn→Rl是凸的向量函數(shù)。如果下面的組1無解，則組2有解(u0，u，v)；如果u0>0，相反的結(jié)論成立[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線性規(guī)劃的對偶性質(zhì)

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

(4)

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

(5)

以下將非線性的 Lagrange對偶方法用在文獻(xiàn)[10]上，更加簡單地證明了線性規(guī)劃的強(qiáng)、弱定理。

定理1弱對偶性定理

注：原問題的可行解的目標(biāo)函數(shù)值是對偶問題目標(biāo)函數(shù)值的上界。

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

定理2強(qiáng)對偶性定理

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

(6)

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

(7)

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

(8)

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

本節(jié)先引入極小極大對偶性Lagrange函數(shù)[6]：

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

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

注：“!≥”表示不大于等于。因?yàn)橄蛄縝-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函數(shù)得出式(9)與(10)等價(jià)，式(11)與(12)等價(jià)，又因?yàn)槭?9)與(11)為一對Lagrange對偶，所以式(10)與(12)是一對對稱的對偶規(guī)劃問題。式(10)剛好就是為原問題(1)，式(12)為原問題的對偶問題(2)。

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

(13)

(14)

(15)

(16)

由上面極小極大對偶性得到問題(13)與問題(14)等價(jià)，問題(15)與問題(16)等價(jià)。又因?yàn)閱栴}(13)與問題(15)為一對Lagrange對偶，所以問題(14)與問題(16)是一對對稱的對偶規(guī)劃問題。

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

表1　另外4種情形

參考文獻(xiàn)：

[1]運(yùn)籌學(xué)教材編寫組.運(yùn)籌學(xué)[M].3版.北京：清華大學(xué)出版社，2005.

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

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

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

[5]劉年磊,毛國柱,趙林.基于強(qiáng)化區(qū)間線性規(guī)劃方法的流域環(huán)境系統(tǒng)管理優(yōu)化[J]. 天津大學(xué)學(xué)報(bào),2012(1):21-28.

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

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

[8]張立衛(wèi).錐約束優(yōu)化[M].北京:科學(xué)出版社，2010.

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

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

(責(zé)任編輯陳艷)

收稿日期：2014-12-24

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(11431004)

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

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

中圖分類號：O174

文獻(xiàn)標(biāo)識碼：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函數(shù)的線性規(guī)劃對偶問題研究[J].重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2015(7):116-119.

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