• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2015-12-31 08:10:36向彥寧李永玲
    關(guān)鍵詞:線性規(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.

    猜你喜歡
    線性規(guī)劃
    基于大學(xué)生選課問題的線性規(guī)劃模型
    集體活動的時間規(guī)劃
    新課程概率統(tǒng)計(jì)學(xué)生易混淆問題
    東方教育(2016年10期)2017-01-16 20:33:22
    基于多樞紐輪輻式運(yùn)輸網(wǎng)絡(luò)模型的安徽省快遞網(wǎng)絡(luò)優(yōu)化
    線性規(guī)劃常見題型及解法
    首都機(jī)場安全環(huán)建設(shè)與管理分析
    基于多元線性規(guī)劃的大學(xué)生理財(cái)計(jì)劃問題研究
    中國市場(2016年22期)2016-07-07 05:11:38
    例談線性規(guī)劃思想在高中數(shù)學(xué)教學(xué)中的應(yīng)用
    擬定生產(chǎn)計(jì)劃的多變量條件下的線性規(guī)劃模型
    商(2016年7期)2016-04-20 09:16:59
    大型超市前端收銀排班優(yōu)化策略
    静安区| 松阳县| 惠来县| 色达县| 大足县| 大关县| 峨山| 本溪| 韶关市| 井研县| 仁怀市| 潼关县| 洱源县| 新竹市| 通渭县| 大方县| 盐城市| 青浦区| 华池县| 江口县| 辽中县| 名山县| 桃源县| 福清市| 历史| 罗平县| 重庆市| 获嘉县| 上犹县| 四子王旗| 乌拉特后旗| 香河县| 云安县| 富民县| 岳西县| 奉节县| 富平县| 西宁市| 肃宁县| 张家界市| 邯郸市|