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

2、于整數(shù)規(guī)劃問題中,決策變量為較大整數(shù)的情形. 此類算法分兩階段: 第一階段為求松弛后線性規(guī)劃問題的最優(yōu)解; 第二階段為將解整數(shù)化,并考慮可行性.,例2: 對偶規(guī)劃松弛方法: 7.1.2的對偶形式為:,其中Y為決策變量.,注:,由對偶理論知,7.1.2和7.1.3有相同的最優(yōu)值,至于采用其中的哪個模型求解7.1.1的下界,需比較哪個計算簡單.,例3. 代理松弛法:,當(7.1.1)中的約束太多時,代理松弛一個約束,代替(7.1.1)中的K個約束,極端情況可以用一個代替全部,注: 代理松弛法保證目標函數(shù),整數(shù)規(guī)劃約束不變, 顯然,由代理松弛法求得的解不一定可行,例4. 拉格朗日松弛方法,基本原理:

3、 將目標函數(shù)中造成問題難的約束吸 收到目標函數(shù)中,并保持目標函數(shù)的線性,使問題容易求解.,Q:為什么對此類方法感興趣?,A: (1). 在一些組合優(yōu)化中,若在原問題中減少一些約束,則使得問題求解難度大大降低.(我們把這類約束稱為難約束). (2). 實際的計算表明此種方法所得到的結(jié)果相當不錯.,7.1 基于規(guī)劃論的松弛方法,松弛的定義（7.1.1）: 問題,整數(shù)規(guī)劃模型:,滿足下列性質(zhì)時,稱為7.1.1的一個松弛(relaxation). 可行解區(qū)域兼容: 目標函數(shù)兼容:,其中, 為7.1.1的可行域.,例7.1.1 set covering problem,問題描述: 設(shè) ,所有 ,且每一列

4、對應一個費用 , 表示第j列覆蓋第i行,要求在最小的費用下選擇一些列,使其覆蓋所有的行.,松弛問題:,松弛模型:,以上問題很容易求得最優(yōu)解,7.2 拉格朗日松弛理論,原整數(shù)規(guī)劃問題,拉格朗日松弛,定理7.2.1 LR同下整數(shù)規(guī)劃問題(7.2.1)有相同 的復雜性,且若IP可行解非空，則:,證明:,注:定理7.2.1說明拉格朗日松弛是IP問題的一個下界,但我們應該求與IP最接近的下界,即:,定義7.2.1 若 ,滿足以下條件,則稱D為凸集.,對于離散點集 ,其凸包定義為:,顯然Con(Q)為凸集.,定理7.2.2 若拉格朗日對偶問題的目標值有限,則,證明:,設(shè)Con(Q)的極點為 ,極方向為 則

5、:,由LD問題有限,則有:,上述問題等價于:,整理得:,其對偶問題為:,即有:,推論7.2.1: 對于任給c,整數(shù)規(guī)劃問題IP和拉 格 朗日對偶問題LD的目標值相等的充要條件為:,證: 顯然有,從而有:,再由定理7.2.2:,若對任何c有 ,則問題得證.,例7.2.1 假設(shè)整數(shù)規(guī)劃問題IP,第一個約束為復雜約束,其拉格朗日松弛后的模型LR為:,4,3,2,1,1,2,3,4,l2,l1,l4,l3,E,D,C,B,A,7.2.3圖解示意,單位化下降方向:,最優(yōu)值只能在(4,0)和(3,4)兩點得到,過這兩點的直線方程:y+x4=16.其垂直方向為:,綜合有:,例7.2.2(繼7.2.1) 例7

6、.2.1中,4,3,2,1,1,2,3,4,D,C,B,4,3,2,1,1,2,3,4,D,C,B,S1,S2,由推論7.2.1可以知道, 由兩個因素有關(guān):第一個因素是目標函數(shù)中的C,推論7.2.1要求對所有的C滿足S1=S2,但也可能存在某個C使得,第二個因素是可行解的區(qū)域.由上面的圖形可知,SI和S2不同,所以存在一個C,使得 不為零,如在例7.2.1中, ,在 達到拉格朗日對偶問題的最優(yōu)值,其最優(yōu)解為(4,0); ,其一個最優(yōu)解也為(4,0).由此我們可以知道,即使拉格朗日松弛在某個 下達到的最優(yōu)解為原問題的可行解,我們也不能斷言 .除非此時 .,定理7.2.3 若線性規(guī)劃松弛問題LP存

7、在可行解,則,注:此定理說明,拉格朗日松弛對偶后的目標值 是IP 問題的一個下界,且不比 差.,定理7.2.3 的充要條件是存在 和 使得:,證明：、充分性：,、必要性：,記為問題的最優(yōu)解，為問題的最優(yōu)解，則：,例7.2.3 (繼例7.2.1) 時, 為問題的一個可行解,此時:,一般情況下,可大致估計:,7.3. 拉格朗日松弛的進一步討論,目的: 對非標準的拉格朗日形式討論.,一、等號約束的松弛,二、LR最優(yōu)解和LP最優(yōu)解的關(guān)系,具體例見例7.3.1。,定理7.3.1 的充要條件為：,三、拉格朗日松弛的整數(shù)性,定義7.3.1 若LR的最優(yōu)解與其整數(shù)約束無關(guān)，則稱該問題具有整數(shù)性，即：,定理7.

8、3.2 若LR具有整數(shù)性，則,四、 拉格朗日分解,7.4 拉格朗日松弛算法,7.4.1 次梯度算法（subgradient optimization）,定義：（凹函數(shù)） 函數(shù) 滿足以下條件稱為凹函數(shù),定理7.4.1 若LR的可行解集合Q為有限個實數(shù)點集，則以下函數(shù)為凹函數(shù),定理7.4.1 函數(shù)為凹函數(shù)的充要條件為：,證明 必要性：設(shè) 為凹函數(shù)，則,H為凸集, 為邊界點,所以存在過 和法方向 的支撐超平面 滿足:,充分性:,A,B,C,定義7.4.2 若 為凹函數(shù),在 向量滿足:,則稱 為 在 的一個次梯度,所有的次梯度集合記為:,定理7.4.3 若 為凹函數(shù), 為 的充要條件為,定理7.4.4

9、 設(shè)LR的可行解集合Q由有限個整數(shù)點組成,其極點為 有:,證明:,注: 若 不是最大值點,則相交的兩個同目標值的平面 滿足,且,兩平面的法方向交角不超過90度.,當 不是光滑點是,在 的鄰域內(nèi),當 充分小時,存在 ,使得:,由 內(nèi)所有次梯度夾角不超過90度,有,由上面的討論可得次梯度優(yōu)化算法如下:,STEP1: 任選初始拉格朗日乘子,STEP2: 對 ,從 中任選一個次梯度 ,若 則停,否則 重復STEP2.,注:,1、 的選取:,2、停止準則：,7.4.2 拉格朗日啟發(fā)式算法,Step1: 拉格朗日次梯度法求IP下界,Step2: 對所求解可行化,例7.4.1 假設(shè)集合覆蓋問題SC通過前面的

10、松弛得到一個解 ,當其不可行時即存在i使得,一個可行化方法是求k,滿足,重復以上步驟,直到所有行都被覆蓋.,集合覆蓋問題的拉格朗日松弛算法:,Step1: 初始化,Step2: 計算,Step3: 若所有行被覆蓋,stop; or 記 表示第i行沒有被覆蓋,在沒有被覆蓋的行中任選一行k,計算,Step4 :,例7.4.2 對集合覆蓋問題,假設(shè):,最優(yōu)解為:,第三行沒有被覆蓋,在可覆蓋第三行中選費用最小的列,7.5 案例應用 能力約束單機排序問題,約束條件(1): 產(chǎn)品需求兩約束 約束條件(2): 個時段產(chǎn)能約束 約束條件(3): 準備時間,下算法的基本思想是將 中較大權(quán)數(shù)所對應的產(chǎn)品盡可能早地

11、生產(chǎn),Step1: 當 時, ,依時段t能力 約束(2),將 盡可能往前安排直到 全部 生產(chǎn),可能出現(xiàn)以下幾種情況: (a)若 的全部需求沒有全部生產(chǎn),且時段t的能力足以滿足 的生產(chǎn)準備，則以時段t的最大余能力生產(chǎn) ，剩余未能生產(chǎn)的分到 時段， 返回step1; (b) 若的全部需求已生產(chǎn)，則當 時停止，否則 返回step1; (c)若 沒有全部產(chǎn)出，且無法在該時段生產(chǎn)， 則 ,返回step1;,Step0: ,從第一時段 開始;,Step2: 若 則 返回step2.,算法,能力約束排序問題的拉格朗日松弛算法,求解以上LRP問題分以下兩步: (1)對給定的 ,求下子問題(SUBP),(2) 對所有 求,定理7.5.2 對于充分大T,若 已知且非負,則SU