運(yùn)籌學(xué)第三章課件

云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)

線性規(guī)劃的決策變量取值可以是任意非負(fù)實(shí)數(shù)，但許多實(shí)際問題中，只有當(dāng)決策變量的取值為整數(shù)時(shí)才有意義。例如，產(chǎn)品的件數(shù)、機(jī)器的臺(tái)數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。

對某一個(gè)項(xiàng)目要不要投資的決策問題，可選用一個(gè)邏輯變量x，當(dāng)x=1表示投資，x=0表示不投資。3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

純整數(shù)規(guī)劃(IP)：xj全部取整數(shù)混合整數(shù)規(guī)劃(MIP)：xj部分取整數(shù)0-1整數(shù)規(guī)劃(BIP)：整數(shù)變量只能取0或1分類2線性規(guī)劃的決策變量取值可以是任意非負(fù)實(shí)數(shù)，但許多實(shí)際問【例3-1】某人有一背包可以裝10公斤重、0.025m3的物品。他準(zhǔn)備用來裝甲、乙兩種物品，每件物品的重量、體積和價(jià)值如表3-1所示。問兩種物品各裝多少件，才能使所裝物品的總價(jià)值最大？表3-1【解】設(shè)甲、乙兩種物品各裝x1、x2件，則數(shù)學(xué)模型為：(3-1)物品重量（公斤/件）體積（m3/件）價(jià)值(元/件)甲乙1.20.80.0020.0025433.1整數(shù)規(guī)劃的數(shù)學(xué)模型

3【例3-1】某人有一背包可以裝10公斤重、0.025m3的

【補(bǔ)充例】投資決策問題。某公司有5個(gè)項(xiàng)目被列入投資計(jì)劃，各項(xiàng)目的投資額和期望的投資收益如下表3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

該公司只有600萬元資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：（1）在項(xiàng)目1、2和3中必須且只有一項(xiàng)被選中；（2）項(xiàng)目3和項(xiàng)目4最多只能選中一項(xiàng)；（3）項(xiàng)目5被選中的前提是項(xiàng)目1必須被選中。如何在上述條件下選擇一個(gè)最好的投資方案，使投資收益最大？項(xiàng)目投資額（萬元）投資收益（萬元）1210160230021031506041308052601804【補(bǔ)充例】投資決策問題。某公司有5個(gè)項(xiàng)目被列入投資計(jì)劃【解】設(shè)xj為選擇第j（j=1,2,3,4,5)個(gè)項(xiàng)目的決策3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

5【解】設(shè)xj為選擇第j（j=1,2,3,4,5)個(gè)項(xiàng)目的【例3-2】在例3-1中，假設(shè)此人還有一只旅行箱，最大載重量為12公斤，其體積是0.02m3。背包和旅行箱只能選擇其一，建立下列幾種情形的數(shù)學(xué)模型，使所裝物品價(jià)值最大。（1）所裝物品不變；（2）如果選擇旅行箱，則只能裝載丙和丁兩種物品，每件物品的重量、體積和價(jià)值如下表所示3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

物品重量（公斤/件）體積（m3/件）價(jià)值(元/件)丙丁1.80.60.00150.002436【例3-2】在例3-1中，假設(shè)此人還有一只旅行箱，最大載重【解】（1）引入0－1變量yj，令j=1,2分別是采用背包及旅行箱裝載。3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

(3-2)此問題也可以建立兩個(gè)整數(shù)規(guī)劃模型。7【解】（1）引入0－1變量yj，令j=1,2分別是采用（2）由于不同載體所裝物品不一樣，數(shù)學(xué)模型為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

其中M為充分大的正數(shù)。當(dāng)使用背包時(shí)(y1=1,y2=0)，式(b)和(d)是多余的；當(dāng)使用旅行箱時(shí)(y1=0,y2=1)，式(a)和(c)是多余的。背包約束旅行箱約束8（2）由于不同載體所裝物品不一樣，數(shù)學(xué)模型為3.1整數(shù)規(guī)（1）右端常數(shù)是k個(gè)值中的一個(gè)時(shí)，類似式(3-2)的約束條件為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

同樣可以討論對于有m個(gè)條件互相排斥、有m（≤m、≥m）個(gè)條件起作用的情形。9（1）右端常數(shù)是k個(gè)值中的一個(gè)時(shí)，類似式(3-2)的約束條件（2）對于m個(gè)（組）條件中有k（≤m）個(gè)（組）起作用時(shí)，類似式(3-3)的約束條件寫成這里yi=1表示第i組約束不起作用（如y1=1式(3-3b)、(3-3d)不起作用），yi=0表示第i個(gè)約束起作用。當(dāng)約束條件是“≥”符號(hào)時(shí)右端常數(shù)項(xiàng)應(yīng)為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

10（2）對于m個(gè)（組）條件中有k（≤m）個(gè)（組）起作用時(shí)【例3-3】試引入0－1變量將下列各題分別表達(dá)為一般線性約束條件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，則x2≥0，否則x2≤8（3）x2取值0，1，3，5，7【解】

（1）3個(gè)約束只有1個(gè)起作用或3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

如果要求至少一個(gè)條件滿足，模型如何改變？11【例3-3】試引入0－1變量將下列各題分別表達(dá)為一般線性約束（3）右端常數(shù)是5個(gè)值中的1個(gè)（2）兩組約束只有一組起作用3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

(1)(2)(3)(4)12（3）右端常數(shù)是5個(gè)值中的1個(gè)（2）兩組約束只有一組起作用3【例3-4】企業(yè)計(jì)劃生產(chǎn)4000件某種產(chǎn)品，該產(chǎn)品可自己加工、外協(xié)加工任意一種形式生產(chǎn)。已知每種生產(chǎn)的固定費(fèi)用、生產(chǎn)該產(chǎn)品的單件成本以及每種生產(chǎn)形式的最大加工數(shù)量（件）限制如表3－2所示，怎樣安排產(chǎn)品的加工使總成本最小。表3－2

固定成本（元）變動(dòng)成本（元／件）最大加工數(shù)（件）本企業(yè)加工50081500外協(xié)加工Ⅰ80052000外協(xié)加工Ⅱ6007不限3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

13【例3-4】企業(yè)計(jì)劃生產(chǎn)4000件某種產(chǎn)品，該產(chǎn)品可自己加工【解】設(shè)xj為采用第j（j=1,2,3）種方式生產(chǎn)的產(chǎn)品數(shù)量，生產(chǎn)費(fèi)用為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

其中kj是固定成本，cj是可變成本。設(shè)0－1變量yj14【解】設(shè)xj為采用第j（j=1,2,3）種方式生產(chǎn)的產(chǎn)品數(shù)（3-4）用WinQSB軟件求解得到：X＝(0，2000，2000)T，Y＝(0，1，1)T，Z=254003.1整數(shù)規(guī)劃的數(shù)學(xué)模型

配合目標(biāo)，使得只有選用第j種加工方式才產(chǎn)生相應(yīng)成本，不選用第j種加工方式就沒有成本。15（3-4）用WinQSB軟件求解得到：3.1整數(shù)規(guī)劃的數(shù)整數(shù)規(guī)劃的一般形式：稱線性規(guī)劃模型（Ⅰ）

（Ⅱ）(LP)為（Ⅰ）的松弛問題。

每一個(gè)整數(shù)規(guī)劃都對應(yīng)一個(gè)松弛問題，整數(shù)規(guī)劃比它的松弛問題約束得更緊。部分或全部取整3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

16整數(shù)規(guī)劃的一般形式：稱線性規(guī)劃模型（Ⅰ）（Ⅱ）(LP)為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

習(xí)題3.4【解】令運(yùn)動(dòng)員甲、乙、丙、丁、戊編號(hào)為1、2、3、4、5，項(xiàng)目高低杠、平衡木、鞍馬、自由體操編號(hào)為1、2、3、4。設(shè)

項(xiàng)目運(yùn)動(dòng)員1234高低杠平衡木鞍馬自由體操1甲x11x12x13x142乙x21x22x23x243丙x31x32x33x344丁x41x42x43x445戊x51x52x53x54173.1整數(shù)規(guī)劃的數(shù)學(xué)模型習(xí)題3.4max=8.6x11+9.7x12+8.9x13+9.4x14+9.2x21+8.3x22+8.5x23+8.1x24+8.8x31

+8.7x32+9.3x33+9.6x34+8.5x41+7.8x42+9.5x43+7.9x44+8x51+9.4x52+8.2x53+7.7x54x11+x12+x13+x14≦3x21+x22+x23+x24≦3x31+x32+x33+x34≦3x41+x42+x43+x44≦3x51+x52+x53+x54≦3x11+x21+x31+x41+x51≧1x12+x22+x32+x42+x52≧1x13+x23+x33+x43+x53≧1x14+x24+x34+x44+x54≧1x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43+x44+x51+x52+x53+x54=10xij=0或1(i=1,2,3,4,5;j=1,2,3,4)3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

18max=8.6x11+9.7x12+8.9x13+9.4x11.整數(shù)規(guī)劃模型的特征2.什么是純（混合）整數(shù)規(guī)劃3.0－1規(guī)劃模型的應(yīng)用下一節(jié)：純整數(shù)規(guī)劃的求解3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

本節(jié)學(xué)習(xí)要點(diǎn)191.整數(shù)規(guī)劃模型的特征下一節(jié)：純整數(shù)規(guī)劃的求解3.1

整數(shù)規(guī)劃解的特點(diǎn)整數(shù)規(guī)劃（Ⅰ）的可行解集是其松弛問題（Ⅱ）的可行解集的子集。線性規(guī)劃問題的可行解集是一個(gè)凸集（稠密的），但整數(shù)規(guī)劃的可行解集不是凸集（離散型）。如果松弛問題（Ⅱ）的最優(yōu)解是整數(shù)解，則一定是整數(shù)規(guī)劃（Ⅰ）的最優(yōu)解。整數(shù)規(guī)劃（Ⅰ）的最優(yōu)值不會(huì)優(yōu)于松弛問題（Ⅱ）的最優(yōu)值。3.2整數(shù)規(guī)劃的求解20整數(shù)規(guī)劃解的特點(diǎn)3.2整數(shù)規(guī)劃的求解203.2整數(shù)規(guī)劃的求解圖3-1點(diǎn)B為最優(yōu)解X＝(3.57，7.14)Z＝35.7用圖解法求解例3-1的松弛問題整數(shù)規(guī)劃問題的可行解集是圖中可行域內(nèi)的整數(shù)點(diǎn)。8.3310松弛問題的最優(yōu)解X=(3.57,7.14),z=35.7x1x2oAC10B圖3-1213.2整數(shù)規(guī)劃的求解圖3-1點(diǎn)B為最優(yōu)解用圖解法求解松弛問題的最優(yōu)解X＝(3.57，7.14)，Z＝35.7“四舍五入”得X=(4,7)不是可行解；用“取整”法來解時(shí)，X=(3,7)雖屬可行解，但代入目標(biāo)函數(shù)得Z=33,并非最優(yōu)。該整數(shù)規(guī)劃問題的最優(yōu)解是X=(5,5)，最優(yōu)值是Z=35即甲、乙兩種物品各裝5件，總價(jià)值35元。

由圖3－1知，點(diǎn)（5，5）不是LP可行域的頂點(diǎn)，直接用圖解法或單純形法都無法求出整數(shù)規(guī)劃問題的最優(yōu)解，因此求解整數(shù)規(guī)劃問題的最優(yōu)解需要采用其它特殊方法。3.2整數(shù)規(guī)劃的求解8.3310松弛問題的最優(yōu)解X=(3.57,7.14),z=35.7x1x2oAC10B圖3-122松弛問題的最優(yōu)解X＝(3.57，7.14)，Z＝35【例3-5】用分支定界法求解例3-1【解】先求對應(yīng)的松弛問題用圖解法得到最優(yōu)解X＝（3.57,7.14）,Z0=35.73.2.1分支定界法23【例3-5】用分支定界法求解例3-1【解】先求對應(yīng)的松弛問8.3310松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC103.2.1分支定界法248.3310松弛問題LP0的最優(yōu)解X=(3.57,7.11010x1x20ABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.5251010x1x20ABCLP1LP234LP1:X=(3,1010x10ACLP134LP1:X=(3,7.6),Z1=34.8①②x1B67LP3:X=(4.33,6),Z3=35.33LP2LP3261010x10ACLP134LP1:X=(3,7.6),x1x11010x10ACLP134LP1:X=(3,7.6),Z1=34.8①②x1B67LP2LP3LP5LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=35此為原IP最優(yōu)解527x1x11010x10ACLP134LP1:X=(3,7.盡管LP1的解中x2不為整數(shù)，但Z5≧Z1，因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。若Z5≦Z1

，則要對LP1進(jìn)行分支。3.2.1分支定界法28盡管LP1的解中x2不為整數(shù)，但Z5≧Z1，因此L上述分枝過程可用下圖表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5

無可行解x2≥7最優(yōu)解3.2.1分支定界法29上述分枝過程可用下圖表示LP0:X=(3.57,7.14分支定界法的步驟：1.求整數(shù)規(guī)劃的松弛問題最優(yōu)解；2.

若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步；3.2.1分支定界法3.任意選一個(gè)非整數(shù)解的變量xi，在松弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個(gè)新的松弛問題，稱為分支。新的松弛問題具有特征：當(dāng)原問題是求最大值時(shí)，目標(biāo)值是分支問題的上界；當(dāng)原問題是求最小值時(shí)，目標(biāo)值是分支問題的下界；30分支定界法的步驟：1.求整數(shù)規(guī)劃的松弛問題最優(yōu)解；3.4.

檢查所有分支的解及目標(biāo)函數(shù)值，若某分支的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分支的目標(biāo)值，則將其它分支剪去不再計(jì)算,若還存在非整數(shù)解并且目標(biāo)值大于（max）整數(shù)解的目標(biāo)值，需要繼續(xù)分支，再檢查，直到得到最優(yōu)解。分支原則：始終選Z值大的，且xi中有分?jǐn)?shù)的LP進(jìn)行分支。定界原則：滿足取整要求，且目標(biāo)函數(shù)值較已定的“界”更優(yōu)，則用該目標(biāo)函數(shù)值替換，重新定界。

3.2.1分支定界法說明：

分支定界法適用于求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃314.

檢查所有分支的解及目標(biāo)函數(shù)值，若某分支的解是整數(shù)并且設(shè)純整數(shù)規(guī)劃

松弛問題的最優(yōu)解3.2.2割平面法設(shè)xi=不為整數(shù)，32設(shè)純整數(shù)規(guī)劃松弛問題的最優(yōu)解3.2.2割平面法設(shè)xi將分離成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和：則有等式兩邊都為整數(shù),并且有3.2.2割平面法33將分離成一個(gè)整數(shù)與一個(gè)非負(fù)真分加入松弛變量si得此式稱為以xi行為源行（來源行）的割平面方程，或分?jǐn)?shù)切割式，或R.E.Gomory(高莫雷)約束方程。將Gomory約束加入到松弛問題的最優(yōu)表中，用對偶單純形法計(jì)算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部變量為整數(shù)。則3.2.2割平面法34加入松弛變量si得此式稱為以xi行為源行（來源行）的割平面方例如，x1行：移項(xiàng)：加入松弛變量s1得割平面方程同理，對于x2行有：3.2.2割平面法35例如，x1行：移項(xiàng)：加入松弛變量s1得割平面方程同理，對于x【例3-6】用割平面法求解下列IP問題【解】對應(yīng)的松弛問題是3.2.2割平面法36【例3-6】用割平面法求解下列IP問題【解】對應(yīng)的松弛問加入松弛變量x3及x4后，用單純形法求解，得到最優(yōu)表3-3。

最優(yōu)解X(0)＝(5/2，15/4),不是IP的最優(yōu)解。選擇表中的第一行(也可以選第二行)為源行Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4表3-33.2.2割平面法37加入松弛變量x3及x4后，用單純形法求解，得到最優(yōu)表3-3。分離系數(shù)后改寫成加入松弛變量x5得到高莫雷約束方程將此式作為約束條件添加到表3－3中，用對偶單純形法計(jì)算，如表3－4所示

3.2.2割平面法38分離系數(shù)后改寫成加入松弛變量x5得到高莫雷約束方程將此式作為Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/4－1/8－1－1/23/4－20015/215/4－2λj00－5/8－1/40430x1x2x41000101/2－1/21/2001－1/43/8－1/2331λj00－1/20－1/8最優(yōu)解X(1)＝(3，3)，最優(yōu)值Z＝21。表3－43.2.2割平面法39Cj43000bCBXBx1x2x3x4x54x1101/4x2x1ACBx1+2x2=100DC6x1+4x2=30Ex1+x2≤6幾何意義

由約束條件得：x3=30-6x1-4x2,x4=10-x1-2x2代入割平面方程-x3-2x4≤-2，得x1+x2≤6

說明：利用割平面法求解整數(shù)規(guī)劃問題時(shí),若從最優(yōu)單純形表中選擇具有最大?。ǚ郑?shù)部分的非整分量所在行構(gòu)造割平面方程，往往可以提高“切割”效率，減少“切割”次數(shù)。

3.2.2割平面法不含任何整數(shù)解40x2x1ACBx1+2x2=100DC6x1+4x2=30E5x15x1+9x2≤45x2x1+x2≤66960思考：

對于兩個(gè)變量的純整數(shù)規(guī)劃問題是否可采用圖解法。最優(yōu)解x1=0,x2=53.2.3整數(shù)規(guī)劃的圖解法415x15x1+9x2≤45x2x1+x2≤66960思考：最步驟：1.作出松弛問題的可行域。2.在可行域內(nèi)作出所有的整數(shù)網(wǎng)格。3.作目標(biāo)函數(shù)等值線，將等值線平行移動(dòng)，最后接觸到的網(wǎng)格點(diǎn)（或平行移動(dòng)到松弛問題的最優(yōu)解點(diǎn)再往回移，首先接觸到的網(wǎng)格點(diǎn)），就是整數(shù)規(guī)劃的最優(yōu)解。3.2.3整數(shù)規(guī)劃的圖解法42步驟：3.2.3整數(shù)規(guī)劃的圖解法421.理解分支與定界的含義2.選擇合適的“枝”生“枝”3.掌握何時(shí)停止生“枝”4.領(lǐng)會(huì)割平面法的基本原理5.分離源行，求出Gomory約束6.在最優(yōu)表中增加Gomory約束，用對偶單純形法迭代下一節(jié)：0－1規(guī)劃的求解3.2整數(shù)規(guī)劃的求解本節(jié)學(xué)習(xí)要點(diǎn)431.理解分支與定界的含義下一節(jié)：0－1規(guī)劃的求解3.23.3.1求解0－1整數(shù)規(guī)劃的隱枚舉法隱枚舉法的步驟：

1.找出任意一可行解，目標(biāo)函數(shù)值為Z0

2.

原問題求最大值時(shí)，則增加一個(gè)約束

作為過濾條件。當(dāng)求最小值時(shí)，上式改為小于等于約束。列出所有可能解，對每個(gè)可能解先檢驗(yàn)是否滿足過濾條件，若滿足再檢驗(yàn)其它約束，若不滿足約束，則不可行，若所有約束都滿足，且目標(biāo)值超過Z0,則應(yīng)更換過濾條件。4.目標(biāo)函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解。3.30－1規(guī)劃的求解443.3.1求解0－1整數(shù)規(guī)劃的隱枚舉法隱枚舉法的步驟：1【例3-7】用隱枚舉法求解下列BIP問題3.30－1規(guī)劃的求解(1)(2)(3)(4)45【例3-7】用隱枚舉法求解下列BIP問題3.30－1規(guī)jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)Zj1(0,0,0,0)

9(1,0,0,0)

2(0,0,0,1)10(1,0,0,1)3(0,0,1,0)

11(1,0,1,0)4(0,0,1,1)12(1,0,1,1)5(0,1,0,0)

13(1,1,0,0)6(0,1,0,1)

14(1,1,0,1)7(0,1,1,0)

15(1,1,1,0)

8(0,1,1,1)16(1,1,1,1)表3－5最優(yōu)解：X＝(1,0,1,1)T，最優(yōu)值Z＝143.30－1規(guī)劃的求解√×√√√√z≧53√√√√275√×

106√√√×16√√√√z≧119√√√√z≧14813118z≥846jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)3.3.2分枝－隱枚舉法求解BIP問題

將分枝定界法與隱枚舉法結(jié)合起來用，得到分枝－隱枚舉法。計(jì)算步驟如下：（1）將BIP問題的目標(biāo)函數(shù)的系數(shù)化為非負(fù)，如3.30－1規(guī)劃的求解473.3.2分枝－隱枚舉法求解BIP問題將分枝定界法當(dāng)變量作了代換后，約束條件中的變量也相應(yīng)作代換。（3）求主枝：目標(biāo)函數(shù)是max形式時(shí)令所有變量等于1，得到目標(biāo)值的上界；目標(biāo)函數(shù)是min形式時(shí)令所有變量等于0，得到目標(biāo)值的下界；如果主枝的解滿足所有約束條件則得到最優(yōu)解，否則轉(zhuǎn)下一步；（4）分枝與定界：從第一個(gè)變量開始依次取“1”或“0”，求極大值時(shí)其后面的變量等于“1”，求極小值時(shí)其后面的變量等于“0”，用分枝定界法搜索可行解和最優(yōu)解。分枝－隱枚舉法是從非可行解中進(jìn)行分枝搜索可行解，第（1）步到第（3）步用了隱枚舉法的思路，第（4）步用了分枝定界法的思路。(2)變量重新排序：變量依據(jù)目標(biāo)函數(shù)系數(shù)值按升排序；3.30－1規(guī)劃的求解48當(dāng)變量作了代換后，約束條件中的變量也相應(yīng)作代換。（3）求主枝停止分枝和需要繼續(xù)分枝的原則：（1）當(dāng)某一子問題是可行解時(shí)則停止分枝并保留；（2）不是可行解但目標(biāo)值劣于現(xiàn)有保留分枝的目標(biāo)值時(shí)停止分枝并剪枝；（3）后續(xù)分枝變量無論取“1”或“0”都不能得到可行解時(shí)停止分枝并剪枝；（4）當(dāng)某一子問題不可行但目標(biāo)值優(yōu)于現(xiàn)有保留分枝的所有目標(biāo)值，則要繼續(xù)分枝。3.30－1規(guī)劃的求解49停止分枝和需要繼續(xù)分枝的原則：3.30－1規(guī)劃的求解4【例3-8】用分枝－隱枚舉法求解下列BIP問題3.30－1規(guī)劃的求解50【例3-8】用分枝－隱枚舉法求解下列BIP問題3.30【解】（1）目標(biāo)函數(shù)系數(shù)全部非負(fù)，直接對變量重新排序（2）求主枝：令X＝(1，1，1，1)得到主枝1，檢查約束條件知(3-10c)不滿足，則進(jìn)行分枝。（3）令x2=0同時(shí)令x3=0及x3=1得到分枝2和分枝3，X2和X3是可行解，分枝停止并保留，如表3-8及圖3-8所示。3.30－1規(guī)劃的求解51【解】（1）目標(biāo)函數(shù)系數(shù)全部非負(fù)，直接對變量重新排序（2）求表3-8令x2=1同時(shí)令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z5＝11小于Z3和Z4，分枝停止并剪枝。注意到分枝6，x4＝1時(shí)只有x1＝0（x1＝1就是主枝），X6不可行并且Z6＝10小于Z3和Z4，分枝停止并剪枝，分枝過程結(jié)束。整個(gè)計(jì)算過程可用圖3－2和表3-8表示。分枝(x2,x3,x4,x1)3-10a3-10b3-10cZj可行性1(1,1,1,1)√√×16不可行2(0,0,1,1)√√√11可行3(0,1,1,1)√√√14可行4(1,0,1,1)√√√13可行5(1,1,0,1)×

11不可行6(1,1,1,0)×

10不可行52表3-8令x2=1同時(shí)令x3=0得到分枝4，X4是可行解，搜索到3個(gè)可行解，3個(gè)目標(biāo)值中Z3最大，因此X3是最優(yōu)解，轉(zhuǎn)換到原問題的最優(yōu)解為X＝（1，0，1，1），最優(yōu)值Z＝14，計(jì)算結(jié)束。圖3－23.30－1規(guī)劃的求解53搜索到3個(gè)可行解，3個(gè)目標(biāo)值中Z3最大，因此X3是最【例3-9】用分枝－隱枚舉法求解下列BIP問題【解】（1）令x2=1－x'2及x5=1－x'5，代入模型后整理得3.30－1規(guī)劃的求解54【例3-9】用分枝－隱枚舉法求解下列BIP問題【解】（1）（2）目標(biāo)函數(shù)系數(shù)按升序?qū)?yīng)的變量重新排列得到模型（3）求主枝。由于目標(biāo)函數(shù)求最小值，令所有變量等于零，得到主枝的解X1＝（0，0，0，0，0），Z1＝－7，檢驗(yàn)約束條件知X1不可行，進(jìn)行分枝。（4）取x1=1和x1=0，分別其它變量等于“1”和

“0”分枝，判斷可行性，計(jì)算過程參見表3－6及圖3－3。3.30－1規(guī)劃的求解55（2）目標(biāo)函數(shù)系數(shù)按升序?qū)?yīng)的變量重新排列得到模型（3）求分枝j上一分枝Xj=(x1,x4,x'2,x'5,x3)3-11a3-11bZj可行性12345主枝1111(0,0,0,0,0)(0,1,0,0,0)(0,0,1,0,0)(0,0,0,1,0)(0,0,0,0,1)√√√×√××××√－7－5－4－3－1不可行不可行不可行不可行可行67891016666(1,0,0,0,0)(1,1,0,0,0)(1,0,1,0,0)(1,0,0,1,0)(1,0,0,0,1)√×√√√××××√－6－4－3－20不可行不可行不可行不可行可行表3－63.30－1規(guī)劃的求解56分枝j上一分枝Xj=(x1,x4,x'2,x'5,x由表3－6知，分枝5和分枝10兩個(gè)問題可行，分枝5優(yōu)于分枝10，其它不可行子問題盡管目標(biāo)值優(yōu)于分枝5，由約束(3-11b)知，繼續(xù)分枝不可能得到其它可行解，因此停止分枝，計(jì)算結(jié)束。分枝5的解X5＝(x1,x4,x'2,x'5,x3)＝（0，0，0，0，1），原BIP的最優(yōu)解為X＝(x1,x2,x3,x4,x5)＝(0，1，1，0，1),最優(yōu)值Z＝－1。圖3－33.30－1規(guī)劃的求解57由表3－6知，分枝5和分枝10兩個(gè)問題可行，分枝5優(yōu)于分枝1在分枝－隱枚舉法的計(jì)算過程中，由于變量已經(jīng)按目標(biāo)函數(shù)系數(shù)從小到大重新排序，因此在選擇子問題分枝的原則是按排序后的變量順序分枝，但變量較多時(shí)搜索可行解的過程可能非常漫長。針對轉(zhuǎn)換后的目標(biāo)函數(shù)特征，極大值問題的解中“1”越多越優(yōu)，極小值問題的解中“0”越多越優(yōu)，因此在選擇變量分枝時(shí)盡可能采用避“0”或“1”的方法，請觀察表3－8及3－6.3.30－1規(guī)劃的求解58在分枝－隱枚舉法的計(jì)算過程中，由于變量已經(jīng)按目標(biāo)函數(shù)

長江綜合商場有5000m2營業(yè)面積招租，擬吸引以下5類商店入租。已知各類商店開設(shè)一個(gè)店鋪占用的面積，在該商場內(nèi)最多與最少開設(shè)的個(gè)數(shù)，以及每類商店開設(shè)不同個(gè)數(shù)時(shí)每個(gè)商店的每月預(yù)計(jì)利潤見表。商場除按租用面積每月收取100元/m2租金外，還按利潤的10%按月收取屋業(yè)管理費(fèi)。問該商場應(yīng)招租上述各類商店各多少個(gè)，使預(yù)期收入為最大？代號(hào)商店類別一個(gè)鋪面面積(m2)開設(shè)數(shù)開設(shè)不同數(shù)時(shí)一個(gè)店鋪利潤(萬元)最少最多1231服裝250139872鞋帽35012109-3百貨600132720204書店300021610-5餐飲40013171512思考商場招租59長江綜合商場有5000m2營業(yè)面積招租，擬吸引以代號(hào)商店類別開設(shè)不同個(gè)數(shù)店鋪1231服裝x11x12x132鞋帽x21x22x233百貨x31x32x334書店x41x42x435餐飲x51x52x53思考商場招租60代號(hào)商店開設(shè)不同個(gè)數(shù)店鋪1231服裝x11x12x132鞋帽maxZ=100(250y1+350y2+600y3+300y4+400y5)+10%(9x11+8×2x12+7×3x13+10x21+9×2x22+…+12×3x53)x11+2x12+3x13=y1x21+2x22+3x23=y2x31+2x32+3x33=y3x41+2x42+3x43=y4x51+2x52+3x53=y5x11+x12+x13=1x21+x22+x23=1x31+x32+x33=1x41+x42+x43≤1x51+x52+x53=1x23=0x43=0250y1+350y2+600y3+300y4+400y5≤5000xij=0或1（i=1,2,3,4,5;j=1,2,3),yi≥0(i=1,…，5）61maxZ=100(250y1+350y2+600y3+300用LINDO軟件計(jì)算，得最優(yōu)解

x12=x22=x33=x42=x53=1，其余xij=0

最優(yōu)值Z=63（萬元）最優(yōu)方案：招租服裝店2個(gè)，鞋帽店2個(gè)，百貨店3個(gè)，書店2個(gè)，餐飲店3個(gè)，預(yù)期收入最大，為63萬元思考商場招租62用LINDO軟件計(jì)算，得最優(yōu)解思考商場招租621.用隱枚舉法求0-1規(guī)劃的最優(yōu)解2.用分枝－隱枚舉法求解0-1規(guī)劃的最優(yōu)解TheEndofChapter33.30－1規(guī)劃的求解本節(jié)學(xué)習(xí)要點(diǎn)631.用隱枚舉法求0-1規(guī)劃的最優(yōu)解TheEndof【案例C-3】證券營業(yè)網(wǎng)點(diǎn)設(shè)置問題【解】引入0－1變量

令bj表示在第j號(hào)城市建一家網(wǎng)點(diǎn)的平均投資額，rj表示第j號(hào)城市每一家網(wǎng)點(diǎn)的平均市場占有率，cj表示第j號(hào)城市每一家網(wǎng)點(diǎn)的平均利潤額。64【案例C-3】證券營業(yè)網(wǎng)點(diǎn)設(shè)置問題【解】引入0－1變量6565謝謝！謝謝！云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)運(yùn)籌學(xué)第三章云南農(nóng)業(yè)大學(xué)

線性規(guī)劃的決策變量取值可以是任意非負(fù)實(shí)數(shù)，但許多實(shí)際問題中，只有當(dāng)決策變量的取值為整數(shù)時(shí)才有意義。例如，產(chǎn)品的件數(shù)、機(jī)器的臺(tái)數(shù)、裝貨的車數(shù)、完成工作的人數(shù)等，分?jǐn)?shù)或小數(shù)解顯然是不合理的。

對某一個(gè)項(xiàng)目要不要投資的決策問題，可選用一個(gè)邏輯變量x，當(dāng)x=1表示投資，x=0表示不投資。3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

純整數(shù)規(guī)劃(IP)：xj全部取整數(shù)混合整數(shù)規(guī)劃(MIP)：xj部分取整數(shù)0-1整數(shù)規(guī)劃(BIP)：整數(shù)變量只能取0或1分類68線性規(guī)劃的決策變量取值可以是任意非負(fù)實(shí)數(shù)，但許多實(shí)際問【例3-1】某人有一背包可以裝10公斤重、0.025m3的物品。他準(zhǔn)備用來裝甲、乙兩種物品，每件物品的重量、體積和價(jià)值如表3-1所示。問兩種物品各裝多少件，才能使所裝物品的總價(jià)值最大？表3-1【解】設(shè)甲、乙兩種物品各裝x1、x2件，則數(shù)學(xué)模型為：(3-1)物品重量（公斤/件）體積（m3/件）價(jià)值(元/件)甲乙1.20.80.0020.0025433.1整數(shù)規(guī)劃的數(shù)學(xué)模型

69【例3-1】某人有一背包可以裝10公斤重、0.025m3的

【補(bǔ)充例】投資決策問題。某公司有5個(gè)項(xiàng)目被列入投資計(jì)劃，各項(xiàng)目的投資額和期望的投資收益如下表3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

該公司只有600萬元資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：（1）在項(xiàng)目1、2和3中必須且只有一項(xiàng)被選中；（2）項(xiàng)目3和項(xiàng)目4最多只能選中一項(xiàng)；（3）項(xiàng)目5被選中的前提是項(xiàng)目1必須被選中。如何在上述條件下選擇一個(gè)最好的投資方案，使投資收益最大？項(xiàng)目投資額（萬元）投資收益（萬元）12101602300210315060413080526018070【補(bǔ)充例】投資決策問題。某公司有5個(gè)項(xiàng)目被列入投資計(jì)劃【解】設(shè)xj為選擇第j（j=1,2,3,4,5)個(gè)項(xiàng)目的決策3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

71【解】設(shè)xj為選擇第j（j=1,2,3,4,5)個(gè)項(xiàng)目的【例3-2】在例3-1中，假設(shè)此人還有一只旅行箱，最大載重量為12公斤，其體積是0.02m3。背包和旅行箱只能選擇其一，建立下列幾種情形的數(shù)學(xué)模型，使所裝物品價(jià)值最大。（1）所裝物品不變；（2）如果選擇旅行箱，則只能裝載丙和丁兩種物品，每件物品的重量、體積和價(jià)值如下表所示3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

物品重量（公斤/件）體積（m3/件）價(jià)值(元/件)丙丁1.80.60.00150.0024372【例3-2】在例3-1中，假設(shè)此人還有一只旅行箱，最大載重【解】（1）引入0－1變量yj，令j=1,2分別是采用背包及旅行箱裝載。3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

(3-2)此問題也可以建立兩個(gè)整數(shù)規(guī)劃模型。73【解】（1）引入0－1變量yj，令j=1,2分別是采用（2）由于不同載體所裝物品不一樣，數(shù)學(xué)模型為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

其中M為充分大的正數(shù)。當(dāng)使用背包時(shí)(y1=1,y2=0)，式(b)和(d)是多余的；當(dāng)使用旅行箱時(shí)(y1=0,y2=1)，式(a)和(c)是多余的。背包約束旅行箱約束74（2）由于不同載體所裝物品不一樣，數(shù)學(xué)模型為3.1整數(shù)規(guī)（1）右端常數(shù)是k個(gè)值中的一個(gè)時(shí)，類似式(3-2)的約束條件為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

同樣可以討論對于有m個(gè)條件互相排斥、有m（≤m、≥m）個(gè)條件起作用的情形。75（1）右端常數(shù)是k個(gè)值中的一個(gè)時(shí)，類似式(3-2)的約束條件（2）對于m個(gè)（組）條件中有k（≤m）個(gè)（組）起作用時(shí)，類似式(3-3)的約束條件寫成這里yi=1表示第i組約束不起作用（如y1=1式(3-3b)、(3-3d)不起作用），yi=0表示第i個(gè)約束起作用。當(dāng)約束條件是“≥”符號(hào)時(shí)右端常數(shù)項(xiàng)應(yīng)為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

76（2）對于m個(gè)（組）條件中有k（≤m）個(gè)（組）起作用時(shí)【例3-3】試引入0－1變量將下列各題分別表達(dá)為一般線性約束條件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，則x2≥0，否則x2≤8（3）x2取值0，1，3，5，7【解】

（1）3個(gè)約束只有1個(gè)起作用或3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

如果要求至少一個(gè)條件滿足，模型如何改變？77【例3-3】試引入0－1變量將下列各題分別表達(dá)為一般線性約束（3）右端常數(shù)是5個(gè)值中的1個(gè)（2）兩組約束只有一組起作用3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

(1)(2)(3)(4)78（3）右端常數(shù)是5個(gè)值中的1個(gè)（2）兩組約束只有一組起作用3【例3-4】企業(yè)計(jì)劃生產(chǎn)4000件某種產(chǎn)品，該產(chǎn)品可自己加工、外協(xié)加工任意一種形式生產(chǎn)。已知每種生產(chǎn)的固定費(fèi)用、生產(chǎn)該產(chǎn)品的單件成本以及每種生產(chǎn)形式的最大加工數(shù)量（件）限制如表3－2所示，怎樣安排產(chǎn)品的加工使總成本最小。表3－2

固定成本（元）變動(dòng)成本（元／件）最大加工數(shù)（件）本企業(yè)加工50081500外協(xié)加工Ⅰ80052000外協(xié)加工Ⅱ6007不限3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

79【例3-4】企業(yè)計(jì)劃生產(chǎn)4000件某種產(chǎn)品，該產(chǎn)品可自己加工【解】設(shè)xj為采用第j（j=1,2,3）種方式生產(chǎn)的產(chǎn)品數(shù)量，生產(chǎn)費(fèi)用為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

其中kj是固定成本，cj是可變成本。設(shè)0－1變量yj80【解】設(shè)xj為采用第j（j=1,2,3）種方式生產(chǎn)的產(chǎn)品數(shù)（3-4）用WinQSB軟件求解得到：X＝(0，2000，2000)T，Y＝(0，1，1)T，Z=254003.1整數(shù)規(guī)劃的數(shù)學(xué)模型

配合目標(biāo)，使得只有選用第j種加工方式才產(chǎn)生相應(yīng)成本，不選用第j種加工方式就沒有成本。81（3-4）用WinQSB軟件求解得到：3.1整數(shù)規(guī)劃的數(shù)整數(shù)規(guī)劃的一般形式：稱線性規(guī)劃模型（Ⅰ）

（Ⅱ）(LP)為（Ⅰ）的松弛問題。

每一個(gè)整數(shù)規(guī)劃都對應(yīng)一個(gè)松弛問題，整數(shù)規(guī)劃比它的松弛問題約束得更緊。部分或全部取整3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

82整數(shù)規(guī)劃的一般形式：稱線性規(guī)劃模型（Ⅰ）（Ⅱ）(LP)為3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

習(xí)題3.4【解】令運(yùn)動(dòng)員甲、乙、丙、丁、戊編號(hào)為1、2、3、4、5，項(xiàng)目高低杠、平衡木、鞍馬、自由體操編號(hào)為1、2、3、4。設(shè)

項(xiàng)目運(yùn)動(dòng)員1234高低杠平衡木鞍馬自由體操1甲x11x12x13x142乙x21x22x23x243丙x31x32x33x344丁x41x42x43x445戊x51x52x53x54833.1整數(shù)規(guī)劃的數(shù)學(xué)模型習(xí)題3.4max=8.6x11+9.7x12+8.9x13+9.4x14+9.2x21+8.3x22+8.5x23+8.1x24+8.8x31

+8.7x32+9.3x33+9.6x34+8.5x41+7.8x42+9.5x43+7.9x44+8x51+9.4x52+8.2x53+7.7x54x11+x12+x13+x14≦3x21+x22+x23+x24≦3x31+x32+x33+x34≦3x41+x42+x43+x44≦3x51+x52+x53+x54≦3x11+x21+x31+x41+x51≧1x12+x22+x32+x42+x52≧1x13+x23+x33+x43+x53≧1x14+x24+x34+x44+x54≧1x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43+x44+x51+x52+x53+x54=10xij=0或1(i=1,2,3,4,5;j=1,2,3,4)3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

84max=8.6x11+9.7x12+8.9x13+9.4x11.整數(shù)規(guī)劃模型的特征2.什么是純（混合）整數(shù)規(guī)劃3.0－1規(guī)劃模型的應(yīng)用下一節(jié)：純整數(shù)規(guī)劃的求解3.1整數(shù)規(guī)劃的數(shù)學(xué)模型

本節(jié)學(xué)習(xí)要點(diǎn)851.整數(shù)規(guī)劃模型的特征下一節(jié)：純整數(shù)規(guī)劃的求解3.1

整數(shù)規(guī)劃解的特點(diǎn)整數(shù)規(guī)劃（Ⅰ）的可行解集是其松弛問題（Ⅱ）的可行解集的子集。線性規(guī)劃問題的可行解集是一個(gè)凸集（稠密的），但整數(shù)規(guī)劃的可行解集不是凸集（離散型）。如果松弛問題（Ⅱ）的最優(yōu)解是整數(shù)解，則一定是整數(shù)規(guī)劃（Ⅰ）的最優(yōu)解。整數(shù)規(guī)劃（Ⅰ）的最優(yōu)值不會(huì)優(yōu)于松弛問題（Ⅱ）的最優(yōu)值。3.2整數(shù)規(guī)劃的求解86整數(shù)規(guī)劃解的特點(diǎn)3.2整數(shù)規(guī)劃的求解203.2整數(shù)規(guī)劃的求解圖3-1點(diǎn)B為最優(yōu)解X＝(3.57，7.14)Z＝35.7用圖解法求解例3-1的松弛問題整數(shù)規(guī)劃問題的可行解集是圖中可行域內(nèi)的整數(shù)點(diǎn)。8.3310松弛問題的最優(yōu)解X=(3.57,7.14),z=35.7x1x2oAC10B圖3-1873.2整數(shù)規(guī)劃的求解圖3-1點(diǎn)B為最優(yōu)解用圖解法求解松弛問題的最優(yōu)解X＝(3.57，7.14)，Z＝35.7“四舍五入”得X=(4,7)不是可行解；用“取整”法來解時(shí)，X=(3,7)雖屬可行解，但代入目標(biāo)函數(shù)得Z=33,并非最優(yōu)。該整數(shù)規(guī)劃問題的最優(yōu)解是X=(5,5)，最優(yōu)值是Z=35即甲、乙兩種物品各裝5件，總價(jià)值35元。

由圖3－1知，點(diǎn)（5，5）不是LP可行域的頂點(diǎn)，直接用圖解法或單純形法都無法求出整數(shù)規(guī)劃問題的最優(yōu)解，因此求解整數(shù)規(guī)劃問題的最優(yōu)解需要采用其它特殊方法。3.2整數(shù)規(guī)劃的求解8.3310松弛問題的最優(yōu)解X=(3.57,7.14),z=35.7x1x2oAC10B圖3-188松弛問題的最優(yōu)解X＝(3.57，7.14)，Z＝35【例3-5】用分支定界法求解例3-1【解】先求對應(yīng)的松弛問題用圖解法得到最優(yōu)解X＝（3.57,7.14）,Z0=35.73.2.1分支定界法89【例3-5】用分支定界法求解例3-1【解】先求對應(yīng)的松弛問8.3310松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC103.2.1分支定界法908.3310松弛問題LP0的最優(yōu)解X=(3.57,7.11010x1x20ABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.5911010x1x20ABCLP1LP234LP1:X=(3,1010x10ACLP134LP1:X=(3,7.6),Z1=34.8①②x1B67LP3:X=(4.33,6),Z3=35.33LP2LP3921010x10ACLP134LP1:X=(3,7.6),x1x11010x10ACLP134LP1:X=(3,7.6),Z1=34.8①②x1B67LP2LP3LP5LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=35此為原IP最優(yōu)解593x1x11010x10ACLP134LP1:X=(3,7.盡管LP1的解中x2不為整數(shù)，但Z5≧Z1，因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。若Z5≦Z1

，則要對LP1進(jìn)行分支。3.2.1分支定界法94盡管LP1的解中x2不為整數(shù)，但Z5≧Z1，因此L上述分枝過程可用下圖表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5

無可行解x2≥7最優(yōu)解3.2.1分支定界法95上述分枝過程可用下圖表示LP0:X=(3.57,7.14分支定界法的步驟：1.求整數(shù)規(guī)劃的松弛問題最優(yōu)解；2.

若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步；3.2.1分支定界法3.任意選一個(gè)非整數(shù)解的變量xi，在松弛問題中加上約束xi≤[xi]及xi≥[xi]+1組成兩個(gè)新的松弛問題，稱為分支。新的松弛問題具有特征：當(dāng)原問題是求最大值時(shí)，目標(biāo)值是分支問題的上界；當(dāng)原問題是求最小值時(shí)，目標(biāo)值是分支問題的下界；96分支定界法的步驟：1.求整數(shù)規(guī)劃的松弛問題最優(yōu)解；3.4.

檢查所有分支的解及目標(biāo)函數(shù)值，若某分支的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分支的目標(biāo)值，則將其它分支剪去不再計(jì)算,若還存在非整數(shù)解并且目標(biāo)值大于（max）整數(shù)解的目標(biāo)值，需要繼續(xù)分支，再檢查，直到得到最優(yōu)解。分支原則：始終選Z值大的，且xi中有分?jǐn)?shù)的LP進(jìn)行分支。定界原則：滿足取整要求，且目標(biāo)函數(shù)值較已定的“界”更優(yōu)，則用該目標(biāo)函數(shù)值替換，重新定界。

3.2.1分支定界法說明：

分支定界法適用于求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃974.

檢查所有分支的解及目標(biāo)函數(shù)值，若某分支的解是整數(shù)并且設(shè)純整數(shù)規(guī)劃

松弛問題的最優(yōu)解3.2.2割平面法設(shè)xi=不為整數(shù)，98設(shè)純整數(shù)規(guī)劃松弛問題的最優(yōu)解3.2.2割平面法設(shè)xi將分離成一個(gè)整數(shù)與一個(gè)非負(fù)真分?jǐn)?shù)之和：則有等式兩邊都為整數(shù),并且有3.2.2割平面法99將分離成一個(gè)整數(shù)與一個(gè)非負(fù)真分加入松弛變量si得此式稱為以xi行為源行（來源行）的割平面方程，或分?jǐn)?shù)切割式，或R.E.Gomory(高莫雷)約束方程。將Gomory約束加入到松弛問題的最優(yōu)表中，用對偶單純形法計(jì)算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部變量為整數(shù)。則3.2.2割平面法100加入松弛變量si得此式稱為以xi行為源行（來源行）的割平面方例如，x1行：移項(xiàng)：加入松弛變量s1得割平面方程同理，對于x2行有：3.2.2割平面法101例如，x1行：移項(xiàng)：加入松弛變量s1得割平面方程同理，對于x【例3-6】用割平面法求解下列IP問題【解】對應(yīng)的松弛問題是3.2.2割平面法102【例3-6】用割平面法求解下列IP問題【解】對應(yīng)的松弛問加入松弛變量x3及x4后，用單純形法求解，得到最優(yōu)表3-3。

最優(yōu)解X(0)＝(5/2，15/4),不是IP的最優(yōu)解。選擇表中的第一行(也可以選第二行)為源行Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4表3-33.2.2割平面法103加入松弛變量x3及x4后，用單純形法求解，得到最優(yōu)表3-3。分離系數(shù)后改寫成加入松弛變量x5得到高莫雷約束方程將此式作為約束條件添加到表3－3中，用對偶單純形法計(jì)算，如表3－4所示

3.2.2割平面法104分離系數(shù)后改寫成加入松弛變量x5得到高莫雷約束方程將此式作為Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/4－1/8－1－1/23/4－20015/215/4－2λj00－5/8－1/40430x1x2x41000101/2－1/21/2001－1/43/8－1/2331λj00－1/20－1/8最優(yōu)解X(1)＝(3，3)，最優(yōu)值Z＝21。表3－43.2.2割平面法105Cj43000bCBXBx1x2x3x4x54x1101/4x2x1ACBx1+2x2=100DC6x1+4x2=30Ex1+x2≤6幾何意義

由約束條件得：x3=30-6x1-4x2,x4=10-x1-2x2代入割平面方程-x3-2x4≤-2，得x1+x2≤6

說明：利用割平面法求解整數(shù)規(guī)劃問題時(shí),若從最優(yōu)單純形表中選擇具有最大?。ǚ郑?shù)部分的非整分量所在行構(gòu)造割平面方程，往往可以提高“切割”效率，減少“切割”次數(shù)。

3.2.2割平面法不含任何整數(shù)解106x2x1ACBx1+2x2=100DC6x1+4x2=30E5x15x1+9x2≤45x2x1+x2≤66960思考：

對于兩個(gè)變量的純整數(shù)規(guī)劃問題是否可采用圖解法。最優(yōu)解x1=0,x2=53.2.3整數(shù)規(guī)劃的圖解法1075x15x1+9x2≤45x2x1+x2≤66960思考：最步驟：1.作出松弛問題的可行域。2.在可行域內(nèi)作出所有的整數(shù)網(wǎng)格。3.作目標(biāo)函數(shù)等值線，將等值線平行移動(dòng)，最后接觸到的網(wǎng)格點(diǎn)（或平行移動(dòng)到松弛問題的最優(yōu)解點(diǎn)再往回移，首先接觸到的網(wǎng)格點(diǎn)），就是整數(shù)規(guī)劃的最優(yōu)解。3.2.3整數(shù)規(guī)劃的圖解法108步驟：3.2.3整數(shù)規(guī)劃的圖解法421.理解分支與定界的含義2.選擇合適的“枝”生“枝”3.掌握何時(shí)停止生“枝”4.領(lǐng)會(huì)割平面法的基本原理5.分離源行，求出Gomory約束6.在最優(yōu)表中增加Gomory約束，用對偶單純形法迭代下一節(jié)：0－1規(guī)劃的求解3.2整數(shù)規(guī)劃的求解本節(jié)學(xué)習(xí)要點(diǎn)1091.理解分支與定界的含義下一節(jié)：0－1規(guī)劃的求解3.23.3.1求解0－1整數(shù)規(guī)劃的隱枚舉法隱枚舉法的步驟：

1.找出任意一可行解，目標(biāo)函數(shù)值為Z0

2.

原問題求最大值時(shí)，則增加一個(gè)約束

作為過濾條件。當(dāng)求最小值時(shí)，上式改為小于等于約束。列出所有可能解，對每個(gè)可能解先檢驗(yàn)是否滿足過濾條件，若滿足再檢驗(yàn)其它約束，若不滿足約束，則不可行，若所有約束都滿足，且目標(biāo)值超過Z0,則應(yīng)更換過濾條件。4.目標(biāo)函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解。3.30－1規(guī)劃的求解1103.3.1求解0－1整數(shù)規(guī)劃的隱枚舉法隱枚舉法的步驟：1【例3-7】用隱枚舉法求解下列BIP問題3.30－1規(guī)劃的求解(1)(2)(3)(4)111【例3-7】用隱枚舉法求解下列BIP問題3.30－1規(guī)jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)Zj1(0,0,0,0)

9(1,0,0,0)

2(0,0,0,1)10(1,0,0,1)3(0,0,1,0)

11(1,0,1,0)4(0,0,1,1)12(1,0,1,1)5(0,1,0,0)

13(1,1,0,0)6(0,1,0,1)

14(1,1,0,1)7(0,1,1,0)

15(1,1,1,0)

8(0,1,1,1)16(1,1,1,1)表3－5最優(yōu)解：X＝(1,0,1,1)T，最優(yōu)值Z＝143.30－1規(guī)劃的求解√×√√√√z≧53√√√√275√×

106√√√×16√√√√z≧119√√√√z≧14813118z≥8112jX(1)(2)(3)(4)ZjjX(1)(2)(3)(4)3.3.2分枝－隱枚舉法求解BIP問題

將分枝定界法與隱枚舉法結(jié)合起來用，得到分枝－隱枚舉法。計(jì)算步驟如下：（1）將BIP問題的目標(biāo)函數(shù)的系數(shù)化為非負(fù)，如3.30－1規(guī)劃的求解1133.3.2分枝－隱枚舉法求解BIP問題將分枝定界法當(dāng)變量作了代換后，約束條件中的變量也相應(yīng)作代換。（3）求主枝：目標(biāo)函數(shù)是max形式時(shí)令所有變量等于1，得到目標(biāo)值的上界；目標(biāo)函數(shù)是min形式時(shí)令所有變量等于0，得到目標(biāo)值的下界；如果主枝的解滿足所有約束條件則得到最優(yōu)解，否則轉(zhuǎn)下一步；（4）分枝與定界：從第一個(gè)變量開始依次取“1”或“0”，求極大值時(shí)其后面的變量等于“1”，求極小值時(shí)其后面的變量等于“0”，用分枝定界法搜索可行解和最優(yōu)解。分枝－隱枚舉法是從非可行解中進(jìn)行分枝搜索可行解，第（1）步到第（3）步用了隱枚舉法的思路，第（4）步用了分枝定界法的思路。(2)變量重新排序：變量依據(jù)目標(biāo)函數(shù)系數(shù)值按升排序；3.30－1規(guī)劃的求解114當(dāng)變量作了代換后，約束條件中的變量也相應(yīng)作代換。（3）求主枝停止分枝和需要繼續(xù)分枝的原則：（1）當(dāng)某一子問題是可行解時(shí)則停止分枝并保留；（2）不是可行解但目標(biāo)值劣于現(xiàn)有保留分枝的目標(biāo)值時(shí)停止分枝并剪枝；（3）后續(xù)分枝變量無論取“1”或“0”都不能得到可行解時(shí)停止分枝并剪枝；（4）當(dāng)某一子問題不可行但目標(biāo)值優(yōu)于現(xiàn)有保留分枝的所有目標(biāo)值，則要繼續(xù)分枝。3.30－1規(guī)劃的求解115停止分枝和需要繼續(xù)分枝的原則：3.30－1規(guī)劃的求解4【例3-8】用分枝－隱枚舉法求解下列BIP問題3.30－1規(guī)劃的求解116【例3-8】用分枝－隱枚舉法求解下列BIP問題3.30【解】（1）目標(biāo)函數(shù)系數(shù)全部非負(fù)，直接對變量重新排序（2）求主枝：令X＝(1，1，1，1)得到主枝1，檢查約束條件知(3-10c)不滿足，則進(jìn)行分枝。（3）令x2=0同時(shí)令x3=0及x3=1得到分枝2和分枝3，X2和X3是可行解，分枝停止并保留，如表3-8及圖3-8所示。3.30－1規(guī)劃的求解117【解】（1）目標(biāo)函數(shù)系數(shù)全部非負(fù)，直接對變量重新排序（2）求表3-8令x2=1同時(shí)令x3=0得到分枝4，X4是可行解，分枝停止并保留。令x2=1、x3=1，x4取“0”和“1”得到分枝5和6，分枝5不可行并且Z5＝11小于Z3和Z4，分枝停止并剪枝。注意到分枝6，x4＝1時(shí)只有x1＝0（x1＝1就是主枝），X6不可行并且Z6＝10小于Z3和Z4，分枝停止并剪枝，分枝過程結(jié)束。整個(gè)計(jì)算過程可用圖3－2和表3-8表示。分枝(x2,x3,x4,x1)3-10a3-10b3-10cZj可行性1(1,1,1,1)√√×16不可行2(0,0,1,1)√√√11可行3(0,1,1,1)√√√14可行4(1,0,1,1)√√√13可行5(1,1,0,1)×

11不可行6(1,1,1,0)×

10不可行118表3-8令x2=1同時(shí)令x3=0得到分枝4，X4是可行解，搜索到3個(gè)可行解，3個(gè)目標(biāo)值中Z3最大，因此X3是最優(yōu)解，轉(zhuǎn)換到原問題的最優(yōu)解為X＝（1，0，1，1），最優(yōu)值Z＝14，計(jì)算結(jié)束。圖3－23.30－1規(guī)劃的求解119搜索到3個(gè)可行解，3個(gè)目標(biāo)值中Z3最大，因此X3是最【例3-9】用分枝－隱枚舉法求解下列BIP問題【解】（1）