拉格朗日松弛算法求解組合優(yōu)化問題

1、Chapter 7:拉格朗日松弛算法7.1 基于規(guī)劃論的松弛方法基于規(guī)劃論的松弛方法7.2 拉格朗日松弛理論拉格朗日松弛理論7.3 拉格朗日松弛的進(jìn)一步討論拉格朗日松弛的進(jìn)一步討論7.4 拉格朗日松弛算法拉格朗日松弛算法7.5 應(yīng)用案例應(yīng)用案例:能力約束單機(jī)排序問題能力約束單機(jī)排序問題主要內(nèi)容:目標(biāo)值最優(yōu)值基于數(shù)學(xué)規(guī)劃: 分支定界法、割平面法、線性規(guī)劃松弛再對(duì)目標(biāo)函數(shù)可行化等的目標(biāo)值。現(xiàn)代優(yōu)化算法：禁忌搜索法、模擬退火法、遺傳算法、蟻群算法等的目標(biāo)值。其它算法：分解法、組合算法等的目標(biāo)值。下界算法：線性規(guī)劃松弛、拉格朗日松弛等的目標(biāo)值。例子1: 線性規(guī)劃松弛: 在7.1.1中,將整數(shù)約束松弛為

2、實(shí)數(shù), 稱其為7.1.1的線性規(guī)劃松弛:min7.1.2,. .TLPnZc xAxbstxR注: 定理7.1.1: 此類算法適合于整數(shù)規(guī)劃問題中,決策變量為較大整數(shù)的情形. 此類算法分兩階段: 第一階段為求松弛后線性規(guī)劃問題的最優(yōu)解; 第二階段為將解整數(shù)化,并考慮可行性.LPIPZZ例2: 對(duì)偶規(guī)劃松弛方法: 7.1.2的對(duì)偶形式為:max7.1.3,. .TDPTnZy bA ycstyR其中Y為決策變量.注:由對(duì)偶理論知,7.1.2和7.1.3有相同的最優(yōu)值,至于采用其中的哪個(gè)模型求解7.1.1的下界,需比較哪個(gè)計(jì)算簡(jiǎn)單.例3. 代理松弛法:當(dāng)(7.1.1)中的約束太多時(shí),代理松弛一個(gè)約

3、束代替(7.1.1)中的K個(gè)約束極端情況可以用一個(gè)代替全部111()kknKKi jjijkkaxb 1,1kkni jjijaxbkK111()nmmi jjijkkaxb 注: 代理松弛法保證目標(biāo)函數(shù),整數(shù)規(guī)劃約束不變, 顯然,由代理松弛法求得的解不一定可行例4. 拉格朗日松弛方法基本原理: 將目標(biāo)函數(shù)中造成問題難的約束吸 收到目標(biāo)函數(shù)中,并保持目標(biāo)函數(shù)的線性,使問題容易求解.Q:為什么對(duì)此類方法感興趣?A: (1). 在一些組合優(yōu)化中,若在原問題中減少一些約束,則使得問題求解難度大大降低.(我們把這類約束稱為難約束). (2). 實(shí)際的計(jì)算表明此種方法所得到的結(jié)果相當(dāng)不錯(cuò).7.1 基于規(guī)

4、劃論的松弛方法松弛的定義（7.1.1）: 問題整數(shù)規(guī)劃模型:min7.1.1,. .TIPnZc xAxbstxZ:min( )RRRx SRPZzx滿足下列性質(zhì)時(shí),稱為7.1.1的一個(gè)松弛(relaxation). 可行解區(qū)域兼容:(1)目標(biāo)函數(shù)兼容:( ),TRc xzxxS RSS其中, 為7.1.1的可行域.S例7.1.1 set covering problem問題描述: 設(shè) ,所有 ,且每一列對(duì)應(yīng)一個(gè)費(fèi)用 , 表示第j列覆蓋第i行,要求在最小的費(fèi)用下選擇一些列,使其覆蓋所有的行.()ijm nAa0,1ija (1)jcjn 1ija 11min(). .1,10,1,1nscjj

5、jni jjjjzc xSCsta ximxjn松弛問題:111min(1)(). .0,1,10nmnLRSCjjiijjjijjzc xa xLRSCst xjn松弛模型:11min(). .0,1,10nmLRSCjjijijzd xLRSCst xjn1mjjiijidca以上問題很容易求得最優(yōu)解1,0*0,jdxother7.2 拉格朗日松弛理論min,():. .,.TIPnZc xAxbIPstBxdxZ難約束（簡(jiǎn)單約束）|,nSxZAxb Bxd( )min():,. .TTLRnZc xbAxLRBxdstxZ（簡(jiǎn)單約束）原整數(shù)規(guī)劃問題拉格朗日松弛|nLRSxZBxd定理7.

6、2.1 LR同下整數(shù)規(guī)劃問題(7.2.1)有相同 的復(fù)雜性,且若IP可行解非空，則:0,( )LRIPzz min. .(7.2.1)Tnc xst BxdxZ( )min():,. .TTTLRnZcA xbLRBxdstxZ（簡(jiǎn)單約束）min,():. .,.TIPnZc xAxbIPstBxdxZ難約束（簡(jiǎn)單約束）證明:注:定理7.2.1說明拉格朗日松弛是IP問題的一個(gè)下界,但我們應(yīng)該求與IP最接近的下界,即:0()max( )LDLRLDzz定義7.2.1 若 ,滿足以下條件,則稱D為凸集., x yD(1),01xyD1( )|,1iiiiiiCon QPPR|1,2,iQP i對(duì)于

7、離散點(diǎn)集 ,其凸包定義為:顯然Con(Q)為凸集.定理7.2.2 若拉格朗日對(duì)偶問題的目標(biāo)值有限,則min|,( ) |,TLDnzc x Axb xCon QQx Bxd xZ其中：證明:()()( )min()min ()min ()TTTLRx QTTTx Con QTTx Con QzcA xbcA xbc xbAx設(shè)Con(Q)的極點(diǎn)為 ,極方向?yàn)?則:|kxkK|jrjJ, ()0min()(),:TTjTTTTkTkx Qif jJcA rcA xbc xbAxother kK 由LD問題有限,則有:000max( )maxmin()TTkTkLDLRk Kzzc xbAx Tj

8、存在， jJ,使得(c -A)r0上述問題等價(jià)于:max(),. .()0,0LDTkTkTTjzc xbAxkKstcA rjJ 整理得:max(),. .,0LDTkTkTjTjzAxbc xkKstArc rjJ 其對(duì)偶問題為:min()1. .()0,;0,.kLDkjjk Kj Jkk Kkjkkkk Kk Kk KkjzcTxrstAxrbkKjJ即有:()min. .TLDx Con Qzc xstAxb推論推論7.2.1: 對(duì)于任給c,整數(shù)規(guī)劃問題IP和拉 格 朗日對(duì)偶問題LD的目標(biāo)值相等的充要條件為:(|)( )|nnCon QxRAxbCon QxRAxb證: 顯然有 |(

9、 )|nnQxRAxbCon QxRAxb(|)( )|)( )|nnnCon QxRAxbCon Con QxRAxbCon QxRAxb從而有:再由定理7.2.2:(|)() |minminnnTTIPLDx Con Qx R Ax bx Con Qx R Ax bzc xzc x若對(duì)任何c有 ,則問題得證.IPLDzz例7.2.1 假設(shè)整數(shù)規(guī)劃問題IP12121212122min 7224520227. .7.2.224IPzxxxxxxxxstxxxZ 第一個(gè)約束為復(fù)雜約束,其拉格朗日松弛后的模型LR為:121212122( )min (7)(22 )4 520227. .27.2.3

10、4LRzxxxxxxstxxxZ 43211234l2l1l4l3EDCBA41(,)1717T7.2.3圖解示意下降方向最優(yōu)解 (7,2) (3,4) -29 (7.5,1) (4,0) -32 (8,0) (4,0) -32( )LRz0121(7,22 )T12( ( ),( )Txx( , *)LRzx22722(,)53655365T單位化下降方向:2272212lim(,)(,)5553655365TT最優(yōu)值只能在(4,0)和(3,4)兩點(diǎn)得到,過這兩點(diǎn)的直線方程:y+x4=16.其垂直方向?yàn)?41(,)1717T22722411,(,)9171753655365T綜合有:1290

11、119( )( )281992889LRLDLRzzz 例7.2.2(繼7.2.1) 例7.2.1中 (2,2) ,(2,3) ,(2,4) ,(3,1) ,(3,2) ,(3,3) ,(3,4) ,(4,0) TTTTTTTTQ 12121(|24)2( )|24nnSCon QxRxxSCon QxRxx 43211234DCB1224xx 43211234DCB1224xx S1S2由推論7.2.1可以知道, 由兩個(gè)因素有關(guān):第一個(gè)因素是目標(biāo)函數(shù)中的C,推論7.2.1要求對(duì)所有的C滿足S1=S2,但也可能存在某個(gè)C使得 IPLDzzIPLDzz第二個(gè)因素是可行解的區(qū)域.由上面的圖形可知,

12、SI和S2不同,所以存在一個(gè)C,使得 不為零,如在例7.2.1中, ,在 達(dá)到拉格朗日對(duì)偶問題的最優(yōu)值,其最優(yōu)解為(4,0); ,其一個(gè)最優(yōu)解也為(4,0).由此我們可以知道,即使拉格朗日松弛在某個(gè) 下達(dá)到的最優(yōu)解為原問題的可行解,我們也不能斷言 .除非此時(shí) .IPLDzz8289LDz 1928IPz IPLDzz0定理7.2.3 若線性規(guī)劃松弛問題LP存在可行解,則LPLDIPzzz注:此定理說明,拉格朗日松弛對(duì)偶后的目標(biāo)值 是IP 問題的一個(gè)下界,且不比 差.LDzLPz定理7.2.3 的充要條件是存在 和 使得:IPLDzz*0*|,nxxZAxb Bxd112212* ()(0)(

13、*, *)* (*)( *)(0)TTTLRbAxzxc xbAxz 證明：、充分性：212( *)( *, *)*TLDLRLRIPzzzxc xz、必要性：記為問題的最優(yōu)解，為問題的最優(yōu)解，則：*x*( *)* (*)( *)( *, *)* (*)( *)( *, *)TTLDLRLRTIPLRzzc xbAxzzxzbAxzzx* (*)( *)( *, *)IPLDTLRzzbAxzzx12* (*),( *)( *, *)TLRbAxzzx 記：212( *, *)* (*)( *)TTLRzxc xbAxz則：例7.2.3 (繼例7.2.1) 時(shí), 為問題的一個(gè)可行解,此時(shí):1*

14、9*(4,0)x 121*(*)( 44)9( *, *)*(*)882828( *)99TLRbAxzxc xbAxz 21288099IPLDzz其中，有，故：一般情況下,可大致估計(jì):121*(*)( 44),2( *, *)*(*)284( *)TLRbAxzxc xbAxz 32( *)322840,4LRIPLDzzz 2于是：故：7.3. 拉格朗日松弛的進(jìn)一步討論目的: 對(duì)非標(biāo)準(zhǔn)的拉格朗日形式討論.一、等號(hào)約束的松弛121212()()()(),ijjiijjiijjiiiijjiiijjiiiijjiiiia xba xba xbba xba xba x nj=1nnj=1j=1

15、nnnj=1j=1j=1將等號(hào)約束寫成標(biāo)準(zhǔn)形式：，把兩個(gè)約束吸收到目標(biāo)函數(shù)有：若令則 無非負(fù)約束。二、LR最優(yōu)解和LP最優(yōu)解的關(guān)系( )( )TIPxIPc xzTLRn+對(duì)于給定的0，z ( )=minc x+ (b-Ax)（LR）s.t.BxdxZ的最優(yōu)解為問題可行，并不能有具體例見例7.3.1。定理7.3.1 的充要條件為：IPLDzz*0* ()0,( *)( *, *)TLRxIPbAxzzx存在，為可行解，使得：三、拉格朗日松弛的整數(shù)性定義7.3.1 若LR的最優(yōu)解與其整數(shù)約束無關(guān)，則稱該問題具有整數(shù)性，即：( )min(). .()( )min(). .TTLRnTTLRLnzc

16、 xbAxBxdstxZLRLRLzc xbAxBxdstxR與線性松弛最優(yōu)解相同。定理7.3.2 若LR具有整數(shù)性，則LDIPzz四、 拉格朗日分解1minminmin(). . . .,( )min(7.3.8). .TIPTTTIPnnnTTLRnzc xzc xc xxyAxbAxbAxbxystBydstBxdstBydx yZxZx yZzc xxzandAxbstxZ2( )min(7.3.9). .TLRnyBydstyZ1212( )( )max( )( )LRLRIPLDLRLRzzzzzz有：其對(duì)偶形式：7.4 拉格朗日松弛算法7.4.1 次梯度算法（subgradien

17、t optimization）定義：（凹函數(shù)） 函數(shù) 滿足以下條件稱為凹函數(shù) 1:mg RR(1) )( )(1) ( ),mgxyg xg yx yR定理7.4.1 若LR的可行解集合Q為有限個(gè)實(shí)數(shù)點(diǎn)集，則以下函數(shù)為凹函數(shù)( )min()|TTLRzc xbAxxQ定理7.4.1 函數(shù)為凹函數(shù)的充要條件為：1*,( ,) ,( *)( )( *)mTmTmxRsssg xg xsxxxR 使得：證明 必要性：設(shè) 為凹函數(shù)，則( )g x112211221212121212( , )|( )(,),(,)(,)(1)(,)(1),(1):(1)()(1) ()(1)Hx zzg xandx z

18、xzHx zxzxxzzgxxg xg xzz有:滿足H為凸集, 為邊界點(diǎn),所以存在過 和法方向 的支撐超平面 滿足:( *, ( *)xg x( *, ( *)xg xs( *)( )( *)Tmg xg xsxxxR 充分性:1212,01, *(1)x xxxx有：1122121212( *)()( *), ( *)()( *)( *)(1)*)()(1) ()( *)()(1) ()TTTg xg xsxxg xg xsxxg xsxxxg xg xg xg xg x則有：即：ABC3S4S( )LRz( )LRz函數(shù)示意圖定義7.4.2 若 為凹函數(shù),在 向量滿足: 1( ) :mg

19、 xRR*mxRmsR( *)(*)( )Tmg xsxxg xxR 則稱 為 在 的一個(gè)次梯度,所有的次梯度集合記為: ( )g xs( *)g x*x定理7.4.3 若 為凹函數(shù), 為 的充要條件為( )g x*xmax ( )|mg xxR0( *)g x 定理7.4.4 設(shè)LR的可行解集合Q由有限個(gè)整數(shù)點(diǎn)組成,其極點(diǎn)為 有: ()kxkK( *)min* ()TTLRk Kzc xbAx* |( *)(), |,1,0( *)TiTiLRiiiiiiLRi IIi zc xbAxiI sbAxs ssz*LR記：則對(duì)任意為z ()的次梯度且：證明:*( ) (*)()()() ()(

20、)( *)i TTiTiTiTiTiTiLRLRsbAxbAxc xbAxc xbAxzz注: 若 不是最大值點(diǎn),則相交的兩個(gè)同目標(biāo)值的平面 滿足 *1122:()():()()TiTiTjTjc xbAxDc xbAxD12*DD且,兩平面的法方向交角不超過90度.當(dāng) 不是光滑點(diǎn)是,在 的鄰域內(nèi),當(dāng) 充分小時(shí),存在 ,使得:*max *,0isjI( )()TjTjLRzc xbAx由 內(nèi)所有次梯度夾角不超過90度,有( *)LRz( )( *)(*) ()()()0TjijLRLRzzbAxbAxbAx由上面的討論可得次梯度優(yōu)化算法如下:STEP1: 任選初始拉格朗日乘子 STEP2: 對(duì)

21、 ,從 中任選一個(gè)次梯度 ,若 則停,否則 重復(fù)STEP2.,1ttt()tgts0ts 1max,0, :1tttstt 注:1、 的選取:10:,0,(,1981):,01( )( ):|ttttUPLPtttatFisherbztztcs 2、停止準(zhǔn)則：:0(),|:( )( ):()tttLRUPLPttLRaTb szorsc ztztdz迭代次數(shù)上限或在一定步數(shù)內(nèi)變化不超過某給定值7.4.2 拉格朗日啟發(fā)式算法Step1: 拉格朗日次梯度法求IP下界Step2: 對(duì)所求解可行化例7.4.1 假設(shè)集合覆蓋問題SC通過前面的松弛得到一個(gè)解 ,當(dāng)其不可行時(shí)即存在i使得12(,)nxx x

22、x10nijjja x一個(gè)可行化方法是求k,滿足1min|1kji jj ncca 重復(fù)以上步驟,直到所有行都被覆蓋.集合覆蓋問題的拉格朗日松弛算法:Step1: 初始化0,0tStep2: 計(jì)算()tLRzStep3: 若所有行被覆蓋,stop; or 記 表示第i行沒有被覆蓋,在沒有被覆蓋的行中任選一行k,計(jì)算1is min|1,1,kjkjkdas其中1mtjjljldcaStep4 : 11,2tkktitiikttstepik 返回例7.4.2 對(duì)集合覆蓋問題12341314234min23451. .110,1,1,2,3,4jxxxxxxstxxxxxxj假設(shè):(1.5,1.6,

23、2.3)T1234( )min 1.10.80.31.2 5.3LRzxxxx( )LRz最優(yōu)解為:(1,0,0,0,),( )4.2LRxz第三行沒有被覆蓋,在可覆蓋第三行中選費(fèi)用最小的列min0.8,0.3,1.20.3代替1231.501.602.20.3124( )min 1.10.50.95.64.5LRzxxxLR1324最優(yōu)解為:x =x =1,x =x =07.5 案例應(yīng)用 能力約束單機(jī)排序問題111mod:min,1,2,1max ,11,0.0,1,2;1,2,0iniiiTititniitiittiiitititelZTxd ina xsYc tT inifxstYoth

24、erintx（1）（2）（3）:iiitiiTdxtidiati：完成 所需要的時(shí)段；： 時(shí)段產(chǎn)品 的產(chǎn)量；產(chǎn)品 的需求；：產(chǎn)品i的單位產(chǎn)品所占用的生產(chǎn)能力；c ：t時(shí)段可提供的生產(chǎn)能力；s： i產(chǎn)品的生產(chǎn)準(zhǔn)備所占用的能力。約束條件(1): 產(chǎn)品需求兩約束約束條件(2): 個(gè)時(shí)段產(chǎn)能約束約束條件(3): 準(zhǔn)備時(shí)間,ititixY T為自由變量，為因變量下算法的基本思想是將 中較大權(quán)數(shù)所對(duì)應(yīng)的產(chǎn)品盡可能早地生產(chǎn),1iin Step1: 當(dāng) 時(shí), ,依時(shí)段t能力 約束(2),將 盡可能往前安排直到 全部 生產(chǎn),可能出現(xiàn)以下幾種情況: (a)若 的全部需求沒有全部生產(chǎn),且時(shí)段t的能力足以滿足 的生產(chǎn)準(zhǔn)備，則以時(shí)段t的最大余能力生產(chǎn) ，剩余未能生產(chǎn)的分到 時(shí)段， 返回step1; (b) 若的全部需求已生產(chǎn)，則當(dāng) 時(shí)停止，否則 返回step1; (c)若 沒有全部產(chǎn)出，且無法在該時(shí)段生產(chǎn)， 則 ,返回step1;Step0: ,從第一時(shí)段 開始;,1,2SUn1t U*max|iiiU*i* id*i*i*i1t 1tt *i *SSi1,SnUUS *UUiStep2: 若 則 返回step2.,1,USn1,1,ttUnS 算法能力約束排序問題的拉格朗日松弛算法0111mo