【正文】 ,極方向?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 , 。在什么條件下該解為 IP的一個(gè)最優(yōu)解？ 定理 的充要條件為： IP LDzz?* 0 ** ( ) 0 , ( * ) ( * , * )T LRx I Pb A x z z x?? ? ??? ? ?存 在 ， 為 可 行 解 ， 使 得 ：三、拉格朗日松弛的整數(shù)性 定義 若 LR的最優(yōu)解與其整數(shù)約束無(wú)關(guān)，則稱該問(wèn)題具有整數(shù)性，即： ( ) m i n{ ( ) }..( ) ( ) m i n{ ( ) }..TTLRnTTLRLnz c x b AxBx dstxZLRL RL z c x b AxBx dstxR??????? ? ???? ? ???與 線 性 松 弛最 優(yōu) 解 相 同 。拉格朗日松弛算法 基于規(guī)劃論的松弛方法 拉格朗日松弛理論 拉格朗日松弛的進(jìn)一步討論 拉格朗日松弛算法 主要內(nèi)容 : 目標(biāo)值 最優(yōu)值 基于數(shù)學(xué)規(guī)劃 : 分支定界法、割平面法、線性規(guī)劃松弛再對(duì)目標(biāo)函數(shù)可行化等的目標(biāo)值。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???????????? ???????? ???????其 中? 上頁(yè)公式的線性規(guī)劃模型為 ? LRSC和 LSC具有整數(shù)性。 例子 1: 線性規(guī)劃松弛 : 在 ,將整數(shù)約束松弛為實(shí)數(shù) , 稱其為 : m i n5 . 1 . 1,...TLPnZ c xA x bstxZ ????? ??? ?m i n5 . 1 . 2,...TLPnZ c xA x bstxR ????? ??? ?1. 定理 : 2. 此類算法適合于整數(shù)規(guī)劃問(wèn)題中 ,決策變量為較大整數(shù)的情形 . 3. 此類算法分兩階段 : 第一階段為求松弛后線性規(guī)劃問(wèn)題的最優(yōu)解 。 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