運籌學(xué)課件第章運輸問題

1、第三章第三章 運輸問題運輸問題第一節(jié)第一節(jié) 運輸問題及其數(shù)學(xué)模型運輸問題及其數(shù)學(xué)模型一、運輸問題的典型形式及其數(shù)學(xué)模型例例1 1 從兩個產(chǎn)地從兩個產(chǎn)地A A1 1、A A2 2將物品運往三個銷地將物品運往三個銷地B B1 1、B B2 2、B B3 3，各產(chǎn)地產(chǎn)量、各，各產(chǎn)地產(chǎn)量、各銷地銷量和各產(chǎn)地運往各銷地每單位物品的運費如表。問：應(yīng)如何調(diào)運可銷地銷量和各產(chǎn)地運往各銷地每單位物品的運費如表。問：應(yīng)如何調(diào)運可使總運輸費用最?。渴箍傔\輸費用最?。拷饨?這是一個產(chǎn)銷平衡問題：總產(chǎn)量這是一個產(chǎn)銷平衡問題：總產(chǎn)量 = = 總銷量總銷量 = 500= 500。 設(shè)設(shè) x xijij 為從產(chǎn)地為從產(chǎn)地A

2、Ai i運往銷地運往銷地B Bj j的運輸量，得到下列單的運輸量，得到下列單 位運費和運輸量表：位運費和運輸量表： 銷地Bj產(chǎn)地AiB1B2B3產(chǎn)量aiA1 6 x11 4 x12 6 x13300A2 6 x21 5 x22 5 x23200銷量bj150150200minZ = 6x11 + 4x12+5x13+6x21 +5x22 +5x23x11 +x12+x13 = 300 x21+x22+x23 = 200 x11 +x21 = 150 x12 +x22 = 150 x13 +x23 = 200 xij 0A1AmB1B2Bna1cijA2a2ambnb2b1求最小運費的運輸方案2

3、. 典型的運輸問題： 銷地銷地產(chǎn)地產(chǎn)地B1B2Bn產(chǎn)量產(chǎn)量A1a1A2a2Amam銷量銷量b1b2bnc11c12cm1c21c22c2nc1ncmncm2 銷地銷地產(chǎn)地產(chǎn)地B1B2Bn產(chǎn)量產(chǎn)量A1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnam銷量銷量b1b2bnc11c12cm1c21c22c2nc1ncmncm2minZ = 6x11 + 4x12+5x13+6x21 +5x22 +5x23x11 +x12+x13 = 300 x21+x22+x23 = 200 x11 +x21 = 150 x12 +x22 = 150 x13 +x23 = 200 xij 0

4、3. 運輸問題的數(shù)學(xué)模型ijijijxcZ2131min31jiijaxi=1,221ijijbxj =1, 2, 3xij 0ijminjijxcZ11minnjiijax1i=1,2,mmijijbx1j =1, 2, ,nxij 0典型運輸問題的數(shù)學(xué)模型二、運輸問題數(shù)學(xué)模型的特點：1. 運輸問題一定有最優(yōu)解；2. 運輸問題約束條件的系數(shù)矩陣：x11 +x12+x13 = 300 x21+x22+x23 = 200 x11 + x21 = 150 x12 +x22 = 150 x13 +x23 = 200 xij 0 x11 x12 x13 x21 x22 x23 1 1 1 1 1 11

5、 1 1 1 1 12個3個x11 +x12+ +x1n =a1 x21+x22+ +x2n =a2 xm1+xm2+ +xmn =amx11 + x21 + xm1 =b1 x12 +x22 + xm2 =b2 x1n +x2n + xmn=bn xij 0 x11 x12 x1n x21 x22 x2n xm1 xm2 xmn 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1mn系數(shù)矩陣的特點： （1）約束條件的系數(shù)矩陣的元素只有兩個：0、1。 （2）元素 xij 對應(yīng)于每一個變量在前m個約束方程中(第i個方程中)出現(xiàn)一次，在后n個約束方程中（第m+j 個方程中）也出現(xiàn)

6、一次。 （3）產(chǎn)銷平衡問題為等式約束。 （4）產(chǎn)銷平衡問題中各產(chǎn)地產(chǎn)量之和與各銷售地點的銷量之和相等。3. 運輸問題基變量的個數(shù)： m+n-1個第二節(jié) 表上作業(yè)法一、表上作業(yè)法的基本思想和步驟：1.基本思想：同單純形法的基本思想基本可行解是否為最優(yōu)解換基結(jié)束YN2. 表上作業(yè)法的步驟（1）尋找初始基可行解； 最小元素法、西北角法、沃格爾法（2）求出非基變量檢驗數(shù)（空格檢驗數(shù)），判斷是否為最優(yōu)解；閉回路法、位勢法（3）換基改進，找到新的基可行解閉回路調(diào)整法（4 ）重復(fù)（2）（3）二、確定初始基可行解（一）最小元素法：從運價最小的格開始，在格內(nèi)的右下角標上可能的最大運輸量。若某行（列）的產(chǎn)量（銷量

7、）已滿足，則把該行（列）劃去。如此繼續(xù)，直至得到一個基本可行解。注:每次填完數(shù)，都只劃去一行或一列，但最后一次同時 劃去剩下的一行和一列。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量8141214484125210391146811求運費最小的運輸方案。例題 （P82例1）1245210391146811（一）最小元素法28 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量1412144810261068081464125210391146811 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量814121448（二

8、）西北角法4125210391146811 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量814121448（二）西北角法8868414（三）沃格爾法（三）沃格爾法伏格爾法思路：一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因而，對差額最大處，就應(yīng)當采用最小運費調(diào)運罰數(shù)=次小費用-最小費用1、在運價表中分別計算出各行、列的行罰數(shù)和列罰數(shù)，并填入該表的最右列和最下行。2、從行或列差額中選出最大者，選擇它所在行或列的最小元素。按類似于最小元素法優(yōu)先供應(yīng)，劃去相應(yīng)的行或列。3、對表中未劃去的元素重復(fù)

9、1，2步，直至所有的行和列被劃掉為止。沃格爾法基本步驟： 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行行罰罰數(shù)數(shù)A1160A2101A3221銷量銷量814121448列罰數(shù)列罰數(shù)251341252103911468110122 1 27614884212三、最優(yōu)解的判別(一)閉回路法 閉回路：從空格出發(fā)，遇到數(shù)字格可以旋轉(zhuǎn)90度，最后回到空格所構(gòu)成的回路。思路：計算空格（非基變量） 檢驗數(shù)求空格檢驗數(shù)有兩種方法4125210391146811 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A110616A28210A314822銷量銷量81412144811=4-4+3-2=1 12=12-11+6

10、-5=222=10-3+4-11+6-5=1 24=9-11+4-3=-131=8-2+3-4+11-6=10 33=11-6+11-4=12（1） 每一空格有且僅有一條閉回路；（2） 不允許由全部頂點是數(shù)字格構(gòu)成的閉回路。注：x11 +x12+ +x1n =a1 x21+x22+ +x2n =a2 xm1+xm2+ +xmn =amx11 + x21 + xm1 =b1 x12 +x22 + xm2 =b2 x1n +x2n + xmn=bn xij 0minZ = c11x11 + c12x12+ +c1nx1n + +cm1xm1 +cm2xm2 + +cmnxmn(二)對偶變量法（位勢

11、法）1.基本原理設(shè)對偶變量向量為 Y=(u1,u2, ,um, v1, v2, ,vn)對偶規(guī)劃為 njjjmiiivbuaW11maxui+vjciji=1,2,3 mj=1,2,3 n j = C j- CBB-1 Pj = Cj - Y Pj ij = C ij- CBB-1 Pij = Cij - Y Pij = Cij - (u1,u2, ,um, v1, v2, ,vn) Pij = Cij - ( ui+ vj ) 當xij 為基變量時 ij = Cij - ( ui+ vj )=0 上式共m+n-1個，而對偶變量有m+n個，因此，任選一個對偶變量為0，可求出其余所有的ui， v

12、j 。 再根據(jù)ij = Cij - ( ui+ vj )求出所有非基變量的檢驗數(shù)。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)產(chǎn)量量uiA110616 u1= A28210 u2=A314822 u3=銷量銷量814121448vjv1=v2=v3=v4=4125210391146811 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)產(chǎn)量量uiA110616 u1=0A28210 u2=-1A314822 u3=-5銷量銷量814121448vjv1=3v2=10 v3=4v4=11412521039114681111=4-(3+0) =1 12=12-(10+0)=222=10-(10-1)=1 24=9-(1

13、1-1)=-131=8-(-5+3)=10 33=11-(-5+4)=12四、解的改進閉回路調(diào)整法 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A110616A28210A314822銷量銷量8141214481324以x24為換入變量，以(A2,B4)為第一個奇數(shù)頂點，對閉回路上頂點依此編號找偶數(shù)點中最小運輸量，閉回路上奇數(shù)頂點加上此數(shù)，偶數(shù)頂點減去此數(shù) 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A110+2 6-216A28 2-2+210A314822銷量銷量814121448 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A112416A28210A314822銷量銷量81412144811=4-

14、11+9-2 =0 12=12-11+6-5=222=10-9+6-5=2 23=3-9+11-4=131=8-6+9-2=9 33=11-6+11-4=124125210391146811五、需要注意的問題 （1）多個空格（非基變量）的檢驗數(shù)為負，任一個都可作為換入變量。一般ij0中最小的對應(yīng)變量作為換入變量。 （2）最優(yōu)解時，如果有某非基變量的檢驗數(shù)為0，則說明該運輸問題有無窮多最有解。 （3）迭代過程中，若某一格填數(shù)時需同時劃去一行和一列，此時出現(xiàn)退化。為保證m+n-1個非空格，需在上述的行或列中填入數(shù)字0(它的位置是在對應(yīng)的同時劃去的那行或那列的所有空格中對應(yīng)單位運價最小的任一空格)練

15、習(xí)： 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量814121448311419281035710求最小運費的運輸方案第三節(jié) 運輸問題的進一步討論一、產(chǎn)銷不平衡的運輸問題例1：31271125943561 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A18A25A39銷量銷量4356產(chǎn)大于銷時，增加一個假想的銷地 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4B5產(chǎn)量產(chǎn)量A18A25A39銷量銷量4356431271125943561000 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4B5產(chǎn)量產(chǎn)量A14048A2325A3549銷量銷量4356431271125943561000當產(chǎn)大于銷時，即

16、njjmiiba11加入假想銷地Bn+1（假想倉庫），銷量為運費為0njjmiinbab111ijminjijxcZ11minnjiijax1i=1,2,mmijijbx1j =1, 2, ,nxij 0ijminjijxcZ11min11njiijaxi=1,2,mmijijbx1j =1, 2, ,n，n+1xij 0當銷大于產(chǎn)時，即njjmiiba11加入假想產(chǎn)地Am+1，產(chǎn)量為運費為0miinjjmaba111ijminjijxcZ11minnjiijax1i=1,2,mmijijbx1j =1, 2, ,nxij 0ijminjijxcZ11minnjijijax1i=1,2,m，m

17、+111miijijbxj =1, 2, ,nxij 0A1B1B2B3A2二、有轉(zhuǎn)運的運輸問題產(chǎn)地銷地m個產(chǎn)地n個銷地都可以作為中間轉(zhuǎn)運站，從而發(fā)送地接收地都有m+n個將m個產(chǎn)地與n個銷地統(tǒng)一編號，產(chǎn)地排在前，銷地排在后，則有,ai:第i個產(chǎn)地的產(chǎn)量bj:第j個銷地的銷量假設(shè)為產(chǎn)銷平衡問題，即數(shù)學(xué)模型數(shù)學(xué)模型Qbanmmjjmii110.0.2121mnmmmbbbaaaxi1 + +xi,i-1 + xi,i+1+ . +xi,m+n =ai+ti i=1,2,mxi1+ +xi,i-1 + xi,i+1+ +x i,i+m= ti i=m+1,m+n x1j+ +xj-1,j+ xj+1

18、,j + +xm+n,j= tj j=1,2,mx1j+ +xj-1,j+ xj+1,j + +xm +n,j = bj+tj j=m+1,m+n xij 0, i,j=1,2,m+n (ij) nmjiinmijjnmiiiijijtcxcz111min其中t i為第i個地點轉(zhuǎn)運物品的數(shù)量ti或tj移到等式左側(cè)，等式兩端加Q 得：xi1 + +xi,i-1 + (Q-ti)+xi,i+1+ . +xi,m+n =Q+ai i=1,2,mxi1+ +xi,i-1 + (Q-ti ) + xi,i+1+ +x i,i+m=Q i=m+1,m+n x1j+ +xj-1,j+ (Q- tj ) +

19、xj+1,j + +xm+n,j= Q j=1,2,mx1j+ +xj-1,j+ (Q- tj)+ xj+1,j + +xm +n,j = Q+bj j=m+1,m+n xij 0, i,j=1,2,m+n (ij) nmjiinmijjnmiiiijijtcxcz111min其中t i為第i個地點轉(zhuǎn)運物品的數(shù)量令xii=Q-ti ,xjj = Q-tj ,cii=-c inminmjnmiiijijQcxcz111min nmjixnmmjbQxmjQxnmmiQxmiaQxijjnmjijnmjijnmjijinmjij, 1, 0, 1, 1, 1, 1,1111其中c i為地i個地點轉(zhuǎn)運單位物品的費用iijccji時，時，當當 接收接收 發(fā)送發(fā)送產(chǎn)地產(chǎn)地銷地銷地發(fā)送發(fā)送量量1 mm+1 m+n產(chǎn)產(chǎn)地地1mx11 x1m