1、第3章運輸問題（TP）學習目標 了解運輸問題模型的特點。 掌握產銷平衡運輸問題的表上作業法。 學會產銷不平衡運輸問題的轉化。 學習表上作業法在物流管理中的典型應用。3 運輸問題（TP）2運輸問題的模型3.1運輸問題的表上作業法3.2產銷不平衡的運輸問題3.3運輸問題的應用案例3.4運輸問題的Excel處理3.53 運輸問題（TP）33.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法4利用表上作業法求解運輸問題時，與單純形法類似，首先要求出一個初始方案（即線性規劃問題的初始基本可行解）。一般來講這個方案不一定是最優的，因此需要給出一個判別準則，并對初始方案進行調整、改進。每進行

2、一次調整，我們就得到一個新的方案（基本可行解），而這個新方案一般比前一個方案要合理些，也就是對應的目標函數z值比前一個方案要小些。經過若干次調整，我們就得到一個使目標函數達到最小值的方案最優方案（最優解），而這些過程都可在產銷矩陣表（運輸表）上進行，故稱為表上作業法。 其實質是單純形法步驟描述方法第一步求初始基行可行解（初始調運方案）最小元素法、元素差額法、第二步求檢驗數并判斷是否得到最優解當非基變量的檢驗數ij全都非負時得到最優解，若存在檢驗數ij 0，說明還沒有達到最優，轉第三步。閉回路法和位勢法第三步調整運量，即換基，選一個變量出基，對原運量進行調整得到新的基可行解，轉入第二步3.2 運

3、輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法5例3.1 設有3個產煤基地A1、A2、A3，4個銷煤基地B1、B2、B3、B4，產地的產量、銷地的銷量以及從各產地至各銷地煤炭的單位運價列于表3.4中，試求出使總運費最低的煤炭調撥方案。63.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法（1）列出運輸問題的產銷矩陣表。73.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法 其中：xij為產地Ai到銷地Bj的運量（i=1,2,3；j1,2,3,4），而將Ai到Bj的單位運價cij用小型字寫在每格的右上角，以便直觀地制定和修改調運方案。 從表3.5的數據

4、可知，例3.1是個滿足產銷平衡條件的產銷平衡問題。（2）初始方案確定的方法最小元素法。最小元素法：就近供應，運價數小的盡可能優先分配。83.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法93.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法這樣，我們便得到這樣問題的一個初始基本可行x11=0 x12=0 x13=4 x14=3 x21=3 x22=0 x23=1 x24=0 x31=0 x32=6 x33=0 x34=3它所對應的目標函數z值為z=30+110+34+103+13+90+21+80+70+46+100+53=86（萬元）因此，在應用最小元素法確

5、定初始方案時，必須注意以下兩點。103.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法1.當選定最小元素（不妨假定為cst）后，如果發現該元素所在行的產地的產量as恰好等于它所在列的銷地的銷量bt（即as=bt），可在產銷矩陣表上xst處填上一個數as，并畫上圈。為了保證調運方案中畫圈的數字為m+n1個，只能在s行的其他格子里都打上“”（或在t列的其他格子里都打上“”），不可以同時把s行和t列的其他格子里都打上“”。2.當最后只剩下一行（或一列）還存在沒有填數和打“”的格子時，規定只允許填數，不允許打“”，其目的也是為了保證畫圈數字的個數恰為m+n1個。3.在特殊情況下可填“

6、0”并畫上圈，這個“0”應與其他畫圈的數字同樣看待。（不限于最后一行或最后一列）。113.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法例在表3.7中，第一步最小元素為c31=1，在x31處填上數字min(13,19)=13，并在x11、x21處打上“”。123.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法3.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法13第二步的最小元素為c32=2，可在x32處填上數字min(6,6)=6，并在x12、x22處打上“”（或在x33、x34處打上“”），由上面的注意（1）可知，不能同時在x12、x22

7、、x33、x34處都打上“”。 繼續運用前面所述的方法，再經過兩步計算，可得到表3.8。143.2 運輸問題的表上作業法3.2.4 確定初始方案的其他方法1. 西北角法153.2 運輸問題的表上作業法3.2.4 確定初始方案的其他方法2沃格爾法單位 銷地 運價 產地產量311310719284741059銷量36563.2 運輸問題的表上作業法16方法1：最小元素法 基本思想是就近供應，即從運價最小的地方開始供應（調運），然后次小，直到最后供完為止。B1B2B3B4產量A17A2 4A39銷量3656311310192741058341633總的運輸費(31)+(64) +(43) +(12)

8、+(310)+(35)=86元3.2 運輸問題的表上作業法17元素差額法對最小元素法進行了改進，考慮到產地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調運，否則會增加總運費。例如下面兩種運輸方案。85102120151515510總運費是z=108+52+151=105最小元素法：3.2 運輸問題的表上作業法85102120151551510后一種方案考慮到C11與C21之間的差額是82=6，如果不先調運x21，到后來就有可能x110，這樣會使總運費增加較大，從而先調運x21，再是x22，其次是x12總運費z=105+152+51=85用元素差額法求得的基本可行解更接近最

9、優解，所以也稱為近似方案。18最小元素法基本步驟：在單位運價表中找出最小的運價cij,其對應的變量xij 優先賦值xij =min(ai ,bj ),使該行或列對應的供或求得到滿足，在產銷平衡表中填對應的供求數值，在單位運價表中劃去該行或列，以示不需再予供應，在剩余的單位運價表中做同樣的操作，直到單位運價表中所有的元素都被劃去為止。表上作業法要求：調運方案的數字格必須為m+n-1個，且有數字格不構成閉回路。一般用最小元素法給出的方案符合這要求。3.2 運輸問題的表上作業法19方法2：Vogel法1）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。B1B2

10、B3B4產量行差額A177A2 41A391銷量3656列差額25133113101927410583.2 運輸問題的表上作業法20B1B2B3B4產量行差額A177A2 41A3 91銷量3656列差額251331131019274105852）再從差值最大的行或列中找出最小運價確定供需關系和供需數量。當產地或銷地中有一方數量供應完畢或得到滿足時，劃去運價表中對應的行或列。重復1)和2)，直到找出初始解為至。3.2 運輸問題的表上作業法21單位 銷地 運價 產地產量行差額311310719284741059銷量3656列差額711352153.2 運輸問題的表上作業法22單位 銷地 運價 產

11、地產量行差額311310719284741059銷量3656列差額713527533.2 運輸問題的表上作業法23單位 銷地 運價 產地產量行差額311310719284741059銷量3656列差額11351536312該方案的總運費:(13)(46)(35)(210)(18)(35)85元3.2 運輸問題的表上作業法24Vogel基本步驟：對單位運價表中求出各行和各列的最小運費和次小運費的差額罰數從行罰數和列罰數中選取最大者，再在它所在的行或列中選取最小元素在產銷平衡表中對應位置，仍按最小元素法的方法，填入可使該行或該列之一得到滿足的數值在單位運價表中劃去該行或列，以示不需再予供應在剩余的

12、單位運價表中找出各行和各列的最小運費和次小運費的差額，直到單位運價表中所有的元素都被劃去為止注意的問題：當同時有兩個差額最大時，選取運費較小的一個.3.2 運輸問題的表上作業法25（3）調運方案的檢驗閉回路法。（計算打“”處的檢驗數）從某一打“”處出發，沿水平方向或垂直方向前進,遇到合適“”的數字格可以旋轉90度，繼續前進,若最后能回到出發點,則所構成的回路為閉回路。 約定作為起始頂點的（打“”）為偶數次頂點，其它頂點（打“”）從1開始順次排列，那麼，該“”檢驗數： =（閉回路上偶數次頂點運距或運價之和）-（閉回路上奇數次頂點運距或運價之和） 結論:在任何可行方案中,以空格(i,j)為一個頂點

13、,其余頂點全是數字格的閉回路存在且唯一。263.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法min的非基變量檢驗數ij的經濟意義: 在保持產銷平衡的條件下,非基變量每增加一個單位運量而成為進基變量時引起目標函數值(總運費）的增量.檢驗原理：利用檢驗數的經濟意義 ij 0 表示總運費增加。3.2 運輸問題的表上作業法作法:先從任意空格(i,j)處出發，作一閉回路給空格(i,j)一個單位的運量,調整閉回路上其余數字格的運量,使達到產銷平衡.則閉回路上總運費的變化值等于空格(i,j)的檢驗數.當所有的檢驗數都為正時，則為最優解.3.2 運輸問題的表上作業法(+1)(-1)(-1)

14、(+1)3312奇點偶點經調運后，運費的變化值為：3-3+2-1=1，即空格( AI,B1)的檢驗數為1依次求出所有空格（非基變量）的檢驗數，當檢驗數還存在負數時，說明原方案還不是最優解。303.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法313.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法323.2.1 產銷平衡運輸問題的表上作業法3.2 運輸問題的表上作業法利用閉回路法檢驗某調運方案是否最優，可按下列步驟進行。 求檢驗數。 （計算打“”處的檢驗數） 根據檢驗數進行判別（若全部大于等于零，則該方案就是最優調運方案，否則就應進行調整。）將所有打“”處的檢

15、驗數填入表中，得到檢驗數表，如表3.12所示。333.2 運輸問題的表上作業法3.2.1 產銷平衡運輸問題的表上作業法當一個運輸問題的產地和銷地個數很多時，用這個方法計算檢驗數的工作十分繁重。 下面介紹一種簡便的求檢驗數的方法位勢法。 表3.23（同表3.6）給出了例3.1利用最小元素法確定的初始調運方案。 第一步是在表3.23中添加新的一列ui列（i的個數等于產地的個數）和新的一行vj行（j的個數等于銷地的個數），如表3.24所示。343.2 運輸問題的表上作業法3.2.3 利用位勢法求檢驗數353.2 運輸問題的表上作業法3.2.3 利用位勢法求檢驗數363.2 運輸問題的表上作業法3.2

16、.3 利用位勢法求檢驗數表3.24中的ui和vj分別稱為第i行和第j列的位勢（i=1, 2,m；j=1,2,n），并規定它們與表中畫圈數字所在的格對應的單位運價有如下關系：第二步是確定ui和vj的數值。由于ui與vj的數值相互之間是有關聯的，所以只要任意給定其中的一個，則可根據關系式（3-3）很容易地將其他所有位勢的數值求出。 373.2 運輸問題的表上作業法3.2.3 利用位勢法求檢驗數例如，在表3.24中，先令v1 = 1，則有u2 + v1 = 1 u2 = 0u2 + v3 = 2 v3 = 2u1 + v3 = 3 u1 = 1u1 + v4 = 10v4 = 9u3 + v4 =

17、5 u3 = 4 u3 + v2 = 4 v2 = 8 把這些數分別填入表3.24的ui列和vj行，得到表3.25。383.2 運輸問題的表上作業法3.2.3 利用位勢法求檢驗數第三步是求出位勢，可以根據下面的原理求“”處格子的檢驗數（即非基變量的檢驗數）。例3.3 對于表3.19所示的調運方案，利用位勢法求檢驗數。解：（1）在表3.19中添加新的ui列和vj行得表3.26。（2）令u1=5，對于各個有圈數字所在格的單位運價，按照關系式cij=(ui+vj)，依次求出各位勢值填入表3.26。393.2 運輸問題的表上作業法3.2.3 利用位勢法求檢驗數（3）利用打“”處的單位運價，根據式（3-

18、4），即可間接求得相應的檢驗數表，如表3.27所示。第一步，求初始調運方案，采用最小元素法，保證有調運量的格子個數（基變量個數）等于m+n1。第二步，求檢驗數。第三步，調整。403.2 運輸問題的表上作業法3.2.2 產銷平衡運輸問題的表上作業法步驟當存在非基變量的檢驗數kl0且kl=minij時，做出過xkl處的閉回路。在最小負檢驗數所在的閉回路上，取奇次點（打“”）中運量最小的記為d。將d填在xkl處，并打“”，同時奇次點減調整量d，偶點加調整量d，得到新的方案。即閉回路上，奇數次頂點的調運量減去d，偶數次頂點（包括起始頂點）的調運量加上d；閉回路之外的變量調運量不變。413.2 運輸問題的表上作業法3.2.2 產銷平衡運輸問題的表上作業法步驟表上作業法B1B2B3B4UiA1A2A3Vj311310192741058436313()()()()調整步驟為：在進基變量的閉回路中標有正號的變量加上調整量d，標有負號的變量減去調整量d，其余變量不變，得到一組新的基可行解。然后求所有非基變量的檢驗數重新檢驗。1253.2 運輸問題的表上作業法42例3.2 某工地有3個高地A1、A2、A3和4個洼地B1、B2、B3、B4，希望用高地的土有計劃地填平洼地。 設各個高地的出土量和各個洼地的填土量如表3.14所示，各個高地與各個洼地之間的距離如表3.15所示，試用表上