運籌學(xué)：第四章 運輸問題

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

產(chǎn)銷平衡和單位運價表B1B2B3產(chǎn)量A151612A224014A33674銷量91011

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

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

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

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

x21+x22+x23=14A2的供給量；x31+x32+x33=4A3的供給量；建立模型:同樣三個需求點的需求量的約束條件為：x11+x21+x31=9；x12+x22+x32=10；x13+x23+x33=11；總運輸成本為TC=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é)模型：運輸問題的一般模式

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

銷地B1B2B3B4產(chǎn)量A1108121140A2111415960A3161418745銷量50253535單位運費產(chǎn)地16B1B2B3B4產(chǎn)量A140A260A345需求量50253535145101611141418157912811一、西北角方法

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

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

（求平衡運輸問題初始解方法）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。該運輸方案的運輸費用=1535。西北角法得到初始方案：x11=40，x21=10，x22=25，x23=10，x33=10，x34=35，其余全是0。總運費=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。該運輸方案的運輸費用=1535。（元）兩種方法結(jié)果比較：求初始基本可行解時注意的問題取定xij的值之后，會出現(xiàn)Ai的產(chǎn)量與Bj的銷量都改為零的情況，這時只能劃取Ai行或Bj列，不能同時劃取行和列。用最小元素法時，可能出現(xiàn)只剩一行或一列的所有格均未填數(shù)或未劃掉，此時在這一行或這一列中除已填上數(shù)的格外均填上零，不能按空格劃掉，要保證填過數(shù)的格為m+n-1，即基變量的個數(shù)為m+n-1個。B1B2B3B4B5產(chǎn)量A171086440A259712640A336581190銷量30406020201701078864665539712114030060200206000200000非零基變量個數(shù)=5；m+n-1=3+5-1=7例如下列例子：非零基變量個數(shù)<m+n-1B1B2B3B4B5產(chǎn)量A171086440A259712640A336581190銷量3040602020170107886466553971211403006020020600002000000填數(shù)的格子必須為3+5-1=7個，基變量的個數(shù)B1B2B3B4B5產(chǎn)量A1

7

10

8

6

440A2

5

9

7

12

640A3

3

6

5

8

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例4.4.四個化工廠生產(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ū)銷售價分別為每千克2.0，2.4，1.8，2.2，1.6，2.0（元）。已知從各廠運往各銷售地區(qū)每千克產(chǎn)品運價如表4-20所示：將綜合表內(nèi)的元素轉(zhuǎn)化為單位利潤（單位利潤＝單位售價－單位成本－單位運價），如表4-22所示58因為是銷大于產(chǎn)的問題，所以要加入一行，其產(chǎn)量為銷量與產(chǎn)量的差額，并根據(jù)題意，將需求方的需要量分為兩種，必須滿足的和可能滿足的，則虛擬的產(chǎn)地就不能供應(yīng)到必須滿足的需求地，因此其利潤為－Ｍ（M是充分大的正數(shù)），而供應(yīng)到其他位置的利潤為0，得到表4-23。59用最?。ù螅┰胤ㄇ蟪跏挤桨福梦粍莘ㄓ嬎銠z驗數(shù)，分別得表4-24和4-25。60有檢驗數(shù)大于零，調(diào)整運量，計算檢驗數(shù)，經(jīng)過兩次運算得到表4-26和4-27。61得到最優(yōu)方案，最大利潤為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)運問題轉(zhuǎn)運問題是運輸問題的擴(kuò)充，貨物從生產(chǎn)點運到轉(zhuǎn)運點，然后再從轉(zhuǎn)運點運往需求點。在實際問題中轉(zhuǎn)運點可以是倉庫等。例：有一電子公司，其生產(chǎn)線在A1、A2兩地，在每個生產(chǎn)線出產(chǎn)的部件可能被運送到公司在B1、B2兩地的任一個倉庫。然后從這兩個倉庫向C1、C2、C3、C4四個城市的零售點發(fā)貨。每一條發(fā)貨線路上每一個部件的運輸成本見表1和2。產(chǎn)地和零售點的生產(chǎn)量和需求量見表3。如何運輸費用最?。?/p>

倉庫生產(chǎn)線

B1B2

A123A231表1

需求點

C1C2C3C4B12636B2

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

200C2