運(yùn)籌學(xué)-5(運(yùn)輸問題)

運(yùn)籌學(xué)基礎(chǔ)教程

5

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

第五章運(yùn)輸問題主要內(nèi)容—你們手中教材p-091第4章

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

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

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

表示從Ai到Bj

的運(yùn)量，那么在供需平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以下數(shù)學(xué)模型：

運(yùn)輸表——運(yùn)輸價(jià)格表

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

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

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

超市倉庫B1B2B3B4儲(chǔ)量A13113107A219284A3741059銷量365620204.2.1

確定初始基本可行解

1．最小元素法——p095

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

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

2020繼續(xù)B1B2B3B4儲(chǔ)量A13113107A21（3）92（1）81-1=0A3741059銷量065-1=46B1B2B3B4儲(chǔ)量A13113（4）107-4=3A21（3）92（1）80A3741059銷量064-4=06繼續(xù)B1B2B3B4儲(chǔ)量A13113（4）103A21（3）92（1）80A374（6）1059-6=3銷量06-6=006B1B2B3B4儲(chǔ)量A13113（4）10（3）3A21（3）92（1）80A374（6）105（3）3銷量0006-6=0最后，得到運(yùn)輸分配表。（分配結(jié)果一定=n+m-1個(gè)）它的運(yùn)輸總成本：

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

超市倉庫B1B2B3B4儲(chǔ)量A1437A2314A3639銷量36562020

2．伏格爾法——p098

最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用,有時(shí)造成在其他處要花幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)j這就有一個(gè)差額，差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)查?；诖?，伏格爾法的步驟是：首先，在表4．1中分別計(jì)算出各行各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該列表的最右列和最下行,見下表：

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

超市倉庫B1B2B3B4行差值A(chǔ)13113100（7）A219281（4）A374（6）1051（9-6）列差值2（3）5（6-6）1（5）3（6）2020B1B2B3B4行差值A(chǔ)13113100（7）A219281（4）A374（6）105（3）2（3-3）列差值2（3）（0）1（5）3（6-3）B1B2B3B4行差值A(chǔ)13113100（7）A21（3）9281（4-3）A374（6）105（3）（0）列差值2（3-3）（0）1（5）2（3）繼續(xù)B1B2B3B4行差值A(chǔ)13113（5）107（7-5）A21（3）9286（1）A374（6）105（3）（0）列差值（0）（0）1（5-5）2（3）B1B2B3B4行差值A(chǔ)13113（5）10（2）（2）A21（3）928（1）（1）A374（6）105（3）（0）列差值（0）（0）（0）（3

-3）最后，得到運(yùn)輸方案：（分配結(jié)果一定=n+m-1個(gè)）它的運(yùn)輸總成本：

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

超市倉庫B1B2B3B4儲(chǔ)量A1527A2314A3639銷量36562020

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

運(yùn)輸問題中的閉合回路是指調(diào)運(yùn)方案中由一個(gè)空格和若干個(gè)有數(shù)字格的水平和垂直連線包圍成的封閉回路。目的是要計(jì)算解中各非基變量(對(duì)應(yīng)空格)的檢驗(yàn)數(shù)σ，方法是令某非基變量取值為1，通過變化原基變量的值，找出一個(gè)新的可行解，將其同原來的基可行解目標(biāo)函數(shù)值的變化比較。閉合回路應(yīng)該這樣選?。簭哪骋豢崭癯霭l(fā)，用水平或垂直直線向前劃，每遇到一數(shù)字格，可以但并非一定要轉(zhuǎn)90度，直到回到起點(diǎn)空格，一定能夠找到唯一的閉合回路。

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

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

a、b、c、d、e、f就是我們需要求的檢驗(yàn)值。B1B2B3B4儲(chǔ)A1a3b

114

33

107A23

1c91

2d84A3e76

4f103

59銷3656

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

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

檢驗(yàn)數(shù)

c（x22）

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

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

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

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

閉回路調(diào)整法——

p47

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

4+1=5，3–1=2（因?yàn)檫@里價(jià)格10，比較高）

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

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

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

(1)當(dāng)倉庫供應(yīng)量大于超市需求量時(shí)，只要增加一個(gè)假想的超市，j=n+1(實(shí)際上是儲(chǔ)存)，該超市總需求量為：?jiǎn)挝贿\(yùn)價(jià)為0，這樣，就轉(zhuǎn)化為平衡的運(yùn)輸問題。

(2)當(dāng)超市需求量大于倉庫供應(yīng)量時(shí)，只要在供需平衡表中增加一個(gè)假想的倉庫i=m+1，該倉庫供應(yīng)量為：而在單位運(yùn)價(jià)表上從該假想倉庫到各超市的運(yùn)價(jià)為0，同樣可以轉(zhuǎn)化為一個(gè)供需平衡的運(yùn)輸問題。

為了讓同學(xué)們能夠自覺理解這個(gè)問題，我們?cè)谙乱豁摦嬕粋€(gè)供需不平衡的案例：例題供大于求的運(yùn)輸問題運(yùn)費(fèi)及產(chǎn)銷量表：B1B2B3產(chǎn)量A1A2A3A464583275651270405020

銷量30