運籌學-5(運輸問題)

運籌學基礎教程

5

黃桐城主編趙弘志改編主講

第五章運輸問題主要內容—你們手中教材p-091第4章

★運輸問題及其數(shù)學模型★表上作業(yè)法★產(chǎn)銷不平衡的運輸問題4.1運輸問題及其數(shù)學模型在物流活動中，經(jīng)常會有大宗貨物的調運問題。如何編制調運方案，把貨物從供應地運到各消費地，而總運費最小，就是我們要解決的問題。一般說來，這種物流中的運輸問題可以用以下數(shù)學語言描述。已知有m個供應地點Ai,i=1,2,…m；可供應某種物資，其供應量分別為ai,i=1,2,…m；以有n個銷地Bj,j=1,2,…n;

其需要量分別為bj,j=1,2,…n;

從Ai到Bj運輸單位物資的運價(單價)為cij，這些數(shù)據(jù)可以匯總到產(chǎn)銷平衡表和單位運價表中。若用xij

表示從Ai到Bj

的運量，那么在供需平衡的條件下，要求得總運費最小的調運方案，可求解以下數(shù)學模型：

運輸表——運輸價格表

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam

銷量b1b2…bn4.2.表上作業(yè)法表上作業(yè)法實質上是單純形法。下面我們結合例題來解析表上作業(yè)法。例4某物流公司有三個倉庫，每天向四個超市供應某種貨物。已知三個倉庫A1，A2和A3的此貨物儲藏量分別為7箱、4箱和9箱。該物流公司把這些貨物分別送往B1、B2、B3和B4四個超市，各超市每日銷量分別為3箱、6箱、5箱和6箱。試用表上作業(yè)法求解滿足供需要求的最佳調運方案，使總運費最少。解：步驟如下：第一步：做出單位運價表與供銷平衡表：

第二步：求初始解。初始解一般可通過最小元素法和伏格爾法兩種方法得到。

超市倉庫B1B2B3B4儲量A13113107A219284A3741059銷量365620204.2.1

確定初始基本可行解

1．最小元素法——p095

最小元素法的基本思想是就近配送，即從單位運價表中最小的運價開始確定供需關系，然后次小，一直到給出初始可行解為止。

超市倉庫B1B2B3B4儲量A13113107A21（3）9284-3=1A3741059銷量3-3=0656

2020繼續(xù)B1B2B3B4儲量A13113107A21（3）92（1）81-1=0A3741059銷量065-1=46B1B2B3B4儲量A13113（4）107-4=3A21（3）92（1）80A3741059銷量064-4=06繼續(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最后，得到運輸分配表。（分配結果一定=n+m-1個）它的運輸總成本：

3×1+6×4+4×3+1×2+3×10+3×5=86元

超市倉庫B1B2B3B4儲量A1437A2314A3639銷量36562020

2．伏格爾法——p098

最小元素法的缺點是：為了節(jié)省一處的費用,有時造成在其他處要花幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應，就考慮次小運費j這就有一個差額，差額越大，說明不能按最小運費調運時，運費增加越多，因而對差額最大處，就應當采用最小運費調查?；诖耍駹柗ǖ牟襟E是：首先，在表4．1中分別計算出各行各列的最小運費和次小運費的差額，并填入該列表的最右列和最下行,見下表：

然后，從行或列差額中選出最大者，選擇它所在行或列的最小元素，在表4-8中B2列是最大差額所在列。B2列中最小元素為4，可確定A3的產(chǎn)品先供應B2的需要，得表4-9。同時將運價表中的B2列數(shù)字劃去，如表

超市倉庫B1B2B3B4行差值A13113100（7）A219281（4）A374（6）1051（9-6）列差值2（3）5（6-6）1（5）3（6）2020B1B2B3B4行差值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）1（5）2（3）繼續(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）最后，得到運輸方案：（分配結果一定=n+m-1個）它的運輸總成本：

3×1+6×4+5×3+2×10+1×8+3×5=82元

超市倉庫B1B2B3B4儲量A1527A2314A3639銷量36562020

4.2.2最優(yōu)性檢驗與方案的調整——p101

運輸問題中的閉合回路是指調運方案中由一個空格和若干個有數(shù)字格的水平和垂直連線包圍成的封閉回路。目的是要計算解中各非基變量(對應空格)的檢驗數(shù)σ，方法是令某非基變量取值為1，通過變化原基變量的值，找出一個新的可行解，將其同原來的基可行解目標函數(shù)值的變化比較。閉合回路應該這樣選取：從某一空格出發(fā)，用水平或垂直直線向前劃，每遇到一數(shù)字格，可以但并非一定要轉90度，直到回到起點空格，一定能夠找到唯一的閉合回路。

如果檢驗數(shù)σ大于等于零，表明對調運方案作出任何改變不會減少運費，現(xiàn)有方案是最優(yōu)的方案。

如果檢驗數(shù)σ為負，則方案需要進一步的改進。改進的方法是從為負的格出發(fā)（當有兩個以上檢驗數(shù)σ負的時，從絕對值最大的負檢驗數(shù)σ格出發(fā)），在這條閉合回路上，作運量的最大可能調整。剛才使用最小元素法得到下表值：

a、b、c、d、e、f就是我們需要求的檢驗值。B1B2B3B4儲A1a3b

114

33

107A23

1c91

2d84A3e76

4f103

59銷3656

檢驗數(shù)a（x11）=3–3+2–1=1

檢驗數(shù)b（x12）=11–10+5–4=2

檢驗數(shù)

c（x22）

=9–2+3–10+5–4=1

檢驗數(shù)d（x24）=8–10+3–2=-1

檢驗數(shù)e（x31）=7–5+10–3+2–1=10

檢驗數(shù)f（x33）=10–5+10–3=12B1B2B3B4A13-a11-b310A219-c28-dA37-e410-f5

閉回路調整法——

p47

當所有檢驗數(shù)都不小于零時，方案即為最優(yōu)調運方案。當檢驗數(shù)還存在負值時，說明該方案不是最優(yōu)，需要調整。

4+1=5，3–1=2（因為這里價格10，比較高）

0+1=1,1–1=0。得到新方案。B1B2B3B4A1

4532A23101A3633、閉回路法。（運價）在給出調運方案的計算表(最終表)上，從每一空格出發(fā)找一條閉回路。即以某空格為起點，用水平或垂直線向前劃，碰到數(shù)字格可轉90度后，繼續(xù)前進，直到回到起始空格。在表4-11中，空格(A1，B1)的閉回路之一如表中虛線所示，檢驗數(shù)δ=+3-10+8–1=O，其中：式中計算所用值為閉回路頂點所在格的運價，起始空格為奇數(shù)位，它的下一個頂點為偶數(shù)位，下面頂點依次奇偶相間，奇數(shù)位取正值，偶數(shù)位取負值，各數(shù)累加的和就為檢驗數(shù)。同樣，可以計算出其他空格的檢驗數(shù)。當所有檢驗數(shù)都不小于零時，方案即為最優(yōu)調運方案。當檢驗數(shù)還存在負值時，說明該方案不是最優(yōu)，需要調整。本次課后的課外作業(yè)習題：請您用最小元素法以及伏格爾法解下面的習題。然后您想想辦法，如何來進行調整？

5161224014367491011126704212315111010104.3供需不平衡的運輸問題前面的問題是供需平衡問題，即但實際問題往往不平衡，或供大于需，或需大于供。只要把供需不平衡問題轉化成供需平衡問題，就可以用上述方法解決，具體方法如下。

(1)當倉庫供應量大于超市需求量時，只要增加一個假想的超市，j=n+1(實際上是儲存)，該超市總需求量為：單位運價為0，這樣，就轉化為平衡的運輸問題。

(2)當超市需求量大于倉庫供應量時，只要在供需平衡表中增加一個假想的倉庫i=m+1，該倉庫供應量為：而在單位運價表上從該假想倉庫到各超市的運價為0，同樣可以轉化為一個供需平衡的運輸問題。

為了讓同學們能夠自覺理解這個問題，我們在下一頁畫一個供需不平衡的案例：例題供大于求的運輸問題運費及產(chǎn)銷量表：B1B2B3產(chǎn)量A1A2A3A464583275651270405020

銷量30