運(yùn)籌學(xué)課程軟件第三章運(yùn)輸問答

1、17/17第三章運(yùn)輸問題一、學(xué)習(xí)目的與要求、掌握表上作業(yè)法及其在產(chǎn)銷均衡運(yùn)輸問題求解中的應(yīng)用、掌握產(chǎn)銷不均衡運(yùn)輸問題求解方法二、課時(shí)6學(xué)時(shí)第一節(jié)運(yùn)輸問題及其數(shù)學(xué)模型一、運(yùn)輸問題的數(shù)學(xué)模型單調(diào)品種運(yùn)輸問題的典型狀況：設(shè)某種物件有m個(gè)產(chǎn)地A1,A2,Am，各產(chǎn)地的產(chǎn)量分別是a1,a2,am；有N個(gè)銷地B1,B2,Bn，各銷地地銷量分別為b1,b2,bn。假設(shè)從產(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)最??？為直觀清楚起見，列出運(yùn)輸表：銷地B2Bn產(chǎn)地B1A1c11c12c1nx11x12x1nA2c21c22c2nx21x22x

2、2nc11c12c1nx11x12x1nAmcm1cm2cmnxXxm1mnm2銷量b1b2bn表中xij為由產(chǎn)地Ai到銷地Bj的物件數(shù)目，cij表示產(chǎn)地Ai到銷地Bj的單位運(yùn)價(jià)。假如運(yùn)輸問題的總產(chǎn)量等于其總銷量，即有mnaibji1j1則稱該運(yùn)輸問題為產(chǎn)銷均衡運(yùn)輸問題；反之，稱為產(chǎn)銷不均衡運(yùn)輸問題。產(chǎn)銷均衡運(yùn)輸問題的數(shù)學(xué)模型以下：產(chǎn)量a1a2ammn1minzi1j1cijxijnxijaii1,2,.,mj1ms.t.xijbjj1,2,.,ni1xij0這就是運(yùn)輸問題的數(shù)學(xué)模型，它包含mn個(gè)變量，(n十m)個(gè)拘束方程其系數(shù)矩陣的構(gòu)造比較松懈，且特別。二、運(yùn)輸問題數(shù)學(xué)模型的特色、運(yùn)輸問題有

3、有限最優(yōu)解，即必有最優(yōu)基本可行解、運(yùn)輸問題拘束條件的系數(shù)矩陣A的秩為(m+n-1)該系數(shù)矩陳中對(duì)應(yīng)于變量xij的系數(shù)向量pij，其重量中除第i個(gè)和第m十j個(gè)為1之外，其余的都為零即Aij(0110)=ei+em+j對(duì)產(chǎn)銷均衡的運(yùn)輸問題擁有以下特色：拘束條件系數(shù)矩陣的元素等于0或1(2)拘束條件系數(shù)矩陣的每一列有兩個(gè)非零元素，對(duì)應(yīng)于每一個(gè)變量在前m個(gè)拘束方程中出現(xiàn)一次，在后n個(gè)拘束方程中也出現(xiàn)一次。其余，關(guān)于產(chǎn)銷均衡問題，還有以下特色全部構(gòu)造拘束條件都是等式拘束各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和第二節(jié)用表上作業(yè)法求解運(yùn)輸問題解題步驟第1步：確立初始基本可行解。第2步：最優(yōu)性鑒別，若最優(yōu)準(zhǔn)則ij0，

4、則目前解最優(yōu)，計(jì)算停止，不然轉(zhuǎn)第3步。第3步：取一個(gè)檢驗(yàn)數(shù)最小的非基變量做進(jìn)基變量。第4步：調(diào)整目前基本可行解，轉(zhuǎn)第2步一、確立初始基本可行解（初始調(diào)運(yùn)方案）以實(shí)例介紹：例某部門有3個(gè)生產(chǎn)同類產(chǎn)品的工廠(產(chǎn)地),生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)(銷地)銷售，各工廠的生產(chǎn)量、各銷點(diǎn)的銷售量（假設(shè)產(chǎn)位均為t）以及各工廠到各銷售點(diǎn)的單位運(yùn)價(jià)（元/t）于下表中，要求研究產(chǎn)品如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最??？銷地B1B2B3B4產(chǎn)量產(chǎn)地A141241116A22103910A38511622銷量8141214A最小元素法銷地B1B2B3B4產(chǎn)量產(chǎn)地A141241116106A2210391082A38511622148銷

5、量814121434總運(yùn)費(fèi)（目標(biāo)函數(shù)）：zcijxij246這個(gè)解滿足拘束條件，其非零變量的個(gè)數(shù)為6（等于i1j1m+n-1=3+4-1=6）。B西北角法銷地B1B2B3B4產(chǎn)量產(chǎn)地2210391064A38511622814銷量814121434總運(yùn)費(fèi)（目標(biāo)函數(shù)）：zcijxij372這個(gè)解滿足拘束條件，其非零變量的個(gè)數(shù)為6（等于i1j1m+n-1=3+4-1=6）。C沃格爾（Vogel）法銷地BBB產(chǎn)行罰數(shù)B產(chǎn)地1234量123454141A12116000711242139A201011166828516A312212148銷量81412144812513列22

6、13罰3212數(shù)4125234總運(yùn)費(fèi)（目標(biāo)函數(shù)）：zcijxij244i1j1二、解的最優(yōu)性檢驗(yàn)、閉回路法銷地B1B2B3B4產(chǎn)量產(chǎn)地A141241110166A2210398210A38511614228銷量8141214檢驗(yàn)數(shù)表銷地B1B2B3B4產(chǎn)量產(chǎn)地A112A21-1A31012銷量因?yàn)?40，故知解不是最優(yōu)解。、對(duì)偶變量法（也稱位勢(shì)法）對(duì)產(chǎn)銷均衡問題，若用u1,u2,um,v1,v2,vn分別表示前m個(gè)拘束條件與后n個(gè)拘束條件的對(duì)偶變量，即有對(duì)偶變量Y(u1,u2,um,v1,v2,vn)這時(shí)對(duì)偶問題的對(duì)偶規(guī)劃寫成mnmaxzaiuibjuji1j1uivjciji1,2,ms.t

7、.1,2,njui,vj的符號(hào)不限由上一章知道，線性規(guī)劃問題變量xj的檢驗(yàn)數(shù)可表示為jcjzjcjCBB1PjcjYPj由此可寫出運(yùn)輸問題某變量xij的檢驗(yàn)數(shù)以下：ijcijzijcijYPijcij(u1,u2,um,v1,v2,vn)Pijcij(uivj)現(xiàn)設(shè)我們已獲取解到了運(yùn)輸問題的一個(gè)基可行解，其基變量是xi1j1,xi12j2,xisjs,smn1因?yàn)榛兞康臋z驗(yàn)數(shù)等于零，故對(duì)這組基變量可寫出方程組ui1vj1ci11,j1ui21vj2ci2,j2uis1vjsci1s,js這個(gè)方程組有m+n-1個(gè)方程。解以上方程組，可得解（上方程組解不獨(dú)一），此方程組解稱為位勢(shì)。由上章知當(dāng)每個(gè)

8、ijcij(uivj)0達(dá)到最優(yōu)解。例用位勢(shì)法對(duì)上例最小元素法有的解作最優(yōu)性檢驗(yàn)。銷地B1B2B3B4產(chǎn)ui產(chǎn)地量A1412411u110616A221039u28210A385116u314822銷量814121448vjv1v2v3v4解：先成立方程組u1v34u1v411u2v12u2v33u3v25u3v46令u20得方程組的解：v12,v33,u11,v410,u34,v29計(jì)算檢驗(yàn)數(shù)銷地B1B2B3B4產(chǎn)ui產(chǎn)地量A1412411116A221039010A385116-422銷量814121448vj29310因?yàn)?40，故知解不是最優(yōu)解。三、解的改良（用閉回路法調(diào)整目前基可行解

9、）解的改良步驟：（1）以xij為換入變量，找出運(yùn)輸表中的閉回路；2）對(duì)極點(diǎn)進(jìn)行編號(hào)；3）確立換出變量：在閉回路上的全部偶數(shù)極點(diǎn)中找出運(yùn)輸量量小的極點(diǎn)，以該格中的變量為換出變量；4）以換出變量值為奇數(shù)極點(diǎn)處的運(yùn)輸量增添值，得新的運(yùn)輸方案；5）檢驗(yàn)新的方案能否為最優(yōu)，如不然重復(fù)以上步驟。例：對(duì)上例進(jìn)行改良求解。銷地B1B2B3B4產(chǎn)ui產(chǎn)地量A1412411210616A221039082010A385116-314822銷量814121448vj2829目標(biāo)函數(shù)值為244u1v34u1v411u2v12u2v49u3v25u3v46令u20得方程組的解：v12,v49,u12,u33,v28,v

10、32銷地B1B2B3B4產(chǎn)ui產(chǎn)地量A14124112020016A2210390021010A385116-39012022銷量814121448vj2829所以此方案為最優(yōu)方案。四、表上作業(yè)法計(jì)算中的幾個(gè)問題、某個(gè)基本可行解有幾個(gè)非基變量的檢驗(yàn)數(shù)為負(fù)若運(yùn)輸問題的某個(gè)基可行解有幾個(gè)非基變量的檢驗(yàn)數(shù)均為負(fù)，在連續(xù)進(jìn)行迭代時(shí)，取它們中的任一變量均可使目標(biāo)函數(shù)值獲取改良，但平常取ij0中最小者對(duì)應(yīng)的變量為換入變量。、無量多個(gè)最優(yōu)解當(dāng)?shù)竭\(yùn)輸問題的最優(yōu)解時(shí)，假如有某非基變量的檢驗(yàn)數(shù)0，則說明該運(yùn)輸問題有無量多最優(yōu)解。（如上例，為獲取另一個(gè)最優(yōu)解，只要讓ij0的非基變量進(jìn)基）、退化問題當(dāng)運(yùn)輸問題某部

11、分產(chǎn)地的產(chǎn)量和與另一部分銷地的銷量和相等時(shí)，在迭代過程中有可能在某個(gè)格填入一個(gè)運(yùn)量時(shí)需同時(shí)劃去運(yùn)輸表的一行和一列，這時(shí)就出現(xiàn)了退化。在運(yùn)輸問題中，退化解是常常發(fā)生的，為了使表上作業(yè)法的迭代工作進(jìn)行下去，退化解應(yīng)在同時(shí)劃去的一行或一列中的某個(gè)空格中填入數(shù)字0，表示這個(gè)格中的變量是取值為0的基變量，使迭代過程中基可行解的重量恰巧為m+n-1個(gè)。b.在用閉回路法調(diào)整目前基本可行解時(shí)，調(diào)整量的取值應(yīng)為minxij/(i,j)為閉回路上全部偶數(shù)號(hào)格點(diǎn)。這時(shí)可能出現(xiàn)有兩個(gè)（或以上）偶數(shù)號(hào)格點(diǎn)的xij都相等且都為極小值，只好取此中一個(gè)為離基格，其余的仍作為基格，而在作運(yùn)輸量調(diào)整時(shí)，運(yùn)輸量與相等的那些偶數(shù)號(hào)格

12、點(diǎn)的xij都將調(diào)整為0，所以得到的也是一個(gè)退化了的基可行解。第三節(jié)運(yùn)輸問題的進(jìn)一步談?wù)撘?、產(chǎn)銷不均衡的運(yùn)輸問題、假如總產(chǎn)量大于總銷量，即mnaibji1j1此時(shí)運(yùn)輸問題的數(shù)學(xué)模型為mnminzcijxiji1j1nxijaii1,2,.,mj1ms.t.xijbjj1,2,.,ni1xij0為借助產(chǎn)銷均衡時(shí)表上作業(yè)法求解，可增添一個(gè)設(shè)想銷地Bn+1，因?yàn)閷?shí)質(zhì)上它不存在，因此由產(chǎn)地Ai（i=1,2,m）調(diào)運(yùn)到這個(gè)設(shè)想銷地的物件數(shù)目xi,n+1（相當(dāng)于松馳變量），其實(shí)是就地存貯在Ai的物件數(shù)目。就地存貯的物件數(shù)目不經(jīng)運(yùn)輸，故可令其運(yùn)價(jià)ci,n+1=0（i=1,2,m）。若令設(shè)想銷地的銷量為bn+1

13、，且mnbn1aibji1j1則模型變?yōu)閙n1minzcijxiji1j1n1xijaii1,2,.,mj1mxijbjj1,2,.,n1i1xij0運(yùn)輸表銷地BBBn+1產(chǎn)量2n產(chǎn)地B1c1c1c1012nA1a1x11xx1n12c2c2c2012nA2a2x21xx2n22c1c1c1012nx11xx1n12cmcmcm012nAmamxm1Xm2xmn銷量b1b2bnbn+12、總銷量大于總產(chǎn)量可設(shè)想增添一個(gè)產(chǎn)地Am+1，它的產(chǎn)量等于nmam1bjaij1i1因?yàn)檫@個(gè)產(chǎn)地其實(shí)不存在，求出由它發(fā)往各銷地的物件數(shù)目xm+1,j（j=1,2,n），實(shí)質(zhì)上各銷地所需物件的欠缺額，明顯有cm+

14、1,j=0（j=1,2,n）。所以數(shù)學(xué)模型為m1nminzcijxiji1j1nxijaii1,2,.,m1j1mxijbjj1,2,.,n1ij0例某市有三個(gè)造紙廠A1,A2,A3,其紙產(chǎn)量分別為8，5，9個(gè)單位，有4個(gè)集頂用戶B1,B2,B3,B4,其需用量為4，3，5，6個(gè)單位，由各廠到各用戶的單位運(yùn)價(jià)如表所示，試確立總運(yùn)費(fèi)最小的調(diào)運(yùn)方案。銷地BBB產(chǎn)B1243產(chǎn)地量A1312348A2112595A367159銷量4356解略:最優(yōu)方案以下銷地B1B2B3產(chǎn)B4產(chǎn)地量A131234484A21125935A36715592銷量4356Minz=49二、有轉(zhuǎn)運(yùn)的運(yùn)輸問題假設(shè)某一產(chǎn)品有m個(gè)

15、產(chǎn)地A1,A2,Am和n個(gè)銷地B1,B2,Bn，都可作為中間站使用，從而發(fā)送物件的地址和接收物件的地址都有m+n個(gè)。這樣一來，我們就獲取一個(gè)擴(kuò)大了的運(yùn)輸問題。令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à)；ci：表示第i個(gè)地址轉(zhuǎn)運(yùn)單位物件的花費(fèi)。若將產(chǎn)地與銷地一致編號(hào)，并把產(chǎn)地排在前，銷地排在后，則有am1am2amn0b1b2bm0假設(shè)為產(chǎn)銷均衡問題，即有mmnaibjQi1j1運(yùn)輸表：銷地產(chǎn)地銷地發(fā)送量1mm1m產(chǎn)地n1x11x1mx1,m1x1,mnQ

16、a1產(chǎn)地mxm1xmmxm,m1xm,mnQamm1xm1,1xm1,mxm1,m1xm1,mnQ銷地Qnmxnm,1xmm,mxmn,m1xmn,mnQ接收量QQQbm1Qbmn運(yùn)價(jià)表：銷地產(chǎn)地銷地發(fā)送量1mm1m產(chǎn)地n1c1c1mc1,m1c1,mnQa1產(chǎn)地mcm1cmcm,m1cm,mnQamm1cm1,mcmcm1,mQcm1,11n銷地mQncmm,mcmn,m1cmQcnm,1n接收量QQQbm1Qbmn例：以以下圖示出了一個(gè)運(yùn)輸系統(tǒng)，它包含兩個(gè)產(chǎn)地、兩個(gè)銷地及一此中轉(zhuǎn)站，各產(chǎn)地產(chǎn)量和各銷地銷量用相應(yīng)節(jié)點(diǎn)處箭線旁的數(shù)字表示，節(jié)點(diǎn)連線上的數(shù)字表示此間的運(yùn)輸單價(jià)，節(jié)點(diǎn)旁的數(shù)字為該地的

17、轉(zhuǎn)運(yùn)單價(jià)，試確立最優(yōu)運(yùn)輸方案。解：銷地產(chǎn)地轉(zhuǎn)運(yùn)銷地產(chǎn)地123451-4532M50(50)10(10)產(chǎn)地5-12M4250(50)(20)2020(20)轉(zhuǎn)32-355350(30)(20)運(yùn)發(fā)送量6090502M5-36450銷50(50)地M456-555050(50)銷量5050508070用最小元素法得初始運(yùn)輸方案，最經(jīng)過2次迭代得最優(yōu)解,總運(yùn)費(fèi)300。第四節(jié)應(yīng)用問題舉例因?yàn)樵谧兞總€(gè)數(shù)相等的狀況下，表上作業(yè)法的計(jì)算遠(yuǎn)比純真形法簡(jiǎn)單得多所以在解決實(shí)質(zhì)問題時(shí)，人們常常盡可能把某些線性規(guī)劃的問題化為運(yùn)輸問題的數(shù)學(xué)模型下邊介紹幾個(gè)典型的例子例1某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別供應(yīng)10，1

18、5，25，20臺(tái)同一規(guī)格的柴油機(jī)已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如表所示又假如生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨的，每臺(tái)每積壓一個(gè)季度需積蓄、保護(hù)等花費(fèi)0.15萬元要求在達(dá)成合同的狀況下，做出使該廠整年生產(chǎn)(包含儲(chǔ)存、保護(hù))花費(fèi)最小的決議解:因?yàn)槊總€(gè)季度生產(chǎn)出來的柴油機(jī)不必定當(dāng)季交貨，所以設(shè)油機(jī)數(shù)依據(jù)合同要求，一定滿足：xij為第i季度生產(chǎn)的用于第j季度交貨的柴x1110 x12x2215x13x23x3325x14x24x34x4420又每季度生產(chǎn)的用于當(dāng)季和此后各季交貨的柴油機(jī)數(shù)不行能超出該季度的生產(chǎn)能力，故又有：x11x12x13x1425x22x232x2435x33x3430

19、x4410第i季度生產(chǎn)的用于j季度交貨的每臺(tái)柴油機(jī)的實(shí)質(zhì)成本cij應(yīng)當(dāng)是該季度單位成本加上積蓄、保護(hù)等花費(fèi)cij的詳細(xì)數(shù)值見表設(shè)用ai表示該廠第i季度的生產(chǎn)能力，bj表示第j季度的合同供應(yīng)量，則問題可寫成：44minzcijxiji1j14xijaij14xijbji1xij0因?yàn)楫?dāng)ji時(shí)，xij=0所以當(dāng)ji時(shí),取cij=M,M為一個(gè)充分大的正數(shù)。其余，因?yàn)槭钱a(chǎn)量大于銷量的不均衡問題，加上一個(gè)設(shè)想的需求D，就能夠把問題變?yōu)楫a(chǎn)銷均衡的運(yùn)輸模型，并寫出產(chǎn)銷均衡表和單位運(yùn)價(jià)表(合在一同，以下)經(jīng)用表上作業(yè)法求解，可得多個(gè)最優(yōu)方案，表332中列出最優(yōu)方案之一即第1季度生產(chǎn)25臺(tái)，10臺(tái)當(dāng)季交貨，15臺(tái)季度交貨；季度生產(chǎn)5臺(tái)用于季度交貨；季度生