《整數(shù)規(guī)劃-課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《整數(shù)規(guī)劃-課件.ppt（146頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、整整 數(shù)數(shù) 規(guī)規(guī) 劃劃整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃問題與模型整數(shù)規(guī)劃問題與模型割平面法和分支定界法割平面法和分支定界法0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃指派問題的匈牙利法指派問題的匈牙利法應(yīng)用案例應(yīng)用案例整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃問題實(shí)例特點(diǎn)模型分類整數(shù)規(guī)劃整數(shù)規(guī)劃應(yīng)用案例投資組合問題旅游售貨員問題背包問題整數(shù)規(guī)劃整數(shù)規(guī)劃投資組合問題背 景實(shí) 例模 型整數(shù)規(guī)劃整數(shù)規(guī)劃背景證券投資證券投資：把一定的資金投入到合適的有價(jià)證券上以規(guī)避風(fēng)險(xiǎn)并獲得最大的利潤項(xiàng)目投資項(xiàng)目投資：財(cái)團(tuán)或銀行把資金投入到若干項(xiàng)目中以獲得中長期的收益最大。整數(shù)規(guī)劃整數(shù)規(guī)劃案例某財(cái)團(tuán)有 萬元的資金，經(jīng)出其考察選中 個(gè)投資項(xiàng)目，每個(gè)項(xiàng)目只能投資

2、一個(gè)。其中第 個(gè)項(xiàng)目需投資金額為 萬元，預(yù)計(jì)5年后獲利 萬元 ，問應(yīng)如何選擇項(xiàng)目使得5年后總收益最大？整數(shù)規(guī)劃整數(shù)規(guī)劃模型變量每個(gè)項(xiàng)目是否投資約束總金額不超過限制目標(biāo)總收益最大整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃旅游售貨員問題背景案例模型整數(shù)規(guī)劃整數(shù)規(guī)劃背景旅游線路安排 預(yù)定景點(diǎn)走且只走一次 路上時(shí)間最短配送線路貨郎擔(dān)問題 送貨地到達(dá)一次 總路程最短案例有一旅行團(tuán)從 出發(fā)要遍游城市 已知從 到 的旅費(fèi)為 ，問應(yīng)如何安排行程使總費(fèi)用最??？整數(shù)規(guī)劃整數(shù)規(guī)劃模型變量是否從i第個(gè)城市到第j個(gè)城市約束 每個(gè)城市只能到達(dá)一次、離開一次整數(shù)規(guī)劃整數(shù)規(guī)劃目標(biāo)總費(fèi)用最小整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃背包問題背景案

3、例模型整數(shù)規(guī)劃整數(shù)規(guī)劃背景郵遞包裹 把形狀可變的包裹用盡量少的車輛運(yùn)走旅行背包 容量一定的背包里裝盡可能的多的物品整數(shù)規(guī)劃整數(shù)規(guī)劃實(shí)例某人出國留學(xué)打點(diǎn)行李，現(xiàn)有三個(gè)旅行包，容積大小分別為1000毫升、1500毫升和2000毫升，根據(jù)需要列出需帶物品清單，其中一些物品是必帶物品共有7件，其體積大小分別為400、300、150、250、450、760、190、（單位毫升）。尚有10件可帶可不帶物品，如果不帶將在目的地購買，通過網(wǎng)絡(luò)查詢可以得知其在目的地的價(jià)格（單位美元）。這些物品的容量及價(jià)格分別見下表，試給出一個(gè)合理的安排方案把物品放在三個(gè)旅行包里。整數(shù)規(guī)劃整數(shù)規(guī)劃物品12345678910體積2

4、00350500430320120700420250100價(jià)格1545100705075200902030整數(shù)規(guī)劃整數(shù)規(guī)劃問題分析變量變量對(duì)每個(gè)物品要確定是否帶同時(shí)要確定放在哪個(gè)包裹里，如果增加一個(gè)虛擬的包裹把不帶的物品放在里面，則問題就轉(zhuǎn)化為確定每個(gè)物品放在哪個(gè)包裹里。如果直接設(shè)變量為每個(gè)物品放在包裹的編號(hào)，則每個(gè)包裹所含物品的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們設(shè)變量為第i個(gè)物品是否放在第j個(gè)包裹中整數(shù)規(guī)劃整數(shù)規(guī)劃約束約束 包裹容量限制 必帶物品限制 選帶物品限制整數(shù)規(guī)劃整數(shù)規(guī)劃目標(biāo)函數(shù)未帶物品購買費(fèi)用最小整數(shù)規(guī)劃整數(shù)規(guī)劃模型整數(shù)規(guī)劃整數(shù)規(guī)劃n特征特征變量整數(shù)性要求n來源來源 問題本身的要

5、求 引入的邏輯變量的需要n性質(zhì)性質(zhì)可行域是離散集合整數(shù)規(guī)劃整數(shù)規(guī)劃線性整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型0-1整數(shù)規(guī)劃模型混合整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型返回0-1整數(shù)規(guī)劃模型返回混合整數(shù)規(guī)劃模型返回算 法與線性規(guī)劃的關(guān)系分支定界算法割平面算法返回與線性規(guī)劃的關(guān)系整數(shù)規(guī)劃放松的線性規(guī)劃可行解是放松問題的可行解最優(yōu)值大于等于放松問題的最優(yōu)值線性規(guī)劃模型max z=x1+4x2s.t.14x1+42x2196 -x1+2x2 5 x1,x20整數(shù)規(guī)劃模型max z=x1+4x2s.t.14x1+42x2196 -x1+2x2 5 x1,x20 x1,x2 為整數(shù)0 1 2 3 4 5 6 7 84321

6、A(2.6,3.8)B(5,3)整數(shù)線性規(guī)劃（整數(shù)線性規(guī)劃（ILP）實(shí)例）實(shí)例線性規(guī)劃的最優(yōu)解A(x1,x2)=(2.6,3.8)不是整數(shù)解，目標(biāo)函數(shù)值為z=17.8。整數(shù)規(guī)劃的最優(yōu)解B(x1,x2)=(5,3)目標(biāo)函數(shù)值為z=17。線性規(guī)劃最優(yōu)解A(2.6,3.8)四舍五入得到的解為(3,4)，不是可行解；舍去尾數(shù)取整的解為(2,3)，目標(biāo)函數(shù)值z=14。因此整數(shù)規(guī)劃的最優(yōu)解一般不能由線性規(guī)劃的最優(yōu)解通過簡單的取整得到。0 1 2 3 4 5 6 7 84321A(2.6,3.8)B(5,3)整數(shù)線性規(guī)劃（整數(shù)線性規(guī)劃（ILP）解的特點(diǎn)）解的特點(diǎn)nILPILP是其中是其中是其中是其中LPLP

7、的一個(gè)子問題，所有解也是的一個(gè)子問題，所有解也是的一個(gè)子問題，所有解也是的一個(gè)子問題，所有解也是LPLP的可行解，所以如果的可行解，所以如果的可行解，所以如果的可行解，所以如果LPLP的最優(yōu)解滿足的最優(yōu)解滿足的最優(yōu)解滿足的最優(yōu)解滿足ILPILP的的的的整數(shù)條件，則已得最優(yōu)解。整數(shù)條件，則已得最優(yōu)解。整數(shù)條件，則已得最優(yōu)解。整數(shù)條件，則已得最優(yōu)解。注釋最優(yōu)解不一定在頂點(diǎn)上達(dá)到最優(yōu)解不一定是放松問題最優(yōu)解的鄰近整數(shù)解整數(shù)可行解遠(yuǎn)多余于頂點(diǎn)，枚舉法不可取分支定界算法算法思想算法步驟算例注釋算法思想隱枚舉法 分支 求解放松問題 舍棄 變界 分支最優(yōu)值比界壞最優(yōu)解為整數(shù)最優(yōu)值比界好最優(yōu)解為非整數(shù)最優(yōu)值比

8、界好整數(shù)規(guī)劃分枝定界法整 數(shù) 規(guī) 劃 在許多線性規(guī)劃問題中,要求最優(yōu)解必須取整數(shù).例如所求的解是機(jī)器的臺(tái)數(shù)、人數(shù)車輛船只數(shù)等.如果所得的解中決策變量為分?jǐn)?shù)或小數(shù)則不符合實(shí)際問題的要求.對(duì)于一個(gè)規(guī)劃問題,如果要求全部決策變量都取整數(shù),稱為純(或全)整數(shù)規(guī)劃;如果僅要求部分決策變量取整數(shù),稱為混合整數(shù)規(guī)劃問題.有的問題要求決策變量僅取0或l兩個(gè)值,稱為0-l規(guī)劃問題.整數(shù)規(guī)劃簡稱為IP問題.這里主要討論的是整數(shù)線性規(guī)劃問題,簡稱為ILP問題.對(duì)于整數(shù)線性規(guī)劃問題,為了得到整數(shù)解,初看起來,似乎只要先不管整數(shù)要求,而求線性規(guī)劃的解,然后將求得的非整數(shù)最優(yōu)解“舍零取整”就可以了.但實(shí)際上,這個(gè)想法卻常

9、常行不通,有時(shí)“舍零取整”后的整數(shù)解根本就不是可行解,有雖然為可行解,卻不是最優(yōu)解.例1 某廠擬用集裝箱托運(yùn)甲乙兩種貨物,每箱的體積、重量、可獲利潤以及托 運(yùn)所受限制見表1.問每集裝箱中兩種貨物各裝多少箱,可使所獲利潤最大?表 1貨物/箱體積/米3重量/百斤利潤/百元甲5220乙4510托運(yùn)限制/集裝箱2413解 設(shè) 分別為甲、乙兩種貨物的托運(yùn)箱數(shù).則這是一個(gè)純整數(shù)規(guī)劃問題.其數(shù)學(xué)模型為:（1）若暫且不考慮 取整數(shù)這一條件.則(1)就變?yōu)橄铝芯€性規(guī)劃:（2）我們將式(2)稱為(1)的伴隨規(guī)劃.解(2)得到最優(yōu)解:（3）但它不滿足(1)的整數(shù)要求.因此它不是(1)的最優(yōu)解,若把解(3)舍零取整,

10、如取X1=(5.0,0)T,但它不是式(1)的可行解.因?yàn)樗粷M足(1)中的約束條件,若取X2=(4.0,0)T.X2是(1)的可行解,但它卻不是(1)的最優(yōu)解,因?yàn)楫?dāng)X2=(4.0,0)T 時(shí),Z2=80,但當(dāng)X3=(4,1)T 時(shí),Z3=90 Z2 即伴隨規(guī)劃的最優(yōu)解通過“舍零取整”得到的X1,X2 都不是(1)的最優(yōu)解.因此通過伴隨規(guī)劃最優(yōu)解的“舍零取 整”的辦法,一般得不到原整數(shù)規(guī)劃問題的最優(yōu)解.若伴隨規(guī)劃(2)的可行域 K 是有界的,則原整數(shù)規(guī)劃(1)的可行域 K 0應(yīng)是K中有限個(gè)格點(diǎn)(整數(shù)點(diǎn)）的集合.見圖1,圖中“*為整數(shù)點(diǎn)(格點(diǎn)).圖1 中四邊形 OABC 是伴隨規(guī)劃(2)的可行

11、域.它的最優(yōu)解為 C 點(diǎn)(4.8,0),而(1)的可行域?yàn)閗0=(0,0),(0,1),(0,2),(1,0),(1,l),(1,2),(2,0),(2,1),(3,0),(3,1),(4,0),(4,l).將C點(diǎn)“舍零取整”后得到的X1=(5.0,0)T不在 K0中,而X2=(4,0)T在K0中,但不是(1)的最優(yōu)解,最優(yōu)解在B點(diǎn).當(dāng)然,我們也會(huì)想到能否用“窮舉法”來求解整數(shù)規(guī)劃.如(1)問題,將 K0 中所有整數(shù)點(diǎn)的目標(biāo)函數(shù)值都計(jì)算出來,然后逐一比較找出最優(yōu)解.這種方法對(duì)變量所能取的整數(shù)值個(gè)數(shù)較少時(shí),勉強(qiáng)可以應(yīng)用.如本例 可取 0,1,2,3,4共5個(gè)數(shù)值.而 只能取0,1,2共三個(gè)數(shù)值,

12、因此其組合最多為15個(gè)(其中有不可行的點(diǎn)).但對(duì)大型問題,這種組合數(shù)的個(gè)數(shù)可能大得驚人!如在指派問題中,有n 項(xiàng)任務(wù)指派n個(gè)人去完成,不同的指派方案共有n!種.當(dāng) n=20 時(shí),這個(gè)數(shù)超過21018.如果用窮舉法每一個(gè)方案都計(jì)算一遍,就是用每秒百萬次的計(jì)算機(jī),也要幾萬年.顯然“窮舉法”并不是一種普遍有效的方法.因此研究求解整數(shù)規(guī)劃的一般方法是有實(shí)際意義的.自20世紀(jì)60年代以來,已發(fā)展了一些常用的解整數(shù)規(guī)劃的算法,如各種類型的割平 面法、分枝定界法、解 0-1 規(guī)劃的隱枚舉法、分解方法、群論方法、動(dòng)態(tài)規(guī)劃方法等等。近十年來有人發(fā)展了一些近似算法及用計(jì)算機(jī)模擬法,也取得了較好的效果.分枝定界法在

13、20世紀(jì)60年代初 Land Doig 和 Dakin 等人提出了分枝定界法.由于該方法靈活且便于用計(jì)算機(jī)求解,所以目前已成為解整數(shù)規(guī)劃的重要方法之一.分枝定界法既可用來解純整數(shù)規(guī)劃,也可用來解混合整數(shù)規(guī)劃.分枝定界法的主要思路是首先求解整數(shù)規(guī)劃的伴隨規(guī)劃,如果求得的最優(yōu)解不符合整數(shù)條件,則增加新約束縮小可行域;將原整數(shù)規(guī)劃問題分枝分為兩個(gè)子規(guī)劃,再解子規(guī)劃的伴隨規(guī)劃通過求解一系列子規(guī)劃的伴隨規(guī)劃及不斷地定界.最后得到原整數(shù)規(guī)劃問題的整數(shù)最優(yōu)解.下面結(jié)合一個(gè)極大化例題來介紹分枝定界法的主要思路.例2 某公司計(jì)劃建筑兩種類型的宿舍.甲種每幢占地0.25 103m2,乙種每幢地0.4103m2.該

14、公司擁有土地3103m2.計(jì)劃甲種宿舍不超過 8 幢,乙種宿舍不超過4幢.甲種宿舍每幢利潤為10萬元，乙種宿舍利潤為每幢20萬元.問該公司應(yīng)計(jì)劃甲、乙兩種類型宿舍各建多少幢時(shí),能使公司獲利最大?解 設(shè)計(jì)劃甲種宿舍建 幢,乙種宿舍建 幢,則本題數(shù)學(xué)模型為:這是一個(gè)純整數(shù)規(guī)劃問題,稱為問題 。將(1)中約束條件的系數(shù)全化為整數(shù),改為：（1）然后去掉整數(shù)條件,得到問題 的伴隨規(guī)劃(2),稱之為問題（2）用單純形法求解問題 ,得到最優(yōu)解及最優(yōu)值：1.計(jì)算原問題 目標(biāo)函數(shù)值的初始上界 因?yàn)閱栴} 的最優(yōu)解不滿足整數(shù)條件,因此 不是問題 的最優(yōu)解,又因?yàn)?的可行域 問題 的可行域 ,故問題 的最優(yōu)值不會(huì)超過

15、問題 的最優(yōu)值.即有因此可令 作為 的初始上界即一般說來,若問題 無可行解,則問題 也無可行解,停止計(jì)算。若問題 的最優(yōu)解 滿足問題 的整數(shù)條件,則 也是問題 的最優(yōu)解,停止計(jì)算.2.計(jì)算原問題 目標(biāo)函數(shù)值的初始下界若能從問題 的約束條件中觀察到一個(gè)整數(shù)可行解,則可將其目標(biāo)函數(shù)值作為問題 目標(biāo)函數(shù)值的初始下界,否則可令初始下界Z=-.給定下界的目的,是希望在求解過程中尋找比當(dāng)前 更好的原問題的目標(biāo)函數(shù)值.對(duì)于本例,很容易得到一個(gè)明顯的可行解X=(0,0)T,Z=0.問題 的最優(yōu)目標(biāo)函數(shù)值決不會(huì)比它小,故可令 =0.3.增加約束條件將原問題分枝當(dāng)問題 的最優(yōu)解 不滿足整數(shù)條件時(shí),在 中任選一個(gè)不

16、符合整數(shù)條件的變量.如本例選 顯然問題 的整數(shù)最優(yōu)解只能是 或 ,而絕不會(huì)在5與6之間.因此當(dāng)將可行域 切去 部分時(shí),并沒有切去 的整數(shù)可行解.可以用分別增加約束條件 及 來達(dá)到在 切去 部分的目的.切去 后就分為 及 兩部分,即問題 分為問題 及問題 兩枝子規(guī)劃.問題 問題 作出問題 的伴隨規(guī)劃 則問題 的可行域?yàn)?見圖2(b).以下我們將由同一問題分解出的兩個(gè)分枝問題稱為一對(duì)分枝.4.分別求解一對(duì)分枝在一般情況下,對(duì)某個(gè)分枝問題(伴隨規(guī)劃)求解時(shí),可能出現(xiàn)以下幾種可能:(a)(a)(b)圖2(1)無可行解若無可行解,說明該枝情況己查明,不需要由此分枝再繼續(xù)分枝,稱該分枝為 樹葉.(2)得到

17、整數(shù)最優(yōu)解若求得整數(shù)最優(yōu)解，則該枝情況己查明,不需要再對(duì)此繼續(xù)分枝，該分枝也是 樹葉.(3)得到非整數(shù)最優(yōu)解若求得某個(gè)分枝問題得到的是不滿足整數(shù)條件的最優(yōu)解，還要區(qū)分兩種情況：該最優(yōu)解的目標(biāo)函數(shù)值Z小于當(dāng)前的下界 ，則該分枝內(nèi)不可能含有原問題的整數(shù)最優(yōu)解，稱為“枯枝”，需剪掉。該最優(yōu)解的目標(biāo)函數(shù)值Z大于當(dāng)前的下界 ，則仍需對(duì)該枝繼續(xù)分枝，以查明該分枝內(nèi)是否有目標(biāo)函數(shù)值比當(dāng)前的 更好的整數(shù)最優(yōu)解。本例中問題 及問題 的模型及求解結(jié)果如下：問題問題解為:解為:問題 的解 是整數(shù)最優(yōu)解,它當(dāng)然也是問題 的整數(shù)可行解,故 的整數(shù)最優(yōu)解即此時(shí)可將 修改為:同時(shí)問題 也被查清,成為“樹葉”。因?yàn)?,不滿足

18、整數(shù)條件,故問題 分別增加約束條件：及 。分為 與 兩枝,建立相應(yīng)的伴隨規(guī)劃問題 與問題問題它們的可行域分別為 見圖3。圖3因?yàn)?，問題無可行解，此問題已是樹葉,已被查清.求解問題 ,得到最優(yōu)解 5.修改上、下界 與(l)修改下界 修改下界的時(shí)機(jī)是:每求出一個(gè)整數(shù)可行解時(shí),都要作修改下界 的工作.修改下界 的原則:在至今所有計(jì)算出的整數(shù)可行解中,選目標(biāo)函數(shù)值最大的那個(gè)作為最新下界 。因此在用分枝定界法的求解全過程中,下界 是不斷增大的.(2)修改上界 上界 的修改時(shí)機(jī)是:每求解完一對(duì)分枝,都要考慮修改上界修改上界 的原則是:挑選在迄今為止所有未被分枝的問題的目標(biāo)函數(shù)值中最大的一個(gè)作為新的上界.

19、新的上界 應(yīng)該小于原來的上界.在分枝定界法的整個(gè)求解過程中,上界的值在不斷減小.問題問題解為:因?yàn)榇藭r(shí) 的解為整數(shù)解,因此修改下界為 =130,而此時(shí)所有未被分枝的問題()的目標(biāo)函數(shù)值中最大的為 ,故修改上界 =130.6.結(jié)束準(zhǔn)則當(dāng)所有分枝均已查明(或無可行解“樹葉”,或?yàn)檎麛?shù)可行解“樹葉”,或其目標(biāo)函數(shù)值不大于下界 ”枯枝”）且此時(shí) ，則已得到了原問題的整數(shù)最優(yōu) 解，即目標(biāo)函數(shù)值為下界 的那個(gè)整數(shù)解.在本例中,當(dāng)解完一對(duì)分枝 后,得到 又 是樹葉,為枯枝,因此所有分枝()均已查明.故已得到問題 的最優(yōu)解:或故該公司應(yīng)建甲種宿舍7幢乙種宿舍3幢;或甲種5幢、乙種4幢時(shí),獲利最大.獲利為130

20、萬元.可將本例的求解過程與結(jié)果用圖5 來描述.問題問題問題問題問題問題問題不可行下面將分枝定界法求解混合型整數(shù)規(guī)劃的計(jì)算步驟歸納如下:第1步:將原整數(shù)線性規(guī)劃問題稱為問題 .去掉問題的整數(shù)條件,得到伴隨規(guī)劃問題 第2步:求解問題 ,有以下幾種可能:(l)沒有可行解,則 也沒有可行解,停止計(jì)算.(2)得到 的最優(yōu)解,且滿足問題 的整數(shù)條件,則 的最優(yōu)解也是 的最優(yōu)解,停止計(jì)算.(3)得到不滿足問題 的整數(shù)條件的 的最優(yōu)解,記它的目標(biāo)函數(shù)值為 ,這時(shí)需要對(duì)問題 (從而對(duì)問題 )進(jìn)行分枝,轉(zhuǎn)下一步.(3)得到不滿足問題 的整數(shù)條件的 的最優(yōu)解,記它的目標(biāo)函數(shù)值為 ,這時(shí)需要對(duì)問題 (從而對(duì)問題 )進(jìn)

21、行分枝,轉(zhuǎn)下一步.第3步:確定初始上下界 與 .以 作為上界 .觀察出問題 的一個(gè)整數(shù)可行解,將其目標(biāo)函數(shù)值記為下界 .若觀察不到,則可記 =-.轉(zhuǎn)下一步.第4步:將問題 分枝.在 的最優(yōu)解 中,任選一個(gè)不符合整數(shù)條件的變量 ,其值為 ,以 表示小于 的最大整數(shù).構(gòu)造兩個(gè)約束條件:將這兩個(gè)約束條件分別加到問題 的約束條件集中,得到 的兩個(gè)分枝:問題 與 對(duì)每個(gè)分枝問題求解,得到以下幾種可能:(1)分枝無可行解該分枝是 樹葉.(2)求得該分枝的最優(yōu)解,且滿足 的整數(shù)條件.將該最優(yōu)解的目標(biāo)函數(shù)值作為新的下界 ,該分枝也是樹葉.(3)求得該分枝的最優(yōu)解,且不滿足 的整數(shù)條件,但其目標(biāo)函數(shù)值不大于當(dāng)前

22、下界 ,則該分枝是“枯枝”需要剪枝.(4)求得不滿足 整數(shù)條件的該分枝的最優(yōu)解,且其目標(biāo)函數(shù)值大于當(dāng)前下界 ,則該分枝需要繼續(xù)進(jìn)行分枝.若得到的是前三種情形之一,表明該分枝情況已探明,不需要繼續(xù)分枝.若求解一對(duì)分枝的結(jié)果表明這一對(duì)分枝都需要繼續(xù)分枝,則可先對(duì)目標(biāo)函數(shù)值大的那個(gè)分校進(jìn)行分枝計(jì)算,且沿著該分枝一直繼續(xù)進(jìn)行下去,直到全部探明情況為止.再返過來求 解目標(biāo)函數(shù)值較小的那個(gè)分枝.第6步:修改上、下界.(1)修改下界 ：每求出一次符合整數(shù)條件的可行解時(shí),都要考慮修改下界 ,選擇迄今為止最好的整數(shù)可行解 相應(yīng)的目標(biāo)函數(shù)值作下界(2)修改上界 ：每求解完一對(duì)分枝,都要考慮修改上界 上界的值應(yīng)是迄

23、今為止所有未被分枝的問題的目標(biāo)函數(shù)值中最大的一個(gè).在每解完一對(duì)分枝、修改完上、下界 和 后,若已有 此時(shí)所有分枝均已查明,即得到了問題 的最優(yōu)值求解結(jié)束.若仍有 ,則說明仍有分枝沒查明,需要繼續(xù)分枝,回到第4步.割平面法割平面法n基本原理：基本原理：基本原理：基本原理：根據(jù)單純形法求得其松弛問題的最優(yōu)解，根據(jù)單純形法求得其松弛問題的最優(yōu)解，根據(jù)單純形法求得其松弛問題的最優(yōu)解，根據(jù)單純形法求得其松弛問題的最優(yōu)解，若不滿足整數(shù)條件，則由最優(yōu)解中選取具有最若不滿足整數(shù)條件，則由最優(yōu)解中選取具有最若不滿足整數(shù)條件，則由最優(yōu)解中選取具有最若不滿足整數(shù)條件，則由最優(yōu)解中選取具有最大真分?jǐn)?shù)部分的非整分量所在

24、行構(gòu)造割平面約大真分?jǐn)?shù)部分的非整分量所在行構(gòu)造割平面約大真分?jǐn)?shù)部分的非整分量所在行構(gòu)造割平面約大真分?jǐn)?shù)部分的非整分量所在行構(gòu)造割平面約束，將其加入原松弛問題中形成一個(gè)新的線性束，將其加入原松弛問題中形成一個(gè)新的線性束，將其加入原松弛問題中形成一個(gè)新的線性束，將其加入原松弛問題中形成一個(gè)新的線性規(guī)劃求解，逐漸縮小解的范圍，又不去掉整數(shù)規(guī)劃求解，逐漸縮小解的范圍，又不去掉整數(shù)規(guī)劃求解，逐漸縮小解的范圍，又不去掉整數(shù)規(guī)劃求解，逐漸縮小解的范圍，又不去掉整數(shù)解，直至找到最優(yōu)解為整數(shù)解結(jié)束。解，直至找到最優(yōu)解為整數(shù)解結(jié)束。解，直至找到最優(yōu)解為整數(shù)解結(jié)束。解，直至找到最優(yōu)解為整數(shù)解結(jié)束。割平面法割平面法n

25、約束條件構(gòu)造的條件約束條件構(gòu)造的條件約束條件構(gòu)造的條件約束條件構(gòu)造的條件1)1)已獲得的不符合整數(shù)要求的線性規(guī)劃最已獲得的不符合整數(shù)要求的線性規(guī)劃最已獲得的不符合整數(shù)要求的線性規(guī)劃最已獲得的不符合整數(shù)要求的線性規(guī)劃最優(yōu)解不滿足該線性約束條件優(yōu)解不滿足該線性約束條件優(yōu)解不滿足該線性約束條件優(yōu)解不滿足該線性約束條件,從而不可能在以后從而不可能在以后從而不可能在以后從而不可能在以后的解中出現(xiàn)的解中出現(xiàn)的解中出現(xiàn)的解中出現(xiàn);2)2)凡是整數(shù)可行解均滿足該線性約束條件凡是整數(shù)可行解均滿足該線性約束條件凡是整數(shù)可行解均滿足該線性約束條件凡是整數(shù)可行解均滿足該線性約束條件,因而整數(shù)最優(yōu)解始終保留在每次形成的

26、線性規(guī)因而整數(shù)最優(yōu)解始終保留在每次形成的線性規(guī)因而整數(shù)最優(yōu)解始終保留在每次形成的線性規(guī)因而整數(shù)最優(yōu)解始終保留在每次形成的線性規(guī)劃中劃中劃中劃中.割平面法割平面法n割平面束構(gòu)造：割平面束構(gòu)造：割平面束構(gòu)造：割平面束構(gòu)造：設(shè)最終單純形表的第設(shè)最終單純形表的第設(shè)最終單純形表的第設(shè)最終單純形表的第i i個(gè)約束條件為：個(gè)約束條件為：個(gè)約束條件為：個(gè)約束條件為：將該約束方程所在系數(shù)和常數(shù)分解為整數(shù)將該約束方程所在系數(shù)和常數(shù)分解為整數(shù)將該約束方程所在系數(shù)和常數(shù)分解為整數(shù)將該約束方程所在系數(shù)和常數(shù)分解為整數(shù)NN和正和正和正和正真分?jǐn)?shù)真分?jǐn)?shù)真分?jǐn)?shù)真分?jǐn)?shù)f f之和，即：之和，即：之和，即：之和，即：則該約束方程等

27、價(jià)于：則該約束方程等價(jià)于：則該約束方程等價(jià)于：則該約束方程等價(jià)于：例：求解例：求解Max Z=x1+x2s.t.-x1+x2 1 3x1+x2 4 x1,x2 0，x1，x2 為整數(shù)為整數(shù)對(duì)應(yīng)的對(duì)應(yīng)的LP的可行域如下圖的可行域如下圖0 1 22 1 A Ax x1 13x3x1 1+x+x2 2 4 4 -x -x1 1+x+x2 2 1 1 C Cx x2 2D DLP的標(biāo)準(zhǔn)型為：的標(biāo)準(zhǔn)型為：Max Z=x1+x2s.t.-x1+x2+x3=1 3x1+x2+x4=4 x1,x2,x3,x4 0最終計(jì)算表中得到非整數(shù)的最優(yōu)解最終計(jì)算表中得到非整數(shù)的最優(yōu)解表表5-2割平面法割平面法nexex：

28、Cj1100CBXBbx1x2x3x40 x3621100 x4204501j1100 35x1入 x3出1x1311/21/200 x4803-21j01/2-1/20 68/3x2入 x4出1x28/301-2/31/31x15/3105/6-1/6j00-1/6-1/6由右邊結(jié)果構(gòu)造割平面束由右邊結(jié)果構(gòu)造割平面束由右邊結(jié)果構(gòu)造割平面束由右邊結(jié)果構(gòu)造割平面束n例（接上）：例（接上）：例（接上）：例（接上）：由上面結(jié)果構(gòu)造割平面束由上面結(jié)果構(gòu)造割平面束由上面結(jié)果構(gòu)造割平面束由上面結(jié)果構(gòu)造割平面束cj11000CBXBbx1x2x3x4x51X15/3105/6-1/601X28/301-2/

29、31/300 x5-2/3-2/300-5/6-5/61j00-1/6-1/60-1/51/5-1X11100-111X216/50101-4/50 x34/50011-6/5j0000-1/5cj110000CBXBbx1x2x3x4x5x61X11100-1101X2 16/50101-4/500 x34/50011-6/500 x6-4/50000-4/51j0000-1/501X10100-105/41X2401010-10X3200110-3/20 x5100001-5/4j00000-1/4 0-1型整數(shù)規(guī)劃型整數(shù)規(guī)劃等價(jià)于等價(jià)于等價(jià)于等價(jià)于取整數(shù)取整數(shù)取整數(shù)取整數(shù)一一一一 引例引

30、例 例：某公司擬在東、西、南三區(qū)建立門市部，有例：某公司擬在東、西、南三區(qū)建立門市部，有例：某公司擬在東、西、南三區(qū)建立門市部，有例：某公司擬在東、西、南三區(qū)建立門市部，有7 7個(gè)位置個(gè)位置個(gè)位置個(gè)位置A Ai i(i=1,2,(i=1,2,7),7)可供選擇?？晒┻x擇?？晒┻x擇?？晒┻x擇。在東區(qū)，由在東區(qū)，由在東區(qū)，由在東區(qū)，由A A1 1、A A2 2、A A3 3 三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)由在西區(qū)由在西區(qū)由在西區(qū)由A A4 4、A A5 5 兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)

31、由在南區(qū)由在南區(qū)由在南區(qū)由A A6 6、A A 7 7兩個(gè)點(diǎn)中至少選一個(gè)。兩個(gè)點(diǎn)中至少選一個(gè)。兩個(gè)點(diǎn)中至少選一個(gè)。兩個(gè)點(diǎn)中至少選一個(gè)。如選用點(diǎn)，設(shè)備投資估計(jì)為如選用點(diǎn)，設(shè)備投資估計(jì)為如選用點(diǎn)，設(shè)備投資估計(jì)為如選用點(diǎn)，設(shè)備投資估計(jì)為b bi i元，每年可獲利潤估計(jì)為元，每年可獲利潤估計(jì)為元，每年可獲利潤估計(jì)為元，每年可獲利潤估計(jì)為c ci i元，但投元，但投元，但投元，但投資總額不能超過資總額不能超過資總額不能超過資總額不能超過B B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最大？元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最大？元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最大？元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最大？解：解：引入

32、引入引入引入0-10-1變量變量變量變量當(dāng)當(dāng)當(dāng)當(dāng)A Ai i點(diǎn)被采用點(diǎn)被采用點(diǎn)被采用點(diǎn)被采用當(dāng)當(dāng)當(dāng)當(dāng)A Ai i點(diǎn)沒被采用點(diǎn)沒被采用點(diǎn)沒被采用點(diǎn)沒被采用東區(qū)，由東區(qū)，由東區(qū)，由東區(qū)，由A A1 1、A A2 2、A A3 3 三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；東區(qū)，由東區(qū)，由東區(qū)，由東區(qū)，由A A1 1、A A2 2、A A3 3 三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；東區(qū)，由東區(qū)，由東區(qū)，由東區(qū)，由A A1 1、A A2 2、A A3 3 三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)

33、中至多選兩個(gè)；在西區(qū)由在西區(qū)由在西區(qū)由在西區(qū)由A A4 4、A A5 5 兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；東區(qū)，由東區(qū)，由東區(qū)，由東區(qū)，由A A1 1、A A2 2、A A3 3 三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)由在西區(qū)由在西區(qū)由在西區(qū)由A A4 4、A A5 5 兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)；東區(qū)，由東區(qū)，由東區(qū)，由東區(qū)，由A A1 1、A A2 2、A A3 3 三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)由在西區(qū)由在西區(qū)由在西區(qū)由A A4 4、A A5 5 兩個(gè)點(diǎn)中至少選兩個(gè)；兩個(gè)點(diǎn)中至少選兩個(gè)；兩個(gè)點(diǎn)中至少選兩個(gè)；兩個(gè)點(diǎn)中至少選兩個(gè)；在南區(qū)由在南區(qū)由在南區(qū)由在南區(qū)由A A6 6、A A 7