chaper松弛算法ppt課件(編輯修改稿)
2025-06-01 12:01 本頁面
【文章內(nèi)容簡介】 的充要條件是存在 和 使得 : IP LDzz ??? *0? ?* { | , }nx x Z Ax b Bx d?? ? ? ?112212* ( ) ( 0)( * , * ) * * ( * ) ( * ) ( 0)TTTLRb Axz x c x b Ax z? ? ?? ? ? ? ?? ? ?? ? ? ?? ? ? ? ? ???證明 ：１、充分性： 2 1 2( * ) ( * , * ) *TLD LR LR I Pz z z x c x z? ? ? ? ? ?? ? ? ? ? ? ? ?２、必要性： 記 為ＩＰ問題的最優(yōu)解， 為ＬＤ問題的最優(yōu)解，則： *x*?( * ) * * ( * ) ( * ) ( * , * )* ( * ) ( * ) ( * , * )TTL D L R L RTI P L Rz z c x b A x z z xz b A x z z x? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ?* ( * ) ( * ) ( * , * )I P L DTLRzzb Ax z z x?? ? ? ????? ? ? ?12* ( * ) , ( * ) ( * , * )T LRb Ax z z x? ? ? ? ?? ? ? ? ? ?記 ：212( * , * ) * * ( * ) ( * )TT LRz x c x b A x z? ? ? ?? ? ?? ? ? ? ???則 ：例 (繼例 ) 時 , 為問題的一個可行解 ,此時 : 1*9? ?* (4,0)x ?121* ( * ) ( 4 4 )9( * , * ) * * ( * )882 8 2 8 ( * )99TLRb A xz x c x b A xz??????? ? ? ? ?? ? ?? ? ? ? ? ? ?2 1 288099 I P L Dzz? ? ? ?? ? ? ? ? ?其 中 ， ， 有 ， 故 ：一般情況下 ,可大致估計 : 121* ( * ) ( 4 4) ,2( * , * ) * * ( * ) 28 4 ( * )T LRb A xz x c x b A x z??? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ?3 2 ( * ) 3 2 2 8 4 0 , 4L R I P L Dz z z??? ? ? ? ? ? ? ? ? ?2于 是 ： 故 ：. 拉格朗日松弛的進一步討論 目的 : 對非標準的拉格朗日形式討論 . 一、等號約束的松弛 1 2 1 212( ) ( ) ( ) ( ),ij j iij j i ij j ii i ij j i i ij j i i i ij ji i i ia x ba x b a x bb a x b a x b a x? ? ? ?? ? ? ??? ? ? ?? ? ? ? ? ? ? ??????? ? ?nj=1nnj=1 j=1n n nj=1 j=1 j=1將 等 號 約 束 寫 成 標 準 形 式 ：，把 兩 個 約 束 吸 收 到 目 標 函 數(shù) 有 ：若 令 則 無 非 負 約 束 。二、 LR最優(yōu)解和 LP最優(yōu)解的關(guān)系 ( ) ( )TIPx I P c x z?????????TLRn+對 于 給 定 的 0 ，z ( )=min{c x+ (bAx)}（ LR ） dxZ的 最 優(yōu) 解 為 問 題 可 行 ， 并 不 能 有具體例見例 。 定理 的充要條件為： IP LDzz?* 0 ** ( ) 0 , ( * ) ( * , * )T LRx I Pb A x z z x?? ? ??? ? ?存 在 ， 為 可 行 解 ， 使 得 ：三、拉格朗日松弛的整數(shù)性 定義 若 LR的最優(yōu)解與其整數(shù)約束無關(guān)，則稱該問題具有整數(shù)性，即： ( ) m i n{ ( ) }..( ) ( ) m i n{ ( ) }..TTLRnTTLRLnz c x b AxBx dstxZLRL RL z c x b AxBx dstxR??????? ? ???? ? ???與 線 性 松 弛最 優(yōu) 解 相 同 。定理 若 LR具有整數(shù)性，則 L D IPzz?四、 拉格朗日分解 1m inm in m in{ ( ) }.... ..,( ) m in{ }( 7 .3 .8 )..TIPT TTIPnnnTTLRnz c xz c x c x x yA x bA x bA x bxys t B y ds t B x d stB y dx y ZxZx y Zz c x x zandA x bstxZ????????? ?? ?? ?????? ????? ? ? ? ??? ?? ? ? ???? ? ? ??? ? ? ??????? ?? ??????2( ) m in{ }( 7 .3 .9 )..TLRnyB y dstyZ???????1212( ) ( )m a x ( ) ( )LR LR I PLD LR LRz z zz z z?????????有 ：其 對 偶 形 式 ： 拉格朗日松弛算法 次梯度算法（ subgradient optimization） 定義： （ 凹函數(shù)） 函數(shù) 滿足以下條件稱為凹函數(shù) 1: mg R R?( ( 1 ) ) ( ) ( 1 ) ( ) , mg x y g x g y x y R? ? ? ?? ? ? ? ? ? ?定理 若 LR的可行解集合 Q為有限個實數(shù)點集，則以下函數(shù)為凹函數(shù) ( ) m in{ ( ) | }TTLRz c x b A x x Q??? ? ? ?定理 函數(shù)為凹函數(shù)的充要條件為： 1* , ( , ) ,( * ) ( ) ( * )mTmTmx R s s sg x g x s x x x R? ? ? ?? ? ? ? ?使 得 ：證明 必要性：設(shè) 為凹函數(shù)，則 ()gx?? 1 1 2 21 1 2 2 1 2 1 21 2 1 2 1 2( , ) | ( ) ( , ) , ( , )( , ) ( 1 ) ( , ) ( ( 1 ) , ( 1 ) ) :( ( 1 ) ) ( ) ( 1 ) ( ) ( 1 )H x z z g x a n d x z x z Hx z x z x x z zg x x g x g x z z? ? ? ? ? ?? ? ? ? ? ?? ? ? ?? ? ? ? ? ? ?? ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1