松弛算法ppt課件-展示頁(yè)
2025-05-10 00:02本頁(yè)面
【正文】 1 2 3 4 D C B 1224xx? ? ?4 3 2 1 1 2 3 4 D C B 1224xx? ? ?S1 S2 由推論 , 由兩個(gè)因素有關(guān) :第一個(gè)因素是目標(biāo)函數(shù)中的 C,推論 有的 C滿足 S1=S2,但也可能存在某個(gè) C使得 IP LDzz?IP LDzz?第二個(gè)因素是可行解的區(qū)域 .由上面的圖形可知 ,SI和 S2不同 ,所以存在一個(gè) C,使得 不為零 ,如在例 , ,在 達(dá)到拉格朗日對(duì)偶問(wèn)題的最優(yōu)值 ,其最優(yōu)解為 (4,0)。 例子 1: 線性規(guī)劃松弛 : 在 ,將整數(shù)約束松弛為實(shí)數(shù) , 稱其為 : m i n,...TLPnZ c xAx bstxR ????? ??? ?注 : : ,決策變量為較大整數(shù)的情形 . : 第一階段為求松弛后線性規(guī)劃問(wèn)題的最優(yōu)解 。 其它算法：分解法、組合算法等的目標(biāo)值。Chapter 8:拉格朗日松弛算法 基于規(guī)劃論的松弛方法 拉格朗日松弛理論 拉格朗日松弛的進(jìn)一步討論 拉格朗日松弛算法 應(yīng)用案例 :能力約束單機(jī)排序問(wèn)題 主要內(nèi)容 : 目標(biāo)值 最優(yōu)值 基于數(shù)學(xué)規(guī)劃 : 分支定界法、割平面法、線性規(guī)劃松弛再對(duì)目標(biāo)函數(shù)可行化等的目標(biāo)值。 現(xiàn)代優(yōu)化算法：禁忌搜索法、模擬退火法、遺傳算法、蟻群算法等的目標(biāo)值。 下界算法：線性規(guī)劃松弛、拉格朗日松弛等的目標(biāo)值。 第二階段為將解整數(shù)化 ,并考慮可行性 . LP IPZZ?例 2: 對(duì)偶規(guī)劃松弛方法 : : m a x7 .1 .3,...TDPTnZ y bA y cstyR ????? ??? ?其中 Y為決策變量 . 注 : 由對(duì)偶理論知 , ,至于采用其中的哪個(gè)模型求解 ,需比較哪個(gè)計(jì)算簡(jiǎn)單 . 例 3. 代理松弛法 : 當(dāng) ()中的約束太多時(shí) ,代理松弛一個(gè)約束 代替 ()中的 K個(gè)約束 極端情況可以用一個(gè)代替全部 1 1 1()kkn K Ki j j ij k ka x b? ? ??? ? ?1,1kkni j j ija x b k K????1 1 1()n m mi j j ij k ka x b? ? ??? ? ?注 : 代理松弛法保證目標(biāo)函數(shù) ,整數(shù)規(guī)劃約束不變 , 顯然 ,由代理松弛法求得的解不一定可行 例 4. 拉格朗日松弛方法 基本原理 : 將目標(biāo)函數(shù)中造成問(wèn)題難的約束吸 收到目標(biāo)函數(shù)中 ,并保持目標(biāo)函數(shù)的線性 ,使問(wèn)題容易求解 . Q:為什么對(duì)此類方法感興趣 ? A: (1). 在一些組合優(yōu)化中 ,若在原問(wèn)題中減少一些約束 ,則使得問(wèn)題求解難度大大降低 .(我們把這類約束稱為難約束 ). (2). 實(shí)際的計(jì)算表明此種方法所得到的結(jié)果相當(dāng)不錯(cuò) . 基于規(guī)劃論的松弛方法 松弛的定義（ ） : 問(wèn)題 整數(shù)規(guī)劃模型 : m i n,...TIPnZ c xAx bstxZ ????? ??? ?: m i n ( )RRRxSR P Z z x??滿足下列性質(zhì)時(shí) ,稱為 (relaxation). (1)可行解區(qū)域兼容 : (2)目標(biāo)函數(shù)兼容 : ( ) ,T Rc x z x x S? ? ?RSS?其中 , 為 . S例 set covering problem 問(wèn)題描述 : 設(shè) ,所有 ,且每一列對(duì)應(yīng)一個(gè)費(fèi)用 , 表示第 j列覆蓋第 i行 ,要求在最小的費(fèi)用下選擇一些列 ,使其覆蓋所有的行 . ()ij m nAa ?? {0,1}ija ?( 1 )jc j n? 1ija ?11m in( ) . . 1 , 1{ 0 , 1 } , 1nsc j jjni j jjjz c xSC s t a x i mx j n???????????? ??????松弛問(wèn)題 : 1 1 1m in { ( 1 ) }( ) . . { 0 , 1 }, 10n m nL R S C j j i ij jj i jjz c x a xLR S C s t x j n??? ? ??? ? ????????????? ? ?松弛模型 : 11m in( ) . . { 0 , 1 }, 10nmLR S C j j ijijz d xL R SC s t x j n????????????????????1mj j i ijid c a???? ?以上問(wèn)題很容易求得最優(yōu)解 1 , 0*0,jdxo th e r??? ?? 拉格朗日松弛理論 m in, ( ):. . ,.TIPnZ c xA x bIPs t B x dxZ????? ??? ??? ?難 約 束（ 簡(jiǎn) 單 約 束 ）{ | , }nS x Z A x b B x d?? ? ? ?( ) m in { ( ) }: ,...TTLRnZ c x b A xLR B x dstxZ????? ? ??? ??? ?（ 簡(jiǎn) 單 約 束 ）原整數(shù)規(guī)劃問(wèn)題 拉格朗日松弛 { | }nLRS x Z B x d?? ? ?定理 LR同下整數(shù)規(guī)劃問(wèn)題 ()有相同 的復(fù)雜性 ,且若 IP可行解非空，則 : 0 , ( )L R I Pzz??? ? ? ?m in. . ( 7 . 2 . 1 )Tncxs t B x dxZ ???( ) m in {( ) }: ,...T T TLRnZ c A x bLR B x dstxZ? ? ???? ? ??? ????（ 簡(jiǎn) 單 約 束 ）m in, ( ):. . ,.TIPnZ c xA x bIPs t B x dxZ ????? ??? ????難 約 束（ 簡(jiǎn) 單 約 束 ）證明 : 注 :定理 IP問(wèn)題的一個(gè)下界 ,但我們應(yīng)該求與 IP最接近的下界 ,即 : 0( ) m a x { ( ) }LD LRL D z z? ???定義 若 ,滿足以下條件 ,則稱 D為凸集 . ,x y D?(1 ) , 0 1x y D? ? ?? ? ? ? ?1( ) { | , 1 }i i i iiiC o n Q P P R? ? ?? ? ? ???{ | 1 , 2 , }iQ P i??對(duì)于離散點(diǎn)集
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1