《拉格朗日松弛算法》ppt課件-文庫(kù)吧
2025-04-14 03:17 本頁(yè)面
【正文】 ?定義 若 ,滿足以下條件 ,則稱(chēng) 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)集 ,其凸包定義為 : 顯然 Con(Q)為凸集 . 定理 若拉格朗日對(duì)偶問(wèn)題的目標(biāo)值有限 ,則 m in { | , ( ) }{ | , }TLDnz c x A x b x C o n x B x d x Z ?? ? ?? ? ?其 中 ：證明 : ()()( ) m i n ( )m i n ( )m i n [ ( ) ]T T TLRxQT T Tx C on QTTx C on Qz c A x bc A x bc x b Ax? ? ???????? ? ?? ? ?? ? ?設(shè) Con(Q)的極點(diǎn)為 ,極方向?yàn)? 則 : { | }kx k K? { | }jr j J?, , ( ) 0m i n ( )( ) , :T T jT T TT k T kxQi f j J c A rc A x bc x b A x o t h e r k K?????? ? ? ? ? ? ? ??? ? ? ?? ? ???由 LD問(wèn)題有限 ,則有 : 000m a x ( ) m a x m i n [ ( ) ]TT k T kL D L R kKz z c x b A x?????????? ? ? ? ??? ? ? ? ???Tj存 在 ， j J , 使 得 ( c A ) r 0上述問(wèn)題等價(jià)于 : m a x( ) ,. . ( ) 0 ,0LDT k T kT T jzc x b A x k Ks t c A r j J??????? ? ? ? ?? ? ? ??整理得 : m a x( ) ,. . ,0LDT k T kT j T jzA x b c x k Ks t A r c r j J??????? ? ? ? ? ?? ? ??其對(duì)偶問(wèn)題為 : m in ( )1. . ( )0 , 。 0 , .kLD k j jk K j JkkKkjk k kk K k K k Kkjz c T x rs t A x r bk K j J???? ? ??????? ? ???? ???????? ? ? ? ?????? ? ?即有 : ()m in..TLDx C o n Qz c xs t A x b???推論 : 對(duì)于仸給 c,整數(shù)規(guī)劃問(wèn)題 IP和拉 格 朗日對(duì)偶問(wèn)題 LD的目標(biāo)值相等的充要條件為 : ( { | }) ( ) { | }nnCon Q x R A x b Con Q x R A x b??? ? ? ? ? ? ?證 : 顯然有 { | } ( ) { | }nnQ x R Ax b C on Q x R Ax b??? ? ? ? ? ? ?( { | } ) ( ( ) { | } )( ) { | }nnnC o n Q x R A x b C o n C o n Q x R A x bC o n Q x R A x b???? ? ? ? ? ? ?? ? ? ?從而有 : 再由定理 : ( { | } ) ( ) { | }m in m innnTTI P L Dx C o n Q x R A x b x C o n Q x R A x bz c x z c x??? ? ? ? ? ? ? ?? ? ?若對(duì)仸何 c有 ,則問(wèn)題得證 . IP LDzz?例 假設(shè)整數(shù)規(guī)劃問(wèn)題 IP 12121212122m i n{ 7 2 }245 202 2 7. . . 224IPz x xxxxxxxstxxxZ?? ? ?? ? ???? ? ? ??? ??????? ? ? ?????第一個(gè)約束為復(fù)雜約束 ,其拉格朗日松弛后的模型 LR為 : 121212122( ) m in { ( 7 ) ( 2 2 ) 4 }5 2 02 2 7. . 2 5 .2 .34LRz x xxxxxs t xxxZ? ? ? ??? ? ? ? ? ?? ? ? ? ?????????? ? ??? ?? 4 3 2 1 1 2 3 4 l2 l1 l4 l3 E D C B A 41( , )17 17 T.3圖解示意 下降方向 最優(yōu)解 (7,2) (3,4) 29 (,1) (4,0) 32 (8,0) (4,0) 32 ? ()LRz ?0??12??1??(7 , 2 2 ) T???? 12( ( ), ( )) Txx?? ( , *)LRzx?227 2 2( , )5 3 6 5 5 3 6 5T??? ? ? ???? ? ? ?單位化下降方向 : 227 2 2 1 2l i m ( , ) ( , )555 3 6 5 5 3 6 5TT???? ? ? ???? ? ??? ? ? ?最優(yōu)值只能在 (4,0)和 (3,4)兩點(diǎn)得到 ,過(guò)這兩點(diǎn)的直線方程 :y+x4= : 41( , )1 7 1 7 T227 2 2 4 1 1, ( , )91 7 1 75 3 6 5 5 3 6 5T?? ?? ? ? ??? ? ? ?? ? ? ?綜合有 : 12 9 0119( ) ( ) 2 81 992 8 89LR LD LRz z z?????? ? ? ? ??
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1