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

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

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

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

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

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

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

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

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

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

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

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