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

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

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

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

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

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

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

2、運輸表中不可能方案的運費取作M，自身對自身的運費為0；

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

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

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

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

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

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

約束條件：

195

x1+273x2≤13654

x1+40x2≤140

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

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

231S解S得：29/6132X254X1

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

231S2對S12分枝：構(gòu)造約束：和形成分枝問題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無可行解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)的松馳問題的最優(yōu)解（6/5，21/10）Z=111/10為各分枝的上界。012344321x1x2分枝：X11,x12P1P2兩個子問題：（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再對（P1）分枝：X11（P3）x22（P4）x23P1P2P3P4（P1）兩個子問題：（P3）MaxZ=4x1+3x2s.t.

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

1,x22整數(shù)用單純形法可解得相應(yīng)的（P3）的最優(yōu)解（1，2）Z=10（P1）兩個子問題：（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原問題的最優(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項目投資預(yù)算模型變量假設(shè):模型:例2：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機和通訊設(shè)備，每種物品的重要性系數(shù)和重量如下：假定登山隊員可攜帶最大重量為25公斤。序號1234567物品食品氧氣冰鎬繩索帳篷相機設(shè)備重量55261224重要系數(shù)201518148410解：如果令xi=1表示登山隊員攜帶物品i，xi=0表示登山隊員不攜帶物品i，則問題表示成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背包問題(KnapsackProblem)一個旅行者,為了準備旅行的必須用品,要在背包內(nèi)裝一些最有用的東西,但有個限制,最多只能裝b公斤的物品,而每件物品只能整個攜帶,這樣旅行者給每件物品規(guī)定了一個“價值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其價值為cj.問題變成:在攜帶的物品總重量不超過b公斤條件下,攜帶哪些物品,可使總價值最大?解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，則問題表示成0-1規(guī)劃:MaxZ=Σcjxjs.t.Σajxjb

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