運籌學-5(運輸問題)

1、運籌學基礎教程運籌學基礎教程5 黃桐城黃桐城 主編主編 趙弘志趙弘志 改編改編 主講主講 第五章第五章 運輸問題運輸問題l主要內(nèi)容主要內(nèi)容你們手中教材你們手中教材p-091第第4章章 運 輸 問 題 及 其 數(shù) 學 模 型運 輸 問 題 及 其 數(shù) 學 模 型 表 上 作 業(yè) 法表 上 作 業(yè) 法 產(chǎn) 銷 不 平 衡 的 運 輸 問 題產(chǎn) 銷 不 平 衡 的 運 輸 問 題4.1 4.1 運運 輸輸 問問 題及其數(shù)學模型題及其數(shù)學模型 在物流活動中，經(jīng)常會有大宗貨物的調(diào)運問題。在物流活動中，經(jīng)常會有大宗貨物的調(diào)運問題。如何編制調(diào)運方案，把貨物從供應地運到各消費如何編制調(diào)運方案，把貨物從供應地運

2、到各消費地，而總運費最小，就是我們要解決的問題。一般地，而總運費最小，就是我們要解決的問題。一般說來，這種物流中的運輸問題可以用以下數(shù)學語言說來，這種物流中的運輸問題可以用以下數(shù)學語言描述。描述。 已知有已知有 m m 個供應地點個供應地點 A Ai i, , i i=1,2,=1,2,m；可供應；可供應某種物資，其供應量分別為某種物資，其供應量分別為a ai i, , i i=1,2,=1,2,m； 以有以有n n個銷地個銷地 B Bj j, ,j j=1,2,=1,2,n; 其需要量分別為其需要量分別為 b bj j, , j j=1,2,=1,2,n; 從從A Ai i到到B Bj j運

3、輸單位物資的運價運輸單位物資的運價( (單價單價) )為為c cijij，這些數(shù)據(jù)，這些數(shù)據(jù)可以匯總到產(chǎn)銷平衡表和單位運價表中。若用可以匯總到產(chǎn)銷平衡表和單位運價表中。若用x xijij 表示從表示從A Ai i到到B Bj j 的運量，那么在供需平衡的條件下，的運量，那么在供需平衡的條件下，要求得總運費最小的調(diào)運方案，可求解以下數(shù)學模要求得總運費最小的調(diào)運方案，可求解以下數(shù)學模型：型： 0,2, 1,2, 1,min1111 ijnjiijmijijminiijijxmiaxnjbxStxcz運運 輸輸 表表運輸價格表運輸價格表 銷地銷地產(chǎn)地產(chǎn)地B1B2Bn產(chǎn)量產(chǎn)量 A1C11C12C1n

4、a1 A2C21C22C2n a2 AmCm1Cm2Cmn am 銷量銷量b1b2bn4.2. 4.2. 表上作業(yè)法表上作業(yè)法 表上作業(yè)法實質(zhì)上是單純形法。下面我們結(jié)合例表上作業(yè)法實質(zhì)上是單純形法。下面我們結(jié)合例題來解析表上作業(yè)法。題來解析表上作業(yè)法。 例例4 4 某物流公司有三個倉庫，每天向四個超市某物流公司有三個倉庫，每天向四個超市供應某種貨物。已知三個倉庫供應某種貨物。已知三個倉庫A A1 1，A A2 2和和A A3 3的此貨物的此貨物儲藏量分別為儲藏量分別為7 7箱、箱、4 4箱和箱和9 9箱。該物流公司把這些貨箱。該物流公司把這些貨物分別送往物分別送往B B1 1、B B2 2、B

5、 B3 3和和B B4 4四個超市，各超市每日銷四個超市，各超市每日銷量分別為量分別為3 3箱、箱、6 6箱、箱、5 5箱和箱和6 6箱。試用表上作業(yè)法求箱。試用表上作業(yè)法求解滿足供需要求的最佳調(diào)運方案，使總運費最少。解滿足供需要求的最佳調(diào)運方案，使總運費最少。解：步驟如下：解：步驟如下： 第一步：做出單位運價表與供銷平衡表：第一步：做出單位運價表與供銷平衡表： 第二步：第二步：求初始解。初始解一般可通過最小元求初始解。初始解一般可通過最小元素法和伏格爾法兩種方法得到。素法和伏格爾法兩種方法得到。 超市超市倉庫倉庫B1B2B3B4儲量儲量A13113107A219284A3741059銷量銷量

6、3656 20 204.2.1 確定初始基本可行解確定初始基本可行解 1 1最小元素法最小元素法 p095 最小元素法的基本思想是就近配送，即從單位運價表中最小元素法的基本思想是就近配送，即從單位運價表中最小的運價開始確定供需關系，然后次小，一直到給出初始最小的運價開始確定供需關系，然后次小，一直到給出初始可行解為止?？尚薪鉃橹?。 超市超市倉庫倉庫B1B2B3B4儲量儲量A13113107A21（3）9284-3=1A3741059銷量銷量3-3=0656 20 20繼續(xù)繼續(xù)B1B2B3B4儲量儲量A13113107A21（3）92（1）81-1=0A3741059銷量銷量065-1=46B1

7、B2B3B4儲量儲量A13113（4）107-4=3A21（3）92 （1）80A3741059銷量銷量064-4=06繼續(xù)繼續(xù)B1B2B3B4儲量儲量A13113（4）103A21（3）92 （1）80A374（6）1059-6=3銷量銷量06-6=006B1B2B3B4儲量儲量A13113（4）10（3）3A21（3）92 （1）80A374 （6）105（3）3銷量銷量0006-6=0最后，得到運輸分配表。最后，得到運輸分配表。（分配結(jié)果一定（分配結(jié)果一定= n + m - 1 個）個）它的運輸總成本：它的運輸總成本： 31+ 64 + 43 + 12 + 310 + 35=86元元 超

8、市超市倉庫倉庫B1B2B3B4儲量儲量A1437A2314A3639銷量銷量3656 20 20 2 2伏格爾法伏格爾法 p098 最小元素法的缺點是：為了節(jié)省一處的費用最小元素法的缺點是：為了節(jié)省一處的費用, , 有有時造成在其他處要花幾倍的運費。伏格爾法考慮時造成在其他處要花幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應，到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應，就考慮次小運費就考慮次小運費j j這就有一個差額，差額越大，說明這就有一個差額，差額越大，說明不能按最小運費調(diào)運時，運費增加越多，因而對差不能按最小運費調(diào)運時，運費增加越多，因而對差額最大處，就應當采用最小運

9、費調(diào)查。基于此，伏額最大處，就應當采用最小運費調(diào)查?；诖?，伏格爾法的步驟是：格爾法的步驟是： 首先，在表首先，在表4 41 1中分別計算出各行各列的最小運中分別計算出各行各列的最小運費和次小運費的差額，并填入該列表的最右列和最費和次小運費的差額，并填入該列表的最右列和最下行下行, ,見下表：見下表： 然后，從行或列差額中選出最大者，選擇它所在行或列然后，從行或列差額中選出最大者，選擇它所在行或列的最小元素，在表的最小元素，在表4-84-8中中B2B2列是最大差額所在列。列是最大差額所在列。B2B2列中最列中最小元素為小元素為4 4，可確定，可確定A3A3的產(chǎn)品先供應的產(chǎn)品先供應B2B2的需要

10、，得表的需要，得表4-94-9。同。同時將運價表中的時將運價表中的B2B2列數(shù)字劃去，如表列數(shù)字劃去，如表 超市超市倉庫倉庫B1B2B3B4行差值行差值A13113100（7）A219281（4）A374（6）1051（9-6）列差值列差值 2（3） 5（6-6）1（5） 3（6） 20 20B1B2B3B4行差值行差值A13113100（7）A219281（4）A374 （6）105（3）2（3-3）列差值列差值2（3）（0）1（5）3（6-3）B1B2B3B4行差值行差值A13113100（7）A21 （3）9281（4-3）A374 （6）105 （3）（0）列差值列差值2（3-3）（0

11、）1（5）2（3）繼續(xù)繼續(xù)B1B2B3B4行差值行差值A13113 （5）107（7-5）A21 （3）9286（1）A374 （6）105 （3）（0）列差值列差值（0）（0）1（5-5）2（3）B1B2B3B4行差值行差值A13113 （5）10（2）（2）A21 （3）928（1）（1）A374 （6）105 （3）（0）列差值列差值（0）（0）（0）（ 3 -3）最后，得到運輸方案：最后，得到運輸方案： （分配結(jié)果一定（分配結(jié)果一定= n + m - 1 個）個）它的運輸總成本：它的運輸總成本： 31+ 64 + 53 + 210 + 18 + 35=82元元 超市超市倉庫倉庫B1B2

12、B3B4儲量儲量A1527A2314A3639銷量銷量3656 20 20 4.2.24.2.2 最優(yōu)性檢驗與方案的調(diào)整最優(yōu)性檢驗與方案的調(diào)整p101 運輸問題中的閉合回路是指調(diào)運方案中由一個空格和若運輸問題中的閉合回路是指調(diào)運方案中由一個空格和若干個有數(shù)字格的水平和垂直連線包圍成的封閉回路。干個有數(shù)字格的水平和垂直連線包圍成的封閉回路。 目的是要計算解中各非基變量目的是要計算解中各非基變量( (對應空格對應空格) )的的檢驗數(shù)檢驗數(shù)，方法是令某非基變量取值為方法是令某非基變量取值為1 1，通過變化原基變量的值，找，通過變化原基變量的值，找出一個新的可行解，將其同原來的基可行解目標函數(shù)值的變出

13、一個新的可行解，將其同原來的基可行解目標函數(shù)值的變化比較?；容^。 閉合回路應該這樣選?。簭哪骋豢崭癯霭l(fā)，用水平或垂閉合回路應該這樣選取：從某一空格出發(fā)，用水平或垂直直線向前劃，每遇到一數(shù)字格，可以但并非一定要轉(zhuǎn)直直線向前劃，每遇到一數(shù)字格，可以但并非一定要轉(zhuǎn) 90度，直到回到起點空格，一定能夠找到唯一的閉合回路。度，直到回到起點空格，一定能夠找到唯一的閉合回路。 如果如果檢驗數(shù)檢驗數(shù) 大于等于零，表明對調(diào)運方案作出任何改大于等于零，表明對調(diào)運方案作出任何改變不會減少運費，現(xiàn)有方案是最優(yōu)的方案。變不會減少運費，現(xiàn)有方案是最優(yōu)的方案。 如果如果檢驗數(shù)檢驗數(shù)為負，則方案需要進一步的改進。改進的為負

14、，則方案需要進一步的改進。改進的方法是從為負的格出發(fā)（當有兩個以上方法是從為負的格出發(fā)（當有兩個以上檢驗數(shù)檢驗數(shù)負的時，從負的時，從絕對值最大的負絕對值最大的負檢驗數(shù)檢驗數(shù)格出發(fā)），在這條閉合回路上，作格出發(fā)），在這條閉合回路上，作運量的最大可能調(diào)整。剛才使用最小元素法得到下表值：運量的最大可能調(diào)整。剛才使用最小元素法得到下表值： a、b、c、d、e、f 就是我們需要求的檢驗值。就是我們需要求的檢驗值。B1B2B3B4儲儲A1a 3b 114 33 107A23 1c 9 1 2d 84A3e 76 4f 103 59銷銷3656 檢驗數(shù)檢驗數(shù) a （x11）= 3 3 + 2 1 =1 檢驗

15、數(shù)檢驗數(shù) b （x12） = 11 10 + 5 4 =2 檢驗數(shù)檢驗數(shù) c （x22） = 9 2 + 3 10 + 5 4 =1 檢驗數(shù)檢驗數(shù) d （x24） = 8 10 + 3 2 = -1 檢驗數(shù)檢驗數(shù) e （x31） = 7 5 + 10 3 + 2 1 =10 檢驗數(shù)檢驗數(shù) f （x33） = 10 5 + 10 3 =12B1B2B3B4A111-b310A219-c28-dA37-e410-f5 閉回路調(diào)整法閉回路調(diào)整法 p47 當所有檢驗數(shù)都不小于零時，方案即為最優(yōu)調(diào)運方案。當所有檢驗數(shù)都不小于零時，方案即為最優(yōu)調(diào)運方案。當檢驗數(shù)還存在負值時，說明該方案不是最優(yōu)，需要調(diào)整。

16、當檢驗數(shù)還存在負值時，說明該方案不是最優(yōu)，需要調(diào)整。 4 + 1 = 5，3 1 = 2（因為這里價格（因為這里價格10，比較高），比較高） 0 + 1 = 1, 1 1= 0 。 得到新方案。得到新方案。B1B2B3B4A14 53 2A231 0 1A363 3 3、閉回路法。、閉回路法。（運價）（運價） 在給出調(diào)運方案的計算表在給出調(diào)運方案的計算表( (最終表最終表) )上，從每一空格出發(fā)上，從每一空格出發(fā)找一條閉回路。即以某空格為起點，用水平或垂直線向前找一條閉回路。即以某空格為起點，用水平或垂直線向前劃，碰到數(shù)字格可轉(zhuǎn)劃，碰到數(shù)字格可轉(zhuǎn)9090度后，繼續(xù)前進，直到回到起始空度后，繼續(xù)

17、前進，直到回到起始空格。在表格。在表4-114-11中，空格中，空格(A1(A1，B1)B1)的閉回路之一如表中虛線所的閉回路之一如表中虛線所示，檢驗數(shù)示，檢驗數(shù)=+3 -10 + 8 =+3 -10 + 8 1 = O 1 = O，其中：式中計算所用，其中：式中計算所用值為閉回路頂點所在格的運價，起始空格為奇數(shù)位，它的下值為閉回路頂點所在格的運價，起始空格為奇數(shù)位，它的下一個頂點為偶數(shù)位，下面頂點依次奇偶相間，奇數(shù)位取正一個頂點為偶數(shù)位，下面頂點依次奇偶相間，奇數(shù)位取正值，偶數(shù)位取負值，各數(shù)累加的和就為檢驗數(shù)。同樣，可以值，偶數(shù)位取負值，各數(shù)累加的和就為檢驗數(shù)。同樣，可以計算出其他空格的檢驗

18、數(shù)。計算出其他空格的檢驗數(shù)。 當所有檢驗數(shù)都不小于零時，方案即為最優(yōu)調(diào)運方案。當所有檢驗數(shù)都不小于零時，方案即為最優(yōu)調(diào)運方案。當檢驗數(shù)還存在負值時，說明該方案不是最優(yōu)，需要調(diào)整。當檢驗數(shù)還存在負值時，說明該方案不是最優(yōu)，需要調(diào)整。 本次課后的課外作業(yè)本次課后的課外作業(yè)習題：請您用習題：請您用最小元素法最小元素法以及以及伏格爾法伏格爾法解下面的習解下面的習題。然后您想想辦法，如何來進行調(diào)整？題。然后您想想辦法，如何來進行調(diào)整？ 5161224014367491011126704212315111010104.3 4.3 供需不平衡的運輸問題供需不平衡的運輸問題 前面的問題是供需平衡問題，即前面的

19、問題是供需平衡問題，即但實際問題往往不平衡，或供大于需，或需大于但實際問題往往不平衡，或供大于需，或需大于供。只要把供需不平衡問題轉(zhuǎn)化成供需平衡問題，供。只要把供需不平衡問題轉(zhuǎn)化成供需平衡問題，就可以用上述方法解決，具體方法如下。就可以用上述方法解決，具體方法如下。 (1)(1)當倉庫供應量大于超市需求量時，只要增加當倉庫供應量大于超市需求量時，只要增加一個假想的超市，一個假想的超市，j=n+1(j=n+1(實際上是儲存實際上是儲存) )，該超市，該超市總總需求量為：需求量為： 單位運價為單位運價為0 0，這樣，就轉(zhuǎn)，這樣，就轉(zhuǎn)化為平衡化為平衡 的運輸問題。的運輸問題。 njjmiiba11njjmiiba11 (2) (2)當超市需求量大于倉庫供應量時，只要在供當超市需求量大于倉庫供應量時，只要在供需平衡表中增加一個假想的倉庫需平衡表中增加一個假想的倉庫i=m+1i=m+1，該倉庫供，該倉庫供應應量為：量為： 而在單位運價表上從該假想倉而在單位運價表上從該假想倉庫庫到各超市的運價為到各超市的運價為0 0，同樣可以轉(zhuǎn)化為一個供需平衡，同樣可以轉(zhuǎn)化為一個供需平衡的運輸問題。的運輸問題。 為了讓同學們能夠自覺理解這個問題，我們在為了讓同學們能夠自覺理解這個問題，我們在下一頁畫一個供需不平衡的案例：下一頁畫一個供需不平衡的案例：m