《拉格朗日松弛算法》PPT課件

《《拉格朗日松弛算法》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、拉格朗日松弛算法基于規(guī)劃論的松弛方法拉格朗日松弛理論拉格朗日松弛的進(jìn)一步討論拉格朗日松弛算法主要內(nèi)容:目標(biāo)值最優(yōu)值基于數(shù)學(xué)規(guī)劃:分支定界法、割平面法、線性規(guī)劃松弛再對(duì)目標(biāo)函數(shù)可行化等的目標(biāo)值?，F(xiàn)代優(yōu)化算法：禁忌搜索法、模擬退火法、遺傳算法、蟻群算法等的目標(biāo)值。其它算法：分解法、組合算法等的目標(biāo)值。下界算法：線性規(guī)劃松弛、拉格朗日松弛等的目標(biāo)值。例子1:線性規(guī)劃松弛:在5.1.1中,將整數(shù)約束松弛為實(shí)數(shù),稱其為5.1.1的線性規(guī)劃松弛:定理5.1.1:此類算法適合于整數(shù)規(guī)劃問題中,決策變量為較大整數(shù)的情形

2、.此類算法分兩階段:第一階段為求松弛后線性規(guī)劃問題的最優(yōu)解;第二階段為將解整數(shù)化,并考慮可行性.注:例2:對(duì)偶規(guī)劃松弛方法:5.1.2的對(duì)偶形式為:其中Y為決策變量.注:由對(duì)偶理論知,5.1.2和5.1.3有相同的最優(yōu)值,至于采用其中的哪個(gè)模型求解5.1.1的下界,需比較哪個(gè)計(jì)算簡(jiǎn)單.例3.代理松弛法:當(dāng)(5.1.1)中的約束太多時(shí),代理松弛一個(gè)約束代替(5.1.1)中的K個(gè)約束極端情況可以用一個(gè)代替全部注:代理松弛法保證目標(biāo)函數(shù),整數(shù)規(guī)劃約束不變,顯然,由代理松弛法求得的解不一定可行例4.拉格朗日松弛

3、方法基本原理:將目標(biāo)函數(shù)中造成問題難的約束吸收到目標(biāo)函數(shù)中,并保持目標(biāo)函數(shù)的線性,使問題容易求解.Q:為什么對(duì)此類方法感興趣?A:(1).在一些組合優(yōu)化中,若在原問題中減少一些約束,則使得問題求解難度大大降低.(我們把這類約束稱為難約束).(2).實(shí)際的計(jì)算表明此種方法所得到的結(jié)果相當(dāng)不錯(cuò).5.1基于規(guī)劃論的松弛方法松弛的定義（5.1.1）:問題整數(shù)規(guī)劃模型:滿足下列性質(zhì)時(shí),稱為5.1.1的一個(gè)松弛(relaxation).可行解區(qū)域兼容:目標(biāo)函數(shù)兼容:其中,為5.1.1的可行域.例5.1.1setco

4、veringproblem問題描述:設(shè),所有,且每一列對(duì)應(yīng)一個(gè)費(fèi)用,表示第j列覆蓋第i行,要求在最小的費(fèi)用下選擇一些列,使其覆蓋所有的行.松弛問題:松弛模型:以上問題很容易求得最優(yōu)解5.2拉格朗日松弛理論原整數(shù)規(guī)劃問題拉格朗日松弛定理5.2.1LR同下整數(shù)規(guī)劃問題(5.2.1)有相同的復(fù)雜性,且若IP可行解非空，則:證明:注:定理5.2.1說明拉格朗日松弛是IP問題的一個(gè)下界,但我們應(yīng)該求與IP最接近的下界,即:定義5.2.1若,滿足以下條件,則稱D為凸集.對(duì)于離散點(diǎn)集,其凸包定義為:顯然Con(Q)為

5、凸集.定理5.2.2若拉格朗日對(duì)偶問題的目標(biāo)值有限,則證明:設(shè)Con(Q)的極點(diǎn)為,極方向?yàn)閯t:由LD問題有限,則有:上述問題等價(jià)于:整理得:其對(duì)偶問題為:即有:推論5.2.1:對(duì)于任給c,整數(shù)規(guī)劃問題IP和拉格朗日對(duì)偶問題LD的目標(biāo)值相等的充要條件為:證:顯然有從而有:再由定理5.2.2:若對(duì)任何c有,則問題得證.例5.2.1假設(shè)整數(shù)規(guī)劃問題IP第一個(gè)約束為復(fù)雜約束,其拉格朗日松弛后的模型LR為:43211234l2l1l4l3EDCBA5.2.3圖解示意下降方向最優(yōu)解(7,2)(3,4)-29(7.

6、5,1)(4,0)-32(8,0)(4,0)-32單位化下降方向:最優(yōu)值只能在(4,0)和(3,4)兩點(diǎn)得到,過這兩點(diǎn)的直線方程:y+x4=16.其垂直方向?yàn)?綜合有:例5.2.2(繼5.2.1)例5.2.1中43211234DCB43211234DCBS1S2由推論5.2.1可以知道,由兩個(gè)因素有關(guān):第一個(gè)因素是目標(biāo)函數(shù)中的C,推論5.2.1要求對(duì)所有的C滿足S1=S2,但也可能存在某個(gè)C使得第二個(gè)因素是可行解的區(qū)域.由上面的圖形可知,SI和S2不同,所以存在一個(gè)C,使得不為零,如在例5.2.1中,,

7、在達(dá)到拉格朗日對(duì)偶問題的最優(yōu)值,其最優(yōu)解為(4,0);,其一個(gè)最優(yōu)解也為(4,0).由此我們可以知道,即使拉格朗日松弛在某個(gè)下達(dá)到的最優(yōu)解為原問題的可行解,我們也不能斷言.除非此時(shí).定理5.2.3若線性規(guī)劃松弛問題LP存在可行解,則注:此定理說明,拉格朗日松弛對(duì)偶后的目標(biāo)值是IP問題的一個(gè)下界,且不比差.定理5.2.3的充要條件是存在和使得:證明：１、充分性：２、必要性：記　為ＩＰ問題的最優(yōu)解，　為ＬＤ問題的最優(yōu)解，則：例5.2.3(繼例5.2.1)時(shí),為問題的一個(gè)可行解,此時(shí):一般情況下,可大致估計(jì):

8、5.3.拉格朗日松弛的進(jìn)一步討論目的:對(duì)非標(biāo)準(zhǔn)的拉格朗日形式討論.一、等號(hào)約束的松弛二、LR最優(yōu)解和LP最優(yōu)解的關(guān)系具體例見例5.3.1。例5.3.1集合覆蓋問題拉格朗日松弛三個(gè)約束，由此得到當(dāng)松弛后問題的一個(gè)最優(yōu)解為原問題（5.3.1）的一個(gè)可行解時(shí)，并不能得到該解為原問題的最優(yōu)解。在什么條件下該解為IP的一個(gè)最優(yōu)解？定理5.3.1的充要條件為：三、拉格朗日松弛的整數(shù)性定義5.3.1若LR的最優(yōu)解與其整數(shù)約束無關(guān)，則稱該問題具有整數(shù)性，即