運(yùn)籌與決策之4整數(shù)規(guī)劃課件

11緒論—Introduction2線性規(guī)劃—LinearProgramming3運(yùn)輸與指派問題—TransportationModels4整數(shù)規(guī)劃—IntegerProgramming5網(wǎng)絡(luò)模型—NetworkModels6項(xiàng)目計(jì)劃—PERT&CPM7排隊(duì)論—QueueingModels8

模擬—Simulation9決策分析—DecisionTheory10多目標(biāo)決策—Multi-objectiveDecision《管理數(shù)量方法》目錄11緒論—Introduc2授課內(nèi)容Case:分銷系統(tǒng)設(shè)計(jì)（P192）整數(shù)規(guī)劃圖解法及分枝定界法MS6.0軟件求解整數(shù)規(guī)劃應(yīng)用舉例銀行選址P209（講義：消防站選址）案例討論：課本出版P2222授課內(nèi)容Case:分銷系統(tǒng)設(shè)計(jì)（P192）3Questions整數(shù)規(guī)劃IP與線性規(guī)劃LP有何不同？整數(shù)規(guī)劃的分類？整數(shù)規(guī)劃的求解方法？分枝定界法的基本思路？分枝問題解可能出現(xiàn)的情況？3Questions整數(shù)規(guī)劃IP與線性規(guī)劃LP有何不同？整4Q1：整數(shù)規(guī)劃與線性規(guī)劃LP區(qū)別：

（要求所有xj的解為整數(shù)，或者要求部分xj的解為整數(shù)）1）一般整數(shù)規(guī)劃。要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃；或者要求部分xj的解為整數(shù)，稱為混合整數(shù)規(guī)劃。2）0-1整數(shù)規(guī)劃。它規(guī)定整數(shù)變量只能有兩個(gè)值，0或1。4Q1：整數(shù)規(guī)劃與線性規(guī)劃LP區(qū)別：

（要求所有xj的5Q2：整數(shù)規(guī)劃的解法圖解法窮舉法分枝定界法(BranchandMethod)割平面法5Q2：整數(shù)規(guī)劃的解法圖解法6Q3：分枝定界法的基本思路maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X為整數(shù)

(B)(B)為(A)的線性規(guī)劃松弛問題。6Q3：分枝定界法的基本思路maxZ=CX(A)maxZ7(C)(D)(B)Xj

i+1(B)Xj

iX*最優(yōu)解Xj*i+1i(C)(D)X*最優(yōu)解為非整數(shù)解，則對(duì)(B)每次分兩枝,每枝多一個(gè)約束條件7(C)(D)(B)(B)X*最優(yōu)解Xj*i+1i(C)(D8Q4：分枝問題解可能出現(xiàn)的情況如何回答？8Q4：分枝問題解可能出現(xiàn)的情況如何回答？9表分枝問題解可能出現(xiàn)的情況情況2,4,5

找到最優(yōu)解情況3

在縮減的域上繼續(xù)分枝定界法情況6問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分枝的整數(shù)解進(jìn)行比較，結(jié)論如情況4。結(jié)果9表分枝問題解可能出現(xiàn)的情況情況2,4,5101緒論—Introduction2線性規(guī)劃—LinearProgramming3運(yùn)輸問題

—TransportationModels4整數(shù)規(guī)劃—IntegerProgramming5網(wǎng)絡(luò)模型—NetworkModels6項(xiàng)目計(jì)劃—PERT&CPM7排隊(duì)論—QueueingModels8

模擬—Simulation9決策分析—DecisionTheory10多目標(biāo)決策—Multi-objectiveDecision《管理數(shù)量方法》目錄101緒論—Introdu11授課內(nèi)容整數(shù)規(guī)劃圖解法及分枝定界法MS6.0軟件求解整數(shù)規(guī)劃應(yīng)用舉例銀行選址P230（講義：消防站選址）案例討論：課本出版P24211授課內(nèi)容整數(shù)規(guī)劃12整數(shù)規(guī)劃舉例產(chǎn)品桌

椅備用資源木工1230油漆工3260搬運(yùn)工0224利潤4050例1、家具廠生產(chǎn)計(jì)劃問題桌，椅各生產(chǎn)多少,可獲最大利潤?12整數(shù)規(guī)劃舉例例1、家具廠生產(chǎn)計(jì)劃問題桌，椅各生產(chǎn)多少,13圖解法求最優(yōu)解解：X*=(15,7.5)Zmax=975該解是否符合實(shí)際要求？0203010102030X1X2DABCDABCC點(diǎn)：X1+2X2=30

3X1+2X2=60如何求解整數(shù)解？13圖解法求最優(yōu)解解：X*=(15,7.5)020301144整數(shù)規(guī)劃整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃144整數(shù)規(guī)劃整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃15整數(shù)規(guī)劃簡介要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃要求部分xj的解為整數(shù)，稱為混合整數(shù)規(guī)劃對(duì)應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問題的最優(yōu)解15整數(shù)規(guī)劃簡介要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃16整數(shù)規(guī)劃的解法圖解法窮舉法分枝定界法割平面法16整數(shù)規(guī)劃的解法圖解法17§4.1整數(shù)規(guī)劃的窮舉法窮舉法：可以通過計(jì)算和比較所有整數(shù)格點(diǎn)的值來求解。17§4.1整數(shù)規(guī)劃的窮舉法窮舉法：可以通過計(jì)算和比較所有整18例：maxZ=40x1+60x2+70x3+160x416x1+35x2+45x3+85x4

100x1,x2,x3,x4為0,1X1=1X1=0111010101X2=0X3=00解法1：枚舉法：x1=1,x2=1,x3=1,x4=0

。枚舉法？18例：maxZ=40x1+60x2+70x3+1192100個(gè)整數(shù)解，用最現(xiàn)代化的計(jì)算機(jī)也要算上幾億億年。窮舉法是無法用來求解實(shí)際問題。最優(yōu)解經(jīng)過四舍五入的方法是否可以？若該整數(shù)規(guī)劃問題有100個(gè)0－1整數(shù)變量，那么整數(shù)解有多少個(gè)？如何回答？192100個(gè)整數(shù)解，用最現(xiàn)代化的計(jì)算機(jī)也要算上幾億億年。若20§4.2分枝定界法的基本思路maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X為整數(shù)

(B)(B)為(A)的線性規(guī)劃松弛問題。20§4.2分枝定界法的基本思路maxZ=CX(A)ma21(C)(D)(B)Xj

i+1(B)Xj

iX*最優(yōu)解Xj*i+1i(C)(D)X*最優(yōu)解為非整數(shù)解，則對(duì)(B)每次分兩枝,每枝多一個(gè)約束條件21(C)(D)(B)(B)X*最優(yōu)解Xj*i+1i(C)(22分枝定界法的步驟思路:暫不考慮整數(shù)條件,用單純形法求解,得整數(shù)解,停;不是整數(shù)解,分枝。分枝:每次分兩枝,每枝多一個(gè)約束條件，（每個(gè)節(jié)點(diǎn)代表一個(gè)子問題）。停止分枝條件:1）子問題無可行解.2）子問題得整數(shù)解.3）子問題的目標(biāo)值比下界差。maxZ定界:1）初始整數(shù)規(guī)劃的松弛問題的最優(yōu)值是上界.2）子問題得整數(shù)解的最優(yōu)值是一個(gè)下界。22分枝定界法的步驟思路:暫不考慮整數(shù)條件,用單純形法求解23分枝問題解可能出現(xiàn)的情況如何回答？23分枝問題解可能出現(xiàn)的情況如何回答？24表分枝問題解可能出現(xiàn)的情況情況2,4,5

找到最優(yōu)解情況3

在縮減的域上繼續(xù)分枝定界法情況6問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分枝的整數(shù)解進(jìn)行比較，結(jié)論如情況4。結(jié)果24表分枝問題解可能出現(xiàn)的情況情況2,4,525舉例例：maxZ=x1+x26x1+

2x2175x1+

9x2

44x1,x2為整數(shù)如何回答？25舉例例：maxZ=x1+x2如何回答？26

松弛問題Z0=5.545X1=1.477X2=4.068子問題1Z1=5.333X1=1X2=4.333子問題2Z2=4.5X1=2X2=2.5子問題3Z3=5X1=1X2=4子問題4無可行解x1≥2x1≤1x2≤4x2≥5分枝定界法求解過程∴最優(yōu)整數(shù)解X1=1X2=4最優(yōu)目標(biāo)函數(shù)值Z=526松弛問題子問題1子問題2子問題3子問題4x1≥2x1≤270-1Programming(BinaryIP)

0-1整數(shù)規(guī)劃決策變量取值0或1，稱0-1或二進(jìn)制變量。0-1變量可數(shù)量化地描述諸如開與關(guān)、取與棄、有與無等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及互斥的約束條件0-1規(guī)劃應(yīng)用：如工廠選址、生產(chǎn)計(jì)劃安排、旅行購物、背包問題、人員安排、代碼選取、線路設(shè)計(jì)、可靠性等270-1Programming(BinaryIP)

28§4.3整數(shù)規(guī)劃建模應(yīng)用舉例：

0-1變量的作用1.Xj=3.從N個(gè)方案中最多選中3個(gè):2.從N個(gè)方案中必須選中一個(gè):28§4.3整數(shù)規(guī)劃建模應(yīng)用舉例：

0-1變量的作用1.29特殊約束的處理1.只有方案J選中時(shí)，方案I才可能被選中:如何表示？xi≤xj2.方案I與方案J是否選中是同時(shí)的:

xi=xj3.矛盾約束:f(x)-5≥0與f(x)≤0→-f(x)+5≤M(1-y)與f(x)≤MyM表示很大的數(shù)，y為0－1變量。如何回答？29特殊約束的處理1.只有方案J選中時(shí)，方案I才可能被選中30特殊約束的處理4.多個(gè)選一:fi(x)≤0,I=1,2,…,n.如何表示？

5.邏輯關(guān)系約束：若f(x)無限制,則g(x)≤0;若f(x)<0不成立,則g(x)無限制.如何表示？

fi(x)≤M(1-yi)I=1,2,…,n.y1+y2+…+yn=1→f(x)≥-M(1-y),g(x)≤My，M表示很大的數(shù)，y為0－1變量。30特殊約束的處理4.多個(gè)選一:fi(x)≤0,I=1310-1整數(shù)規(guī)劃模型及其應(yīng)用8.3.1資金預(yù)算（投資決策）問題8.3.2固定成本問題8.3.3配送系統(tǒng)設(shè)計(jì)8.3.4銀行選址（覆蓋問題）8.3.5產(chǎn)品設(shè)計(jì)與市場(chǎng)份額優(yōu)化310-1整數(shù)規(guī)劃模型及其應(yīng)用8.3.1資金預(yù)算（投資決策32整數(shù)規(guī)劃應(yīng)用舉例例華美公司有5個(gè)項(xiàng)目被列入投資計(jì)劃，各項(xiàng)目的投資額和期望的投資收益見下表：該公司只有600萬元資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：1.在項(xiàng)目1、2和3中必須（只）有一項(xiàng)被選中；2.項(xiàng)目3和4只能選中一項(xiàng)；（必須選一項(xiàng)）3.項(xiàng)目5被選中的前提是項(xiàng)目1必須被選中。如何在上述條件下選擇一個(gè)最好的投資方案，使投資收益最大。32整數(shù)規(guī)劃應(yīng)用舉例例華美公司有5個(gè)項(xiàng)目被列入投資計(jì)劃，各33

項(xiàng)目投資收益表

項(xiàng)目投資額（萬元）投資收益（萬元）

121015023002103100604130805260180Xj=1表項(xiàng)目j選中,Xj=0表項(xiàng)目j未選中.j=1,2,3,4,5.約束條件如何表示？33項(xiàng)目投資收益表項(xiàng)目投資額（萬元）34計(jì)算過程解:Xj=1表項(xiàng)目j選中,Xj=0表項(xiàng)目j未選中.j=1,2,3,4,5.Z表示總收益.則模型如下:

MaxZ=150X1+210X2+60X3+80X4+180X5s.t:210X1+300X2+100X3+130X4+260X5

≤600X1+X2+X3=1X3+X4=1X5

≤X1Xj=0或1;j=1,2,3,4,5.34計(jì)算過程解:Xj=1表項(xiàng)目j選中,Xj=0表項(xiàng)目j35

例解決某市消防站的布點(diǎn)問題。該城市共有6個(gè)區(qū)，每個(gè)都可以建消防站。市政府希望建設(shè)的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時(shí)，消防車要在15分鐘內(nèi)趕到現(xiàn)場(chǎng)。據(jù)實(shí)地測(cè)定，各區(qū)之間消防車行駛的時(shí)間見下表：請(qǐng)幫助該市制定一個(gè)最節(jié)省的計(jì)劃。

消防車在各區(qū)行駛距離表

地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6

010

16282720

100243217

1016240122721283212015

252717271501420

10

2125140Howtosolve？35例解決某市消防站的布點(diǎn)問題。該城市共有6個(gè)區(qū)，每個(gè)36計(jì)算過程解:Xj=1表地區(qū)設(shè)消防站,Xj=0表地區(qū)不設(shè)消防站.Z=消防站總數(shù),則模型如下:

MinZ=X1+X2+X3+X4+X5+X6s.t.X1+X2≥1X1+X2+X6≥1X3+X4≥1X3+X4+X5≥1X4+X5+X6≥1X2+X5+X6≥1Xj=0或1；j=1,2,3,4,5,6.36計(jì)算過程解:Xj=1表地區(qū)設(shè)消防站,Xj=0表地區(qū)不37銀行選址P209俄亥俄信托公司（OhioTrustCompany）希望在俄亥俄西北部20個(gè)縣進(jìn)行選址，該地區(qū)還沒有首席業(yè)務(wù)處（PrincipalPlaceofbusinessPPB）。根據(jù)俄亥俄州的銀行法，如果金融企業(yè)在任何一個(gè)縣設(shè)立PPB，就可以在該縣及其比鄰的縣設(shè)立分支機(jī)構(gòu)。俄亥俄信托公司想知道在那些縣設(shè)立PPB會(huì)使其數(shù)量最少？37銀行選址P209俄亥俄信托公司（OhioTrustC38表俄亥俄信托公司考慮的各縣鄰居考慮的縣鄰縣的數(shù)字代號(hào)考慮的縣鄰縣的數(shù)字代號(hào)12，12，16118，10，13，14，15，18，19，2021，3，12121，2，3，10，13，1632，4，9，10，12，13133，10，11，12，15，1643，5，7，91411，15，2054，6，71511，13，14，1665，7，17161，12，13，1574，5，6，8，9，17，18176，7，1887，9，10，11，18187，8，11，17，1993，4，7，8，101911，18，20103，8，9，11，12，132011，14，1938表俄亥俄信托公司考慮的各縣鄰居考慮的縣鄰縣的數(shù)字代號(hào)39整數(shù)規(guī)劃選址模型使用OR軟件對(duì)該問題進(jìn)行求解，我們得出需要3個(gè)PPB，他們應(yīng)分別選址在7、11、12。39整數(shù)規(guī)劃選址模型使用OR軟件對(duì)該問題進(jìn)行求解，我們得出需40例紅光服裝廠可生產(chǎn)三種服裝：西服、襯衫和羽絨服。生產(chǎn)不同種類的服裝要使用不同的設(shè)備，紅光服裝廠可從專業(yè)租賃公司租用這些設(shè)備。設(shè)備租金和其他經(jīng)濟(jì)參數(shù)見下表：假定市場(chǎng)需求不成問題，服裝廠每月可用工人工時(shí)為2000小時(shí)，該廠如何安排生產(chǎn)可使每月的利潤最大？40例紅光服裝廠可生產(chǎn)三種服裝：西服、襯衫和羽絨服。生產(chǎn)不41表產(chǎn)品經(jīng)濟(jì)參數(shù)

序號(hào)服裝種類設(shè)備租金元生產(chǎn)成本元/件銷售價(jià)格元/件人工工時(shí)

小時(shí)/件設(shè)備工時(shí)

小時(shí)/件設(shè)備可用工時(shí)123西服襯衫羽絨服500020003000280302004004030051430．5230030030041表產(chǎn)品經(jīng)濟(jì)參數(shù)序服裝設(shè)備生產(chǎn)成本銷售價(jià)格人工工時(shí)42解:

1.目標(biāo)函數(shù)是什么?每月的利潤最大，Ｚ=收入-租金-生產(chǎn)成本。2.決策變量是什么?租用與不租用設(shè)備?與租用后產(chǎn)品生產(chǎn)量是多少?3.約束條件是什么?１).人工工時(shí)只有2000小時(shí).２).設(shè)備工時(shí)約束.42解:1.目標(biāo)函數(shù)是什么?每月的利潤最大，Ｚ=收入-43Yj=租用第j種設(shè)備;Xj=第Ｉ種產(chǎn)品生產(chǎn)量。MaxZ=400X1+40X2+300X3-280X1-30X2-200X3-5000Y1-2000Y2-3000Y3s.t.5X1+X2+4X3≤20003X1≤300Y10.5X2≤300y22X3≤300Y3Xj≥0,且為整數(shù),j=1,2,3.Yj=0或1,j=1,2,343Yj=租用第j種設(shè)備;Xj=第Ｉ種產(chǎn)品生產(chǎn)量。44案例1課本出版P222整數(shù)規(guī)劃模型44案例1課本出版P222整數(shù)規(guī)劃模型45課本出版計(jì)算結(jié)果現(xiàn)狀優(yōu)化結(jié)果x2=x5=x6=1，預(yù)期銷售量73,000copies.1）Susan：優(yōu)化結(jié)果x2=x8=1，預(yù)期銷售量80,000copies.

2）Monica：優(yōu)化結(jié)果x2=x5=x8=1，預(yù)期銷售量105,000copies.3）由于上述結(jié)果均為出版修訂本教材，長期看對(duì)公司發(fā)展不利，故可增加約束至少出版1本新書。45課本出版計(jì)算結(jié)果現(xiàn)狀優(yōu)化結(jié)果x2=x5=x646下次課內(nèi)容P17整數(shù)規(guī)劃作業(yè)4.44.6建模，并用MS6.0計(jì)算第九章

網(wǎng)絡(luò)模型哥尼斯堡七橋問題最小樹問題最短路問題最大流問題46下次課內(nèi)容P17整數(shù)規(guī)劃作業(yè)第九章網(wǎng)絡(luò)模型471緒論—Introduction2線性規(guī)劃—LinearProgramming3運(yùn)輸與指派問題—TransportationModels4整數(shù)規(guī)劃—IntegerProgramming5網(wǎng)絡(luò)模型—NetworkModels6項(xiàng)目計(jì)劃—PERT&CPM7排隊(duì)論—QueueingModels8

模擬—Simulation9決策分析—DecisionTheory10多目標(biāo)決策—Multi-objectiveDecision《管理數(shù)量方法》目錄11緒論—Introduc48授課內(nèi)容Case:分銷系統(tǒng)設(shè)計(jì)（P192）整數(shù)規(guī)劃圖解法及分枝定界法MS6.0軟件求解整數(shù)規(guī)劃應(yīng)用舉例銀行選址P209（講義：消防站選址）案例討論：課本出版P2222授課內(nèi)容Case:分銷系統(tǒng)設(shè)計(jì)（P192）49Questions整數(shù)規(guī)劃IP與線性規(guī)劃LP有何不同？整數(shù)規(guī)劃的分類？整數(shù)規(guī)劃的求解方法？分枝定界法的基本思路？分枝問題解可能出現(xiàn)的情況？3Questions整數(shù)規(guī)劃IP與線性規(guī)劃LP有何不同？整50Q1：整數(shù)規(guī)劃與線性規(guī)劃LP區(qū)別：

（要求所有xj的解為整數(shù)，或者要求部分xj的解為整數(shù)）1）一般整數(shù)規(guī)劃。要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃；或者要求部分xj的解為整數(shù)，稱為混合整數(shù)規(guī)劃。2）0-1整數(shù)規(guī)劃。它規(guī)定整數(shù)變量只能有兩個(gè)值，0或1。4Q1：整數(shù)規(guī)劃與線性規(guī)劃LP區(qū)別：

（要求所有xj的51Q2：整數(shù)規(guī)劃的解法圖解法窮舉法分枝定界法(BranchandMethod)割平面法5Q2：整數(shù)規(guī)劃的解法圖解法52Q3：分枝定界法的基本思路maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X為整數(shù)

(B)(B)為(A)的線性規(guī)劃松弛問題。6Q3：分枝定界法的基本思路maxZ=CX(A)maxZ53(C)(D)(B)Xj

i+1(B)Xj

iX*最優(yōu)解Xj*i+1i(C)(D)X*最優(yōu)解為非整數(shù)解，則對(duì)(B)每次分兩枝,每枝多一個(gè)約束條件7(C)(D)(B)(B)X*最優(yōu)解Xj*i+1i(C)(D54Q4：分枝問題解可能出現(xiàn)的情況如何回答？8Q4：分枝問題解可能出現(xiàn)的情況如何回答？55表分枝問題解可能出現(xiàn)的情況情況2,4,5

找到最優(yōu)解情況3

在縮減的域上繼續(xù)分枝定界法情況6問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分枝的整數(shù)解進(jìn)行比較，結(jié)論如情況4。結(jié)果9表分枝問題解可能出現(xiàn)的情況情況2,4,5561緒論—Introduction2線性規(guī)劃—LinearProgramming3運(yùn)輸問題

—TransportationModels4整數(shù)規(guī)劃—IntegerProgramming5網(wǎng)絡(luò)模型—NetworkModels6項(xiàng)目計(jì)劃—PERT&CPM7排隊(duì)論—QueueingModels8

模擬—Simulation9決策分析—DecisionTheory10多目標(biāo)決策—Multi-objectiveDecision《管理數(shù)量方法》目錄101緒論—Introdu57授課內(nèi)容整數(shù)規(guī)劃圖解法及分枝定界法MS6.0軟件求解整數(shù)規(guī)劃應(yīng)用舉例銀行選址P230（講義：消防站選址）案例討論：課本出版P24211授課內(nèi)容整數(shù)規(guī)劃58整數(shù)規(guī)劃舉例產(chǎn)品桌

椅備用資源木工1230油漆工3260搬運(yùn)工0224利潤4050例1、家具廠生產(chǎn)計(jì)劃問題桌，椅各生產(chǎn)多少,可獲最大利潤?12整數(shù)規(guī)劃舉例例1、家具廠生產(chǎn)計(jì)劃問題桌，椅各生產(chǎn)多少,59圖解法求最優(yōu)解解：X*=(15,7.5)Zmax=975該解是否符合實(shí)際要求？0203010102030X1X2DABCDABCC點(diǎn)：X1+2X2=30

3X1+2X2=60如何求解整數(shù)解？13圖解法求最優(yōu)解解：X*=(15,7.5)020301604整數(shù)規(guī)劃整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃144整數(shù)規(guī)劃整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃61整數(shù)規(guī)劃簡介要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃要求部分xj的解為整數(shù)，稱為混合整數(shù)規(guī)劃對(duì)應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問題的最優(yōu)解15整數(shù)規(guī)劃簡介要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃62整數(shù)規(guī)劃的解法圖解法窮舉法分枝定界法割平面法16整數(shù)規(guī)劃的解法圖解法63§4.1整數(shù)規(guī)劃的窮舉法窮舉法：可以通過計(jì)算和比較所有整數(shù)格點(diǎn)的值來求解。17§4.1整數(shù)規(guī)劃的窮舉法窮舉法：可以通過計(jì)算和比較所有整64例：maxZ=40x1+60x2+70x3+160x416x1+35x2+45x3+85x4

100x1,x2,x3,x4為0,1X1=1X1=0111010101X2=0X3=00解法1：枚舉法：x1=1,x2=1,x3=1,x4=0

。枚舉法？18例：maxZ=40x1+60x2+70x3+1652100個(gè)整數(shù)解，用最現(xiàn)代化的計(jì)算機(jī)也要算上幾億億年。窮舉法是無法用來求解實(shí)際問題。最優(yōu)解經(jīng)過四舍五入的方法是否可以？若該整數(shù)規(guī)劃問題有100個(gè)0－1整數(shù)變量，那么整數(shù)解有多少個(gè)？如何回答？192100個(gè)整數(shù)解，用最現(xiàn)代化的計(jì)算機(jī)也要算上幾億億年。若66§4.2分枝定界法的基本思路maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X為整數(shù)

(B)(B)為(A)的線性規(guī)劃松弛問題。20§4.2分枝定界法的基本思路maxZ=CX(A)ma67(C)(D)(B)Xj

i+1(B)Xj

iX*最優(yōu)解Xj*i+1i(C)(D)X*最優(yōu)解為非整數(shù)解，則對(duì)(B)每次分兩枝,每枝多一個(gè)約束條件21(C)(D)(B)(B)X*最優(yōu)解Xj*i+1i(C)(68分枝定界法的步驟思路:暫不考慮整數(shù)條件,用單純形法求解,得整數(shù)解,停;不是整數(shù)解,分枝。分枝:每次分兩枝,每枝多一個(gè)約束條件，（每個(gè)節(jié)點(diǎn)代表一個(gè)子問題）。停止分枝條件:1）子問題無可行解.2）子問題得整數(shù)解.3）子問題的目標(biāo)值比下界差。maxZ定界:1）初始整數(shù)規(guī)劃的松弛問題的最優(yōu)值是上界.2）子問題得整數(shù)解的最優(yōu)值是一個(gè)下界。22分枝定界法的步驟思路:暫不考慮整數(shù)條件,用單純形法求解69分枝問題解可能出現(xiàn)的情況如何回答？23分枝問題解可能出現(xiàn)的情況如何回答？70表分枝問題解可能出現(xiàn)的情況情況2,4,5

找到最優(yōu)解情況3

在縮減的域上繼續(xù)分枝定界法情況6問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分枝的整數(shù)解進(jìn)行比較，結(jié)論如情況4。結(jié)果24表分枝問題解可能出現(xiàn)的情況情況2,4,571舉例例：maxZ=x1+x26x1+

2x2175x1+

9x2

44x1,x2為整數(shù)如何回答？25舉例例：maxZ=x1+x2如何回答？72

松弛問題Z0=5.545X1=1.477X2=4.068子問題1Z1=5.333X1=1X2=4.333子問題2Z2=4.5X1=2X2=2.5子問題3Z3=5X1=1X2=4子問題4無可行解x1≥2x1≤1x2≤4x2≥5分枝定界法求解過程∴最優(yōu)整數(shù)解X1=1X2=4最優(yōu)目標(biāo)函數(shù)值Z=526松弛問題子問題1子問題2子問題3子問題4x1≥2x1≤730-1Programming(BinaryIP)

0-1整數(shù)規(guī)劃決策變量取值0或1，稱0-1或二進(jìn)制變量。0-1變量可數(shù)量化地描述諸如開與關(guān)、取與棄、有與無等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及互斥的約束條件0-1規(guī)劃應(yīng)用：如工廠選址、生產(chǎn)計(jì)劃安排、旅行購物、背包問題、人員安排、代碼選取、線路設(shè)計(jì)、可靠性等270-1Programming(BinaryIP)

74§4.3整數(shù)規(guī)劃建模應(yīng)用舉例：

0-1變量的作用1.Xj=3.從N個(gè)方案中最多選中3個(gè):2.從N個(gè)方案中必須選中一個(gè):28§4.3整數(shù)規(guī)劃建模應(yīng)用舉例：

0-1變量的作用1.75特殊約束的處理1.只有方案J選中時(shí)，方案I才可能被選中:如何表示？xi≤xj2.方案I與方案J是否選中是同時(shí)的:

xi=xj3.矛盾約束:f(x)-5≥0與f(x)≤0→-f(x)+5≤M(1-y)與f(x)≤MyM表示很大的數(shù)，y為0－1變量。如何回答？29特殊約束的處理1.只有方案J選中時(shí)，方案I才可能被選中76特殊約束的處理4.多個(gè)選一:fi(x)≤0,I=1,2,…,n.如何表示？

5.邏輯關(guān)系約束：若f(x)無限制,則g(x)≤0;若f(x)<0不成立,則g(x)無限制.如何表示？

fi(x)≤M(1-yi)I=1,2,…,n.y1+y2+…+yn=1→f(x)≥-M(1-y),g(x)≤My，M表示很大的數(shù)，y為0－1變量。30特殊約束的處理4.多個(gè)選一:fi(x)≤0,I=1770-1整數(shù)規(guī)劃模型及其應(yīng)用8.3.1資金預(yù)算（投資決策）問題8.3.2固定成本問題8.3.3配送系統(tǒng)設(shè)計(jì)8.3.4銀行選址（覆蓋問題）8.3.5產(chǎn)品設(shè)計(jì)與市場(chǎng)份額優(yōu)化310-1整數(shù)規(guī)劃模型及其應(yīng)用8.3.1資金預(yù)算（投資決策78整數(shù)規(guī)劃應(yīng)用舉例例華美公司有5個(gè)項(xiàng)目被列入投資計(jì)劃，各項(xiàng)目的投資額和期望的投資收益見下表：該公司只有600萬元資金可用于投資，由于技術(shù)上的原因，投資受到以下約束：1.在項(xiàng)目1、2和3中必須（只）有一項(xiàng)被選中；2.項(xiàng)目3和4只能選中一項(xiàng)；（必須選一項(xiàng)）3.項(xiàng)目5被選中的前提是項(xiàng)目1必須被選中。如何在上述條件下選擇一個(gè)最好的投資方案，使投資收益最大。32整數(shù)規(guī)劃應(yīng)用舉例例華美公司有5個(gè)項(xiàng)目被列入投資計(jì)劃，各79

項(xiàng)目投資收益表

項(xiàng)目投資額（萬元）投資收益（萬元）

121015023002103100604130805260180Xj=1表項(xiàng)目j選中,Xj=0表項(xiàng)目j未選中.j=1,2,3,4,5.約束條件如何表示？33項(xiàng)目投資收益表項(xiàng)目投資額（萬元）80計(jì)算過程解:Xj=1表項(xiàng)目j選中,Xj=0表項(xiàng)目j未選中.j=1,2,3,4,5.Z表示總收益.則模型如下:

MaxZ=150X1+210X2+60X3+80X4+180X5s.t:210X1+300X2+100X3+130X4+260X5

≤600X1+X2+X3=1X3+X4=1X5

≤X1Xj=0或1;j=1,2,3,4,5.34計(jì)算過程解:Xj=1表項(xiàng)目j選中,Xj=0表項(xiàng)目j81

例解決某市消防站的布點(diǎn)問題。該城市共有6個(gè)區(qū)，每個(gè)都可以建消防站。市政府希望建設(shè)的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時(shí)，消防車要在15分鐘內(nèi)趕到現(xiàn)場(chǎng)。據(jù)實(shí)地測(cè)定，各區(qū)之間消防車行駛的時(shí)間見下表：請(qǐng)幫助該市制定一個(gè)最節(jié)省的計(jì)劃。

消防車在各區(qū)行駛距離表

地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6

010

16282720

100243217

1016240122721283212015

252717271501420

10

2125140Howtosolve？35例解決某市消防站的布點(diǎn)問題。該城市共有6個(gè)區(qū)，每個(gè)82計(jì)算過程解:Xj=1表地區(qū)設(shè)消防站,Xj=0表地區(qū)不設(shè)消防站.Z=消防站總數(shù),則模型如下:

MinZ=X1+X2+X3+X4+X5+X6s.t.X1+X2≥1X1+X2+X6≥1X3+X4≥1X3+X4+X5≥1X4+X5+X6≥1X2+X5+X6≥1Xj=0或1；j=1,2,3,4,5,6.36計(jì)算過程解:Xj=1表地區(qū)設(shè)消防站,Xj=0表地區(qū)不83銀行選址P209俄亥俄信托公司（OhioTrustCompany）希望在俄亥俄西北部20個(gè)縣進(jìn)行選址，該地區(qū)還沒有首席業(yè)務(wù)處（PrincipalPlaceofbusinessPPB）。根據(jù)俄亥俄州的銀行法，如果金融企業(yè)在任何一個(gè)縣設(shè)立PPB，就可以在該縣及其比鄰的縣設(shè)立分支機(jī)構(gòu)。俄亥俄信托公司想知道在那些縣設(shè)立PPB會(huì)使其數(shù)量最少？37銀行選址P209俄亥俄信托公司（OhioTrustC84表俄亥俄信托公司考慮的各縣鄰居考慮的縣鄰縣的數(shù)字代號(hào)考慮的縣鄰縣