運(yùn)輸問題模型與算法

4運(yùn)輸問題—數(shù)學(xué)模型及其解法

4.1運(yùn)輸問題數(shù)學(xué)模型

4.2運(yùn)輸問題的求解方法

4.3對解進(jìn)行檢驗(yàn)及改進(jìn)

4.4運(yùn)輸問題的進(jìn)一步討論

4.5應(yīng)用問題舉例

P&T公司的配送問題案例Figure1LocationofthecanneriesandwarehousesfortheP&TCompanyproblem.運(yùn)輸數(shù)據(jù)CanneryOutputWarehouseAllocationBellingham75truckloadsSacramento80truckloadsEugene125truckloadsSaltLakeCity65truckloadsAlbertLea100truckloadsRapidCity70truckloadsTotal300truckloadsAlbuquerque85truckloadsTotal300truckloads目前的運(yùn)輸計劃WarehouseFrom\ToSacramentoSaltLakeCityRapidCityAlbuquerqueCanneryBellingham75000Eugene565550AlbertLea001585卡車的運(yùn)輸成本W(wǎng)arehouseFrom\ToSacramentoSaltLakeCityRapidCityAlbuquerqueCanneryBellingham$464$513$654$867Eugene352416690791AlbertLea995682388685總的運(yùn)輸成本=75($464)+5($352)+65($416)+55($690)+15($388)+85($685)

=$165,595運(yùn)輸問題的特點(diǎn)供應(yīng)/需求假設(shè)每一個出發(fā)地都有一個固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地。每一個目的地都有一個固定得需求量，整個需求量都必須由出發(fā)地滿足?？尚薪獾奶匦援?dāng)且僅當(dāng)供應(yīng)量的總和等于需求量的總和時，運(yùn)輸問題才有可行解。成本假設(shè)從任何一個出發(fā)地到任何一個目的地的貨物配送成本和所配送的數(shù)量成線性比例關(guān)系。這個成本就等于配送的單位成本乘以所配送的數(shù)量。網(wǎng)絡(luò)表示4.1運(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)銷平衡設(shè)xij表示產(chǎn)地i

運(yùn)往銷地j

的物資量，wij表示對應(yīng)的單位運(yùn)費(fèi)，則我們有運(yùn)輸問題的數(shù)學(xué)模型如下：運(yùn)輸問題有mn個決策變量，m+n

個約束條件。由于產(chǎn)銷平衡條件，只有m+n–1個相互獨(dú)立，因此，運(yùn)輸問題的基變量只有m+n–1個.例1某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200

xij≥0(i=1、2；j=1、2、3）運(yùn)輸問題有有限最優(yōu)解約束條件非常有規(guī)律，技術(shù)系數(shù)非0即1平衡運(yùn)輸問題數(shù)學(xué)模型特點(diǎn)m行n行每個變量Xij對應(yīng)的矩陣列中,除第i個元素和第m+j個元素為1外,其余元素為零.每行有n個1，其余為0。所有結(jié)構(gòu)的約束條件是等式約束各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和運(yùn)輸問題的解解滿足所有的約束條件;基變量對應(yīng)的約束方程組的系數(shù)列向量線性無關(guān);解中非零變量Xij的個數(shù)不能大于(m+n-1)個;為使迭代求解順利進(jìn)行,基變量的個數(shù)在迭代過程中保持為(m+n-1)個;基變量的個數(shù)遠(yuǎn)小于決策變量的個數(shù).4.2運(yùn)輸問題的求解方法采用表上作業(yè)法，稱為位勢法運(yùn)算中涉及兩個表：運(yùn)費(fèi)表和產(chǎn)銷平衡表(分配表)運(yùn)費(fèi)表分配表尋找初始可行解的方法

1、西北角法從x11開始分配，從西北向東南方向逐個分配xij

的分配公式例2

例4.2.1西北角法

2、最低費(fèi)用法

采用最小費(fèi)用優(yōu)先分配的原則f(x)=121，費(fèi)用比西北角法低84

3、運(yùn)費(fèi)差額法（沃格爾法-Volge）最小元素法初看十分合理。但是，有時按某一最小單位運(yùn)價優(yōu)先安排物品調(diào)運(yùn)時，卻可能導(dǎo)致對其它代銷點(diǎn)配送時費(fèi)用更高，從而使總費(fèi)用增加。對每一個供銷地或銷售地，均可由它到各銷售地或各供應(yīng)地的單位運(yùn)價中找出最小單位運(yùn)價和次小單位運(yùn)價，并稱這兩個單位運(yùn)價之差為該供應(yīng)地或銷售地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小單位運(yùn)價安排運(yùn)輸時造成的運(yùn)費(fèi)損失不大；反之，如果罰數(shù)的值很大，不按最小運(yùn)價組織運(yùn)輸就會造成很大的損失，故應(yīng)盡量按最小單位運(yùn)價安排運(yùn)輸。采用最大差額費(fèi)用(即利用每行或列中最小費(fèi)用與次最小之間的差額中選最大)優(yōu)先分配的原則。f(x)=98，比最低費(fèi)用法又低了23

某種物品先放在A1、A2和A3三個倉庫中，再運(yùn)往使用地B1、B2、B3和B4，其間的距離（或單位運(yùn)價）如下表所示，各倉庫的存量和使用地的需要量也都表示于下表中，試建立使總運(yùn)輸費(fèi)用最小的運(yùn)輸問題數(shù)學(xué)模型。用前面講的三種方法分別求可行解用上面的三種表上作業(yè)法，求下列運(yùn)輸問題的解

銷地產(chǎn)地B1B2B3B3產(chǎn)量A116A210A322銷量81412144124112103985116表1用上面的三種求下列運(yùn)輸問題的解

銷地產(chǎn)地B1B2B3B3產(chǎn)量A18816A26410A381422銷量81412144124112103985116用西北角法求的可行解表2412用上面的三種求下列運(yùn)輸問題的解

銷地產(chǎn)地B1B2B3B3產(chǎn)量A110616A28210A314822銷量81412144124112103985116用最小元素法求的可行解表3用上面的三種求下列運(yùn)輸問題的解

銷地產(chǎn)地B1B2B3B3產(chǎn)量A112416A28210A314822銷量81412144124112103985116用沃爾格法求的可行解表44.3對解的可行性進(jìn)行檢驗(yàn)

運(yùn)輸表中的格子是空的,則代表是非基變量.若存在非基變量的檢驗(yàn)數(shù)小于零,說明得到的解不是最優(yōu)解！運(yùn)輸問題常用的解檢驗(yàn)方法有2種：閉回路法；位勢法

銷地產(chǎn)地B1B2B3B3產(chǎn)量A110616A28210A314822銷量81412144124112103985116檢驗(yàn)用最小元素法求的可行解（下表）是否最優(yōu)表34.3.1利用閉回路法檢驗(yàn)分配方案是否最優(yōu)運(yùn)量表中的空格中無數(shù)字，表示該空格所對應(yīng)的變量為非基變量。判斷運(yùn)輸問題的解是否是最優(yōu)解，可以參照單純形法，非基變量的檢驗(yàn)數(shù)是否均大于等于0。如何計算檢驗(yàn)數(shù)？某一非基變量值調(diào)整為1個單位，為保證供需平衡，閉回路（除1個非基變量外，其它頂點(diǎn)上均為基變量）上的基變量值做相應(yīng)的調(diào)整，由此而出現(xiàn)的運(yùn)費(fèi)變化值為檢驗(yàn)數(shù)。閉回路形式有：4.3.1利用閉回路法檢驗(yàn)分配方案是否最優(yōu)表3中的可行解用閉回路法計算的檢驗(yàn)數(shù)

銷地產(chǎn)地B1B2B3B3產(chǎn)量A112A21-1A31012銷量因X23的檢驗(yàn)數(shù)小于0，表3的調(diào)運(yùn)方案不是最優(yōu)解表5

4.3.2利用位勢法檢驗(yàn)分配方案是否最優(yōu)思路：不用閉回路法，如何獲得xij的檢驗(yàn)數(shù)?找到原問題的基礎(chǔ)可行解，保持互補(bǔ)松弛條件:(YA-C)X=0，求出對應(yīng)對偶問題的解。若該對偶問題的解非可行，則原問題的解不是最優(yōu)解；否則，達(dá)到最優(yōu)解。復(fù)習(xí)：若X,Y分別為(P),(D)的可行解，則X,Y為最優(yōu)解的充要條件是：利用位勢法檢驗(yàn)分配方案是否最優(yōu)

平衡運(yùn)輸問題數(shù)學(xué)模型

平衡運(yùn)輸問題的對偶問題uivj對偶變量動輸問題變量的檢驗(yàn)數(shù)表示為:設(shè)已得到運(yùn)輸問題的基可行解,其基變量是:

由于基變量的檢驗(yàn)數(shù)等于0,故對于這組基變量可寫出方程組:

可以證明上面的方程有解,且由于對偶變量數(shù)比方程數(shù)多一個,故解不唯一.稱上面方程的解為位勢.

對上面的方程組求解,然后計算運(yùn)輸問題的檢驗(yàn)數(shù),若有檢驗(yàn)數(shù)小于零,則原運(yùn)輸問題的解不是最優(yōu)解.

位勢法的原理為滿足互補(bǔ)松弛條件，原問題中xij被選為基變量，即xij0，則要求對偶問題中ui+vj=cij，即該行的松弛變量為0共有m+n1個基變量xij

，因此可得m+n1個等式ui+vj=cijm+n1個等式中有m+n個變量ui

和vj

（？），因此，令任一個ui

或vj=0，從而解出其它m+n1個的值；這就是位勢法若對所有非基變量有cij

(ui

+vj)

0，即ui

+vjcij，表明當(dāng)前ui

和vj

是對偶問題的可行解，由互補(bǔ)松弛定理可知當(dāng)前m+n1個基變量xij

是最優(yōu)解，否則從cij

(ui

+vj)<0中找最小者，對應(yīng)xij

就是入變量

銷地產(chǎn)地B1B2B3B4產(chǎn)量A110616A28210A314822銷量81412144124112103985116檢驗(yàn)用最小元素法求的可行解（下表）是否最優(yōu)表3利用位勢法檢驗(yàn)計算位勢根據(jù)基變量的檢驗(yàn)數(shù)為0，有下面的方程令U2=0,得各變量的值為：V1=2,V3=3,U1=1,V4=10U3=-4,V2=9

銷地產(chǎn)地B1B2B3B4uiA1121A21-10A31012-4vj293104124112103985116檢驗(yàn)用最小元素法求的可行解（下表）是否最優(yōu)表6利用位勢法檢驗(yàn)4.3.3解的改進(jìn)

運(yùn)輸問題中,若某一非基變量的檢驗(yàn)數(shù)小于零,說明這個非基變量作為基變量時,運(yùn)輸費(fèi)用將更小.因而當(dāng)前解不是最優(yōu)解.用閉回路法進(jìn)行調(diào)整.

將檢驗(yàn)數(shù)最小的非基變量作為換入變量,找出它在運(yùn)輸表中的閉回去路,取閉回路中所有偶數(shù)點(diǎn)中最小運(yùn)量,在所有奇數(shù)點(diǎn)上都增加這一最小運(yùn)量,在所有偶數(shù)點(diǎn)上減少這一最小運(yùn)量.

然后,再對調(diào)整后的解進(jìn)行最優(yōu)性檢驗(yàn),如不是最優(yōu)解,就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整,一直到得出最優(yōu)解為止.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A110+26-216A282-2+210A314822銷量81412144124112103985116改進(jìn)用最小元素法求的可行解把x24作為進(jìn)基變量表7目標(biāo)函數(shù)值z=244

銷地產(chǎn)地B1B2B3B4uiA1021240A28212-2A3914128-5vj4104114124112103985116再次進(jìn)行最優(yōu)性檢驗(yàn)，并將非基變量檢驗(yàn)數(shù)填在表格上中（紅色帶圈數(shù)字）：表8表中解為最優(yōu)解！4.3.4需要說明的幾個問題若運(yùn)輸問題的某一可行解有幾個非基變量的檢驗(yàn)數(shù)均為負(fù),在繼續(xù)進(jìn)行迭代時,取它們中的任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善,但通常取檢驗(yàn)數(shù)小于零中最小者對應(yīng)的變量為換入變量.當(dāng)?shù)竭\(yùn)輸問題有最優(yōu)解時,如果有某非基變量的檢驗(yàn)數(shù)等于零,則說明該運(yùn)輸問題有無窮多最優(yōu)解.當(dāng)運(yùn)輸問題某部分產(chǎn)地的產(chǎn)量和,與某一部分銷地的銷量和相等時,在迭代過程中有可能在某個格填入一個運(yùn)量時需要同時劃去運(yùn)輸表的一行和一列,這時就出現(xiàn)了退化.在運(yùn)輸問題中,退化解是時常發(fā)生的,為了使一表上作業(yè)法的迭代工作進(jìn)行下去,退化時在同時劃去一行或一列的某個格中填入數(shù)字0,表示這個格中的變量是取值為0的基變量,使迭代過程中可行解的分量恰好為(m+n-1)個.4.4運(yùn)輸問題的進(jìn)一步討論4.4.1產(chǎn)銷不平衡

1)供過于求，即a

i>bj.數(shù)學(xué)模型為:

為借助于產(chǎn)銷平衡時的表上作業(yè)法求解,可增加一個假想的銷地Bn+1,由于實(shí)際上它不存在,因而由產(chǎn)地Ai(i=1,2,…,m)調(diào)運(yùn)到這個假想銷地的物品數(shù)量xi,n+1(相當(dāng)于松馳變量),實(shí)際上是就地存貯在Ai的物品數(shù)量.就地存貯的物品不經(jīng)運(yùn)輸,故其單位運(yùn)費(fèi)ci,n+1=0(i=1,2,…,m)令假想銷地的銷量為bn+1,且

注意相對應(yīng)的運(yùn)輸表!4.4.1產(chǎn)銷不平衡

1)供不應(yīng)求，即ai<bj.假想產(chǎn)地Am+1,它的產(chǎn)量等于:

由于這個假想的產(chǎn)地不存在,求出的由它發(fā)往各個銷地的物品數(shù)量xm+1,j(j=1,2,…,n),實(shí)際上是各銷地所需物品的欠缺額,顯然有:例某市有三個造紙廠A1、A2、A3，其紙的產(chǎn)量分別為8、5和9個單位。有4個集中用戶，其需要量分別是4、3、5和6個單位。由各造紙廠到各用戶的單位運(yùn)輸價格如下表所示，請確定總運(yùn)費(fèi)最小的調(diào)運(yùn)方案。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A18A25A39銷量435631234112596715

假定m個產(chǎn)地A1,A2,…,Am

和n銷地B1,B2,…,Bn

都可以作為中間轉(zhuǎn)運(yùn)站使用，從而發(fā)送物品的地點(diǎn)和接收物品的地點(diǎn)都有m+n個，這就是轉(zhuǎn)運(yùn)問題。為建立數(shù)學(xué)模型，令：4.4.2有轉(zhuǎn)運(yùn)的運(yùn)輸問題ai:第i個產(chǎn)地的產(chǎn)量（凈供應(yīng)量）；bj:第j個銷地的銷量（凈需要量）；Xij:由第i個發(fā)送地運(yùn)到第j個接收地的物品數(shù)量；cij

:由第i個發(fā)送地到第j個接收地的單位運(yùn)價；ti:第i個地點(diǎn)轉(zhuǎn)運(yùn)物品的數(shù)量；ci:第i個地點(diǎn)轉(zhuǎn)運(yùn)物品的費(fèi)用。

現(xiàn)將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面，銷地排在后面，則有：am+1=am+2=…=am+n=0b1=b2=…=bm=0假定為平衡運(yùn)輸問題，即有有轉(zhuǎn)運(yùn)的運(yùn)輸問題有轉(zhuǎn)運(yùn)的運(yùn)輸問題的數(shù)學(xué)模型令：

將上式中各約束條件中的ti或tj移到等式左側(cè)，然后兩側(cè)加上Q并令：有下面的運(yùn)輸表達(dá)式：有轉(zhuǎn)運(yùn)的運(yùn)輸問題的運(yùn)量表

接收發(fā)送產(chǎn)地銷地發(fā)送量1…mm+1…m+n產(chǎn)地1X11…X1mX1m+1…X1m+nQ+a1…………………

……mXm1…XmmXm,m+1…Xm,m+nQ+am+1銷地m+1Xm+1,1…Xm+1,mXm+1,m+1…Xm+1,m+nQ……………………m+nXm+n,1…Xm+n,mXm+n,m+1…Xm+n,n+nQ接收量Q…QQ+bm+1Q+bm+n有轉(zhuǎn)運(yùn)的運(yùn)輸問題運(yùn)價表

接收發(fā)送產(chǎn)地銷地發(fā)送量1…mm+1…m+n產(chǎn)地1-c1…c1mc1m+1…c1m+nQ+a1…………………

……mcm1…-cmcm,m+1…cm,m+nQ+am+1銷地m+1cm+1,1…cm+1,m-cm+1…cm+1,m+nQ……………………m+ncm+n,1…cm+n,mcm+n,m+1…-cm+nQ接收地Q…QQ+bm+1Q+bm+n例一個運(yùn)輸系統(tǒng)包括了二個產(chǎn)地①和②、二個銷地④和⑤及一個中間轉(zhuǎn)運(yùn)站③，各產(chǎn)地的產(chǎn)量和各銷地的銷量用相應(yīng)節(jié)點(diǎn)處箭線旁的數(shù)字表示，節(jié)點(diǎn)聯(lián)線上的數(shù)字表示期間的運(yùn)輸單價，節(jié)點(diǎn)旁的數(shù)字為該地的轉(zhuǎn)運(yùn)單價，試確定最優(yōu)運(yùn)輸方案。123410532254041332012424041310532144353242401356530520105321443532424013

接收發(fā)送產(chǎn)地轉(zhuǎn)運(yùn)銷地12345發(fā)送量產(chǎn)地-4532M605-12M490轉(zhuǎn)運(yùn)32-35550銷地2M5-3650M456-550接收量5050508070

運(yùn)價表56530520105321443532424013用最小元素法得初始運(yùn)輸方案如下表所示。

接收發(fā)送12345發(fā)送量15010602502020903500504505055050接收量5050508070再經(jīng)過兩次迭代后得最優(yōu)解。其運(yùn)輸方案如下表所示：

接收發(fā)送12345發(fā)送量15010602502020903500504505055050接收量5050508070再經(jīng)過兩次迭代后得最優(yōu)解。其運(yùn)輸方案如下表所示：

接收發(fā)送12345發(fā)送量150106025020209033020504505055050接收量5050508070最優(yōu)時的總運(yùn)輸成本為3004.5應(yīng)用問題舉例

由于運(yùn)輸問題的表上作業(yè)法,遠(yuǎn)比一般單純形法計算簡單,因而人們在解決有些實(shí)際問題時,常設(shè)法將其轉(zhuǎn)化為運(yùn)輸問題的數(shù)學(xué)模型求解,下面通過幾個例子加以說明.

例4.5.1

某企業(yè)和用戶簽訂了設(shè)備交貨合同,已知該企業(yè)各季度的生產(chǎn)能力，每臺設(shè)備的生產(chǎn)成本和每季度末的交貨量（見下表），若生產(chǎn)出來的設(shè)備當(dāng)季不交貨，每臺設(shè)備每季度需支付保管維護(hù)費(fèi)0.1萬元,試問在遵守合同的條件下,企業(yè)應(yīng)如何安排生產(chǎn)計劃,才能使年消耗費(fèi)用最低?季度工廠生產(chǎn)能力交貨量(臺)每臺設(shè)備生產(chǎn)成本(萬元)1251512.02352011.03302511.54202012.5求解步驟:1)設(shè)xij表示第i季度生產(chǎn)第j季度交貨的設(shè)備臺數(shù),ai表示第i季度的生產(chǎn)能力,表示bj第j季度的交貨量;2)計算成本,第i季度生產(chǎn)第j季度交貨的每臺設(shè)備成本(生產(chǎn)成本+保管成本);3)建立數(shù)學(xué)模型;4)當(dāng)j<i時,cij是一個充分大的正數(shù)；5）把不平衡運(yùn)輸問題轉(zhuǎn)化為平衡運(yùn)輸問題,設(shè)計運(yùn)輸表:

生產(chǎn)季交貨季1234112.012.112.212.32？11.011.111.2311.511.6412.5成本表表9生產(chǎn)能力交貨量2035302515202520Minz=12.0x11+12.1x12+12.2x13+12.3x14+

Mx21+11.0x22+11.1x23+11.2x24

+Mx31+Mx32+11.5x33+11.6x34+Mx41+Mx41+MX41+12.5x44x11+x12+x13+x14≤25x22+x23+x24≤35x33+x34≤30x44≤20X11=15X12+x22=20X13+x23+x33=25X14+x24+x34+x44=20Xij0(i,j=1,2,3,4)

生產(chǎn)季交貨季1234D生產(chǎn)量1252

353

30420交貨量152025203012.012.112.212.3011.011.111.2011.511.6012.50MMMMMMM是一個很在的正數(shù).運(yùn)價表表10該類問題一般的數(shù)學(xué)模型表示：

當(dāng)j<i時，cij=M,M是一個很大的正數(shù)！

例

有三個產(chǎn)地A1、A2和A3生產(chǎn)同一種物品，使用者為B1、B2和B3，各產(chǎn)地到各使用者的單位運(yùn)輸價格表示于下表中，這三個使用者的需求量分別為10、4和6個單位。由于銷售需要和客觀條件的限制，產(chǎn)地A1至少要發(fā)出6個單位的產(chǎn)品，它最多只能生產(chǎn)11個單位的產(chǎn)品；A2必須發(fā)出7個單位的產(chǎn)品；A3至少要發(fā)出4個單位的產(chǎn)品。試根據(jù)上述條件用表上作業(yè)法求該運(yùn)輸問題的最優(yōu)運(yùn)輸方案。例題的單位運(yùn)輸價格表

使用生產(chǎn)B1B2B3生產(chǎn)量A12436≤a1≤11A2156a2=7A3324a3≥4使用量1046表11分析:總需求量為20,當(dāng)a1=6時,A3的最大生產(chǎn)量為7.如果A1和A3都取最大值,總產(chǎn)量為25,大于實(shí)際需求量20.增加虛擬的銷地.將A1和A3的產(chǎn)量分為兩部分,1)必須發(fā)出的,運(yùn)往實(shí)在需求地,不能運(yùn)往虛銷地;2)非必須發(fā)出的,可以運(yùn)往虛擬地,單位運(yùn)輸價格為0.

生產(chǎn)季交貨季B1B2B3B4生產(chǎn)量A16A‘15A27A34A‘33交貨量10465242433M0156M324M3240表12例某公司承擔(dān)4條航線的運(yùn)輸任務(wù),已知(1)各條航線的起點(diǎn)城市和終點(diǎn)城市,及每天的航班數(shù)(見表A);(2)各城市間的