第12講目錄轉(zhuǎn)運(yùn)問(wèn)題(補(bǔ)充證明)CH4整數(shù)規(guī)劃§4.1整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型及解的特點(diǎn)§4.2分支定界法

（第二章習(xí)題講解）§4.30-1整數(shù)規(guī)劃§4.4指派問(wèn)題§4.5應(yīng)用舉例“轉(zhuǎn)運(yùn)問(wèn)題”證明例2、某公司有A1、A2、A3三個(gè)分廠生產(chǎn)某種物資，分別供應(yīng)B1、B2、B3、B4四個(gè)地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表：

試求總費(fèi)用為最少的調(diào)運(yùn)方案。假設(shè)：

1.每個(gè)分廠的物資不一定直接發(fā)運(yùn)到銷地，可以從其中幾個(gè)產(chǎn)地集中一起運(yùn)；

2.運(yùn)往各銷地的物資可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其他銷地；

3.除產(chǎn)銷地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。運(yùn)價(jià)如下表：解：把此轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)化為一般運(yùn)輸問(wèn)題：

1、把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時(shí)看作產(chǎn)地和銷地；

2、運(yùn)輸表中不可能方案的運(yùn)費(fèi)取作M，自身對(duì)自身的運(yùn)費(fèi)為0；

3、Ai：產(chǎn)量為20+原產(chǎn)量，銷量為20；Ti

：產(chǎn)量、銷量均為20；Bi：產(chǎn)量為20，銷量為20+原銷量，其中20為各點(diǎn)可能變化的最大流量；

4、對(duì)于最優(yōu)方案，其中xii

為自身對(duì)自身的運(yùn)量，實(shí)際上不進(jìn)行運(yùn)作。擴(kuò)大的運(yùn)輸問(wèn)題產(chǎn)銷平衡與運(yùn)價(jià)表：§4.1整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型及解的特點(diǎn)

整數(shù)線性規(guī)劃問(wèn)題的一般形式例1.某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表所示。甲種貨物至多托運(yùn)4件，問(wèn)兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大。解：設(shè)x1、

x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型目標(biāo)函數(shù)：Maxz=2x1+3x2

約束條件：

195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0為整數(shù)。貨物每件體積（立方英尺）每件重量（百千克）每件利潤(rùn)（百元）甲乙19527344023托運(yùn)限制1365140

整數(shù)線性規(guī)劃問(wèn)題的分類全整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃0-1整數(shù)線性規(guī)劃整數(shù)規(guī)劃與其松弛問(wèn)題當(dāng)放棄整數(shù)約束時(shí)得到的線性規(guī)劃稱為整數(shù)規(guī)劃的松弛問(wèn)題。整數(shù)規(guī)劃的可行域是松弛問(wèn)題的可行域，反之不成立。§4.2分支定界法混合整數(shù)規(guī)劃的求解---分枝定界方法分枝：當(dāng)不符合整數(shù)要求時(shí)，構(gòu)造兩個(gè)約束條件：加入松弛問(wèn)題分別形成兩個(gè)子問(wèn)題（分枝）定界：當(dāng)子問(wèn)題獲得整數(shù)規(guī)劃的一個(gè)可行解，則它的目標(biāo)函數(shù)值就構(gòu)成一個(gè)界限例1132X254X1

231S解S得：29/6132X254X1

231S2對(duì)S分枝：構(gòu)造約束：和形成分枝問(wèn)題S1和S2，得解B和CS1SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9132X254X1

231S2對(duì)S1分枝：構(gòu)造約束：和形成分枝問(wèn)題S11和S12，得解DS12S11無(wú)可行解SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無(wú)可行解S12D:x1=33/14,x2=2Z=61/14132X254X1

231S2對(duì)S12分枝：構(gòu)造約束：和形成分枝問(wèn)題S121和S122，得解E和FS121S122SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無(wú)可行解S12D:x1=33/14,x2=2Z=61/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=4例2用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20整數(shù)用單純形法可解得相應(yīng)的松馳問(wèn)題的最優(yōu)解（6/5，21/10）Z=111/10為各分枝的上界。012344321x1x2分枝：X11,x12P1P2兩個(gè)子問(wèn)題：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20，x1

1

，整數(shù)用單純形法可解得相應(yīng)的（P1）的最優(yōu)解（1，9/4）Z=43/4（P2）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20，x1

2

，整數(shù)用單純形法可解得相應(yīng)的（P2）的最優(yōu)解（2，1/2）Z=19/2012344321x1x2再對(duì)（P1）分枝：X11（P3）x22（P4）x23P1P2P3P4（P1）兩個(gè)子問(wèn)題：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x22整數(shù)用單純形法可解得相應(yīng)的（P3）的最優(yōu)解（1，2）Z=10（P1）兩個(gè)子問(wèn)題：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x23整數(shù)用單純形法可解得相應(yīng)的（P4）的最優(yōu)解（0，3）Z=9X12X2

2X11X23P1:(1,9/4)Z=43/4P4:(0,3)Z=9P2:(2,1/2)Z=19/2P3:(1,2)Z=10P:(6/5,21/10)Z=111/10原問(wèn)題的最優(yōu)解（1，2）Z=10第二章習(xí)題講解（由助教完成）§4.30-1整數(shù)規(guī)劃

1、0-1整數(shù)規(guī)劃變量只能取0或1的整數(shù)線性規(guī)劃2、0-1規(guī)劃的應(yīng)用例1項(xiàng)目投資預(yù)算模型變量假設(shè):模型:例2：一登山隊(duì)員做登山準(zhǔn)備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機(jī)和通訊設(shè)備，每種物品的重要性系數(shù)和重量如下：假定登山隊(duì)員可攜帶最大重量為25公斤。序號(hào)1234567物品食品氧氣冰鎬繩索帳篷相機(jī)設(shè)備重量55261224重要系數(shù)201518148410解：如果令xi=1表示登山隊(duì)員攜帶物品i，xi=0表示登山隊(duì)員不攜帶物品i，則問(wèn)題表示成0-1規(guī)劃:MaxZ=20x1+15x2+18x3+14x4

+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x725xi=1或xi=0i=1,2,….7背包問(wèn)題(KnapsackProblem)一個(gè)旅行者,為了準(zhǔn)備旅行的必須用品,要在背包內(nèi)裝一些最有用的東西,但有個(gè)限制,最多只能裝b公斤的物品,而每件物品只能整個(gè)攜帶,這樣旅行者給每件物品規(guī)定了一個(gè)“價(jià)值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其價(jià)值為cj.問(wèn)題變成:在攜帶的物品總重量不超過(guò)b公斤條件下,攜帶哪些物品,可使總價(jià)值最大?解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，則問(wèn)題表示成0-1規(guī)劃:MaxZ=Σcjxjs.t.Σajxjb

xj=0或1例3工廠-銷售點(diǎn)配置問(wèn)題生產(chǎn)廠顧客需求銷售點(diǎn)45DCBA7IIIII213I工廠-銷售點(diǎn)配置問(wèn)題-問(wèn)題描述問(wèn)題:為使經(jīng)營(yíng)成本最低,應(yīng)開設(shè)那些工廠及銷售點(diǎn)?工廠-銷售點(diǎn)配置問(wèn)題-模型參數(shù)工廠-銷售點(diǎn)配置問(wèn)題-模型