1拉格朗日松弛算法---TheLagrangianRelaxationMethod拉格朗日松弛Outline21.基本原理及用途2.如何應(yīng)用3.簡單例子4.在實際問題中的應(yīng)用5.難點探討拉格朗日松弛

引入拉格朗日松弛算法3拉格朗日松弛是求解下界的一種方法拉格朗日松弛應(yīng)用于求解約束規(guī)劃問題目標函數(shù)值增大最優(yōu)值上界下界gap拉格朗日松弛

為什么拉格朗日松弛可以求得下界？基本原理4將造成問題難的約束吸收到目標函數(shù)中，并使得目標函數(shù)仍保持線性，使得問題容易求解。拉格朗日松弛后變換為：IP的最優(yōu)解是LR的一個可行解，所以，原問題：拉格朗日乘子（非負）拉格朗日松弛基本原理5g(x):原問題Defg(x):原問題的可行域f(x):松弛后的問題Deff(x):松弛問題的可行域拉格朗日松弛用途6為什么拉格朗日松弛popular?第一，對于線性整數(shù)規(guī)劃問題，將難約束吸收到目標函數(shù)后，問題變得容易求解。第二，實際的計算結(jié)果證實拉格朗日松弛方法所給的下界相當(dāng)不錯，且計算時間可以接受。同時，可以進一步利用拉格朗日松弛的基本原理構(gòu)造基于拉格朗日松弛的啟發(fā)式算法。不一定是可行解，但是可以求得下界獲得可行解（上界）/最優(yōu)解（最優(yōu)值）為什么拉格朗日松弛popular？拉格朗日松弛Outline71.基本原理及用途2.如何應(yīng)用3.簡單例子4.在實際問題中的應(yīng)用5.難點探討拉格朗日松弛如何應(yīng)用8如何選取松弛的條件？原則：該條件去掉后使得問題容易求解。如何選擇最優(yōu)的拉格朗日乘子？原問題的拉格朗日松弛為：原問題的拉格朗日對偶為：最好的下界拉格朗日松弛如何應(yīng)用—凹函數(shù)9凹函數(shù)（向上凸的）梯度法光滑的（可微）次梯度法非光滑（不可微）拉格朗日松弛如何應(yīng)用—梯度法10梯度法：在某一點，沿梯度方向搜索，能找到函數(shù)的極值點。ABC步驟：任給一個初始出發(fā)點，設(shè)為X0，X0X1（2）計算該點當(dāng)前梯度（導(dǎo)數(shù)）y’；（3）修改當(dāng)前參數(shù)X1=X0+d*y’（4）計算該點當(dāng)前梯度（導(dǎo)數(shù)）y’；

……重復(fù)（1）設(shè)定一個步長d；一元函數(shù)拉格朗日松弛如何應(yīng)用—次梯度法11次梯度法：在某一點，沿次梯度方向搜索，能找到函數(shù)的極值點。為的一個可行解次梯度不唯一步驟：STEP1:STEP2:，

否則，步長：拉格朗日松弛如何應(yīng)用—步長12為原問題的一個上界，可以由一個可行解的目標值確定，也可以通過估計的方法得到。可隨t的變化逐步修正。原問題的下界，

在給定的若干步?jīng)]有變化時，則取其一半。

拉格朗日松弛如何應(yīng)用—停止原則13（1）迭代次數(shù)不超過T。這是一種最為簡單的原則，但解的質(zhì)量無法保證。停止原則：（2）。這是最為理想的狀態(tài)，此時，達到拉格朗日對偶的最優(yōu)解。在實際計算中，由于問題的復(fù)雜性和計算機本身的計算誤差，這樣的結(jié)果難達到，常常用來代替。（3）可變時，這種情況表示已得到原問題的最優(yōu)解。最優(yōu)值為。（4）在規(guī)定的步數(shù)內(nèi)變化不超過一個給定的值。這時認為目標值不可能再變化，因此，停止運算。拉格朗日松弛Outline141.基本原理及用途2.如何應(yīng)用3.簡單例子4.在實際問題中的應(yīng)用5.難點探討拉格朗日松弛簡單例子15拉格朗日松弛簡單例子16拉格朗日松弛簡單例子17

StartingwithZUP=6,β=2andi=0fori=1,2,3,迭代三次。求出每次迭代的下界和拉格朗日乘子。

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