【正文】 : 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于 是 ： 故 ：. 拉格朗日松弛的進一步討論 目的 : 對非標(biāo)準(zhǔn)的拉格朗日形式討論 . 一、等號約束的松弛 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將 等 號 約 束 寫 成 標(biāo) 準(zhǔn) 形 式 ：，把 兩 個 約 束 吸 收 到 目 標(biāo) 函 數(shù) 有 ：若 令 則 無 非 負(fù) 約 束 。拉格朗日松弛算法 基于規(guī)劃論的松弛方法 拉格朗日松弛理論 拉格朗日松弛的進一步討論 拉格朗日松弛算法 主要內(nèi)容 : 目標(biāo)值 最優(yōu)值 基于數(shù)學(xué)規(guī)劃 : 分支定界法、割平面法、線性規(guī)劃松弛再對目標(biāo)函數(shù)可行化等的目標(biāo)值。二、 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的一個最優(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) 解 相 同 。 其它算法：分解法、組合算法等的目標(biāo)值。 第二階段為將解整數(shù)化 ,并考慮可行性 . LP IPZZ?注 : 例 2: 對偶規(guī)劃松弛方法 : : m a x,...TDPTnZ y bA y cstyR ????? ??? ?其中 Y為決策變量 . 注 : 由對偶理論知 , ,至于采用其中的哪個模型求解 ,需比較哪個計算簡單 . 例 3. 代理松弛法 : 當(dāng) ()中的約束太多時 ,代理松弛一個約束 代替 ()中的 K個約束 極端情況可以用一個代替全部 1 1 1()kkn K Ki j j ij k ka x b? ? ??? ? ?1,1kkni j j ija x b k K????1 1 1()n m mi j j ij k ka x b? ? ??? ? ?注 : 代理松弛法保證目標(biāo)函數(shù) ,整數(shù)規(guī)劃約束不變 , 顯然 ,由代理松弛法求得的解不一定可行 例 4. 拉格朗日松弛方法 基本原理 : 將目標(biāo)函數(shù)中造成問題難的約束吸 收到目標(biāo)函數(shù)中 ,并保持目標(biāo)函數(shù)的線性 ,使問題容易求解 . Q:為什么對此類方法感興趣 ? A: (1). 在一些組合優(yōu)化中 ,若在原問題中減少一些約束 ,則使得問題求解難度大大降低 .(我們把這類約束稱為難約束 ). (2). 實際的計算表明此種方法所得到的結(jié)果相當(dāng)不錯 . 基于規(guī)劃論的松弛方法 松弛的定義（ ） : 問題 整數(shù)規(guī)劃模型 : m in5 . 1 . 1,...TIPnZ c xA x bstxZ ????? ??? ?: m i n ( )RRRxSRP Z z x??滿足下列性質(zhì)時 ,稱為 (relaxation). (1)可行解區(qū)域兼容 : (2)目標(biāo)函數(shù)兼容 : ( ) ,T Rc x z x x S? ? ?RSS?其中 , 為 . S例 set covering problem 問題描述 : 設(shè) ,所有 ,且每一列對應(yīng)一個費用 , 表示第 j列覆蓋第 i行 ,要求在最小的費用下選擇一些列 ,使其覆蓋所有的行 . ()ij m nAa ?? {0,1}ija ?( 1 )jc j n? 1ija ?11m in( ) . . 1 , 1{ 0 , 1 }, 1ns c j jjni j jjjz c xS C s t a x i mx j n???????????? ??????松弛問題 : 1 1 1m in{ ( 1 ) }( ) . . { 0 , 1 } , 10n m nL RSC j j i ij jj i jjz c x a xL RS C s t x j n??? ? ??? ? ?????????????