拉格朗日松弛

1、Page1拉格朗日松弛算法- The Lagrangian Relaxation MethodPageOutline21. 基本原理及用途2. 如何應(yīng)用3. 簡(jiǎn)單例子4. 在實(shí)際問(wèn)題中的應(yīng)用5. 難點(diǎn)探討Page 引入拉格朗日松弛算法3n 拉格朗日松弛是求解下界的一種方法n 拉格朗日松弛應(yīng)用于求解 約束規(guī)劃問(wèn)題目標(biāo)函數(shù)值增大最優(yōu)值上界下界gapPagen 為什么拉格朗日松弛可以求得下界？基本原理4將造成問(wèn)題難的約束吸收到目標(biāo)函數(shù)中，并使得目標(biāo)函數(shù)仍保持線性，使得問(wèn)題容易求解。拉格朗日松弛后變換為：IP的最優(yōu)解是LR的一個(gè)可行解，所以，原問(wèn)題：拉格朗日乘子（非負(fù)）Page基本原理5g(x): 原

2、問(wèn)題Def g(x):原問(wèn)題的可行域f(x): 松弛后的問(wèn)題Def f(x): 松弛問(wèn)題的可行域Page用途6n 為什么拉格朗日松弛 popular ? 第一，對(duì)于線性整數(shù)規(guī)劃問(wèn)題，將難約束吸收到目標(biāo)函數(shù)后，問(wèn)題變得容易求解。 第二，實(shí)際的計(jì)算結(jié)果證實(shí)拉格朗日松弛方法所給的下界相當(dāng)不錯(cuò)，且計(jì)算時(shí)間可以接受。同時(shí)，可以進(jìn)一步利用拉格朗日松弛的基本原理構(gòu)造基于拉格朗日松弛的啟發(fā)式算法。不一定是可行解，但是可以求得下界 獲得可行解（上界）/最優(yōu)解（最優(yōu)值）為什么拉格朗日松弛 popular ？PageOutline71. 基本原理及用途2. 如何應(yīng)用3. 簡(jiǎn)單例子4. 在實(shí)際問(wèn)題中的應(yīng)用5. 難點(diǎn)探

3、討Page如何應(yīng)用8n 如何選取松弛的條件？原則：該條件去掉后使得問(wèn)題容易求解。n 如何選擇最優(yōu)的拉格朗日乘子？原問(wèn)題的拉格朗日松弛為：原問(wèn)題的拉格朗日對(duì)偶為：最好的下界Page如何應(yīng)用凹函數(shù)9凹函數(shù)（向上凸的）梯度法光滑的（可微）次梯度法非光滑（不可微）Page如何應(yīng)用梯度法10梯度法：在某一點(diǎn)，沿梯度方向搜索，能找到函數(shù)的極值點(diǎn)。ABC步驟：任給一個(gè)初始出發(fā)點(diǎn)，設(shè)為X0，X0X1（2）計(jì)算該點(diǎn)當(dāng)前梯度（導(dǎo)數(shù)） y；（3）修改當(dāng)前參數(shù) X1=X0+d* y（4）計(jì)算該點(diǎn)當(dāng)前梯度（導(dǎo)數(shù)） y； 重復(fù)（1）設(shè)定一個(gè)步長(zhǎng)d；一元函數(shù)Page如何應(yīng)用次梯度法11次梯度法：在某一點(diǎn)，沿次梯度方向搜索，

4、能找到函數(shù)的極值點(diǎn)。 為 的一個(gè)可行解次梯度不唯一步驟：STEP1:STEP2: ， 否則，步長(zhǎng)：Page如何應(yīng)用步長(zhǎng)12為原問(wèn)題的一個(gè)上界，可以由一個(gè)可行解的目標(biāo)值確定，也可以通過(guò)估計(jì)的方法得到?？呻St 的變化逐步修正。原問(wèn)題的下界， 在給定的若干步?jīng)]有變化時(shí)，則取其一半。Page如何應(yīng)用停止原則13（1）迭代次數(shù)不超過(guò) T。這是一種最為簡(jiǎn)單的原則，但解的質(zhì)量無(wú)法保證。停止原則：（2） 。這是最為理想的狀態(tài)，此時(shí)， 達(dá)到拉格朗日對(duì)偶的最優(yōu)解。在實(shí)際計(jì)算中，由于問(wèn)題的復(fù)雜性和計(jì)算機(jī)本身的計(jì)算誤差，這樣的結(jié)果難達(dá)到，常常用 來(lái)代替。（3） 可變時(shí)，這種情況表示已得到原問(wèn)題的最優(yōu)解。最優(yōu)值為 。（

5、4） 在規(guī)定的步數(shù)內(nèi)變化不超過(guò)一個(gè)給定的值。這時(shí)認(rèn)為目標(biāo)值不可能再變化，因此，停止運(yùn)算。PageOutline141. 基本原理及用途2. 如何應(yīng)用3. 簡(jiǎn)單例子4. 在實(shí)際問(wèn)題中的應(yīng)用5. 難點(diǎn)探討Page簡(jiǎn)單例子15Page簡(jiǎn)單例子16Page簡(jiǎn)單例子17 Starting with ZUP=6,=2 and i=0 for i=1,2,3, 迭代三次。 求出每次迭代的下界和拉格朗日乘子。TX)(=0，0，0，0101312111=+=LBZTS）1 ，1 ，1（1=423061=-=TTT）4，4，4（0，）1 ，1 ，1（40，0，02= +)max(= 原約束：Page簡(jiǎn)單例子181

6、234643212+-=xxxxMinTX)(=1 ，1 ，1 ，1221234162-=+-=LBZTS）2，1，1（2-=3826）2（62=-=TTT）03434（0，）2，1，1（384，4，43,= -+)max(=Page簡(jiǎn)單例子1938311383243213+3-=xxxxMinTX)(=0，0，0，1323823=+3-=LBZTS）1 ，0（30=821263=-=TTT）03434（0，）1 ，0，0（80，34，344,= +)max(=PageOutline201. 基本原理及用途2. 如何應(yīng)用3. 簡(jiǎn)單例子4. 在實(shí)際問(wèn)題中的應(yīng)用5. 難點(diǎn)探討Page實(shí)際問(wèn)題中的應(yīng)

7、用原問(wèn)題21復(fù)雜約束：船舶必須在到港之后靠泊Page實(shí)際問(wèn)題中的應(yīng)用松弛后的問(wèn)題22Page實(shí)際問(wèn)題中的應(yīng)用松弛后的問(wèn)題23三維指派問(wèn)題二維指派問(wèn)題匈牙利法Page 24實(shí)際問(wèn)題中的應(yīng)用獲得可行解的啟發(fā)式算法停止準(zhǔn)則1停止準(zhǔn)則2Page實(shí)際問(wèn)題中的應(yīng)用25將次梯度法擴(kuò)展為拉格朗日松弛啟發(fā)式算法。每更改一次拉格朗日乘子，求出一個(gè)下界，構(gòu)造啟發(fā)式算法修改不可行解，得到一個(gè)上界。目標(biāo)函數(shù)值增大最優(yōu)值上界下界gapPageOutline261. 基本原理及用途2. 如何應(yīng)用3. 簡(jiǎn)單例子4. 在實(shí)際問(wèn)題中的應(yīng)用5. 難點(diǎn)探討Page難點(diǎn)探討27（1）松弛條件的選取。將復(fù)雜的約束條件松弛，復(fù)雜指的是該約束導(dǎo)致模型在多項(xiàng)式時(shí)間內(nèi)不能求解。一個(gè)問(wèn)題的計(jì)算時(shí)間 m(n