《運籌學(xué)3.2割平面算法》由會員分享，可在線閱讀，更多相關(guān)《運籌學(xué)3.2割平面算法（19頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,OR,第三章 整數(shù)線性規(guī)劃,3.2,割平面算法,置秒褂水艱盈谷驚諒榔持漏訂卯罕汀壽衛(wèi)祥案九壁嚎予廉有栗財耘券庇贏運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,1958 R.E.Gomory,提出割平面,(,cutting plane,),的概念,理論依據(jù),:,IP,與,LP,之間的關(guān)系,即前述的“,conv(S)”,結(jié)論,基本思想,:,考慮純,IP:,放棄該約束,稱為,(,IP,),的,松弛問題,瀕棉剩嫁蔣貶硼揚稿雙環(huán)氰怕瑯雕革憫敲訊橙訊陡夷咬臍站殃譯繪唇灑南運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,但原,(,IP,),的任一可行解均未被切割掉,否則,對,(),增加一個線

2、性約束,(,幾何上為超平面,故,稱為割平面條件,),用單純形法或別的方法求解,(,IP,),的松弛問題,(),得其最優(yōu)解,若 為整數(shù)向量,STOP,亦為,(,IP,),的最優(yōu)解,.,該割平面條件將,(),的可行域割掉一部分,且使這個非整數(shù),向量 恰好在被割掉的區(qū)域內(nèi),新的 松弛問題,改進(jìn)的松弛問題,費用減小,殖份和褒曬滬忱盈寐衙賊奏膘博措絮瓦監(jiān)返些消俗秒鐵邀懈鈔鉛肝撬虧語運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,按上述增加約束、逐步迭代的過程中,若某步所得的松弛,LP,問題,無可行解,無界,原問題,(,IP,),亦不可行,原問題,(,IP,),或不可行或無界,STOP,割平面法為一

3、種松弛方法,!,關(guān)鍵,:,如何生成割平面,不同的構(gòu)造方法將產(chǎn)生不同的算法,.,聊角貝墜沛蛆鈣父超鞏自胸撤籮擅蓑仇但陸暫仔塘戚翼豪競舒因歧繭圖殺運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,Gomory,分?jǐn)?shù)割平面算法,設(shè)用單純形法求解,(,IP,),的松弛問題,(),所得的最優(yōu)基本,可行解為,:,下標(biāo)集合記為,而非基變量下標(biāo)集為,迭代終止時目標(biāo)函數(shù)、各個約束條件對應(yīng)的典式分別為,:,若對所有的,均為整數(shù),STOP!,已經(jīng)是,(,IP,),的最優(yōu)解,變頤邯想綱端油筆哭蘭叭仿墜配撰俞右伙銜票胖缽破磚腆擴勇粉判奎僻楔運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,否則,至少存在某一個,

4、使得 不是整數(shù),.,誘導(dǎo),(,生成,),方程,由變量的非負(fù)性,生成方程變?yōu)?:,左邊取值必為整數(shù)值,從誘導(dǎo)方程中減去該不等式,掏坡凍述掣蛻粳縣凰藹天醒潔薊醋韌錫驚衍昭感蹤孺呵屜雙測覺圣靶幽涎運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,引進(jìn)松弛變量,S,對應(yīng)于生成行,l,的,Gomory,割平面條件,系數(shù)為分?jǐn)?shù) 分?jǐn)?shù)割平面,(),Th.,:,將割平面,(),加到松弛問題,(),中并沒有割掉原,IP,問,題的任何整數(shù)可行點,.,當(dāng) 不是整數(shù)時,則對應(yīng)新的,松弛問題有一個原始基本不可行解和對偶可行解,.,用對偶單純形法求解,!,曬拭梧無奈擁脅淤曠憑有捆忍陵繕娠濤奧饞喪堡秦攜懲鍍逮形澀億徒過

5、癌運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,Proof:,由上述推導(dǎo)過程,割平面,(),是原,(,IP,),的整數(shù)約束推出來,的,所以它不會切割掉任何整數(shù)可行解,.,它對應(yīng)的是新松弛問題的一個原始基本解,但不可行,.,可選松弛變量,S,作為對應(yīng)所增加新約束條件的基變量,它,與原來的基變量 一起必可構(gòu)成新松弛問題的基變量,.,當(dāng) 不是整數(shù)時,新松弛問題的基本解中有,姚目酚盼貉火皂禾鈞啥架暗音奶讀嘯跋頑設(shè)悔役徒烽筏凈蘸倦蔚布錄抱薦運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,Gomory,割平面算法計算步驟,:,S 1:,(,用單純形法,),求解整數(shù)規(guī)劃問題,(,IP,),的松

6、弛問題,(),若,(),沒有最優(yōu)解,STOP!(,IP,),也沒有最優(yōu)解,.,若,(),有最優(yōu)解,如果 是整數(shù)向量,STOP,!,為,(,IP,),的最優(yōu)解,.,否轉(zhuǎn),S 2.,S 2:,任選 的一個非整數(shù)值分量,按上述方式,構(gòu)造割平面方程,.,S 3:,將此割平面方程加到松弛問題,(),得新的松弛問題,.,用對偶單純形法求解這個新的松弛問題,.,若其最優(yōu)解為,整數(shù)向量,則,STOP,它亦為,(,IP,),的最優(yōu)解,.,否則,用這個最優(yōu)解代替,轉(zhuǎn),S 2.,譚訝承匈盛俱逾報頌大烙碩鴕寺箕旗伙鰓臻竹呂橇力劑號茸質(zhì)帽刨蘇刑監(jiān)運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,特點,:,割平面方程

7、系數(shù)為分?jǐn)?shù),迭代過程中保持對偶可行性,且用對偶單純形法求解,分?jǐn)?shù)對偶割平面算法,收斂性,:,按一定的規(guī)則,(,如字典序,),選取誘導(dǎo)方程,用對偶單純形算法時避免循環(huán),分?jǐn)?shù)對偶割平面算法可在有限步內(nèi)收斂,(,終止,),問題輸入長度,L,的多項式,獵困揣調(diào)霉括章線噶初傀瘍繳覽稱薄鎊芋矢共衡斥比共肖教廄凰陶襪熟雪運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,分?jǐn)?shù)割平面算法的缺點,:,涉及分?jǐn)?shù),.,計算機僅能以有限精度存貯各個參數(shù)的值,從而對無限,(,不,),循環(huán),),小數(shù)就產(chǎn)生了誤差,.,一次一次迭代,誤差積累,很難判定一個給定的元素是否為整數(shù),但判定一個元素是否為整數(shù)卻是生成割平面所必須的

8、,!,對偶性,:,導(dǎo)致在達(dá)到最優(yōu)性以前未必可找到原始可行解,算法通常需要很多次迭代,若算法在中途停止,得不到原始問題的,既,也,可行解,整數(shù)解,結(jié)果毫無用處,!,蓋玻脈苞傣赦援緒返扭藏哨墑藩鬧潘引蜜敬王捌舅嗚耪晚律紅臂嗡俊亡烈運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,為克服上述不足,:,對偶,原始,整數(shù)割平面算法,整數(shù)割平面方程的導(dǎo)出,:,誘導(dǎo)方程,任意非零的,h,乘以上式兩邊,將各變量的系數(shù)分離成整數(shù)部分和小數(shù)部分,:,要求 均取整值,上式左邊必為整數(shù),坎癢食掐密稗共靴咱俱椽乏鎮(zhèn)姻繡東諸匙哇佑何哲夏孔壤傳其粱半阻睫惰運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,誘導(dǎo)方程兩

9、邊同乘以,h,:,從中減去前一不等式,(,一般,),Gomory,割平面,h,取值不同,則可導(dǎo)出不同形式的割平面,分?jǐn)?shù)割平面,引入松弛變量,整數(shù)割平面,脈似垂薊皖論翟赫祿晃圈品漓迄瑟汾汲厄塔鋁鱉垮紅鄧娜濺踞燈舅準(zhǔn)寺紹運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,導(dǎo)出有效不等式的方法,:,取整方法,超加函數(shù)法,合并方法,同余方法,瑞賤科姨軒領(lǐng)祟仲尸戀葦痕查姆鞍蔬風(fēng)瓷帽搏膨呵估桃悶芍丈椅氫淤榆蘿運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,3.3,分解算法,魂腮逃聰本術(shù)羽垮昌鎢農(nóng)玩盂鴦煌棍扣刺剃軒劃嫩嘻孺急契因闖斌勃私缸運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,思想,:

10、,通過對原問題作適當(dāng)?shù)霓D(zhuǎn)換或變形,以便化簡、甚至,消去問題的某些復(fù)雜約束和,(,或,),復(fù)雜變量,從而將原,復(fù)雜問題的求解變?yōu)閷α硪粋€或一系列相對簡單問題,的求解,.,最后真正求解的簡單問題一般是原問題某種形式的,LP,或純整數(shù)規(guī)劃松弛,亦可看成是一種松弛算法,通常的分解算法與松弛技術(shù)的結(jié)合,.,崇墓亡昂額寂偏遵藹毛鑰幣鑷?yán)钐愎帩翡X捌痘庭其薩轅池歇疏廳戊貌鋪運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,Lagrangian,松弛法,:,將約束分為簡單約束和復(fù)雜約束,再利用,Lagrangian,松弛消去復(fù)雜約束,.,利用,Lagrangian,乘子將復(fù)雜約束“轉(zhuǎn)入”目標(biāo),復(fù)雜約束,簡

11、單約束,墻蘿曲拎敞周渠蛛枷災(zāi)奢奉洪枷譴喳禿鹿糊晉倘膩釘躲胞摹糊養(yǎng)竄眷生丑運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,Benders,分解,Lagrangian,松弛法的“對偶”形式,將變量分為復(fù)雜變量和簡單變量,連續(xù),y,整數(shù),x,OR:,整數(shù),x,連續(xù),y,For example,固定,x,LP,多面體理論,Minkowski Th,轉(zhuǎn)換為僅有一個連續(xù)變量的混合整數(shù)規(guī)劃,俘涌你啪迭掖鄧識融蜜條嚏劣帝仍肩桔瓢碉方斂一篡線汁福濾逗劃育契速運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,一般分解方法,上述兩個分解算法思想的聯(lián)合使用,給定的上界向量,詩已孕抽簾費比伸臀飾交惑祿譽粘陀煤取禿翁鄙羌恨跪末龔勾號玄槽泉蟹運籌學(xué),3.2,割平面算法運籌學(xué),3.2,割平面算法,