第三章運(yùn)輸問題-數(shù)學(xué)模型及其解法

第三章運(yùn)輸問題

—數(shù)學(xué)模型及其解法順風(fēng)而呼，聲非加疾也，而聞?wù)哒谩＜佥涶R者，非利足也，而致千里；假舟楫者，非能水也，而絕江河。君子生非異也，善假于物也。荀子《勸學(xué)》第三章運(yùn)輸問題

—數(shù)學(xué)模型及其解法1第1節(jié)運(yùn)輸問題的數(shù)學(xué)模型有m個產(chǎn)地生產(chǎn)某種物資，有n個地區(qū)需要該類物資;令a1,a2,…,am表示各產(chǎn)地產(chǎn)量，b1,b2,…,bn表示各銷地的銷量，ai=bj

稱為產(chǎn)銷平衡;cij表示從Ai到Bj的單位運(yùn)費(fèi)，這些數(shù)據(jù)可匯總于產(chǎn)銷平衡表和單位運(yùn)價表中，見表3-1，表3-2。有時可把這兩表合二為一。2銷地產(chǎn)地1┉n產(chǎn)量

12┆m

a1a2┆am銷量b1┈bn

表3-1表3-23設(shè)xij表示產(chǎn)地i

運(yùn)往銷地j

的物資量，在產(chǎn)銷平衡的條件下，要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，則運(yùn)輸問題的數(shù)學(xué)模型如下：4運(yùn)輸問題有mn個決策變量，m+n

個約束條件,其系數(shù)矩陣為5Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j變量xij的系數(shù)向量Pij為對產(chǎn)銷平衡的運(yùn)輸問題，由于有以下關(guān)系式存在：因此模型最多只有m+n–1個約束方程相互獨(dú)立，因此，運(yùn)輸問題的基變量只有m+n–1個。6第2節(jié)表上作業(yè)法

表上作業(yè)法是單純形法在求解運(yùn)輸問題時的一種簡化方法，其實(shí)質(zhì)是單純形法。但具體計算和術(shù)語有所不同?？蓺w納為：(1)找出初始基可行解。即在(m×n)產(chǎn)銷平衡表上用西北角法或最小元素法，Vogel法給出m+n-1個數(shù)字，稱為數(shù)字格。它們就是初始基變量的取值。。(2)求各非基變量的檢驗(yàn)數(shù)，即在表上計算空格的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。(3)確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調(diào)整。(4)重復(fù)(2)，(3)直到得到最優(yōu)解為止。

7例1

某公司經(jīng)銷甲產(chǎn)品。它下設(shè)三個加工廠。每日的產(chǎn)量分別是：A1為7噸，A2為4噸，A3為9噸。該公司把這些產(chǎn)品分別運(yùn)往四個銷售點(diǎn)。各銷售點(diǎn)每日銷量為：B1為3噸，B2為6噸，B3為5噸，B4為6噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價為表3-3所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)為最少。

表3-3單位運(yùn)價表表3-4產(chǎn)銷平衡表

82.1確定初始基可行解

產(chǎn)銷平衡的運(yùn)輸問題總是存在可行解。因有必存在xij≥0，i=1，…，m，j=1，…，n，這就是可行解。又因0≤xij≤min(aj，bj)故運(yùn)輸問題必存在最優(yōu)解。確定初始基可行解的方法很多，現(xiàn)介紹最小元素法和伏格爾(Vogel)法。91.

最小元素法

這方法的基本思想是就近供應(yīng)，即從單位運(yùn)價表中最小的運(yùn)價開始確定供銷關(guān)系，然后次小。一直到給出初始基可行解為止。以例1進(jìn)行討論。第一步：從表3-3中找出最小運(yùn)價為1，這表示先將A2的產(chǎn)品供應(yīng)給B1。因a2＞b1，A2除滿足B1的全部需要外，還可多余1噸產(chǎn)品。在表3-4的(A2，B1)的交叉格處填上3。得表3-5。并將表3-3的B1列運(yùn)價劃去。得表3-6。10表3-5.表3-611第二步：在表3-6未劃去的元素中再找出最小運(yùn)價2，確定A2多余的1噸供應(yīng)B3，并給出表3-7，表3-8。

12第三步：在表3-8未劃去的元素中再找出最小運(yùn)價3；這樣一步步地進(jìn)行下去，直到單位運(yùn)價表上的所有元素劃去為止，最后在產(chǎn)銷平衡表上得到一個調(diào)運(yùn)方案，見表3-9。這方案的總運(yùn)費(fèi)為86元。

133

4

1

432

2

最小元素法：依次選單位運(yùn)費(fèi)最小的調(diào)運(yùn)，以得到初始調(diào)運(yùn)方案如下：B1B2B3B4

供應(yīng)量A1A2A3

B1B2B3B4

1311109

87105A1A2A3需求量產(chǎn)地

銷地31４3746393656205調(diào)運(yùn)表

單位運(yùn)費(fèi)表：（單位：百元）142.伏格爾法

最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，有時造成在其他處要多花幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個差額。差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時，運(yùn)費(fèi)增加越多。因而對差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。

15伏格爾法的步驟是：

第一步：在表3-3中分別計算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，見表3-10。

16第二步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表3-10中B2列是最大差額所在列。B2列中最小元素為4，可確定A3的產(chǎn)品先供應(yīng)B2的需要。得表3-11

17同時將運(yùn)價表中的B2列數(shù)字劃去。如表3-12所示。18第三步：對表3-12中未劃去的元素再分別計算出各行、各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。重復(fù)第一、二步。直到給出初始解為止。用此法給出例1的初始解列于表3-13。

19初始調(diào)運(yùn)表B1B2B3B4

供應(yīng)量B1B2B3B4

行的差額3113100列的差額111221987410553A1A3A2A1A2A3需求量333666122094755523226771081082.差額法20由以上可見：伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外，其余步驟相同。伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。本例用伏格爾法給出的初始解就是最優(yōu)解。212-2最優(yōu)解的判別

判別的方法是計算空格(非基變量)的檢驗(yàn)數(shù)cij-CBB-1Pij，i,j∈N。因運(yùn)輸問題的目標(biāo)函數(shù)是要求實(shí)現(xiàn)最小化，故當(dāng)所有的cij-CBB-1Pij≥0時，為最優(yōu)解。下面介紹兩種求空格檢驗(yàn)數(shù)的方法。1.閉回路法；2.位勢法221.閉回路法在給出調(diào)運(yùn)方案的計算表上，如表3-13，從每一空格出發(fā)找一條閉回路。它是以某空格為起點(diǎn)。用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時可以轉(zhuǎn)90°后，繼續(xù)前進(jìn)，直到回到起始空格為止。閉回路如圖3-1的(a),(b),(c)等所示。從每一空格出發(fā)一定存在和可以找到唯一的閉回路。23從每一空格出發(fā)一定存在和可以找到唯一的閉回路。因(m+n-1)個數(shù)字格(基變量)對應(yīng)的系數(shù)向量是一個基。任一空格(非基變量)對應(yīng)的系數(shù)向量是這個基的線性組合。如Pij,i,j∈N可表示為

24其中Pik,Plk,Pls,Pus,Puj∈B。而這些向量構(gòu)成了閉回路(見圖3-2)。

254

3

7U1314U2

639

U3311310

1928

74105A1A2A3單位運(yùn)費(fèi)表B1B2B3B4

供應(yīng)量A1A2A3需求量B1B2B3B4365620

例2.1中用最小元素法得到的初始調(diào)運(yùn)表：+3-3+2-1=1>0X11+11-10+5-4=2>0X12+9-2+3-10+5-4=1>0X22+8-2+3-10=-1<0X24+7-1+2-3+10-5=10>0X31+10-3+10-5=12>0X3326得非基變量的閉回路及檢驗(yàn)數(shù)如下表：非基變量閉回路檢驗(yàn)數(shù)

X11X11

X13X23X21X11+3-3+2-1=1>0

X12X12

X14X34X32X12+11-10+5-4=2>0X22X22

X23X13X14X34+9-2+3-10+

X32X225-4=1>0

X31X31

X21X23X13X14+7-1+2-3+10

X34X31-5=10>0X33

X33X13X14X34X33+10-3+10-5=12>0X24X24

X23X13X14X24+8-2+3-10=-1<0X24X24

X23X13X14X24+8-2+3-10=-1<027在已給出初始解的表3-9中，以(A1，B1)空格為起點(diǎn)，其他為數(shù)字格的閉回路如表3-14中的虛線所示。在這表中閉回路各頂點(diǎn)所在格的右上角數(shù)字是單位運(yùn)價。28可見這調(diào)整的方案使運(yùn)費(fèi)增加

(+1)×3+(-1)×3+(+1)×2+(-1)×１=1(元)

這表明若這樣調(diào)整運(yùn)量將增加運(yùn)費(fèi)。將“1”這個數(shù)填入(A1，B1)格，這就是檢驗(yàn)數(shù)。按以上所述，可找出所有空格的檢驗(yàn)數(shù)，

見表3-15。

當(dāng)檢驗(yàn)數(shù)還存在負(fù)數(shù)時，說明原方案不是最優(yōu)解，要繼續(xù)改進(jìn)，改進(jìn)方法見2.3小節(jié)。

292.位勢法用閉回路法求檢驗(yàn)數(shù)時，需給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時，這種計算很繁。下面介紹較為簡便的方法——位勢法。設(shè)u1，u2，…，um;v1，v2，…，vn是對應(yīng)運(yùn)輸問題的m+n個約束條件的對偶變量。B是含有一個人工變量xa的(m+n)×(m+n)初始基矩陣。人工變量xa在目標(biāo)函數(shù)中的系數(shù)ca=0，從線性規(guī)劃的對偶理論可知。

30而每個決策變量xij的系數(shù)向量Pij=ei+em+j，所以CBB-1Pij=ui+vj。于是檢驗(yàn)數(shù)由單純形法得知所有基變量的檢驗(yàn)數(shù)等于0。即

因非基變量的檢驗(yàn)數(shù)

這就可以從已知的ui，vj值中求得。這些計算可在表格中進(jìn)行。

31例如，在例1的由最小元素法得到的初始解中x23，x34，x21，x32，x13，x14是基變量。

xa為人工變量，這時對應(yīng)的檢驗(yàn)數(shù)是：

基變量檢驗(yàn)數(shù)xaca-u1=0∵ca=0∴u1=0x23c23-(u2+v3)=0即2-(u2+v3)=0x34c34-(u3+v4)=05-(u3+v4)=0x21c21-(u2+v1)=01-(u2+v1)=0x32c32-(u3+v2)=04-(u3+v2)=0x13c13-(u1+v3)=03-(u1+v3)=0x14c14-(u1+v4)=010-(u1+v4)=0從以上7個方程中,由u1=0可求得u2=-1,u3=-5,v1=2,v2=9,v3=3,v4=1032以例1說明。

第一步：按最小元素法給出表3-9的初始解，然后做表3-16；即在對應(yīng)表3-9的數(shù)字格處填入單位運(yùn)價，見表3-16。

33第二步：在表3-16上增加一行一列，在列中填入ui，在行中填入vj，得表3-17。

先令u1=0，然后按ui+vj=cij，

i，j∈B相繼地確定ui，vj。由表3-17可見，當(dāng)u1=0時，由u1+v3=3可得v3=3，由u1+v4=10可得v4=10；在v4=10時，由u3+v4=5可得u3=-5，以此類推可確定所有的ui，vj的數(shù)值。

34

第三步：按σij=cij-(ui+vj),i,j∈N計算所有空格的檢驗(yàn)數(shù)。如

σ11=c11-(u1+v1)=3-(0+2)=1

σ12=c12-(u1+v2)=11-(0+9)=2

這些計算可直接在表3-17上進(jìn)行。為了方便，特設(shè)計計算表，如表3-18。

表3-18中還有負(fù)檢驗(yàn)數(shù)。說明未得最優(yōu)解，還可以改進(jìn)。

35上述檢驗(yàn)數(shù)的計算更可用下表簡單計算：(1)將基變量的運(yùn)費(fèi)填入下表，算出位勢Ui,Uj

U1=U2=U3=V1=V2=V3=V4=3101254(2)計算非基變量檢驗(yàn)數(shù)：0-1-510392311987102310U1=0U2=-1U3=-5V1=V2=V3=V4=9-0-2=1-0-9=2-(-1)-9=1-(-1)-10=-1-(-5)-2=10-(-5)-3=12362.3

改進(jìn)的方法——閉回路調(diào)整法

當(dāng)在表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時，表明未得最優(yōu)解。若有兩個和兩個以上的負(fù)檢驗(yàn)數(shù)時，一般選其中最小的負(fù)檢驗(yàn)數(shù)，以它對應(yīng)的空格為調(diào)入格。即以它對應(yīng)的非基變量為換入變量。由表3-18得(2，4)為調(diào)入格。以此格為出發(fā)點(diǎn)，作一閉回路，如表3-19所示。37表3-19

38(2，4)格的調(diào)入量θ是選擇閉回路上具有(-1)的數(shù)字格中的最小者。即θ=min(1,3)=1(其原理與單純形法中按θ規(guī)劃來確定換出變量相同)。然后按閉回路上的正、負(fù)號，加入和減去此值，得到調(diào)整方案，如表3-20所示。

39對表3-20給出的解，再用閉回路法或位勢法求各空格的檢驗(yàn)數(shù)，見表3-21。表中的所有檢驗(yàn)數(shù)都非負(fù)，故表3-20中的解為最優(yōu)解。這時得到的總運(yùn)費(fèi)最小是85元。

40由此看出：把X24作為調(diào)入基變量，而調(diào)出基的變量，從X24閉回路中需減少的轉(zhuǎn)角點(diǎn)處找。即X14與X23，取其調(diào)運(yùn)較小的量，對應(yīng)的變量為調(diào)出變量。改進(jìn)后得新的調(diào)運(yùn)表B1B2B3B4

供應(yīng)量A1需求量A2A334936736652043152141此時基變量數(shù)仍為6個保持不變。重復(fù)剛才的檢驗(yàn)過程，經(jīng)計算，可知目前的方案為最優(yōu)?？傎M(fèi)用是：

MinZ=5＊3+2＊10+3＊1+1＊8+6＊4+5＊3=85（百元）.421.無窮多最優(yōu)解

在本章2.1節(jié)中提到，產(chǎn)銷平衡的運(yùn)輸問題必定存在最優(yōu)解。那么有唯一最優(yōu)解還是無窮多最優(yōu)解?判別依據(jù)與第1章3.3節(jié)講述的相同。即某個非基變量(空格)的檢驗(yàn)數(shù)為0時，該問題有無窮多最優(yōu)解。表3-21空格(1，1)的檢驗(yàn)數(shù)是0，表明例1有無窮多最優(yōu)解。可在表3-20中以(1，1)為調(diào)入格，作閉回路(1，1)+-(1，4)--(2，4)+-(2，1)--(1，1)+。確定θ=min(2,3)=2。經(jīng)調(diào)整后得到另一最優(yōu)解，見表3-22。2.4

表上作業(yè)法計算中的問題

43表3-2244初始解退化即所求初始基變量的個數(shù)少于m+n1。必須補(bǔ)足基變量的個數(shù)，否則不能正常解出m+n個ui

和vj,,,有以下兩種情況：(1)當(dāng)確定初始解的各供需關(guān)系時，若在(i,j)格填入某數(shù)字后，出現(xiàn)Ai處的余量等于Bj處的需量。這時在產(chǎn)銷平衡表上填一個數(shù)，而在單位運(yùn)價表上相應(yīng)地要劃去一行和一列。為了使在產(chǎn)銷平衡表上有(m+n-1)個數(shù)字格。必須補(bǔ)足基變量的個數(shù)，否則不能正常解出m+n個ui

和vj

2.退化

45(2)在用閉回路法調(diào)整時，在閉回路上出現(xiàn)兩個和兩個以上的具有(-1)標(biāo)記的相等的最小值。這時只能選擇其中一個作為調(diào)入格。而經(jīng)調(diào)整后，得到退化解。這時另一個數(shù)字格必須填入一個0，表明它是基變量。當(dāng)出現(xiàn)退化解后，并作改進(jìn)調(diào)整時，可能在某閉回路上有標(biāo)記為(-1)的取值為0的數(shù)字格，這時應(yīng)取調(diào)整量θ=0。所補(bǔ)基變量的值為0，補(bǔ)充的原則：(1)盡量先選運(yùn)費(fèi)小的實(shí)變量；(2)補(bǔ)充后不能有某個基變量獨(dú)占一行一列46第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法

前面所講表上作業(yè)法，都是以產(chǎn)銷平衡為前提條件的；但是實(shí)際問題中產(chǎn)銷往往是不平衡的。就需要把產(chǎn)銷不平衡的問題化成產(chǎn)銷平衡的問題。當(dāng)產(chǎn)大于銷47運(yùn)輸問題的數(shù)學(xué)模型可寫成

目標(biāo)函數(shù)：滿足：48由于總的產(chǎn)量大于銷量，就要考慮多余的物資在哪一個產(chǎn)地就地儲存的問題。設(shè)xi,n+1是產(chǎn)地Ai的儲存量，于是有：

49令：當(dāng)i=1,…，m，j=1,…，n時

當(dāng)i=1,…，m，j=n+1時將其分別代入，得到50滿足：由于這個模型中所以這是一個產(chǎn)銷平衡的運(yùn)輸問題。

若當(dāng)產(chǎn)大于銷時，只要增加一個假想的銷地j=n+1(實(shí)際上是儲存)，該銷地總需要量為

而在單位運(yùn)價表中從各產(chǎn)地到假想銷地的單位運(yùn)價為就轉(zhuǎn)化成一個產(chǎn)銷平衡的運(yùn)輸問題

.51

當(dāng)銷大于產(chǎn)時，可以在產(chǎn)銷平衡表中增加一個假想的產(chǎn)地i=m+1，該地產(chǎn)量為

在單位運(yùn)價表上令從該假想產(chǎn)地到各銷地的運(yùn)，同樣可以轉(zhuǎn)化為一個產(chǎn)銷平衡的運(yùn)輸問題.。

52

例2設(shè)有三個化肥廠(A，B，C)供應(yīng)四個地區(qū)(Ⅰ，Ⅱ，Ⅲ，Ⅳ)的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價如表3-25所示。試求出總的運(yùn)費(fèi)最節(jié)省的化肥調(diào)撥方案。

表3-25

53解這是一個產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬噸，最高需求為無限。根據(jù)現(xiàn)有產(chǎn)量，第Ⅳ個地區(qū)每年最多能分配到60萬噸，這樣最高需求為210萬噸，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個假想的化肥廠D，其年產(chǎn)量為50萬噸。由于各地區(qū)的需要量包含兩部分，如地區(qū)Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠D供給，令相應(yīng)運(yùn)價為M(任意大正數(shù))，而另一部分20萬噸滿足或不滿足均可以，因此可以由假想化肥廠D供給，按前面講的，令相應(yīng)運(yùn)價為0。對凡是需求分兩種情況的地區(qū)，實(shí)際上可按照兩個地區(qū)看待。這樣可以寫出這個問題的產(chǎn)銷平衡表(表3-26)和單位運(yùn)價表(表3-27)。54

產(chǎn)銷平衡表(表3-26),單位運(yùn)價表(表3-27)

55根據(jù)表上作業(yè)法計算，可以求得這個問題的最優(yōu)方案如表3-28所示

56練習(xí)：某制藥公司在全國設(shè)有三個生產(chǎn)基地，其中某品種藥的日產(chǎn)量為：A1廠700箱，A2廠400箱，A3廠900箱。這些生產(chǎn)基地每天將這些藥分別運(yùn)往四個地區(qū)的經(jīng)銷部門，各經(jīng)銷部門每天的需求量為：B1部門300箱，B2部門600箱，B3部門500箱，B4部門600箱。已知從每個生產(chǎn)基地到各銷售部門每箱藥品的運(yùn)價如表所示，問該制藥公司應(yīng)如何調(diào)運(yùn)，使在滿足各銷售部門需要的情況下，總的運(yùn)輸費(fèi)用最少？57表

各生產(chǎn)基地到各銷售部門每箱藥品的運(yùn)費(fèi)生產(chǎn)基地銷售部門B1B2B3B4A10.31.10.31.0A20.10.90.20.8A30.70.41.00.5（金額單位：元）58問題的運(yùn)輸表

59問題的一個基本可行解

60產(chǎn)量400和銷量300最小者(一)最小元素法61最小元素0.262最小元素0.363最小元素0.464最小元素0.5650.30.10.20.466二、解的最優(yōu)性檢驗(yàn)(一)閉回路法11=c11-c21+c23-c13=0.3-0.3+0.2-0.