用表上作業(yè)法求解運輸問題課件

第13章運輸問題（TransportationProblem）在線性規(guī)劃問題中，有一類特殊類型的問題－－運輸問題。這類問題主要研究把某種物資從若干個產(chǎn)地調(diào)運到若干個銷地，每個產(chǎn)地的供應(yīng)量和每個銷地的銷售量及從一個產(chǎn)地到一個銷地的運輸費用已知，要求確定一個總運費最少的方案。第13章運輸問題在線性規(guī)劃問題中，有一類1第13章運輸問題（TransportationProblem）物資調(diào)配問題（MaterialTransferringProblem）運輸問題及數(shù)學(xué)模型（ModelforTransportation）用表上作業(yè)法求解運輸問題（SolveTransportationProblembyTable）運輸問題的進-步討論（FurtherDiscussionaboutTransportationProblem）應(yīng)用問題舉例（Parexample）第13章運輸問題（TransportationProb2物資調(diào)配問題在經(jīng)濟建設(shè)中，經(jīng)常會碰到大宗物資調(diào)運問題，如煤、鋼鐵，木材、糧食等物，在全國有若干生產(chǎn)基地，根據(jù)已有交通網(wǎng)絡(luò)，應(yīng)如何制訂調(diào)運方案，將這些物資運到各銷售地點，而運費最小，效率最高。在物流系統(tǒng)中，物資的調(diào)撥和配送是物流管理決策的一項主要工作。在市場經(jīng)濟條件下，對資源實行市場實行優(yōu)化配置，有利于國民經(jīng)濟持續(xù)發(fā)展。物資調(diào)配問題在經(jīng)濟建設(shè)中，經(jīng)常會碰到大宗物3運輸問題及數(shù)學(xué)模型本章研究單一品種物資的運輸調(diào)度問題。其典型情況是：設(shè)某種物品有個產(chǎn)地（或供方）Ai（i=1，2，…，m），各產(chǎn)地的產(chǎn)量分別是ai（i=1，2，…，m），有n個銷地Bj（j=1，2，…，n）,各銷地的銷量分別為bj（j=1，2，…，n）。假定從Ai（i=1，2，…，m）產(chǎn)地向銷地Bj（j=1，2，…，n）運輸單位物品的運價是。問怎樣調(diào)運這些物品才能使總運費最小?1.運輸問題數(shù)學(xué)模型運輸問題及數(shù)學(xué)模型本章研究單一品種物資的運4這是由多個產(chǎn)地供應(yīng)多個銷地的單品種物品運輸問題。為直觀起見，可列出該問題的運輸表（見下頁）。表中的變量Xij（i=1，2，…，m；j=1，2，…，n）為由產(chǎn)地Ai運往銷地Bj的物品數(shù)量。cij為Ai到Bj的單位運價。有時，將單位運價單獨列入另一個表中，并稱其為運價表。運輸單價cij銷售地Bi供應(yīng)量B1B2…Bnai產(chǎn)地AiA1c11c12…c1na1A2c21c22…c2na2┆┆┆…┆┆Amcm1cm2…cmnam銷售量bjb1b2…bn分布變量表A1x11x12…x1nA2x21x22…x2n┆┆┆…┆Amxm1xm2…xmn這是由多個產(chǎn)地供應(yīng)多個銷地的單品種物品運輸問5產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型可表示如下：其中，約束條件右側(cè)常數(shù)ai和bj滿足如果運輸問題的總產(chǎn)量等于其總銷量，即有則稱該運輸問題為產(chǎn)銷平衡運輸問題；反之，稱產(chǎn)銷不平衡運輸問題。產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型可表示如下：其中，約束條件右側(cè)常數(shù)6（1）運輸問題有有限最優(yōu)解2.運輸問題數(shù)學(xué)模型的特點對前述運輸問題，若令其變量其中，，則xij就是前述述運輸問題的一個可行解；另一方面，其目標(biāo)函數(shù)有下界。目標(biāo)函數(shù)值不會趨于-∞。由此可知，運輸問題必存在有限最優(yōu)解。（1）運輸問題有有限最優(yōu)解2.運輸問題數(shù)學(xué)模型的特點對前7（2）運輸問題約束條件的系數(shù)矩陣即除第i個和第m+j個分量為l外，其它分量全等于0。其系數(shù)列向量的結(jié)構(gòu)是：（2）運輸問題約束條件的系數(shù)矩陣即除第i個和第m+j個分量8由此可知，運輸問題具有下述特點：（1）約束條件系數(shù)矩陣的元素等于0或1。（2）約束條件系數(shù)矩陣的每一列有兩個非零元素，這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次。對產(chǎn)銷平衡運輸問題，除上述兩個特點外，還有以下特點：所有結(jié)構(gòu)約束條件都是等式約束，各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。由此可知，運輸問題具有下述特點：9例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城市銷售，各煤礦的供應(yīng)量和需求量如下頁表，各城市的需求量其間的距離(或單位運價)cij如表下頁表方格中的數(shù)據(jù)所示，試建立使總運輸量(或總運費)最小的運輸問題數(shù)學(xué)模型。單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020A2735820A3329440需求量bj302510158080例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城10解：設(shè)Xij為第i煤礦向第j城市的供應(yīng)量，cij表示為第i煤礦向第j城市供應(yīng)煤的單位運價。i=1，2，3；j=1，2，3，4。本例中a1+a2+a3=b1+b2+b3+b4=80，故是產(chǎn)銷平衡運輸問題。則可寫出其數(shù)學(xué)模型。解：設(shè)Xij為第i煤礦向第j城市的供應(yīng)量，cij表示為第i煤11根據(jù)運輸問題的數(shù)學(xué)模型求出的運輸問題的解X=(xij)，代表著一個運輸方案，其中每一個變量xij的值表示由Ai調(diào)運數(shù)量為xij的物品給Bij。前已指出運輸問題是一種線性規(guī)劃問題，可設(shè)想用迭代法進行求解，即先找出它的某一個基可行解，再進行解的最優(yōu)性檢驗，若它不是最優(yōu)解，就進行迭代調(diào)整，以得到一個新的更好的解，繼續(xù)檢驗和調(diào)整改進，直至得到最優(yōu)解為止。3.運輸問題的解

根據(jù)運輸問題的數(shù)學(xué)模型求出的運輸問題的解X=(xij12例1的一個基可行解：單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 8080例1的一個基可行解：單價cij銷售地Bj供應(yīng)量aiB1B2B13用表上作業(yè)法求解運輸問題表上作業(yè)法是求解運輸問題的一種簡便而有效的方法，其求解工作在運輸表上進行。表上作業(yè)法是一種迭代法，迭代步驟為：先按某種規(guī)則找出一個初始解(初始調(diào)運方案)；再對現(xiàn)行解作最優(yōu)性判別；若這個解不是最優(yōu)解，就在運輸表上對它進行調(diào)整改進，得出一個新解；再判別，再改進；直至得到運輸問題的最優(yōu)解為止。如前所述，迭代過程得出的所有解都要求是運輸問題的基可行解。用表上作業(yè)法求解運輸問題表上作業(yè)法是求解運輸問題的14步驟：（1）找出初始即可行解，即在產(chǎn)銷平衡表上分配初始調(diào)運方案，保證xij≥0，，并且xij>0的格（又稱實格）必須有m+n-1個；（2）求出各非基變量的檢驗數(shù)σij（空格檢驗數(shù)），σij≥0時停止計算；σij<0時在繼續(xù)調(diào)整調(diào)運方案（換基迭代法）；（3）確定進基變量（空格換入變量）和出基變量（實格調(diào)出變量），找出新的基可行解（用空格閉回路法調(diào)整）；（4）重復(fù)第1-3步，直至獲得σij≥0，輸出xij*和minZ=Z*為止。步驟：151.給出運輸問題的初始基可行解(初始調(diào)運方案)結(jié)合例1詳細說明表上作業(yè)法的解題步驟:（1）畫出運輸問題的求解作業(yè)表（見例1），由于，可以轉(zhuǎn)入（2）；（2）找出初始基可行解（又稱分配初始調(diào)運方案）。確定初始調(diào)運方案的方法很多，下面介紹三種常用的方法。單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 80801.給出運輸問題的初始基可行解(初始調(diào)運方案)16a.最小元素法容易直觀想到，為了減少運費，應(yīng)優(yōu)先考慮單位運價最小(或運距最短)的供銷業(yè)務(wù)，最大限度地滿足其供銷量。即對所有i和j，找出ci0j0=min(cij)，并將xi0j0=min(ai0,bj0)的物品量由Ai0供應(yīng)給Bj0；若xi0j0=ai0，則產(chǎn)地Ai0的可供物品己用完，以后不再繼續(xù)考慮這個產(chǎn)地，且Bj0的需求量由bj0減少為bj0-ai0。如果xi0j0=bj0，則銷地bj0的需求已全部得到滿足，以后不再考慮這個銷地，且Ai0的可供量由ai0減少為ai0-bj0。a.最小元素法17然后，在余下的供、銷點的供銷關(guān)系中，繼續(xù)按上述方法安排調(diào)運，直至安排完所有供銷任務(wù)，得到一個完整的調(diào)運方案(完整的解)為止。這樣就得到了運輸問題的一個初始基可行解(初始調(diào)運方案)。由于該方法基于優(yōu)先滿足單位運價(或運距)最小的供銷業(yè)務(wù)．故稱為最小元素法。然后，在余下的供、銷點的供銷關(guān)系中，繼續(xù)按上述18最小元素法分配的初始調(diào)運方案單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x23=10x24=10A3329440x31=10x32=25x34=5需求量bj30251015 8080最小元素法分配的初始調(diào)運方案單價cij銷售地Bj供應(yīng)B1B19b.西北角法西北角法與最小元素法不同，它不是優(yōu)先考慮具有最小單位運價的供銷業(yè)務(wù)，而是優(yōu)先滿足運輸表中西北角(即左上角)上空格的供銷需求。b.西北角法20西北角法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 8080西北角法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)B1B2B21c.沃格爾法使用最小元素法有時按某一最小單位運價優(yōu)先安排調(diào)運時，可能導(dǎo)致不得不采用運費很高的其它供銷點對，使整個運輸費用增加。對每一個供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運價中找出最小單位運價和次小單位運價，并稱這兩個單位運價之差為該地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小單位運價安排運輸時造成的運費損失不大；反之，如果罰數(shù)的值很大，不按最小運價組織運輸就會造成很大損失，故應(yīng)盡量按最小單位運價安排運輸。沃格爾法就是基于這種考慮提出來的。c.沃格爾法22沃格爾法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)量ai行罰數(shù)B1B2B3B412345供應(yīng)A1162102011⑤00x11=10x13=10地AiA2735820224④x22=20A332944011111x31=20x32=5x34=15需求量bj30251015

列罰數(shù)1213④

221③0

32100

44100

5④200

沃格爾法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)量ai23對比以上3種方法的初始調(diào)運方案，可看出，伏格爾法優(yōu)于其他方法，也就是說伏格爾法確定的初始解得目標(biāo)函數(shù)距離最優(yōu)解目標(biāo)函數(shù)最近，因而迭代運算數(shù)為最少，效率高。方法西北角法最小元素法伏格爾法目標(biāo)函數(shù)Z300250220對比以上3種方法的初始調(diào)運方案，可看出，伏格242.解的最優(yōu)性檢驗要判定運輸問題的某個解是否為最優(yōu)解，可仿照一般單純形法，檢驗這個解的各非基變量(對應(yīng)于運輸表中的空格)的檢驗數(shù)，苦有某空格的檢驗數(shù)為負，說明將變?yōu)榛兞繉⑹惯\輸費用減少，故當(dāng)前這個解不是最優(yōu)解。若所有空格的檢驗數(shù)全非負，則不管樣變換解均能使運輸費用降低，即目標(biāo)函數(shù)值已無法改進，這個解就是最優(yōu)解。a.閉回路法2.解的最優(yōu)性檢驗要判定運輸問題的某個解25現(xiàn)結(jié)合例1中用最小元素法給出的初始解，說明檢驗數(shù)的計算方法。其中一條閉回路檢驗數(shù)表銷售地供應(yīng)地B1B2B3B4A1σ12=6σ13=3σ14=8A2σ21=0σ22=-–3*A3σ33=8因σ22=–3<0，故知該解不是最優(yōu)解，還有待調(diào)整改正?，F(xiàn)結(jié)合例1中用最小元素法給出的初始解，說明檢26閉回路可以是一個簡單的矩形，也可以是由水平和豎直邊線組成的其它更為復(fù)雜的封閉多邊形.閉回路可以是一個簡單的矩形，也可以是由水平和27運輸問題的進—步討論

上—節(jié)講述的運輸問題的算法，是以總產(chǎn)量等于總銷量(產(chǎn)銷平衡)為前提的。實際上在很多運輸問題中，總產(chǎn)量不等于總銷量。這時，為了使用前述表上作業(yè)法求解，就需將產(chǎn)銷不平衡運輸問題化為產(chǎn)銷平衡運輸問題。1.產(chǎn)銷不平衡的運輸問題運輸問題的進—步討論上—節(jié)講述的運輸問題的28如果總產(chǎn)量大于總銷量，即這時的數(shù)學(xué)模型是如果總產(chǎn)量大于總銷量，即29為借助于產(chǎn)銷平衡時的表上作業(yè)法求解，可增加一個假想的銷地Bn+1，由于實際上它不存在，因而由產(chǎn)地Ai(i=1,2,…,m)調(diào)運到這個假想銷地的物品數(shù)量xi,n+1(相當(dāng)于松弛變量)，實際上是就地存貯在Ai的物品數(shù)量。就地存貯的物品不經(jīng)運輸，故其單位運價ci,n+1(i=1,2,…,m)。為借助于產(chǎn)銷平衡時的表上作業(yè)法求解，可增加一個假想的30若令假想銷地的銷量為bn+1，且則模型變?yōu)閷?yīng)的運輸表見下頁。若令假想銷地的銷量為bn+1，且對應(yīng)的運輸表見下頁。31單價cij銷售地Bj供應(yīng)量aiB1…BnBn+1供應(yīng)地AiA1C11c12c1n0a1X11A2c21c22c2n0a2x21x22Amcm1cm2cmn0amx32x33x34需求量bjb1…Bn單價cij銷售地Bj供應(yīng)B1…BnBn+1供A1C11c1232總銷量大于總產(chǎn)量的情形可仿照上述類似處理，即增加一個假想的產(chǎn)地Am+1，它的產(chǎn)量等于

由于這個假想的產(chǎn)地并不存在，求出的由它發(fā)往各個銷地的物品數(shù)量，實際上是各銷地所需物品的欠缺額，顯然有總銷量大于總產(chǎn)量的情形可仿照上述類似處理，即33單價cij銷售地Bj供應(yīng)量aiB1B2B2B4供應(yīng)地AiA1413459A21236106A3782610需求量bj54672522例：由各煤廠到各用戶的單位運價如表所示，請確定總運費最少的調(diào)運方案。單價cij銷售地Bj供應(yīng)B1B2B2B4供A1413459A34單價cij銷售地BjB1B2B2B4供應(yīng)地AiA141345A2123610A37826需求量bj546725-22=3供應(yīng)量ai9610

555B5單價cij銷售地BjB1B2B2B435在以上討論中，假定物品由產(chǎn)地直接運送到銷售目的地，不經(jīng)中間轉(zhuǎn)運。但是，常常會遇到這種情形：需先將物品由產(chǎn)地運到某個中間轉(zhuǎn)運站(可能是另外的產(chǎn)、銷地或中間轉(zhuǎn)運倉庫)，然后再轉(zhuǎn)運到銷售地。有時，經(jīng)轉(zhuǎn)運比直接運到目的地更為經(jīng)濟?？傊?，很多情況下，在決定運輸方案時有必要把轉(zhuǎn)運也考慮進去。顯然．考慮轉(zhuǎn)運將使運輸問題變得更為復(fù)雜。2.有轉(zhuǎn)運的運輸問題

(a)無轉(zhuǎn)運(b)包含轉(zhuǎn)運在以上討論中，假定物品由產(chǎn)地直接運送到銷售目36

假定m個產(chǎn)地A1,A2,…,Am和n個銷地B1,B2,…,Bn都可以作為中間轉(zhuǎn)運站使用，從而發(fā)送物品的地點相接收物品的地點都有m+n個。這樣一來，我們就得到了一個擴大了的運輸問題。為建立其數(shù)學(xué)模型，令：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)運單位物品的費用。假定m個產(chǎn)地A1,A2,…,Am和n個銷地B37現(xiàn)將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面，銷地排在后面，則有假定為平衡運輸問題，即有現(xiàn)將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面，銷地排在后面，則有38根據(jù)前面對平衡運輸問題的討論，可得該擴大了的運輸問題的數(shù)學(xué)模型如下：根據(jù)前面對平衡運輸問題的討論，可得該擴大了的運輸問題的數(shù)學(xué)模39將上述模型中的各約束等式右側(cè)的ti或tj移到等號左側(cè)，然后在各式等號兩端分別加上Q，并今，則可把模型寫成：將上述模型中的各約束等式右側(cè)的ti或tj移到等號左側(cè)，然后在40要特別注意，在此模型中，對所有i=j，cij=-ci。由于目標(biāo)函數(shù)中這一項為常數(shù)，它不影響求最優(yōu)解，在優(yōu)化過程中可不予考慮。該模型的運輸表和運價表見下頁。當(dāng)不考慮轉(zhuǎn)運費時，可令。要特別注意，在此模型中，對所有i=j，cij41運輸表接收地供應(yīng)地供應(yīng)地銷售地發(fā)送量1…mm+1…m+n供應(yīng)地1x11…x1mx1,m+1…x1,m+nQ+a1……………………mxm.,1…xmmxm,m+1…xm,m+nQ+am銷售地m+1xm+1,1…xm+1,mxm+1,m+1…xm+1,m+nQ……………………m+nxm+n,1xm+1,n+mxm+n,m+1…xm+n,m+nQ接收量Q…QQ+bm+1…Q+bm+n運輸表接收地供應(yīng)地銷售地42運價表接收地供應(yīng)地供應(yīng)地銷售地發(fā)送量1…mm+1…m+n供應(yīng)地1-c1…c1mc1,m+1…c1,m+nQ+a1……………………mcm.,1…-cmcm,m+1…cm,m+nQ+am銷售地m+1cm+1,1…cm+1,mcm+1…cm+1,m+nQ……………………m+ncm+n,1cm+n,mvm+n,m+1…-cm+nQ接收量Q…QQ+bm+1…Q+bm+n運價表接收地供應(yīng)地銷售地發(fā)送量1…m43例2：已知A1，A2，A3三個飲料廠生產(chǎn)同一規(guī)格的飲料，用相同價格供應(yīng)B1，B2，B3三個銷售網(wǎng)點銷售。有兩個轉(zhuǎn)運站T1，T2，并且產(chǎn)品運輸可以在各產(chǎn)地，各銷售地及各轉(zhuǎn)運站之間轉(zhuǎn)運。已知各產(chǎn)地、銷地、中轉(zhuǎn)站相互之間每噸貨物的單位運價和產(chǎn)量，見下頁表。例2：已知A1，A2，A3三個飲料廠生產(chǎn)同一44各產(chǎn)地、銷地、中轉(zhuǎn)站之間的關(guān)系產(chǎn)地轉(zhuǎn)運站銷售地產(chǎn)量A1A2A3T1T2B1B2B3產(chǎn)地A1862━410830A2851395910A3654228720轉(zhuǎn)運站T12148463T2━328232銷售地B149242━5B2105863━4B38973254銷售量153510（1）對擴大的運輸問題建立運價表。對于沒有運輸路線的去任意大的正數(shù)M；對自己運輸?shù)倪\價cij=0。（2）所有轉(zhuǎn)運站的轉(zhuǎn)運量等于銷量，即Q=30+20+10=15+35+10=60,取T1，T2的產(chǎn)量與運量均為60t。（3）在原來的產(chǎn)量與銷量的數(shù)值在加上調(diào)運量，三個產(chǎn)地的產(chǎn)量為90t，70t，80t,銷量均為60t；三個銷量為75t,95t,70t,產(chǎn)量均為60t.如下頁表所示。各產(chǎn)地、銷地、中轉(zhuǎn)站之間的關(guān)系產(chǎn)地轉(zhuǎn)運站銷售地產(chǎn)量A1A2A45用表上作業(yè)法求解的最優(yōu)方案運量銷售地產(chǎn)量A1A2A3T1T2B1B2B3產(chǎn)地A160151590A2551570A3602080T15451060T2402060B16060B26060B36060銷售量6060606060759570用表上作業(yè)法求解的最優(yōu)方案運量銷售地產(chǎn)量A1A246實際最優(yōu)方案及最優(yōu)運輸路線如圖，最小費用為300。A1A2A3B1B2B3T1T23015102015152020510實際最優(yōu)方案及最優(yōu)運輸路線如圖，最小費用為300。A1A2A47第11、12、13章知識小結(jié)預(yù)測概述時間序列預(yù)測技術(shù)移動平均預(yù)測法指數(shù)平滑預(yù)測法回歸分析預(yù)測技術(shù)一元線性回歸預(yù)測法多元線性回歸預(yù)測分析庫存優(yōu)化確定性庫存模型確定性庫存基本模型缺貨事后補足的模型批量折扣庫存模型運輸問題物資調(diào)配問題運輸問題及數(shù)學(xué)模型用表上作業(yè)法求解運輸問題運輸問題的進-步討論應(yīng)用問題舉例第11、12、13章知識小結(jié)預(yù)測概述庫存優(yōu)化運輸問題48第13章運輸問題（TransportationProblem）在線性規(guī)劃問題中，有一類特殊類型的問題－－運輸問題。這類問題主要研究把某種物資從若干個產(chǎn)地調(diào)運到若干個銷地，每個產(chǎn)地的供應(yīng)量和每個銷地的銷售量及從一個產(chǎn)地到一個銷地的運輸費用已知，要求確定一個總運費最少的方案。第13章運輸問題在線性規(guī)劃問題中，有一類49第13章運輸問題（TransportationProblem）物資調(diào)配問題（MaterialTransferringProblem）運輸問題及數(shù)學(xué)模型（ModelforTransportation）用表上作業(yè)法求解運輸問題（SolveTransportationProblembyTable）運輸問題的進-步討論（FurtherDiscussionaboutTransportationProblem）應(yīng)用問題舉例（Parexample）第13章運輸問題（TransportationProb50物資調(diào)配問題在經(jīng)濟建設(shè)中，經(jīng)常會碰到大宗物資調(diào)運問題，如煤、鋼鐵，木材、糧食等物，在全國有若干生產(chǎn)基地，根據(jù)已有交通網(wǎng)絡(luò)，應(yīng)如何制訂調(diào)運方案，將這些物資運到各銷售地點，而運費最小，效率最高。在物流系統(tǒng)中，物資的調(diào)撥和配送是物流管理決策的一項主要工作。在市場經(jīng)濟條件下，對資源實行市場實行優(yōu)化配置，有利于國民經(jīng)濟持續(xù)發(fā)展。物資調(diào)配問題在經(jīng)濟建設(shè)中，經(jīng)常會碰到大宗物51運輸問題及數(shù)學(xué)模型本章研究單一品種物資的運輸調(diào)度問題。其典型情況是：設(shè)某種物品有個產(chǎn)地（或供方）Ai（i=1，2，…，m），各產(chǎn)地的產(chǎn)量分別是ai（i=1，2，…，m），有n個銷地Bj（j=1，2，…，n）,各銷地的銷量分別為bj（j=1，2，…，n）。假定從Ai（i=1，2，…，m）產(chǎn)地向銷地Bj（j=1，2，…，n）運輸單位物品的運價是。問怎樣調(diào)運這些物品才能使總運費最小?1.運輸問題數(shù)學(xué)模型運輸問題及數(shù)學(xué)模型本章研究單一品種物資的運52這是由多個產(chǎn)地供應(yīng)多個銷地的單品種物品運輸問題。為直觀起見，可列出該問題的運輸表（見下頁）。表中的變量Xij（i=1，2，…，m；j=1，2，…，n）為由產(chǎn)地Ai運往銷地Bj的物品數(shù)量。cij為Ai到Bj的單位運價。有時，將單位運價單獨列入另一個表中，并稱其為運價表。運輸單價cij銷售地Bi供應(yīng)量B1B2…Bnai產(chǎn)地AiA1c11c12…c1na1A2c21c22…c2na2┆┆┆…┆┆Amcm1cm2…cmnam銷售量bjb1b2…bn分布變量表A1x11x12…x1nA2x21x22…x2n┆┆┆…┆Amxm1xm2…xmn這是由多個產(chǎn)地供應(yīng)多個銷地的單品種物品運輸問53產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型可表示如下：其中，約束條件右側(cè)常數(shù)ai和bj滿足如果運輸問題的總產(chǎn)量等于其總銷量，即有則稱該運輸問題為產(chǎn)銷平衡運輸問題；反之，稱產(chǎn)銷不平衡運輸問題。產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型可表示如下：其中，約束條件右側(cè)常數(shù)54（1）運輸問題有有限最優(yōu)解2.運輸問題數(shù)學(xué)模型的特點對前述運輸問題，若令其變量其中，，則xij就是前述述運輸問題的一個可行解；另一方面，其目標(biāo)函數(shù)有下界。目標(biāo)函數(shù)值不會趨于-∞。由此可知，運輸問題必存在有限最優(yōu)解。（1）運輸問題有有限最優(yōu)解2.運輸問題數(shù)學(xué)模型的特點對前55（2）運輸問題約束條件的系數(shù)矩陣即除第i個和第m+j個分量為l外，其它分量全等于0。其系數(shù)列向量的結(jié)構(gòu)是：（2）運輸問題約束條件的系數(shù)矩陣即除第i個和第m+j個分量56由此可知，運輸問題具有下述特點：（1）約束條件系數(shù)矩陣的元素等于0或1。（2）約束條件系數(shù)矩陣的每一列有兩個非零元素，這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次。對產(chǎn)銷平衡運輸問題，除上述兩個特點外，還有以下特點：所有結(jié)構(gòu)約束條件都是等式約束，各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。由此可知，運輸問題具有下述特點：57例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城市銷售，各煤礦的供應(yīng)量和需求量如下頁表，各城市的需求量其間的距離(或單位運價)cij如表下頁表方格中的數(shù)據(jù)所示，試建立使總運輸量(或總運費)最小的運輸問題數(shù)學(xué)模型。單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020A2735820A3329440需求量bj302510158080例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城58解：設(shè)Xij為第i煤礦向第j城市的供應(yīng)量，cij表示為第i煤礦向第j城市供應(yīng)煤的單位運價。i=1，2，3；j=1，2，3，4。本例中a1+a2+a3=b1+b2+b3+b4=80，故是產(chǎn)銷平衡運輸問題。則可寫出其數(shù)學(xué)模型。解：設(shè)Xij為第i煤礦向第j城市的供應(yīng)量，cij表示為第i煤59根據(jù)運輸問題的數(shù)學(xué)模型求出的運輸問題的解X=(xij)，代表著一個運輸方案，其中每一個變量xij的值表示由Ai調(diào)運數(shù)量為xij的物品給Bij。前已指出運輸問題是一種線性規(guī)劃問題，可設(shè)想用迭代法進行求解，即先找出它的某一個基可行解，再進行解的最優(yōu)性檢驗，若它不是最優(yōu)解，就進行迭代調(diào)整，以得到一個新的更好的解，繼續(xù)檢驗和調(diào)整改進，直至得到最優(yōu)解為止。3.運輸問題的解

根據(jù)運輸問題的數(shù)學(xué)模型求出的運輸問題的解X=(xij60例1的一個基可行解：單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 8080例1的一個基可行解：單價cij銷售地Bj供應(yīng)量aiB1B2B61用表上作業(yè)法求解運輸問題表上作業(yè)法是求解運輸問題的一種簡便而有效的方法，其求解工作在運輸表上進行。表上作業(yè)法是一種迭代法，迭代步驟為：先按某種規(guī)則找出一個初始解(初始調(diào)運方案)；再對現(xiàn)行解作最優(yōu)性判別；若這個解不是最優(yōu)解，就在運輸表上對它進行調(diào)整改進，得出一個新解；再判別，再改進；直至得到運輸問題的最優(yōu)解為止。如前所述，迭代過程得出的所有解都要求是運輸問題的基可行解。用表上作業(yè)法求解運輸問題表上作業(yè)法是求解運輸問題的62步驟：（1）找出初始即可行解，即在產(chǎn)銷平衡表上分配初始調(diào)運方案，保證xij≥0，，并且xij>0的格（又稱實格）必須有m+n-1個；（2）求出各非基變量的檢驗數(shù)σij（空格檢驗數(shù)），σij≥0時停止計算；σij<0時在繼續(xù)調(diào)整調(diào)運方案（換基迭代法）；（3）確定進基變量（空格換入變量）和出基變量（實格調(diào)出變量），找出新的基可行解（用空格閉回路法調(diào)整）；（4）重復(fù)第1-3步，直至獲得σij≥0，輸出xij*和minZ=Z*為止。步驟：631.給出運輸問題的初始基可行解(初始調(diào)運方案)結(jié)合例1詳細說明表上作業(yè)法的解題步驟:（1）畫出運輸問題的求解作業(yè)表（見例1），由于，可以轉(zhuǎn)入（2）；（2）找出初始基可行解（又稱分配初始調(diào)運方案）。確定初始調(diào)運方案的方法很多，下面介紹三種常用的方法。單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 80801.給出運輸問題的初始基可行解(初始調(diào)運方案)64a.最小元素法容易直觀想到，為了減少運費，應(yīng)優(yōu)先考慮單位運價最小(或運距最短)的供銷業(yè)務(wù)，最大限度地滿足其供銷量。即對所有i和j，找出ci0j0=min(cij)，并將xi0j0=min(ai0,bj0)的物品量由Ai0供應(yīng)給Bj0；若xi0j0=ai0，則產(chǎn)地Ai0的可供物品己用完，以后不再繼續(xù)考慮這個產(chǎn)地，且Bj0的需求量由bj0減少為bj0-ai0。如果xi0j0=bj0，則銷地bj0的需求已全部得到滿足，以后不再考慮這個銷地，且Ai0的可供量由ai0減少為ai0-bj0。a.最小元素法65然后，在余下的供、銷點的供銷關(guān)系中，繼續(xù)按上述方法安排調(diào)運，直至安排完所有供銷任務(wù)，得到一個完整的調(diào)運方案(完整的解)為止。這樣就得到了運輸問題的一個初始基可行解(初始調(diào)運方案)。由于該方法基于優(yōu)先滿足單位運價(或運距)最小的供銷業(yè)務(wù)．故稱為最小元素法。然后，在余下的供、銷點的供銷關(guān)系中，繼續(xù)按上述66最小元素法分配的初始調(diào)運方案單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x23=10x24=10A3329440x31=10x32=25x34=5需求量bj30251015 8080最小元素法分配的初始調(diào)運方案單價cij銷售地Bj供應(yīng)B1B67b.西北角法西北角法與最小元素法不同，它不是優(yōu)先考慮具有最小單位運價的供銷業(yè)務(wù)，而是優(yōu)先滿足運輸表中西北角(即左上角)上空格的供銷需求。b.西北角法68西北角法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)量aiB1B2B3B4供應(yīng)地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 8080西北角法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)B1B2B69c.沃格爾法使用最小元素法有時按某一最小單位運價優(yōu)先安排調(diào)運時，可能導(dǎo)致不得不采用運費很高的其它供銷點對，使整個運輸費用增加。對每一個供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運價中找出最小單位運價和次小單位運價，并稱這兩個單位運價之差為該地的罰數(shù)。若罰數(shù)的值不大，當(dāng)不能按最小單位運價安排運輸時造成的運費損失不大；反之，如果罰數(shù)的值很大，不按最小運價組織運輸就會造成很大損失，故應(yīng)盡量按最小單位運價安排運輸。沃格爾法就是基于這種考慮提出來的。c.沃格爾法70沃格爾法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)量ai行罰數(shù)B1B2B3B412345供應(yīng)A1162102011⑤00x11=10x13=10地AiA2735820224④x22=20A332944011111x31=20x32=5x34=15需求量bj30251015

列罰數(shù)1213④

221③0

32100

44100

5④200

沃格爾法分配初始調(diào)運方案單價cij銷售地Bj供應(yīng)量ai71對比以上3種方法的初始調(diào)運方案，可看出，伏格爾法優(yōu)于其他方法，也就是說伏格爾法確定的初始解得目標(biāo)函數(shù)距離最優(yōu)解目標(biāo)函數(shù)最近，因而迭代運算數(shù)為最少，效率高。方法西北角法最小元素法伏格爾法目標(biāo)函數(shù)Z300250220對比以上3種方法的初始調(diào)運方案，可看出，伏格722.解的最優(yōu)性檢驗要判定運輸問題的某個解是否為最優(yōu)解，可仿照一般單純形法，檢驗這個解的各非基變量(對應(yīng)于運輸表中的空格)的檢驗數(shù)，苦有某空格的檢驗數(shù)為負，說明將變?yōu)榛兞繉⑹惯\輸費用減少，故當(dāng)前這個解不是最優(yōu)解。若所有空格的檢驗數(shù)全非負，則不管樣變換解均能使運輸費用降低，即目標(biāo)函數(shù)值已無法改進，這個解就是最優(yōu)解。a.閉回路法2.解的最優(yōu)性檢驗要判定運輸問題的某個解73現(xiàn)結(jié)合例1中用最小元素法給出的初始解，說明檢驗數(shù)的計算方法。其中一條閉回路檢驗數(shù)表銷售地供應(yīng)地B1B2B3B4A1σ12=6σ13=3σ14=8A2σ21=0σ22=-–3*A3σ33=8因σ22=–3<0，故知該解不是最優(yōu)解，還有待調(diào)整改正。現(xiàn)結(jié)合例1中用最小元素法給出的初始解，說明檢74閉回路可以是一個簡單的矩形，也可以是由水平和豎直邊線組成的其它更為復(fù)雜的封閉多邊形.閉回路可以是一個簡單的矩形，也可以是由水平和75運輸問題的進—步討論

上—節(jié)講述的運輸問題的算法，是以總產(chǎn)量等于總銷量(產(chǎn)銷平衡)為前提的。實際上在很多運輸問題中，總產(chǎn)量不等于總銷量。這時，為了使用前述表上作業(yè)法求解，就需將產(chǎn)銷不平衡運輸問題化為產(chǎn)銷平衡運輸問題。1.產(chǎn)銷不平衡的運輸問題運輸問題的進—步討論上—節(jié)講述的運輸問題的76如果總產(chǎn)量大于總銷量，即這時的數(shù)學(xué)模型是如果總產(chǎn)量大于總銷量，即77為借助于產(chǎn)銷平衡時的表上作業(yè)法求解，可增加一個假想的銷地Bn+1，由于實際上它不存在，因而由產(chǎn)地Ai(i=1,2,…,m)調(diào)運到這個假想銷地的物品數(shù)量xi,n+1(相當(dāng)于松弛變量)，實際上是就地存貯在Ai的物品數(shù)量。就地存貯的物品不經(jīng)運輸，故其單位運價ci,n+1(i=1,2,…,m)。為借助于產(chǎn)銷平衡時的表上作業(yè)法求解，可增加一個假想的78若令假想銷地的銷量為bn+1，且則模型變?yōu)閷?yīng)的運輸表見下頁。若令假想銷地的銷量為bn+1，且對應(yīng)的運輸表見下頁。79單價cij銷售地Bj供應(yīng)量aiB1…BnBn+1供應(yīng)地AiA1C11c12c1n0a1X11A2c21c22c2n0a2x21x22Amcm1cm2cmn0amx32x33x34需求量bjb1…Bn單價cij銷售地Bj供應(yīng)B1…BnBn+1供A1C11c1280總銷量大于總產(chǎn)量的情形可仿照上述類似處理，即增加一個假想的產(chǎn)地Am+1，它的產(chǎn)量等于

由于這個假想的產(chǎn)地并不存在，求出的由它發(fā)往各個銷地的物品數(shù)量，實際上是各銷地所需物品的欠缺額，顯然有總銷量大于總產(chǎn)量的情形可仿照上述類似處理，即81單價cij銷售地Bj供應(yīng)量aiB1B2B2B4供應(yīng)地AiA1413459A21236106A3782610需求量bj54672522例：由各煤廠到各用戶的單位運價如表所示，請確定總運費最少的調(diào)運方案。單價cij銷售地Bj供應(yīng)B1B2B2B4供A1413459A82單價cij銷售地BjB1B2B2B4供應(yīng)地AiA141345A2123610A37826需求量bj546725-22=3供應(yīng)量ai9610

555B5單價cij銷售地BjB1B2B2B483在以上討論中，假定物品由產(chǎn)地直接運送到銷售目的地，不經(jīng)中間轉(zhuǎn)運。但是，常常會遇到這種情形：需先將物品由產(chǎn)地運到某個中間轉(zhuǎn)運站(可能是另外的產(chǎn)、銷地或中間轉(zhuǎn)運倉庫)，然后再轉(zhuǎn)運到銷售地。有時，經(jīng)轉(zhuǎn)運比直接運到目的地更為經(jīng)濟?？傊?，很多情況下，在決定運輸方案時有必要把轉(zhuǎn)運也考慮進去。顯然．考慮轉(zhuǎn)運將使運輸問題變得更為復(fù)雜。2.有轉(zhuǎn)運的運輸問題

(a)無轉(zhuǎn)運(b)包含轉(zhuǎn)運在以上討論中，假定物品由產(chǎn)地直接運送到銷售目84

假定m個產(chǎn)地A1,A2,…,Am和n個銷地B1,B2,…,Bn都可以作為中間轉(zhuǎn)運站使用，從而發(fā)送物品的地點相接收物品的地點都有m+n個。這樣一來，我們就得到了一個擴大了的運輸問題。為建立其數(shù)學(xué)模型，令：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)運單位物品的費用。假定m個產(chǎn)地A1,A2,…,Am和n個銷地B85現(xiàn)將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面，銷地排在后面，則有假定為平衡運輸問題，即有現(xiàn)將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面，銷地排在后面，則有86根據(jù)前面對平衡運輸問題的討論，可得該擴大了的運輸問題的數(shù)學(xué)模型如下：根據(jù)前面對平衡運輸問題的討論，可得該擴大了的運輸問題的數(shù)學(xué)模87將上述模型中的各約束等式右側(cè)的ti或tj移到等號左側(cè)，然后在各式等號兩端分別加上Q，并今，則可把模型寫成：將上述模型中的各約束等式右側(cè)的ti或tj移到等號左側(cè)，然后在88要特別注意，在此模型中，對所有i=j，cij=-ci。由于