chaper 7 松弛算法.ppt

chaper 7 松弛算法.ppt

ID:48167043

大?。?75.50 KB

頁數(shù):48頁

時間:2020-01-17

chaper 7 松弛算法.ppt_第1頁
chaper 7 松弛算法.ppt_第2頁
chaper 7 松弛算法.ppt_第3頁
chaper 7 松弛算法.ppt_第4頁
chaper 7 松弛算法.ppt_第5頁
資源描述:

《chaper 7 松弛算法.ppt》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、Chapter7:拉格朗日松弛算法7.1基于規(guī)劃論的松弛方法7.2拉格朗日松弛理論7.3拉格朗日松弛的進(jìn)一步討論7.4拉格朗日松弛算法7.5應(yīng)用案例:能力約束單機(jī)排序問題主要內(nèi)容:目標(biāo)值最優(yōu)值基于數(shù)學(xué)規(guī)劃:分支定界法、割平面法、線性規(guī)劃松弛再對目標(biāo)函數(shù)可行化等的目標(biāo)值。現(xiàn)代優(yōu)化算法:禁忌搜索法、模擬退火法、遺傳算法、蟻群算法等的目標(biāo)值。其它算法:分解法、組合算法等的目標(biāo)值。下界算法:線性規(guī)劃松弛、拉格朗日松弛等的目標(biāo)值。例子1:線性規(guī)劃松弛:在7.1.1中,將整數(shù)約束松弛為實數(shù),稱其為7.1.1的線性規(guī)劃松弛

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

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

4、函數(shù)兼容:其中,為7.1.1的可行域.例7.1.1setcoveringproblem問題描述:設(shè),所有,且每一列對應(yīng)一個費用,表示第j列覆蓋第i行,要求在最小的費用下選擇一些列,使其覆蓋所有的行.松弛問題:松弛模型:以上問題很容易求得最優(yōu)解7.2拉格朗日松弛理論原整數(shù)規(guī)劃問題拉格朗日松弛定理7.2.1LR同下整數(shù)規(guī)劃問題(7.2.1)有相同的復(fù)雜性,且若IP可行解非空,則:證明:注:定理7.2.1說明拉格朗日松弛是IP問題的一個下界,但我們應(yīng)該求與IP最接近的下界,即:定義7.2.1若,滿足以下條件,則稱D

5、為凸集.對于離散點集,其凸包定義為:顯然Con(Q)為凸集.定理7.2.2若拉格朗日對偶問題的目標(biāo)值有限,則證明:設(shè)Con(Q)的極點為,極方向為則:由LD問題有限,則有:上述問題等價于:整理得:其對偶問題為:即有:推論7.2.1:對于任給c,整數(shù)規(guī)劃問題IP和拉格朗日對偶問題LD的目標(biāo)值相等的充要條件為:證:顯然有從而有:再由定理7.2.2:若對任何c有,則問題得證.例7.2.1假設(shè)整數(shù)規(guī)劃問題IP第一個約束為復(fù)雜約束,其拉格朗日松弛后的模型LR為:43211234l2l1l4l3EDCBA7.2.3圖解示

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

7、一個C,使得不為零,如在例7.2.1中,,在達(dá)到拉格朗日對偶問題的最優(yōu)值,其最優(yōu)解為(4,0);,其一個最優(yōu)解也為(4,0).由此我們可以知道,即使拉格朗日松弛在某個下達(dá)到的最優(yōu)解為原問題的可行解,我們也不能斷言.除非此時.定理7.2.3若線性規(guī)劃松弛問題LP存在可行解,則注:此定理說明,拉格朗日松弛對偶后的目標(biāo)值是IP問題的一個下界,且不比差.定理7.2.3的充要條件是存在和使得:證明:1、充分性:2、必要性:記 為IP問題的最優(yōu)解, 為LD問題的最優(yōu)解,則:例7.2.3(繼例7.2.1)時,為問題的一個可

8、行解,此時:一般情況下,可大致估計:7.3.拉格朗日松弛的進(jìn)一步討論目的:對非標(biāo)準(zhǔn)的拉格朗日形式討論.一、等號約束的松弛二、LR最優(yōu)解和LP最優(yōu)解的關(guān)系具體例見例7.3.1。定理7.3.1的充要條件為:三、拉格朗日松弛的整數(shù)性定義7.3.1若LR的最優(yōu)解與其整數(shù)約束無關(guān),則稱該問題具有整數(shù)性,即:定理7.3.2若LR具有整數(shù)性,則四、拉格朗日分解7.4拉格朗日松弛算法7.4.1次梯度算法(subgr

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。