運(yùn)籌學(xué) 運(yùn)輸問題

2023/2/71第三章

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

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

銷地產(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

運(yùn)往銷地Bj

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

行n

行第i

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

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

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

銷地產(chǎn)地B1B2B3產(chǎn)量A134210A23534銷量356x11x12x13x21x22x23解題思路：（1）假設(shè)變量（2）分析約束（3）明確目標(biāo)（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是該運(yùn)輸問題的一個(gè)可行解。目標(biāo)函數(shù)值z=452023/2/79§3-2用表上作業(yè)法求解運(yùn)輸問題它是求解運(yùn)輸問題的一種簡便而有效的方法,其求解過程在運(yùn)輸表上進(jìn)行,它是一種迭代法,其步驟為：1.先按某種規(guī)劃找出一個(gè)初始解(初始調(diào)運(yùn)方案）；2.對(duì)現(xiàn)行解作最優(yōu)性判別；3.若不是最優(yōu)解,就在表上對(duì)它進(jìn)行調(diào)整改進(jìn),得出一個(gè)新解；4.再判別,再改進(jìn),直到得到運(yùn)輸問題的最優(yōu)解為止；※在迭代過程中,得出的所有解都要求是運(yùn)輸問題的基可行解。例2某部門有3個(gè)生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個(gè)銷售地出售，各工廠的生產(chǎn)量，各銷售地的銷售量（假定單位均為噸）以及各工廠到各銷售地的單位運(yùn)價(jià)（元/噸）示于表3-4中，要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最小？返回第三章目錄2023/2/710一、確定運(yùn)輸問題的初始基可行解（初始調(diào)運(yùn)方案）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該運(yùn)輸問題一個(gè)初始可行解為：x13=10,x14=6,x21=8,x23=2,x32=14,x34=8.總運(yùn)費(fèi)＝4×10＋11×6＋2×8＋3×2＋5×14＋6×8＝2462023/2/711用西北角法確定運(yùn)輸問題的初始可行解

銷地產(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.總運(yùn)輸費(fèi)用z＝8×4＋8×12＋6×10＋4×3＋8×11＋14×6＝3722023/2/712用沃格爾法確定運(yùn)輸問題的初始可行解

銷地產(chǎn)地B1B2B3B4產(chǎn)量行罰數(shù)12345A141241116A22103910A38511622銷量814121448列罰數(shù)123450112513140122138012128761212002243.沃格爾法該運(yùn)輸問題的可行解為：x13=12,x14=4,x21=8,x24=2,x32=14,x34=8,其他變量等于0。總運(yùn)輸費(fèi)z＝2440806020404002023/2/713確定初始可行解的三種方法比較最小元素法：z＝246西北角法：z＝372沃格爾法：z＝244沃格爾法解出的目標(biāo)函數(shù)值最小，最小元素法次之，西北角法最大；一般說來，沃格爾法得出的解質(zhì)量最好，在運(yùn)輸問題中，常用來作最優(yōu)解的近似解。二、解的最優(yōu)性檢驗(yàn)2023/2/7141.最小元素法解題思想：為了減少運(yùn)費(fèi),應(yīng)優(yōu)先考慮單位運(yùn)價(jià)最小(或運(yùn)距最短)的供銷業(yè)務(wù),最大限度地滿足其供銷量。解題步驟：(4)在余下的供銷點(diǎn)的供銷關(guān)系中,繼續(xù)安排調(diào)運(yùn),直到安排完成所有供銷任務(wù),得到一個(gè)完整的方案為止。確定初始基可行解（初始調(diào)運(yùn)方案）2023/2/7152.西北角法解題思想:優(yōu)先滿足運(yùn)輸表中西北角(即左上角)上空格的供銷量需求.解題步驟:(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)運(yùn),最后得出一個(gè)初始方案。用西北角法確定運(yùn)輸問題的初始可行解2023/2/7163.沃格爾法解題思想：對(duì)于每一個(gè)供應(yīng)地或銷售地，均可由它到各銷售地或到各供應(yīng)地的單位運(yùn)價(jià)中找出最小單位運(yùn)價(jià)和次小單位運(yùn)價(jià),并稱這兩個(gè)單位運(yùn)價(jià)之差為該供應(yīng)地或銷售地的罰數(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)輸。解題步驟：（1）先計(jì)算運(yùn)輸表中每一行和每一列的罰數(shù)值，并稱為行罰數(shù)和列罰數(shù)。（2）將行罰數(shù)填入位于運(yùn)輸表右側(cè)行罰數(shù)欄的左邊第一列的相應(yīng)格子中；列罰數(shù)填入位于運(yùn)輸表下邊列罰數(shù)欄的第一行的相應(yīng)格子中。（3）找出該列和該行的列罰數(shù)和行罰數(shù)中的最大值；根據(jù)最大罰數(shù)值的位置在運(yùn)輸表中運(yùn)價(jià)最小的格中填入一個(gè)盡可能大的運(yùn)輸量，并劃去對(duì)應(yīng)的一行或一列。（4）繼續(xù)找其它列和行的列罰數(shù)和行罰數(shù)；找出其它運(yùn)輸量；已劃去的不再找。直到最后按排完，即得到一個(gè)初始運(yùn)輸方案。用沃爾沃法確定運(yùn)輸問題的初始可行解2023/2/717二、解的最優(yōu)性檢驗(yàn)得到了初始可行解后，應(yīng)對(duì)其進(jìn)行判別是否是最優(yōu)解,常用方法有：閉回路法和對(duì)偶變量法。1.閉回路法解題思想：對(duì)運(yùn)輸表中的解的各非基變量即某空格(Ai,Bj)進(jìn)行檢驗(yàn);若存在檢驗(yàn)數(shù)為負(fù)，說明將xij變?yōu)榛兞亢?，將使運(yùn)費(fèi)減少；故當(dāng)前解不是最優(yōu)解；若所有檢驗(yàn)數(shù)為正，則無論怎樣變換解均不能使運(yùn)輸費(fèi)降低，即當(dāng)前解是最優(yōu)解。解題步驟：以某空格(Ai,Bj)為頂點(diǎn)，由填有數(shù)字的其它格為其它頂點(diǎn)，通過水平線段和豎直線段組成封閉多邊形。可以是簡單的多邊形，也可以是復(fù)雜的多邊形。然后順時(shí)針或逆時(shí)針轉(zhuǎn)，以(Ai,Bj)為第一頂點(diǎn)格，奇格為正，偶格為負(fù)，將單位運(yùn)價(jià)之代數(shù)和作為該空格的檢驗(yàn)數(shù)sij

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

銷地產(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.對(duì)偶變量法（位勢法）:解題思想：用u1,u2,…,um分別表示與前m個(gè)約束相對(duì)應(yīng)的對(duì)偶變量，用v1,v2,…,vn分別表示與后n個(gè)約束相對(duì)應(yīng)的對(duì)偶變量，即對(duì)偶變量向量：Y=(u1,u2,…,um,v1,v2,…,vn)將運(yùn)輸問題的數(shù)學(xué)模型寫成對(duì)偶規(guī)劃：2023/2/720經(jīng)過整理得出運(yùn)輸問題變量xij的檢驗(yàn)數(shù)為：如果所有的sij≥0，則所求得的可行解是最優(yōu)解，如果存在sij＜0，則所求得的可行解不是最優(yōu)解，需要改進(jìn)。2023/2/721解題步驟：(一）在運(yùn)輸表右邊增加一位勢列ui；在下邊增加一位勢行vj；(二）計(jì)算位勢(三）計(jì)算檢驗(yàn)數(shù)：

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

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

和位勢行vj

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

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

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

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

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

銷地產(chǎn)地B1B2…BnBn+1（儲(chǔ)存）產(chǎn)量A1x11c11x12c12……x1nc1nx1,n+10a1A2x21c21x22c22……x2nc2nx2,n+10a2┆┆…┆…┆…┆…┆…┆Amxm1cm1xm2cm2……xmncmnxm,n+10am銷量b1b2…bn2023/2/731(2)如果總銷量大于總產(chǎn)量，則增加一個(gè)假想產(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)運(yùn)的運(yùn)輸問題由于空間位置的需要，需考慮轉(zhuǎn)運(yùn)問題，才能使總運(yùn)費(fèi)最小。A1A2B2B1B3產(chǎn)地銷地A2A1B2B1B3產(chǎn)地銷地（a)無轉(zhuǎn)運(yùn)（a)包含轉(zhuǎn)運(yùn)比較以上兩圖。顯然，包含轉(zhuǎn)運(yùn)的運(yùn)輸問題復(fù)雜得多。2023/2/733假定m個(gè)產(chǎn)地A1,A2,…,Am和n個(gè)銷地B1,B2,…,Bn都可以作為中間轉(zhuǎn)運(yùn)站使用，從而發(fā)送物品的地點(diǎn)和接收物品的地點(diǎn)都有m+n個(gè)。ai

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

：第j個(gè)銷地的銷量（凈需要量）；xij

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

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

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

接收發(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

有一個(gè)運(yùn)輸系統(tǒng)包括二個(gè)產(chǎn)地（①、②）、二個(gè)銷地（④、⑤）及一個(gè)中間轉(zhuǎn)運(yùn)站（③），各產(chǎn)地的產(chǎn)量和各銷地銷量用相應(yīng)節(jié)點(diǎn)處箭線旁的數(shù)字表示，節(jié)點(diǎn)聯(lián)線上的數(shù)字表示其間的運(yùn)輸單價(jià)，節(jié)點(diǎn)旁的數(shù)字為該地的轉(zhuǎn)運(yùn)單價(jià)，試確定最優(yōu)運(yùn)輸方案。解：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ù)，可得該問題的運(yùn)輸表3-192023/2/739表3-19

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

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

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

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

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