1、Page;.1拉格朗日松弛算法- The Lagrangian Relaxation MethodPage;.2OutlinePage;.3 引入拉格朗日松弛算法n拉格朗日松弛是求解下界的一種方法n拉格朗日松弛應用于求解 約束規劃問題目標函數值增大最優值上界下界gapPage;.4n 為什么拉格朗日松弛可以求得下界？基本原理將造成問題難的約束吸收到目標函數中，并使得目標函數仍保持線性，使得問題容易求解。拉格朗日松弛后變換為：IP的最優解是LR的一個可行解，所以，原問題：拉格朗日乘子（非負）Page;.5基本原理g(x): 原問題Def g(x):原問題的可行域f(x): 松弛后的問題Def f

2、(x): 松弛問題的可行域Page;.6用途n為什么拉格朗日松弛 popular ?第一，對于線性整數規劃問題，將難約束吸收到目標函數后，問題變得容易求解。第二，實際的計算結果證實拉格朗日松弛方法所給的下界相當不錯，且計算時間可以接受。同時，可以進一步利用拉格朗日松弛的基本原理構造基于拉格朗日松弛的啟發式算法。不一定是可行解，但是可以求得下界 獲得可行解（上界）/最優解（最優值）為什么拉格朗日松弛 popular ？Page;.7OutlinePage;.8如何應用n如何選取松弛的條件？原則：該條件去掉后使得問題容易求解。n如何選擇最優的拉格朗日乘子？原問題的拉格朗日松弛為：原問題的拉格朗日對

3、偶為：最好的下界Page;.9如何應用凹函數凹函數（向上凸的）梯度法光滑的（可微）次梯度法非光滑（不可微）Page;.10如何應用梯度法梯度法：在某一點，沿梯度方向搜索，能找到函數的極值點。ABC步驟：任給一個初始出發點，設為X0，X0X1（2）計算該點當前梯度（導數） y；（3）修改當前參數 X1=X0+d* y（4）計算該點當前梯度（導數） y； 重復（1）設定一個步長d；一元函數Page;.11如何應用次梯度法次梯度法：在某一點，沿次梯度方向搜索，能找到函數的極值點。 為 的一個可行解次梯度不唯一步驟：STEP1:STEP2: ， 否則，步長：Page;.12如何應用步長為原問題的一個上

4、界，可以由一個可行解的目標值確定，也可以通過估計的方法得到。可隨t 的變化逐步修正。原問題的下界， 在給定的若干步沒有變化時，則取其一半。 Page;.13如何應用停止原則（1）迭代次數不超過 T。這是一種最為簡單的原則，但解的質量無法保證。停止原則：（2） 。這是最為理想的狀態，此時， 達到拉格朗日對偶的最優解。在實際計算中，由于問題的復雜性和計算機本身的計算誤差，這樣的結果難達到，常常用 來代替。（3） 可變時，這種情況表示已得到原問題的最優解。最優值為 。（4） 在規定的步數內變化不超過一個給定的值。這時認為目標值不可能再變化，因此，停止運算。Page;.14OutlinePage;.1

5、5簡單例子Page;.16簡單例子Page;.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;.18簡單例子1234643212+-=xxxxMinTX)(=1 ，1 ，1 ，1221234162-=+-=LBZTS）2，1，1（2-=3826）2（62=-=TTT）03434（0，）2，1，1（384，4

6、，43,= -+)max(=Page;.19簡單例子38311383243213+3-=xxxxMinTX)(=0，0，0，1323823=+3-=LBZTS）1 ，0（30=821263=-=TTT）03434（0，）1 ，0，0（80，34，344,= +)max(=Page;.20OutlinePage;.21實際問題中的應用原問題復雜約束：船舶必須在到港之后靠泊Page;.22實際問題中的應用松弛后的問題Page;.23實際問題中的應用松弛后的問題三維指派問題二維指派問題匈牙利法Page;.24實際問題中的應用獲得可行解的啟發式算法停止準則1停止準則2Page;.25實際問題中的應用將次梯度法擴展為拉格朗日松弛啟發式算法。每更改一次拉格朗日乘子，求出一個下界，構造啟發式算法修改不可行解，得到一個上界。目標函數值增大最優值上界下界gapPage;.26OutlinePage;.27難點探討（1）松弛條件的選取。將復雜的約束條件松弛，復雜指的是該約束導致模型在多項式時間內不能求解。一個問題的計算時間 m(n) 不大于問題大小 n 的