運籌學(xué) 運輸問題

2023/2/71第三章

運輸問題第一節(jié) 運輸問題及其數(shù)學(xué)模型第二節(jié) 用表上作業(yè)法求解運輸問題第三節(jié) 運輸問題的進一步討論第四節(jié)應(yīng)用問題舉例講四節(jié)：2023/2/72§3-1運輸問題及其數(shù)學(xué)模型一、運輸問題的數(shù)學(xué)模型設(shè)某物品有m個產(chǎn)地A1,A2,…,Am；各產(chǎn)地的產(chǎn)量分別是a1,a2,…,am；有n個銷地B1,B2,…,Bn。各銷地的銷量分別是b1,b2,…,bn

；假如從產(chǎn)地Ai(i=1,2,…,m)向銷地Bj(j=1,2,…,n)運輸單位物品的運價是cij；問怎樣調(diào)運這些物品才能使總運費最??？這個問題是一個多產(chǎn)地多銷地的單品種物品運輸問題。把這個問題整理成為一個表,稱之為運價表。（見下頁）返回第三章目錄2023/2/73表3-1運價表

銷地產(chǎn)地B1B2┅Bm產(chǎn)量A1x11c11x12c12┅…x1nc1na1A2x21c21x22c22┅…x2nc2na2┇┇…┇…┅……┇Amxm1cm1xm2cm2┅…xmncmnam銷量b1b2┅bn變量xij(i=1,2,..,m;j=1,2,…,n)為由產(chǎn)地Ai

運往銷地Bj

的物品數(shù)量。稱為產(chǎn)銷平衡運輸問題稱為產(chǎn)銷不平衡運輸問題2023/2/74產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型這是一個線性規(guī)劃問題，可以用單純形法求解。但是，由于它所含變量多，求解極不方便。即使求解一個m＝3，n＝4的簡單運輸問題，變量數(shù)目也將達到19個之多。因此，必須尋找更簡便的求解方法。產(chǎn)量約束銷量約束非負約束總運輸費用極小化由某一產(chǎn)地運往各個銷地的物品數(shù)量之和等于該產(chǎn)地的產(chǎn)量由各個產(chǎn)地運往某一銷地的物品數(shù)量之和等一該銷地的銷量非負條件2023/2/75二、運輸問題的數(shù)學(xué)模型的特點1.運輸問題有有限最優(yōu)解對運輸問題的數(shù)學(xué)模型，若令變量另外，在運輸問題的數(shù)學(xué)模型中,目標函數(shù)是取最小值,它的值不會趨于無窮大,在實際問題中也不可能出現(xiàn)這種情況,因此,運輸問題有有限最優(yōu)解。對運輸問題數(shù)學(xué)模型的約束條件進行整理,得其系數(shù)矩陣的結(jié)構(gòu)形式為：其中：是運輸問題的一個可行解2023/2/762.運輸問題約束條件的系數(shù)矩陣m

行n

行第i

個第(m+j)個系數(shù)列向量的結(jié)構(gòu)：即除第i個和第(m+j)個分量為1外，其它分量全等于0。2023/2/77運輸問題的特點:(1)

約束條件系數(shù)矩陣的元素等于0或1；(2)

約束條件系數(shù)矩陣的每一列有兩個非零元素，對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次,在后n個約束方程中也出現(xiàn)一次。如果是產(chǎn)銷平衡運輸問題,還有以下特點：（3）所有結(jié)構(gòu)約束條件都是等式約束；（4）各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。例1某種物品先存放在兩個倉庫A1和A2中，再運往三個使用地B1，B2，B3，其間的運距（或單位運價）如表3-2小方格中的數(shù)據(jù)所示，試建立使總運輸量（或總運費）最小的運輸問題數(shù)學(xué)模型。2023/2/78表3-2

銷地產(chǎn)地B1B2B3產(chǎn)量A134210A23534銷量356x11x12x13x21x22x23解題思路：（1）假設(shè)變量（2）分析約束（3）明確目標（4）建立模型（5）求解變量（6）分析方案（7）得出決論66-6=010-6=434-3=13-3=011-1=05-1=444-4=04-4=000顯然x11=3,x12=1,x13=6,x22=4,x21=0,x23=0是該運輸問題的一個可行解。目標函數(shù)值z=452023/2/79§3-2用表上作業(yè)法求解運輸問題它是求解運輸問題的一種簡便而有效的方法,其求解過程在運輸表上進行,它是一種迭代法,其步驟為：1.先按某種規(guī)劃找出一個初始解(初始調(diào)運方案）；2.對現(xiàn)行解作最優(yōu)性判別；3.若不是最優(yōu)解,就在表上對它進行調(diào)整改進,得出一個新解；4.再判別,再改進,直到得到運輸問題的最優(yōu)解為止；※在迭代過程中,得出的所有解都要求是運輸問題的基可行解。例2某部門有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售地出售，各工廠的生產(chǎn)量，各銷售地的銷售量（假定單位均為噸）以及各工廠到各銷售地的單位運價（元/噸）示于表3-4中，要求研究產(chǎn)品如何調(diào)運才能使總運費最小？返回第三章目錄2023/2/710一、確定運輸問題的初始基可行解（初始調(diào)運方案）1.最小元素法：

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448810-8=222-2=0212-2=101016-10=610-10=031414-14=022-14=8488-8=014-8=6566-6=06-6=08-8=0661該運輸問題一個初始可行解為：x13=10,x14=6,x21=8,x23=2,x32=14,x34=8.總運費＝4×10＋11×6＋2×8＋3×2＋5×14＋6×8＝2462023/2/711用西北角法確定運輸問題的初始可行解

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量8141214482.西北角法88-8=0116-8=888-8=014－8=6266－6=010-6=4344-4=012-4=8488-8=022-8=1451466初始可行解為：x11=8,x12=8,x22=6,x23=4,x33=8,x34=14.總運輸費用z＝8×4＋8×12＋6×10＋4×3＋8×11＋14×6＝3722023/2/712用沃格爾法確定運輸問題的初始可行解

銷地產(chǎn)地B1B2B3B4產(chǎn)量行罰數(shù)12345A141241116A22103910A38511622銷量814121448列罰數(shù)123450112513140122138012128761212002243.沃格爾法該運輸問題的可行解為：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8,其他變量等于0?？傔\輸費z＝2440806020404002023/2/713確定初始可行解的三種方法比較最小元素法：z＝246西北角法：z＝372沃格爾法：z＝244沃格爾法解出的目標函數(shù)值最小，最小元素法次之，西北角法最大；一般說來，沃格爾法得出的解質(zhì)量最好，在運輸問題中，常用來作最優(yōu)解的近似解。二、解的最優(yōu)性檢驗2023/2/7141.最小元素法解題思想：為了減少運費,應(yīng)優(yōu)先考慮單位運價最小(或運距最短)的供銷業(yè)務(wù),最大限度地滿足其供銷量。解題步驟：(4)在余下的供銷點的供銷關(guān)系中,繼續(xù)安排調(diào)運,直到安排完成所有供銷任務(wù),得到一個完整的方案為止。確定初始基可行解（初始調(diào)運方案）2023/2/7152.西北角法解題思想:優(yōu)先滿足運輸表中西北角(即左上角)上空格的供銷量需求.解題步驟:(1).最先填xij=min(ai,bj),即(Ai,Bj

)；(2).若

xij=ai

，則Ai

行不在考慮,且Bj

列剩下bj-ai

來填左上角其它空格.(3).若

xij=bj

，則Bj

列不再考慮,且Ai

行剩下ai

-bj

來填左上角其它空格.(4).如此繼續(xù)完成調(diào)運,最后得出一個初始方案。用西北角法確定運輸問題的初始可行解2023/2/7163.沃格爾法解題思想：對于每一個供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運價中找出最小單位運價和次小單位運價,并稱這兩個單位運價之差為該供應(yīng)地或銷售地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小單位運價安排運輸時造成的運費損失不大；反之，若罰數(shù)的值很大，不按最小運價組織運輸就會造成很大的損失；故應(yīng)盡量按最小單位運價按排運輸。解題步驟：（1）先計算運輸表中每一行和每一列的罰數(shù)值，并稱為行罰數(shù)和列罰數(shù)。（2）將行罰數(shù)填入位于運輸表右側(cè)行罰數(shù)欄的左邊第一列的相應(yīng)格子中；列罰數(shù)填入位于運輸表下邊列罰數(shù)欄的第一行的相應(yīng)格子中。（3）找出該列和該行的列罰數(shù)和行罰數(shù)中的最大值；根據(jù)最大罰數(shù)值的位置在運輸表中運價最小的格中填入一個盡可能大的運輸量，并劃去對應(yīng)的一行或一列。（4）繼續(xù)找其它列和行的列罰數(shù)和行罰數(shù)；找出其它運輸量；已劃去的不再找。直到最后按排完，即得到一個初始運輸方案。用沃爾沃法確定運輸問題的初始可行解2023/2/717二、解的最優(yōu)性檢驗得到了初始可行解后，應(yīng)對其進行判別是否是最優(yōu)解,常用方法有：閉回路法和對偶變量法。1.閉回路法解題思想：對運輸表中的解的各非基變量即某空格(Ai,Bj)進行檢驗;若存在檢驗數(shù)為負，說明將xij變?yōu)榛兞亢?，將使運費減少；故當(dāng)前解不是最優(yōu)解；若所有檢驗數(shù)為正，則無論怎樣變換解均不能使運輸費降低，即當(dāng)前解是最優(yōu)解。解題步驟：以某空格(Ai,Bj)為頂點，由填有數(shù)字的其它格為其它頂點，通過水平線段和豎直線段組成封閉多邊形?？梢允呛唵蔚亩噙呅?，也可以是復(fù)雜的多邊形。然后順時針或逆時針轉(zhuǎn)，以(Ai,Bj)為第一頂點格，奇格為正，偶格為負，將單位運價之代數(shù)和作為該空格的檢驗數(shù)sij

：若所有sij≥0，則是最優(yōu)解：若存在sij＜0，則不是最優(yōu)解。2023/2/718用閉回路法對解的最優(yōu)性進行檢驗

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141210461116A2821023910A38145118622銷量8141214481012-1112s11=c11-c21+c23-c14=4-2+3-4=1s31=c31-c34+c14-c13+c23-c21=8-6+11-4+3-2=10s12=c12-c32+c34-c14=12-5+6-11=2s22=c22-c32+c34-c14+c13-c23=10-5+6-11+4-3=1s33=c33-c34+c14-c13=11-6+11-4=12s24=c24-c14+c13-c23=9-11+4-3=-1由于s24＝-1＜0所以，上表中的解不是最優(yōu)解。2023/2/7192.對偶變量法（位勢法）:解題思想：用u1,u2,…,um分別表示與前m個約束相對應(yīng)的對偶變量，用v1,v2,…,vn分別表示與后n個約束相對應(yīng)的對偶變量，即對偶變量向量：Y=(u1,u2,…,um,v1,v2,…,vn)將運輸問題的數(shù)學(xué)模型寫成對偶規(guī)劃：2023/2/720經(jīng)過整理得出運輸問題變量xij的檢驗數(shù)為：如果所有的sij≥0，則所求得的可行解是最優(yōu)解，如果存在sij＜0，則所求得的可行解不是最優(yōu)解，需要改進。2023/2/721解題步驟：(一）在運輸表右邊增加一位勢列ui；在下邊增加一位勢行vj；(二）計算位勢(三）計算檢驗數(shù)：

sij=cij-(ui+vj)由于基變量的檢驗數(shù)sij＝0，故對這組基變量可以寫出方程組：這個方程組有（m+n-1)方程，（m+n）個變量，所以它的解不是唯一解。這個方程組的解稱為位勢。2023/2/722例3用位勢法對前例運輸問題作最優(yōu)性檢驗。

銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA141210461116u1A2821023910u2A38145118622u3銷量814121448vjv1v2v3v4（1）在運價表上增加一位勢列ui

和位勢行vj

，（上表）（2）建立位勢方程組，計算位勢。10-429310（3）計算檢驗數(shù)。sij＝cij－（ui+vj)1102112-1由于s24=-1＜0，所以上表得出的可行解不是最優(yōu)解。需要改進2023/2/723建立位勢方程組，計算位勢u2＝0，v1＝2v3＝3，u1＝1v4＝10

，u3＝－4v2＝9任意指定某一位勢等于一個較小的整數(shù)或零，如

u2＝0將計算結(jié)果填入運輸表的位勢列和位勢行。2023/2/724三.解的改進1.改進原因?qū)\輸問題來說,若某空格的檢驗數(shù)sij為負，說明將這個非基變量變?yōu)榛兞繒r運費會減小，因而這個解不是最優(yōu)解,還需要改進；2.改進方法在運輸表中，找出sij＜0的空格對應(yīng)的閉回路Lij，在滿足所有約束條件的前提下，使xij盡量增大并相應(yīng)調(diào)整此閉回路上其它頂點的運輸量,以得到另一個更好的基可行解。2023/2/7253.改進步驟：(1)以xij為換入變量，找出它在運輸表中的閉回路；(2)以空格(Ai,Bj)為第一個奇數(shù)頂點，沿閉回路的順時針或逆時針方向前進，對閉回路上的頂點依次編號；(3)在閉回路上的所有偶數(shù)頂點中，找出運輸量最小(minxij)的頂點(格子)，以該格中的變量為換出變量；(4)以minxij為調(diào)整量，將該閉回路上所有奇數(shù)頂點處的運輸量都增加這一數(shù)值，所有偶數(shù)頂點處的運輸量都減少這一數(shù)值，從而得出一新的運輸方案。該方案的總運費比原運輸方案的總運費減少，改變量等于sij(minxij)。（5）對得到的新解進行最優(yōu)性判別。重復(fù)上述步驟，直到得到最優(yōu)解為止。2023/2/726例4對例2用最小元素法得出的解進行改進（2）計算檢驗數(shù)，對解的最優(yōu)性進行判斷。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141210461116A2821023910A38145118622銷量814121448（+2）（-2）（+2）（-2）124

21122109（1）因為s24＜0，所以，以此格——（A2，B4）為頂點尋找一個閉回路，進行解的改進?！遱ij≥0,∴最優(yōu)解為：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8 z＝12×4＋4×11＋8×2＋2×9＋14×5＋8×6＝2442023/2/727四、需要說明的幾個問題1.若運輸問題的某一基可行解中，有幾個非基變量的檢驗數(shù)均為負，在繼續(xù)進行迭代時，取它們中的任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取sij＜0中最小者對應(yīng)的變量為換入變量。2.當(dāng)?shù)竭\輸問題的最優(yōu)解時，如果有某非基變量的檢驗數(shù)等于零，則說明該運輸問題有多重最優(yōu)解。3.當(dāng)運輸問題某部分產(chǎn)地的產(chǎn)量和，與某一部分銷地的銷量和相等時，在迭代過程中有可能在某個格填入一個運量時，需同時劃去運輸表的一行和一列，即出現(xiàn)退化。退化是時有發(fā)生的，為使迭代進行下去，退化時在同時劃去的一行或一列中的某個格中填入0，表示該格變量取值為0的基變量，使迭代過程中基可行解的分量恰好為(m+n–1)個。2023/2/728§3-3運輸問題的進一步討論一、產(chǎn)銷不平衡的運輸問題解題思想：把產(chǎn)銷不平衡的運輸問題轉(zhuǎn)化為產(chǎn)銷平衡問題。返回第三章目錄2023/2/729可假想一個銷地Bn+1，其銷量為bn+1，其實質(zhì)沒有運輸，只是就地儲藏。設(shè)調(diào)運假想銷地的物品數(shù)量為xi,n+1；故其單位運價ci,n+1＝0;且此式對應(yīng)的運輸表見下頁。2023/2/730產(chǎn)量大于銷量的運輸表

銷地產(chǎn)地B1B2…BnBn+1（儲存）產(chǎn)量A1x11c11x12c12……x1nc1nx1,n+10a1A2x21c21x22c22……x2nc2nx2,n+10a2┆┆…┆…┆…┆…┆…┆Amxm1cm1xm2cm2……xmncmnxm,n+10am銷量b1b2…bn2023/2/731(2)如果總銷量大于總產(chǎn)量，則增加一個假想產(chǎn)地，它的產(chǎn)量等于總銷量與總產(chǎn)量之差。

銷地產(chǎn)地B1B2…Bn產(chǎn)量A1x11c11x12c12……x1nc1na1A2x21c21x22c22……x2nc2na2┆┆…┆…┆…┆…┆Amxm1cm1xm2cm2……xmncmnamAm+1(假想產(chǎn)地）00……0銷量b1b2…bnxm+1,1xm+1,2xm+1,n2023/2/732二、有轉(zhuǎn)運的運輸問題由于空間位置的需要，需考慮轉(zhuǎn)運問題，才能使總運費最小。A1A2B2B1B3產(chǎn)地銷地A2A1B2B1B3產(chǎn)地銷地（a)無轉(zhuǎn)運（a)包含轉(zhuǎn)運比較以上兩圖。顯然，包含轉(zhuǎn)運的運輸問題復(fù)雜得多。2023/2/733假定m個產(chǎn)地A1,A2,…,Am和n個銷地B1,B2,…,Bn都可以作為中間轉(zhuǎn)運站使用，從而發(fā)送物品的地點和接收物品的地點都有m+n個。ai

：第i個產(chǎn)地的產(chǎn)量（凈供應(yīng)量）；bj

：第j個銷地的銷量（凈需要量）；xij

：第i個發(fā)送地運到第j個接收地的物品數(shù)量；cij

：由第i個發(fā)送地運到第j個接收地的單位運價；ti

：第i個地點轉(zhuǎn)運物品的數(shù)量；ci

：第i個地點轉(zhuǎn)運單位物品的費用；則有：am+1=am+2=,…,am+n=0，b1=b2=,…,=bm=0n個銷地的凈產(chǎn)量等于零。m個產(chǎn)地地的凈銷量等于零。2023/2/734有轉(zhuǎn)運的運輸問題模型：由第i個產(chǎn)地發(fā)送到各個地方的物品數(shù)量之和，等于該產(chǎn)地的產(chǎn)量加上經(jīng)它轉(zhuǎn)運的物品數(shù)量。由第i個發(fā)送地發(fā)送到各個地方的物品數(shù)量之和，等于經(jīng)它轉(zhuǎn)運的物品數(shù)量。由各地運到第j地的物品數(shù)量之和，等于轉(zhuǎn)運量。由各地運到第j地的物品數(shù)量之和，等于凈需要量加上轉(zhuǎn)運量。令xii=Q-ti或xjj=Q-tj

，則ti=Q-xii,tj=Q-xjj經(jīng)整理得：2023/2/735注意：在上式中，對所有i＝j(luò)，cij＝－ci。由于目標函數(shù)中是常數(shù),故不影響求最優(yōu)解。其對應(yīng)的表如下有轉(zhuǎn)運問題的運輸表有轉(zhuǎn)運問題的運價表2023/2/736有轉(zhuǎn)運問題的運輸表

接收發(fā)送產(chǎn)地銷地發(fā)送量1…mm+1…m+n產(chǎn)地1x11…x1mx1,m+1…x1,m+nQ+a1┆┆…┆┆…┆┆mxm1…xmmxm,m+1…xm,m+nQ+am銷地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,m+nQ接收量Q…QQ+bm+1…Q+bm+n表3-172023/2/737有轉(zhuǎn)運問題的運價表

接收發(fā)送產(chǎn)地銷地發(fā)送量1…mm+1…m+n產(chǎn)地1-c1…c1mc1,m+1…c1,m+nQ+a1┆┆…┆┆…┆┆mcm1…-cmcm,m+1…cm,m+nQ+am銷地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+1…Q+bm+n表3-182023/2/738例6

有一個運輸系統(tǒng)包括二個產(chǎn)地（①、②）、二個銷地（④、⑤）及一個中間轉(zhuǎn)運站（③），各產(chǎn)地的產(chǎn)量和各銷地銷量用相應(yīng)節(jié)點處箭線旁的數(shù)字表示，節(jié)點聯(lián)線上的數(shù)字表示其間的運輸單價，節(jié)點旁的數(shù)字為該地的轉(zhuǎn)運單價，試確定最優(yōu)運輸方案。解：a1=10,a2=40,a3=a4=a5=0b1=b2=b3=0,b4=30,b5=20Q=10+40=30+20=50c1=4,c2=1,c3=3,c4=3,c5=512345105243402145536305320以M表示足夠大的正數(shù)，可得該問題的運輸表3-192023/2/739表3-19

接收發(fā)送產(chǎn)地轉(zhuǎn)運銷地發(fā)送量12345產(chǎn)地1-4532M6025-12M490轉(zhuǎn)運332-35550銷地42M5-36505M456-550接收量5050508070例6圖2023/2/740表3-20

接收發(fā)送產(chǎn)地轉(zhuǎn)運銷地發(fā)送量12345產(chǎn)地150-453102M602550-1220M20490轉(zhuǎn)運33250-350550銷地42M550-36505M45650-550接收量50505080702023/2/741表3-21

接收發(fā)送產(chǎn)地轉(zhuǎn)運銷地發(fā)送量12345產(chǎn)地150-453102M602550-1220M20490轉(zhuǎn)運33250-305550銷地42M550-36505M45650-550接收量50505080702023/2/742表3-22

接收發(fā)送產(chǎn)地轉(zhuǎn)運銷地發(fā)送量12345產(chǎn)地150-453102M602550-1202M20490轉(zhuǎn)運33230-3205550銷地42M550-36505M45650-550接收量5050508070Excel求解2023/2/743§3-4運用問題舉例例題一：某公司承擔(dān)4條航線的運輸任務(wù)，已知：（1）各條航線的起點城市和終點城市及每天的航班數(shù)見表3-28；（2）各城市間的航行時間見表3-29；（3）所有航線都使用同一種船只，每次裝船和卸船時間均為1天。問該公司至少應(yīng)配備多少條船才能滿足所有航線運輸?shù)男枰勘?-28航線起點城市終點城市每天航班數(shù)1ED32BC23AF14DB1表3-29各城市間的航行時間返回第三章目錄2023/2/744表3-29各城市間的航行時間（天）解：所需船只可分為兩部分：（1）各航線航行、裝船、卸船所占用的船只，對各航線逐一分析，所需船只數(shù)列入表3-30中，累計共需91條船。

至從ABCDEFA0121477B1031388C23015557851703F7852030返回表3-282023/2/745表3-30各航線航行、裝船、卸船所占用的船只（2）各港口之間調(diào)度所需船只數(shù)。這由每天到達港口的船只數(shù)與它所需發(fā)出的船只數(shù)不相等而產(chǎn)生。各港口城市每天到達船只數(shù)、需求船只數(shù)及其差額如表3-31中。航線裝船天數(shù)卸船天數(shù)航行天數(shù)小計航班數(shù)所需船只11117193572113521031179194111315115表3-31各港口城市每天到達、需求及差額船只數(shù)城市ABCDEF每天到達012301每天需要120130余缺數(shù)-1-122-31航線2023/