1、.,1,第3章 運(yùn)輸問題,.,2,3.1 運(yùn)輸問題的典例和數(shù)學(xué)模型,3.2 運(yùn)輸問題的求解方法：表上作業(yè)法,3.3 幾類特殊的運(yùn)輸問題,3.4 運(yùn)輸問題的應(yīng)用,.,3,運(yùn)輸問題： 根據(jù)已有的交通網(wǎng)，如何制定運(yùn)輸方案，使得這些物資被運(yùn)送到各個(gè)銷售地，并保證某個(gè)指標(biāo)最優(yōu)(例如總運(yùn)費(fèi)最小)。,.,4,3.1 運(yùn)輸問題的典例和數(shù)學(xué)模型,一、典例 某食品公司經(jīng)營糖果業(yè)務(wù)，公司下設(shè)三個(gè)工廠A1、A2、A3，四個(gè)銷售門市部B1、B2、B3、B4。已知每天各自的生產(chǎn)量、銷售量及調(diào)運(yùn)時(shí)的單位運(yùn)輸費(fèi)用情況。問：如何調(diào)運(yùn)可使總費(fèi)用最??？,生產(chǎn)量：A17噸， A2 4噸， A3 9噸 銷售量：B1 3噸，B2 6噸，

2、B3 5噸，B4 6噸,產(chǎn)地,單位運(yùn)價(jià),銷地,B1 B2 B3 B4,A1,A2,A3,3 11 3 10,1 9 2 8,7 4 10 5,.,5,調(diào)運(yùn)示意圖,A1,A2,A3,B1,B2,B3,B4,7噸,4噸,9噸,3噸,6噸,5噸,6噸,x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,產(chǎn)地,銷地,.,6,二、建立模型,設(shè) xij第i產(chǎn)地到第j銷地之間的調(diào)運(yùn)量，則有,Min z = cij xij,3,4,i=1,j=1,x11+x12+x13+x14=7,x11+x21+x31=3,xij0,(i=1,2,3；j=1,2,4),產(chǎn)量限制,

3、銷量限制,x21+x22+x23+x24=4,x31+x32+x33+x34=9,x12+x22+x32=6,x13+x23+x33=5,x14+x24+x34=6,.,7,單位運(yùn)價(jià)表,產(chǎn)銷平衡表,.,8,一般模型表示 (ai=bj),.,9,三、模型的特點(diǎn),1.變量數(shù)：mn個(gè) 2.約束方程數(shù)：m+n個(gè) 最大獨(dú)立方程數(shù)：m+n-1 3.系數(shù)列向量結(jié)構(gòu)：,Pij=,第i個(gè)分量 第m+j個(gè)分量,0 1 1 0,.,10,x11 x12 x1n x21 x22 x2n , xm1 xm2 xmn,1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1

4、1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1,i=1 i=2 i=m j=1 j=2 j=n, , , , , , ,.,11,關(guān)于運(yùn)輸模型的幾個(gè)結(jié)論： (1)設(shè)有m個(gè)產(chǎn)地，n個(gè)銷地且產(chǎn)銷平衡的運(yùn)輸問題，則基變量數(shù)是m+n-1； (2)若變量組B包含有閉回路，則B中變量對應(yīng)的列向量線性相關(guān)； (3)m+n-1個(gè)變量組構(gòu)成基變量的充要條件是它不包含任何閉回路。,.,12,初始基可行解,新的基可行解,最優(yōu)否？,STOP,Y,N,3.2 運(yùn)輸問題的求解方法：表上作業(yè)法,單純形法求解思路,.,13,表上作業(yè)法步驟: 初始運(yùn)輸方案最優(yōu)性檢

5、驗(yàn)改進(jìn)運(yùn)輸方案 一、初始方案的確定 1.最小元素法 2.Vogel法 二、最優(yōu)性檢驗(yàn) 1.閉回路法 2.位勢法 三、方案改進(jìn)方法 在閉回路內(nèi)改進(jìn)。,.,14,3,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)量,銷量,3 11 3 10 1 9 2 8 7 4 10 5,6,3,4,1,3,3 6 5 6,7 4 9,單位運(yùn)價(jià)表,產(chǎn)銷平衡表,最小元素法,.,15,例,產(chǎn)地,銷地,A1 A2,B1 B2,15 15,10 20,產(chǎn)量,銷量,2,8,5,1,最小元素法：z=810+25+115=105,Vogel法：z=105+152

6、+51=85,Vogel法,.,16,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,7 4 9,產(chǎn)量,銷量,3 6 5 6,6,3,5,2,1,3,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,行兩最小元素之差,列兩最小元素之差,3 11 3 10 1 9 2 8 7 4 10 5,0 1 1,2 5 1 3,0 1 2,2 - 1 3,0 1 -,2 - 1 2,7 6 -,- - 1 2,Vogel法,產(chǎn)銷平衡表,.,17,針對最小元素法和vogel法，需要說明的幾點(diǎn)：,(1) 任何運(yùn)輸問題都有基可行解，且有最優(yōu)解；,(2) 如果供應(yīng)量和需求量都是整數(shù)，那么一定可以得到整數(shù)

7、形式的最優(yōu)解;,(4) 若在中途同時(shí)有行列要求得到滿足，將同時(shí)劃掉一行一列，最后數(shù)字格個(gè)數(shù)將少于m+n-1個(gè)。為使數(shù)字格的個(gè)數(shù)恰好等于m+n-1，在同時(shí)劃去的行列中，任選（或選其價(jià) 格系數(shù)最小元素對應(yīng)的）空格，填上數(shù)字0作為特殊的數(shù)字格（即基變量）。,(3) 用最小元素法和vogel法得到的是運(yùn)輸問題的一個(gè)基可行解，數(shù)字格對應(yīng)基變量；,.,18,例,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)量,銷量,2 7 3 11 8 4 6 9 4 3 10 5,20,30 25 10 15,20 10 50,單位運(yùn)價(jià)表,產(chǎn)銷平衡表,10

8、,25,15,10,0,.,19,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)量,銷量,3 11 3 10 1 9 2 8 7 4 10 5,6,3,4,3,1,3,3 6 5 6,7 4 9,3 6 5 6,7 4 9,產(chǎn)量,銷量,3,6,3,5,2,1,(1),(2),(1),(-1),(10),(12),z=c11-c13+c23-c21=1=11,z=c12-c14+c34-c32=2=12,(0),(2),(2),(9),(1),(12),單位運(yùn)價(jià)表,產(chǎn)銷平衡表,閉

9、 回 路 法,.,20,注: 只要求的基變量是正確的，并且數(shù)目為m+n-1個(gè)，那么每個(gè)非基變量的閉回路存在且唯一，因此，檢驗(yàn)數(shù)唯一。,.,21,產(chǎn)地,銷地,A1 A2 A3,B1 B1 B3 B4,位勢法,4,1,3,2.計(jì)算行位勢和列位勢； 令v1=1，則依cij=ui+vj 計(jì)算各 ui和vj,3.計(jì)算空格處位勢； ij=ui+vj,行位勢ui,列位勢vj,1,1,0,-4,2,8,9,4.計(jì)算空格處檢驗(yàn)數(shù)： ij=cij- ij,1.數(shù)字格處上添上對應(yīng)的運(yùn)價(jià)；,銷地,A1 A2 A3,B1 B1 B3 B4,3 11 3 10 1 9 2 8 7 4 10 5,產(chǎn)地,單位運(yùn)價(jià)表,位勢表:

10、,2,10,5,(2),(9),(8),(9),(-3),(-2),.,22,產(chǎn)地,銷地,A1 A2 A3,B1 B1 B3 B4,7 4 9,產(chǎn)量,銷量,3 6 5 6,6,3,4,3,(-1),3,(1),(2),(1),(10),1,(12),檢驗(yàn)數(shù)表,注：位勢法求檢驗(yàn)數(shù)的依據(jù)是對偶理論。,.,23,注: 對于同一組基變量，所求的檢驗(yàn)數(shù)是唯一的； (2) 在最優(yōu)解表中，有非基變量（即空格)的檢驗(yàn)數(shù)為0，根據(jù)線性規(guī)劃單純形法原理知，應(yīng)有無窮多最優(yōu)解，即有多解。運(yùn)輸問題表上作業(yè)法求多解的方法：任選一檢驗(yàn)系數(shù)為0的空格入基，進(jìn)行方案改進(jìn)，可得新的最優(yōu)解； (3) 在進(jìn)行調(diào)運(yùn)方案改進(jìn)時(shí)，若沿閉合

11、回路出現(xiàn)多個(gè)可作為調(diào)出變量的數(shù)字格（即閉回路上的數(shù)字格最小值有多個(gè)），此時(shí)，任選一個(gè)為調(diào)出變量，其余的填0，保證調(diào)整后的調(diào)運(yùn)方案中仍有m+n-1個(gè)數(shù)字格。,.,24,5,例：,產(chǎn)地,銷地,A1 A2 A3,B1 B1 B3 B4,7 4 9,產(chǎn)量,銷量,3 6 5 6,6,3,5,2,1,3,(0),(2),(2),(9),(1),(12),產(chǎn)地,銷地,A1 A2 A3,B1 B1 B3 B4,7 4 9,產(chǎn)量,銷量,3 6 5 6,6,3,3,1,2,.,25,4,(1),產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)量,銷量,6,3,2,2,3,3 6 6 5,6 5 9,(2)

12、,(1),(-1),(10),(12),例：,6,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)量,銷量,6,3,0,3,3 6 6 5,6 5 9,2,.,26,練習(xí),產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)量,銷量,10 1 20 11 12 7 9 20 2 14 16 18,5 15 15 10,15 25 5,單位運(yùn)價(jià)表,產(chǎn)銷平衡表,.,27,最小元素法,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)量,銷量,10 1 20 11 12 7

13、9 20 2 14 16 18,5 15 15 10,15 25 5,單位運(yùn)價(jià)表,產(chǎn)銷平衡表,15,5,15,10,0,0,.,28,Vogel法,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)地,銷地,A1 A2 A3,B1 B2 B3 B4,產(chǎn)量,銷量,10 1 20 11 12 7 9 20 2 14 16 18,5 15 15 10,15 25 5,單位運(yùn)價(jià)表,產(chǎn)銷平衡表,8 6 7 7,9 2 12,5,- 6 11 9,10 2 -,15,- 6 - 9,10 13 -,10,5,10,0,.,29,注:表上作業(yè)法適用于下列情形： cij0； min z； 產(chǎn)銷平衡。,表

14、上作業(yè)法步驟,.,30,3.3 幾類特殊的運(yùn)輸問題,一、產(chǎn)銷不平衡問題,1產(chǎn)銷,2銷產(chǎn),二、需求量不確定,三、中轉(zhuǎn)問題,.,31,Min z= cij xij,n,i=1,j=1,m,一、產(chǎn)銷不平衡問題,1產(chǎn)銷(aibj),Min z= cijxij+0xi,n+1,n,i=1,j=1,m,i=1,m,.,32,產(chǎn)地,銷地,A1 A2 Am,B1 B2 Bn,C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn,Bn+1, ,產(chǎn)銷問題單位運(yùn)價(jià)表,銷量,產(chǎn)量,b1 b2 bn,a1 a2 am,aibj,.,33,Min z= cij xij,n,i=1,j=1,m,2銷產(chǎn)(b

15、jai),Min z= cijxij +0xm+1,j,n,i=1,j=1,m,j=1,n,.,34,產(chǎn)地,銷地,A1 A2 Am,B1 B2 Bn,C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn,Am+1,銷產(chǎn)問題單位運(yùn)價(jià)表,0 0 0,銷量,產(chǎn)量,b1 b2 bn,a1 a2 am,bjai,.,35,例：有A、B、C三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)、的農(nóng)用化肥，三個(gè)工廠每年各自的產(chǎn)量為A-50萬噸，B-60萬噸，C-50萬噸。四個(gè)地區(qū)的需求量分別是地區(qū)最高50萬噸，最低30萬噸，地區(qū)為70萬噸，地區(qū)為30萬噸以下，地區(qū)不低于10萬噸。問：如何調(diào)運(yùn)，可使總的調(diào)運(yùn)費(fèi)用最??？單位

16、調(diào)運(yùn)費(fèi)用如下表所示。,產(chǎn)地,銷地,A, ,產(chǎn)量,最低需求,16 13 22 17 14 13 19 15 19 20 23 ,單位運(yùn)價(jià)表,50 60 50,30 70 0 10,單位：萬元/萬噸,設(shè) xij-第i工廠調(diào)至第j需求地區(qū)的化肥數(shù)量,二、需求量不確定,B,C,最高需求,50 70 30 不限,.,36,A B C, ,16 16 13 22 17 17,14 14 13 19 15 15,19 19 20 23 M M,M 0 M 0 M 0,供應(yīng),需求,產(chǎn)量,銷 量,50 60 50,30 20 70 30 10 50,產(chǎn)銷平衡表,D,50,注：M表示無窮大正數(shù)，最低需求不能由D生

17、產(chǎn)地提供。,.,37,最優(yōu)方案：,.,38,練習(xí),產(chǎn)地,銷地,A, ,最高發(fā)量,4 6 7 - 7 8,單位運(yùn)價(jià)表,60 40 400,B,C,銷量,70 80 50,D,最低發(fā)量,80 40 不限50,5 4 6 4 5 -,.,39,三、中轉(zhuǎn)問題,在前面的例題中，若既可以從Ai運(yùn)到Bj，也可以經(jīng)過中間站T1、T2、T3、T4或者Ai、Bj轉(zhuǎn)運(yùn)，稱為擴(kuò)大的運(yùn)輸問題。,幾點(diǎn)說明： 1.所有的產(chǎn)地、銷地、中間站均視作產(chǎn)地、銷地； 2.不能出現(xiàn)循環(huán)倒運(yùn)現(xiàn)象，允許自身往自身最多調(diào)運(yùn)一次，運(yùn)價(jià)為cii=0； 3.轉(zhuǎn)運(yùn)量可定位總的產(chǎn)量之和； 4.實(shí)際產(chǎn)地產(chǎn)量為轉(zhuǎn)運(yùn)量與該產(chǎn)地實(shí)際產(chǎn)量之和，實(shí)際銷地銷量為轉(zhuǎn)

18、運(yùn)量與實(shí)際銷量之和。,.,40,A1 A2 A3,T1 T2 T3 T4,B1 B2 B3 B4,A1 A2 A3,T1 T2 T3 T4,B1 B2 B3 B4,0 1 3 1 0 - 3 - 0,2 1 4 3 3 5 - 2 1 - 2 3,3 11 3 10 1 9 2 8 7 4 10 5,2 3 1 1 5 - 4 - 2 3 2 3,3 1 7 11 9 4 3 2 10 10 8 5,0 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0,2 8 4 6 4 5 2 7 1 8 2 4 1 - 2 6,2 4 1 1 8 5 8 - 4 2 2 2 6 7 4 6,0

19、1 4 2 1 0 2 1 4 2 0 3 2 1 3 0,產(chǎn),銷,產(chǎn)量,銷量,27 24 29,20 20 20 20,20 20 20 20,20 20 20,20 20 20 20,23 26 25 26,產(chǎn)銷平衡表,.,41,3.4 運(yùn)輸問題的應(yīng)用,.,42,例：某工廠按合同規(guī)定必須于當(dāng)年的每個(gè)季度末分別提供10、15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表示。又如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個(gè)季度需要存儲維護(hù)費(fèi)用0.15萬元。要求在完成合同的情況下，做出使全年生產(chǎn)費(fèi)用最小的決策。,季度,生產(chǎn)能力,(臺),單位成本,(萬元/臺),253

20、53010,10.811.111.011.3,.,43,模型：設(shè)xij第i季度生產(chǎn)，用于第j季度交貨的數(shù)量。,obj. min z= cij xij,i=1j=1,4 4,x11+x12+x13+x1425,x22+x23+x2435,x33+x3430,x4410,x11 =10,x12+x22 =15,x13+x23+x33 =25,x14+x24+x34+x44=20,xij 0 ,(i=1,4;j=1,4),供應(yīng)：,需求：,.,44,單位費(fèi)用表：, ,10.8 10.95 11.10 11.25,M 11.10 11.25 11.40,M M 11.00 11.15,M M M 11.30,單位：萬元,供應(yīng),需求,.,45,例: 某餐館承辦宴會，每晚連續(xù)舉行，共舉行五次。宴會上需用特殊的餐巾，根據(jù)參加的人數(shù)，預(yù)計(jì)每晚的需要量為：第一天1000條，第二天700條，第三天800條，第四天1200條，第五天1500條，五天之后，所有的餐巾作廢。宴會中用過的餐巾經(jīng)過洗滌處理后可以重復(fù)使用，這樣可以降低使用成本。已知每條新餐巾需要1元的費(fèi)用，送洗時(shí)可選擇兩種方式：快洗僅需要一天時(shí)間，每條洗滌費(fèi)用為0.2元，慢洗需要兩天時(shí)間，每條洗滌費(fèi)用0.1元。問：如何安