拉格朗日松弛算法ppt課件-閱讀頁
2025-05-14 03:17本頁面
【正文】 LD 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? ? ? ?? ? ?? ? ? ? ???則 ：例 (繼例 ) 時(shí) , 為問題的一個(gè)可行解 ,此時(shí) : 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? ? ? ?? ? ? ? ? ?其 中 ， ， 有 ， 故 ：一般情況下 ,可大致估計(jì) : 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于 是 ： 故 ：. 拉格朗日松弛的進(jìn)一步討論 目的 : 對(duì)非標(biāo)準(zhǔn)的拉格朗日形式討論 . 一、等號(hào)約束的松弛 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將 等 號(hào) 約 束 寫 成 標(biāo) 準(zhǔn) 形 式 ：，把 兩 個(gè) 約 束 吸 收 到 目 標(biāo) 函 數(shù) 有 ：若 令 則 無 非 負(fù) 約 束 。 ? 例 1 2 3 41314234m in 2 3 4 51..11{ 0 , 1 }, 1 , 2 , 3 , 4ix x x xxxstxxx x xxi? ? ?????? ? ??? 1 2 3 41 , 0 , x x x z? ? ? ? ?直 觀 的 結(jié) 果 是 最 優(yōu) 解 ：? 拉格朗日松弛三個(gè)約束， 1 2 1 3 21 3 3 1 3 41 2 3( ) m in{( 2 ) ( 3 )( 4 ) ( 5 )}. . { 0 , 1 }, 1 , 2 , 3 , 4LRjz x xxxs t x j? ? ? ?? ? ? ?? ? ?? ? ? ? ?? ? ? ? ? ?? ? ??? 1 2 3 4 1 , ( ) 25 . 3 . 1LRL R I Px x x x zzz?? ? ? ? ? ??其 最 優(yōu) 解 為為 穩(wěn) 妥 的 一 個(gè) 可 行 解 ， 但? 由此得到當(dāng)松弛后問題的一個(gè)最優(yōu)解為原問題（ ）的一個(gè)可行解時(shí)，并不能得到該解為原問題的最優(yōu)解。L D IPzz?? 例 （續(xù) ）例 SC的拉格朗日松弛為 111m in. . { 0 , 1 }, 1()0nmLR SC j j ijijmj j i ijiz d xs t x j nLR S Cd c a???????????? ???????? ???????其 中? 上頁公式的線性規(guī)劃模型為 ? LRSC和 LSC具有整數(shù)性。 or 記 表示第 i行沒有被覆蓋 ,在沒有被覆蓋的行中仸選一行 k,計(jì)算 1is ?m in{ | 1 , 1 },k j k j kd a s? ? ? ? 其 中1mtj j ljld c a???? ?Step4 : 1 1 , 2tkkti tiikt t st e pik????? ? ???? ? ?????返 回例 對(duì)集合覆蓋問題 1 2 3 41314234m i n 2 3 4 51. . 11{ 0 , 1 } , 1 , 2 , 3 , 4jx x x xxxs t x xx x xxj? ? ?????? ? ???假設(shè) : (1 .5 , 1 .6 , 2 .3 ) T? ?1 2 3 4( ) m in { 1 . 1 0 . 8 0 . 3 1 . 2 } 5 . 3LRz x x x x? ? ? ? ? ? ?()LRz ? 最優(yōu)解為 : ( 1 , 0 , 0 , 0 , ) , ( ) 4 . 2LRxz ???第三行沒有被覆蓋 ,在可覆蓋第三行中選費(fèi)用最小的列 m i n { 0 . 8 , 0 . 3 ,1 . 2 } 0 . 3? ?? 代 替1231 .5 01 .6 02 .2 0 .3????? ? ? ? ??? ? ? ? ????? ? ? ? ??? ? ? ? ?? ? ? ???1 2 4( ) m i n{ 1. 1 0. 5 0. 9 } 5. 6 4. 5LRz x x xLR? ? ? ? ? ? ?1 3 2 4最 優(yōu) 解 為 :x =x =1 ,x =x =0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1