運(yùn)籌學(xué)：第四章 運(yùn)輸問(wèn)題

第四章運(yùn)輸問(wèn)題第一節(jié)運(yùn)輸問(wèn)題的基本模型第二節(jié)求解初始方案的方法第三節(jié)最優(yōu)性檢驗(yàn)第四節(jié)解的改進(jìn)第五節(jié)供需不平衡及轉(zhuǎn)運(yùn)問(wèn)題第六節(jié)用Excel求解運(yùn)輸問(wèn)題案例：調(diào)度問(wèn)題第一節(jié)運(yùn)輸問(wèn)題的基本模型一、引例二、基本模型某公司經(jīng)銷(xiāo)甲產(chǎn)品，它下設(shè)三個(gè)工廠和三個(gè)銷(xiāo)售點(diǎn)。各工廠每日的產(chǎn)量和各銷(xiāo)售點(diǎn)每日的銷(xiāo)量，以及從各工廠到銷(xiāo)售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如表。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿(mǎn)足各銷(xiāo)售點(diǎn)的需求量的前提下，使總運(yùn)費(fèi)為最小。

產(chǎn)銷(xiāo)平衡和單位運(yùn)價(jià)表B1B2B3產(chǎn)量A151612A224014A33674銷(xiāo)量91011

30銷(xiāo)地單位費(fèi)產(chǎn)地運(yùn)一、引例B1B2B3產(chǎn)量A112A214A34需求量910113061502436773794其余為0?？傔\(yùn)費(fèi)=9*5+3*1+7*4+7*0+4*7=104表中的紅色數(shù)字就是滿(mǎn)足供需平衡的一組解，其總運(yùn)費(fèi)為104B1B2B3產(chǎn)量A112A214A34需求量91011306150243671110342其余為0?？傔\(yùn)費(fèi)=2*5+10*1+3*2+11*0+4*3=38表中的紅色數(shù)字就是滿(mǎn)足供需平衡的另一組解，其總運(yùn)費(fèi)為38那么問(wèn)題來(lái)了，是否還有其他解的總運(yùn)費(fèi)更小呢？運(yùn)輸問(wèn)題的提出:假設(shè)A1，A2，…，Am是生產(chǎn)某種同樣商品的生產(chǎn)點(diǎn)，其中在Ai生產(chǎn)的商品量為ai(i=1,2,…,m)個(gè)單位。在這些生產(chǎn)點(diǎn)上生產(chǎn)的商品發(fā)送到消費(fèi)點(diǎn)B1，B2，…，Bn銷(xiāo)售，其中在Bj的需求量為bj(j=1,2,…,n)個(gè)單位。假定商品可從任何生產(chǎn)點(diǎn)運(yùn)輸?shù)饺魏蜗M(fèi)點(diǎn)，而從Ai到Bj運(yùn)送單位商品的運(yùn)輸費(fèi)用為cij。問(wèn)：應(yīng)怎樣制定運(yùn)送計(jì)劃，才能使總運(yùn)輸費(fèi)用最小。二、基本模型設(shè)從Ai到Bj裝運(yùn)的貨物量為xij，則xij應(yīng)滿(mǎn)足約束條件（4.1）使總運(yùn)輸費(fèi)用C(x）達(dá)到最?。?如果在每個(gè)生產(chǎn)點(diǎn)的生產(chǎn)量等于在每個(gè)消費(fèi)點(diǎn)的需求量，即

（4.2）則稱(chēng)滿(mǎn)足約束條件（4.1）、（4.2）的運(yùn)輸問(wèn)題為供需平衡模型的運(yùn)輸問(wèn)題。首先假設(shè)xij：表示從起點(diǎn)Ai運(yùn)送到終點(diǎn)Bj的貨物數(shù)量，i=1，2，3；j=1，2，3：從A1運(yùn)輸貨物的成本

TC1=5x11+x12+6x13；從A2運(yùn)輸貨物的成本TC2=2x21+4x22+0x23；從A3運(yùn)輸貨物的成本TC3=3x31+6x32+7x33用x11+x12+x13表示從A1運(yùn)出的貨物總量，則有：

x11+x12+x13=12；同理可得：

x21+x22+x23=14A2的供給量；x31+x32+x33=4A3的供給量；建立模型:同樣三個(gè)需求點(diǎn)的需求量的約束條件為：x11+x21+x31=9；x12+x22+x32=10；x13+x23+x33=11；總運(yùn)輸成本為T(mén)C=TC1+TC2+TC3；建立模型:

minTCs.t.x11+x12+x13=12；x21+x22+x23=14；x31+x32+x33=4；x11+x21+x31=9；x12+x22+x32=10；x13+x23+x33=11；xij≥0；i=1，2，3；j=1，2，3。最優(yōu)決策數(shù)學(xué)模型：運(yùn)輸問(wèn)題的一般模式

目標(biāo)函數(shù)供給約束需求約束非負(fù)約束一般運(yùn)輸問(wèn)題的基本原則最小化所有運(yùn)輸費(fèi)用之和供給=需求產(chǎn)品是離散計(jì)量的要求運(yùn)輸量是整數(shù)個(gè)單位產(chǎn)品線性約束計(jì)算過(guò)程：1．尋找初始可行解；2．檢查是否已達(dá)到最優(yōu)。若已是最優(yōu)或無(wú)可行解，則結(jié)束；3．進(jìn)一步改善目前的解；其中，兩種確定初始可行解的方法：（1）西北角方法（2）最小元素法第二節(jié)求解初始方案的方法產(chǎn)銷(xiāo)平衡和單位運(yùn)價(jià)表運(yùn)輸問(wèn)題例子

銷(xiāo)地B1B2B3B4產(chǎn)量A1108121140A2111415960A3161418745銷(xiāo)量50253535單位運(yùn)費(fèi)產(chǎn)地16B1B2B3B4產(chǎn)量A140A260A345需求量50253535145101611141418157912811一、西北角方法

（求平衡運(yùn)輸問(wèn)題初始解方法）西北角方法將min{a,b}賦值給空格(A1,B1)17B1B2B3B4產(chǎn)量A140A260A345需求量50253535145101611141418157912811402525103510求初始解35/102550/1045/3560/50/254035一、西北角方法

（求平衡運(yùn)輸問(wèn)題初始解方法）由此可得初始基可行解x11=40，x21=10，x22=25，x23=10，x33=10，x34=35，其余全是0。該運(yùn)輸方案的運(yùn)輸費(fèi)用=10×40+11×10+25×14+25×15+10×18+35×7=166018二、最小元素法

（求平衡運(yùn)輸問(wèn)題初始解方法）B1B2B3B4產(chǎn)量A1③15②25(40)(15)0A2④35⑤25(60)(25)0A3⑥10①35(45)(10)0需求量(50)(35)0(25)0(35)(10)0(35)0145101411118129151814167由此可得初始基可行解x11=15，x12=25，x21=35，x23=25，x33=10，x34=35，其余全為0。該運(yùn)輸方案的運(yùn)輸費(fèi)用=1535。西北角法得到初始方案：x11=40，x21=10，x22=25，x23=10，x33=10，x34=35，其余全是0?？傔\(yùn)費(fèi)=10×40+11×10+25×14+25×15+10×18+35×7=1660（元）最小元素法得到初始方案：x11=15，x12=25，x21=35，x23=25，x33=10，x34=35，其余全為0。該運(yùn)輸方案的運(yùn)輸費(fèi)用=1535。（元）兩種方法結(jié)果比較：求初始基本可行解時(shí)注意的問(wèn)題取定xij的值之后，會(huì)出現(xiàn)Ai的產(chǎn)量與Bj的銷(xiāo)量都改為零的情況，這時(shí)只能劃取Ai行或Bj列，不能同時(shí)劃取行和列。用最小元素法時(shí)，可能出現(xiàn)只剩一行或一列的所有格均未填數(shù)或未劃掉，此時(shí)在這一行或這一列中除已填上數(shù)的格外均填上零，不能按空格劃掉，要保證填過(guò)數(shù)的格為m+n-1，即基變量的個(gè)數(shù)為m+n-1個(gè)。B1B2B3B4B5產(chǎn)量A171086440A259712640A336581190銷(xiāo)量30406020201701078864665539712114030060200206000200000非零基變量個(gè)數(shù)=5；m+n-1=3+5-1=7例如下列例子：非零基變量個(gè)數(shù)<m+n-1B1B2B3B4B5產(chǎn)量A171086440A259712640A336581190銷(xiāo)量3040602020170107886466553971211403006020020600002000000填數(shù)的格子必須為3+5-1=7個(gè)，基變量的個(gè)數(shù)B1B2B3B4B5產(chǎn)量A1

7

10

8

6

440A2

5

9

7

12

640A3

3

6

5

8

1190銷(xiāo)量3040602020170107886466553971211403020600200第三節(jié)最優(yōu)性檢驗(yàn)由西北角法和最小元素法得到的解需要檢驗(yàn)是否為最優(yōu)解。如何檢驗(yàn)？下面給出兩種檢驗(yàn)的方法：（1）閉合回路法（2）位勢(shì)法一、閉回路法：初始解第一次變化平衡運(yùn)輸問(wèn)題的最優(yōu)解；；；按照同樣方法可得到表中其它空格的檢驗(yàn)數(shù)。由于

所以表4-9中得到的解不是最優(yōu)解。閉回路具有如下特征：①除起點(diǎn)（終點(diǎn)）外，其余頂點(diǎn)都在有數(shù)字的格中；②回路的邊是水平線段和垂直線；③任一行或列中，若有頂點(diǎn)，則有且僅有兩個(gè)。由閉合回路法檢驗(yàn)解是否為最優(yōu)，就要計(jì)算每個(gè)空格的檢驗(yàn)數(shù)，當(dāng)空格數(shù)較多時(shí)，計(jì)算量將很大，為此可采用下面的位勢(shì)法。

閉回路例子：例3.1B1B2B3B4產(chǎn)量A1826711242A213105493

73A3534381263銷(xiāo)量5234517產(chǎn)地銷(xiāo)地用最小元素法對(duì)例中的產(chǎn)銷(xiāo)平衡表求初始解該例有3個(gè)產(chǎn)地，4個(gè)銷(xiāo)地，所以應(yīng)該有3+4-1=6個(gè)基變量，即初始解有6個(gè)數(shù)字格，符合要求表中的紅色數(shù)字為初始解，可計(jì)算對(duì)應(yīng)運(yùn)費(fèi)為z=112元3343322232在已經(jīng)求得初始解的產(chǎn)銷(xiāo)平衡表上作閉回路的方法任選一個(gè)空格（沒(méi)有運(yùn)量的格），可以且只可以作一條閉回路，將其起點(diǎn)所在格的單位運(yùn)價(jià)按一正一負(fù)依次計(jì)算，若所有結(jié)果為非負(fù)，說(shuō)明這個(gè)方案已經(jīng)是最優(yōu)；若結(jié)果存在負(fù)數(shù)，說(shuō)明這個(gè)方案不是最優(yōu)，負(fù)的那條閉回路還可以調(diào)整，使總運(yùn)費(fèi)減少！74-1二、位勢(shì)法

考慮下列供需平衡的運(yùn)輸問(wèn)題設(shè)B是的初始基矩陣。對(duì)偶問(wèn)題為：對(duì)偶問(wèn)題的解決策變量xij的系數(shù)向量為：所有基變量的檢驗(yàn)數(shù)等于0。即

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

ui,vj當(dāng)所有非基變量（即空格）的檢驗(yàn)數(shù)大于零時(shí)為最優(yōu)解34以例4.1為例來(lái)說(shuō)明計(jì)算過(guò)程。在例4.1中由最小元素法得到的初始解中，x11，x12，x21，x23，x33，x34是基變量。這時(shí)對(duì)應(yīng)的檢驗(yàn)數(shù)是：由上表和計(jì)算非基變量（即空格）的檢驗(yàn)數(shù)得：位勢(shì)法判別最優(yōu)V1=0U1=8U3=5V2=-1V4=3U2=6V3=-1778456-104455在已經(jīng)用最小元素法求得初始解的產(chǎn)銷(xiāo)平衡表上，任選一個(gè)數(shù)字格（有運(yùn)量的格），讓其行位勢(shì)或列位勢(shì)取0（也可取任意數(shù)值，但取0運(yùn)算最簡(jiǎn)單，最后結(jié)果一樣！），可以依次求得其他數(shù)字格的行位勢(shì)和列位勢(shì)，從而可求得空格的位勢(shì)！用空格的單位運(yùn)價(jià)減求得的位勢(shì)，就得其空格的檢驗(yàn)數(shù)，結(jié)果和判別標(biāo)準(zhǔn)同閉回路法！第四節(jié)解的改進(jìn)當(dāng)所有的非基本變量檢驗(yàn)數(shù)大于等于零時(shí)，為最優(yōu)解。否則改進(jìn)該解。其步驟如下：（1）確定調(diào)整格取最小負(fù)檢驗(yàn)數(shù)，對(duì)應(yīng)的變量作為進(jìn)基變量，相應(yīng)格稱(chēng)為調(diào)整格。（2）確定改進(jìn)路線以該空格為第一奇數(shù)頂點(diǎn)，沿閉回路的逆時(shí)針?lè)较蚯斑M(jìn)，對(duì)閉回路上的頂點(diǎn)依此編號(hào)。（3）在閉回路上的所有偶數(shù)頂點(diǎn)中，找出運(yùn)輸量最小的頂點(diǎn)(格子)，以該格中的變量為換出變量。（4）以閉回路上的最小運(yùn)量為調(diào)整量，將該閉回路上所有奇數(shù)頂點(diǎn)處的運(yùn)輸量都增加這一個(gè)數(shù)值，所有偶數(shù)頂點(diǎn)處的運(yùn)輸量減去這一數(shù)值，從而得到一個(gè)新的運(yùn)輸方案。然后，再對(duì)得到的新解進(jìn)行最優(yōu)性檢驗(yàn)，如不是最優(yōu)解，重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，直至得到最優(yōu)解為止。

下面結(jié)合例4.1給出解改進(jìn)的步驟：因最小負(fù)檢驗(yàn)數(shù)為，故以x13為起點(diǎn)，依此x11,x12,x23

為頂點(diǎn)得到一閉回路，見(jiàn)表4-11，表中小括弧中的數(shù)為非基變量的檢驗(yàn)數(shù)，中括弧中的數(shù)為最小負(fù)檢驗(yàn)數(shù)。表4-11利用閉回路對(duì)原方案進(jìn)行調(diào)整-1上面求了空格的檢驗(yàn)數(shù)后，發(fā)現(xiàn)只有A1B2格的檢驗(yàn)數(shù)為-1，說(shuō)明未達(dá)最優(yōu)。于是以這格為

起點(diǎn)作一個(gè)閉回路，該回路上的每個(gè)單位運(yùn)量還可以減少一個(gè)單位運(yùn)價(jià)！因此需盡量多的調(diào)整一些運(yùn)量到這個(gè)空格（此格最多可以調(diào)2，運(yùn)費(fèi)將減少2）。而其他格子不會(huì)受到影響。這樣得到一個(gè)新解，繼續(xù)檢驗(yàn)！2015記x13為第一個(gè)奇數(shù)頂點(diǎn)，則

分別為第二、四個(gè)偶數(shù)頂點(diǎn)。因?yàn)?3因此以15為調(diào)整量，做如下調(diào)整：偶數(shù)頂點(diǎn)減15；奇數(shù)頂點(diǎn)加15，得表4-12

經(jīng)上述調(diào)整后，原基變量

變?yōu)榉腔兞?，非基變?/p>

變?yōu)榛兞?。由此得到新的基變量為：x12，x13，x21，x23，x33，x34。再用位勢(shì)計(jì)算各檢驗(yàn)數(shù)知，所有檢驗(yàn)數(shù)均大于等于零，故得到最優(yōu)解：x12=25，x13=15，x21=50，x23=10，x33=10，x34=35，其余為0。總運(yùn)價(jià)為：44例4.3.某公司經(jīng)銷(xiāo)某產(chǎn)品，它下設(shè)三個(gè)工廠和四個(gè)銷(xiāo)售點(diǎn)。各工廠每日的產(chǎn)量和各銷(xiāo)售點(diǎn)每日的銷(xiāo)量，以及從各工廠到銷(xiāo)售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如表4-13。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿(mǎn)足各銷(xiāo)售點(diǎn)的需求量的前提下，使總運(yùn)費(fèi)為最小。45931218993129946解：使用最小元素法得到一個(gè)調(diào)運(yùn)方案，如表4-14，總費(fèi)用為516元。

由單純形法得知所有基變量x23，x34，x21，x32，x13，x14的檢驗(yàn)數(shù)等于0。即47可解得：U1=0V3=6V4=20U2=-2V1=4U3=-10V2=18

在表4-15上增加一行一列，在列中填入,在行中填入，得表4-164849

在表4-17中還有負(fù)數(shù)檢驗(yàn)（價(jià)值系數(shù)）數(shù)(見(jiàn)表4-17中小括號(hào)中的數(shù))，說(shuō)明未得到最優(yōu)解，用閉回路法調(diào)整改進(jìn)。選空格處的最小負(fù)檢驗(yàn)數(shù)格（2，4）為調(diào)入格。以此格為出發(fā)點(diǎn)，作一閉回路，如表4-18所示：50

（2，4）格的調(diào)入量

是選擇閉回路上具有（-3）的數(shù)組格中的最小者，即=min{3,9}=3。然后按照閉回路上的正、負(fù)號(hào)，加入和減去此值，得到調(diào)整方案，如表4-19所示。51表4-19中的所有檢驗(yàn)數(shù)都非負(fù)，故表中的解為最優(yōu)解。第五節(jié)供需不平衡及轉(zhuǎn)運(yùn)問(wèn)題一、供需不平衡問(wèn)題二、轉(zhuǎn)運(yùn)問(wèn)題一、供需不平衡問(wèn)題供大于求通過(guò)設(shè)立虛擬的銷(xiāo)售點(diǎn)來(lái)完成，要求各個(gè)供應(yīng)點(diǎn)到各個(gè)虛擬的銷(xiāo)售點(diǎn)的運(yùn)價(jià)為M，可以保證先滿(mǎn)足實(shí)際的銷(xiāo)售點(diǎn)的需求。供小于求通過(guò)設(shè)立虛擬的供應(yīng)點(diǎn)來(lái)完成，要求各個(gè)虛擬的供應(yīng)點(diǎn)到各個(gè)的銷(xiāo)售點(diǎn)的運(yùn)價(jià)為M，可以保證先滿(mǎn)足銷(xiāo)售點(diǎn)的實(shí)際需求。1．當(dāng)供大于求，即時(shí)，其運(yùn)輸模型為：2．當(dāng)供小于求，即時(shí)，其運(yùn)輸模型為：

例4.4.四個(gè)化工廠生產(chǎn)甲、乙、丙、丁產(chǎn)品，產(chǎn)量分別為200，300，400，100（噸），供應(yīng)A，B，C，D，E，F(xiàn)地區(qū)，其需要為200，150，400，100，150，150（噸）。各廠每千克產(chǎn)品成本分別為1.2，1.4，1.1，1.5（元），各地區(qū)銷(xiāo)售價(jià)分別為每千克2.0，2.4，1.8，2.2，1.6，2.0（元）。已知從各廠運(yùn)往各銷(xiāo)售地區(qū)每千克產(chǎn)品運(yùn)價(jià)如表4-20所示：將綜合表內(nèi)的元素轉(zhuǎn)化為單位利潤(rùn)（單位利潤(rùn)＝單位售價(jià)－單位成本－單位運(yùn)價(jià)），如表4-22所示58因?yàn)槭卿N(xiāo)大于產(chǎn)的問(wèn)題，所以要加入一行，其產(chǎn)量為銷(xiāo)量與產(chǎn)量的差額，并根據(jù)題意，將需求方的需要量分為兩種，必須滿(mǎn)足的和可能滿(mǎn)足的，則虛擬的產(chǎn)地就不能供應(yīng)到必須滿(mǎn)足的需求地，因此其利潤(rùn)為－Ｍ（M是充分大的正數(shù)），而供應(yīng)到其他位置的利潤(rùn)為0，得到表4-23。59用最?。ù螅┰胤ㄇ蟪跏挤桨?，用位勢(shì)法計(jì)算檢驗(yàn)數(shù)，分別得表4-24和4-25。60有檢驗(yàn)數(shù)大于零，調(diào)整運(yùn)量，計(jì)算檢驗(yàn)數(shù)，經(jīng)過(guò)兩次運(yùn)算得到表4-26和4-27。61得到最優(yōu)方案，最大利潤(rùn)為maxz=200×0.3＋50×0.8＋100×0.5＋100×0.4＋300×0.4＋100×0.3＋150×０＋150×0.7=445二、轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)運(yùn)問(wèn)題是運(yùn)輸問(wèn)題的擴(kuò)充，貨物從生產(chǎn)點(diǎn)運(yùn)到轉(zhuǎn)運(yùn)點(diǎn)，然后再?gòu)霓D(zhuǎn)運(yùn)點(diǎn)運(yùn)往需求點(diǎn)。在實(shí)際問(wèn)題中轉(zhuǎn)運(yùn)點(diǎn)可以是倉(cāng)庫(kù)等。例：有一電子公司，其生產(chǎn)線在A1、A2兩地，在每個(gè)生產(chǎn)線出產(chǎn)的部件可能被運(yùn)送到公司在B1、B2兩地的任一個(gè)倉(cāng)庫(kù)。然后從這兩個(gè)倉(cāng)庫(kù)向C1、C2、C3、C4四個(gè)城市的零售點(diǎn)發(fā)貨。每一條發(fā)貨線路上每一個(gè)部件的運(yùn)輸成本見(jiàn)表1和2。產(chǎn)地和零售點(diǎn)的生產(chǎn)量和需求量見(jiàn)表3。如何運(yùn)輸費(fèi)用最小？

倉(cāng)庫(kù)生產(chǎn)線

B1B2

A123A231表1

需求點(diǎn)

C1C2C3C4B12636B2

4461表2生產(chǎn)線生產(chǎn)量A1600A2400需求點(diǎn)需求量C1

200C2