【正文】 ,其凸包定義為 : 顯然 Con(Q)為凸集 . 定理 若拉格朗日對偶問題的目標值有限 ,則 m i n { | , ( ) }{ | , }TLDnz c x A x b x C o n x B x d x Z ?? ? ?? ? ?其 中 ：證明 : ()()( ) m in ( )m in ( )m in [ ( ) ]T T TLRxQT T Tx Con QTTx Con Qz c A x bc A x bc x b A x? ? ???????? ? ?? ? ?? ? ?設 Con(Q)的極點為 ,極方向為 則 : { | }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問題有限 ,則有 : 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上述問題等價于 : 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??????? ? ? ? ? ?? ? ??其對偶問題為 : m in ( )1. . ( )0 , 。 ,其一個最優(yōu)解也為 (4,0).由此我們可以知道 ,即使拉格朗日松弛在某個 下達到的最優(yōu)解為原問題的可行解 ,我們也不能斷言 .除非此時 . IP LDzz?8289LDz ?? 19??28IPz ???IP LDzz? 0??定理 若線性規(guī)劃松弛問題 LP存在可行解 ,則 L P L D IPz z z??注 :此定理說明 ,拉格朗日松弛對偶后的目標值 是 IP 問題的一個下界 ,且不比 差 . LDzLPz定理 的充要條件是存在 和 使得 : IP L Dzz ??? *0? ?* { | , }nx x Z A x b B x d?? ? ? ?112212* ( ) ( 0 )( * , * ) * * ( * ) ( * ) ( 0 )TTTLRb A xz x c x b A x z? ? ?? ? ? ? ?? ? ?? ? ? ?? ? ? ? ? ???證明 ：１、充分性： 2 1 2( * ) ( * , * ) *TL D L R L R 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 A x z z x?? ? ? ????? ? ? ?12* ( * ) , ( * ) ( * , * )T LRb A x z z x? ? ? ? ?? ? ? ? ? ?記 ：212( * , * ) * * ( * ) ( * )TT LRz x c x b Ax z? ? ? ?? ? ?? ? ? ? ???則 ：例 (繼例 ) 時 , 為問題的一個可行解 ,此時 : 1*9? ?* (4, 0)x ?121* ( * ) ( 4 4)9( * , * ) * * ( * )8828 28 ( * )99TLRb A xz x c x b A xz??????? ? ? ? ?? ? ?? ? ? ? ? ? ?2 1 288099 I P LDzz? ? ? ?? ? ? ? ? ?其 中 ， ， 有 ， 故 ：一般情況下 ,可大致估計 : 121* ( * ) ( 4 4 ) ,2( * , * ) * * ( * ) 2 8 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ù) 有 ：若 令 則 無 非 負 約 束 。 定理 的充要條件為： IP LDzz?* 0 ** ( ) 0 , ( * ) ( * , * )T LRx I Pb A x z z x?? ? ??? ? ?存 在 ， 為 可 行 解 ， 使 得 ：三、拉格朗日松弛的整數(shù)性 定義 若 LR的最優(yōu)解與其整數(shù)約束無關，則稱該問題具有整數(shù)性，即： ( ) m i n{ ( ) }..( ) ( ) m i n{ ( ) }..TTLRnTTLR Lnz c x b AxBx dstxZLRL RL z c x b AxBx dstxR??????? ? ???? ? ???與 線 性 松 弛最 優(yōu) 解 相 同 。 or 記 表示第 i行沒有被覆蓋 ,在沒有被覆蓋的行中仸選一行 k,計算 1is ?m in { | 1 , 1 },k j k j kd a s? ? ? ? 其 中1