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

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

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

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

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

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

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

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

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

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

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

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

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

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