[教育]運籌學(xué)3.2割平面算法

1、§ 3.2 割平面算法,1958 R.E.Gomory 提出割平面(cutting plane)的概念,理論依據(jù) : IP與LP之間的關(guān)系, 即前述的“conv(S)”結(jié)論,基本思想 :,考慮純IP :,放棄該約束,稱為( IP )的松弛問題,,,但原( IP )的任一可行解均未被切割掉,否則, 對( )增加一個線性約束(幾何上為超平面, 故稱為割平面條件),用單純形法或別的方法求解( IP )的松弛問題(

2、 ), 得其最優(yōu)解 ,,若 為整數(shù)向量→STOP, 亦為( IP )的最優(yōu)解.,該割平面條件將( )的可行域割掉一部分, 且使這個非整數(shù)向量 恰好在被割掉的區(qū)域內(nèi),,新的 松弛問題改進的松弛問題,,,,費用減小,,按上述增加約束、逐步迭代的過程中, 若某步所得的松弛LP問題,,,無可行解,無界,原問題( IP )亦不可行,原問題( IP )或不可行或無界,,,STOP,,割平面法為一種松弛方法 !,關(guān)

3、鍵 : 如何生成割平面, 不同的構(gòu)造方法將產(chǎn)生不同的算法 .,Gomory 分數(shù)割平面算法,設(shè)用單純形法求解( IP )的松弛問題( )所得的最優(yōu)基本可行解為 :,,下標集合記為 , 而非基變量下標集為,迭代終止時目標函數(shù)、各個約束條件對應(yīng)的典式分別為 :,若對所有的 , 均為整數(shù),STOP ! 已經(jīng)是( IP )的最優(yōu)解,,,,,否則, 至少存在某一個

4、 ,使得 不是整數(shù) .,誘導(dǎo)(生成)方程,由變量的非負性,生成方程變?yōu)?:,左邊取值必為整數(shù)值,從誘導(dǎo)方程中減去該不等式,,引進松弛變量S,對應(yīng)于生成行l(wèi) 的Gomory割平面條件,系數(shù)為分數(shù)→ 分數(shù)割平面,,,,( △ ),Th. : 將割平面(△)加到松弛問題( )中并沒有割掉原IP問 題的任何整數(shù)可行點. 當 不是整數(shù)時, 則對應(yīng)新的

5、 松弛問題有一個原始基本不可行解和對偶可行解 .,,用對偶單純形法求解 !,,Proof:,由上述推導(dǎo)過程, 割平面(△)是原( IP )的整數(shù)約束推出來的, 所以它不會切割掉任何整數(shù)可行解 .,它對應(yīng)的是新松弛問題的一個原始基本解, 但不可行 .,可選松弛變量S作為對應(yīng)所增加新約束條件的基變量, 它與原來的基變量 一起必可構(gòu)成新松弛問題的基變量.,當 不是整數(shù)時, , 新松

6、弛問題的基本解中有,Gomory 割平面算法計算步驟 :,S 1 : (用單純形法)求解整數(shù)規(guī)劃問題( IP )的松弛問題( ),若( )沒有最優(yōu)解, STOP ! ( IP )也沒有最優(yōu)解 .若( )有最優(yōu)解 , 如果 是整數(shù)向量, STOP ! 為( IP ) 的最優(yōu)解. 否轉(zhuǎn) S 2 .,S 2 : 任選 的一個非整數(shù)值分量 , 按上述方式

7、 構(gòu)造割平面方程 .,S 3 : 將此割平面方程加到松弛問題( )得新的松弛問題. 用對偶單純形法求解這個新的松弛問題. 若其最優(yōu)解為 整數(shù)向量, 則STOP, 它亦為( IP )的最優(yōu)解. 否則, 用這個最優(yōu)解代替 , 轉(zhuǎn)S 2 .,特點 :,割平面方程系數(shù)為分數(shù),迭代過程中保持對偶

8、可行性,且用對偶單純形法求解,分數(shù)對偶割平面算法,收斂性 :,按一定的規(guī)則(如字典序)選取誘導(dǎo)方程,用對偶單純形算法時避免循環(huán),分數(shù)對偶割平面算法可在有限步內(nèi)收斂(終止),,,,,問題輸入長度L的多項式,,分數(shù)割平面算法的缺點 :,① 涉及分數(shù).,計算機僅能以有限精度存貯各個參數(shù)的值,從而對無限((不)循環(huán))小數(shù)就產(chǎn)生了誤差 .,一次一次迭代誤差積累,很難判定一個給定的元素是否為整數(shù),但判定一個元素是否為整數(shù)卻是生成割平面所必須

9、的 !,② 對偶性 :導(dǎo)致在達到最優(yōu)性以前未必可找到原始可行解,算法通常需要很多次迭代,結(jié)果毫無用處 !,,,為克服上述不足 :,整數(shù)割平面方程的導(dǎo)出 :,誘導(dǎo)方程,任意非零的h乘以上式兩邊,將各變量的系數(shù)分離成整數(shù)部分和小數(shù)部分 :,,,∵要求 均取整值,,∴ 上式左邊必為整數(shù),誘導(dǎo)方程兩邊同乘以[h] :,從中減去前一不等式,(一般) Gomory 割平面,h取值不同, 則可導(dǎo)出不同形式的割平面,分數(shù)割平面,引

10、入松弛變量,整數(shù)割平面,,,導(dǎo)出有效不等式的方法 :,,取整方法,超加函數(shù)法,合并方法,同余方法,§ 3.3 分解算法,思想 : 通過對原問題作適當?shù)霓D(zhuǎn)換或變形, 以便化簡、甚至 消去問題的某些復(fù)雜約束和(或)復(fù)雜變量, 從而將原 復(fù)雜問題的求解變?yōu)閷α硪粋€或一系列相對簡單問題 的求解 .,∵ 最后真正求解的簡單問題一般是原問題某種形式的LP

11、 或純整數(shù)規(guī)劃松弛,∴ 亦可看成是一種松弛算法,通常的分解算法與松弛技術(shù)的結(jié)合 .,,Lagrangian 松弛法 :,將約束分為簡單約束和復(fù)雜約束, 再利用Lagrangian 松弛消去復(fù)雜約束 .,利用Lagrangian 乘子將復(fù)雜約束“轉(zhuǎn)入”目標,,復(fù)雜約束,簡單約束,Benders 分解,Lagrangian 松弛法的“對偶”形式,將變量分為復(fù)雜變量和簡單變量,連續(xù) y,整數(shù) x,OR : 整數(shù) x