管理運(yùn)籌學(xué)02-7運(yùn)輸問題

1、Transportation Model第四節(jié)運(yùn)輸問題一、運(yùn)輸問題及其數(shù)學(xué)模型二、表上作業(yè)法求解運(yùn)輸問題三、產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用運(yùn)輸問題及其數(shù)學(xué)模型問題的提出運(yùn)輸問題：產(chǎn)地、銷地、產(chǎn)量、銷量例1有A1，A2，A3三座鐵礦，每天要把生產(chǎn)的鐵礦石運(yùn)往B1，B2，B3，B4四個(gè)煉鐵廠。各礦的產(chǎn)量、各廠的銷量以及各廠礦間的運(yùn)價(jià)如下表所示。問應(yīng)如何組織調(diào)運(yùn)才能使運(yùn)費(fèi)最少？3運(yùn)輸問題及其數(shù)學(xué)模型(百元/百噸 )4z 總運(yùn)費(fèi)（百元）xij Ai運(yùn)給Bj的鐵礦石數(shù)量（百噸）B1B2B3B4產(chǎn)量A1 A2 A3632575843297523銷量2314運(yùn)輸問題及其數(shù)學(xué)模型(百元/百噸 )5B1B2B3B4

2、產(chǎn)量A16x113x122x135x145A27x215x228x234x242A33x312x329x337x343銷量2314運(yùn)輸問題及其數(shù)學(xué)模型數(shù)學(xué)模型為:min z = 6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34x11+x12+x13+x14x21+x22+x23+x24= 5= 2x31+x32+x33+x34 = 3x11+x21+x31= 2= 3= 1s.t.x12+x22+x32x13+x23+x24j =1, 2, 3, 4 )+x33x14( i =1, 2, 3;+x34 = 4xij06運(yùn)輸模

3、型的特點(diǎn)：(1) 它有mn個(gè)變量，m+n個(gè)約束方程(2) 其系數(shù)陣具有特殊的結(jié)構(gòu)1111m=3行111111111A =11111n=4行1111117運(yùn)輸問題及其數(shù)學(xué)模型表式模型 產(chǎn)銷平衡的運(yùn)輸問題: ai=bj 產(chǎn)大于銷的運(yùn)輸問題: aibj 產(chǎn)小于銷的運(yùn)輸問題: aibj8B1B2Bn產(chǎn)量A 1c11x11c12x12c1nx1na1A 2c21x21c22x22c2nx2na2Amcm1xm1cm2xm2cmnxm nam銷量b1b2bn ai bj運(yùn)輸問題及其數(shù)學(xué)模型1、運(yùn)輸問題的網(wǎng)絡(luò)圖、線性規(guī)劃模型及運(yùn)輸表設(shè)有同一種貨物從m個(gè)供應(yīng)地1，2，m運(yùn)往n個(gè)需求地1，2，n。第i個(gè)供應(yīng)地的

4、供應(yīng)量（Supply） 0) ，第j個(gè)需求地的需求量（Demand）為 si (si 0)。每單位貨物從供應(yīng)地i運(yùn)到需求地j的為 d j (d j運(yùn)價(jià)為 cij 。求一個(gè)使總運(yùn)費(fèi)最小的運(yùn)輸方案。如果從任一供應(yīng)地到任一需求地都有道路通行，這樣的運(yùn)輸問題稱為完全的運(yùn)輸問題；如果總供應(yīng)量等于總需求量，這樣的運(yùn)輸問題稱為供求平衡的運(yùn)輸問題。我們先考慮完全的、供求平衡的運(yùn)輸問題。運(yùn)輸問題及其數(shù)學(xué)模型d1c11 c1 j c1n ci1cij右圖是運(yùn)輸問題的網(wǎng)絡(luò)表示形式。1s11sid jijcincm1cmjcmnsmmdnn運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題也可以用線性規(guī)劃表示。設(shè) xij為從供應(yīng)地i運(yùn)往需

5、求地j的運(yùn)量，則總運(yùn)費(fèi)最小的線性規(guī)劃問題如下式所示。min z = c11x11 + c12 x12 + + c1n x1n+ c21x21 + c22 x22+ + c2n x2n + + cm1xm1 + cm2 xm2 + + cmn xmn= s1= s2x11 + x12+ + x1nx21 +x22 + +x2nstxn1 + xn2+ xn1+ xn2+ + xmn= sm= d1= d2+ x21x11+ x22x12+ x2n+ xmn= dnx1n 0,1 i m,1 j nxij運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題線性規(guī)劃變量個(gè)數(shù)為nm個(gè)，每個(gè)變量與運(yùn)輸網(wǎng)絡(luò)的一條邊對(duì)應(yīng)，所有的變

6、量都是非負(fù)的。約束個(gè)數(shù)為m+n個(gè)，全部為等式約束。前m個(gè)約束是供應(yīng)地的供應(yīng)量約束，后n個(gè)約束是需求地的需求量約束。運(yùn)輸問題約束的特點(diǎn)是約束左邊所有的系數(shù)都是0或1，而且每一列中恰有兩個(gè)系數(shù)是1，其他都是0。運(yùn)輸問題及其數(shù)學(xué)模型在運(yùn)輸問題線性規(guī)劃模型中，令X = (x11, x12 , x1n , x21, x22 , x2n ,., xm1, xm2 ,xmn )C = (c11, c12 , c1n , c21, c22 , c2n , cm1 , cm 2 ,cmn ) 111L111Lm行LLLL1 11LA= 111O111On列OOOO1 11On列n列n列n列b = (s1 , s

7、2 , , sm , d1 , d2 , , dn )則運(yùn)輸問題的線性規(guī)劃可以寫成：運(yùn)輸問題及其數(shù)學(xué)模型完全的運(yùn)輸問題系數(shù)矩陣A中，列向量 pij中只有兩個(gè)元素是1，其他元素都是0。第一個(gè)1位于矩陣的第i行，第二個(gè)1位于矩陣的第m+j行。這個(gè)列向量可以表示為兩個(gè)單位向量之和，即 0 0 0 1 1 0 第i行LLL= = + = ei+ em+ jpijLLL第m + j行 1 0 1 0 0 0 運(yùn)輸問題及其數(shù)學(xué)模型12n運(yùn)輸問題除了用網(wǎng)絡(luò)表示及線性規(guī)劃表示外， 還可以用運(yùn)輸表表示， 見右表。運(yùn)輸表是一個(gè)m行n列的表格，每一行對(duì)應(yīng)于一個(gè)供應(yīng)地，每1s12s2一列對(duì)應(yīng)于一個(gè)需求地。運(yùn)輸表共有m

8、n個(gè)格子，每個(gè)格子對(duì)應(yīng)于從一個(gè)供應(yīng)地出發(fā)到一個(gè)需求地的運(yùn)輸路線。msmdndd12c11c12c1nx11x12x1nc21c22c2 nx21x22x2ncm1cm 2cmnxm1xm 2xmn運(yùn)輸問題及其數(shù)學(xué)模型上頁表中，每一格的左上角小方格內(nèi)的數(shù)字表明從相應(yīng)的供應(yīng)地i到需求地j的運(yùn)價(jià)cij，每一格右下角表明從相應(yīng)的供應(yīng)地i到需求地j的運(yùn)量 xij。表右方表明各供應(yīng)地的供應(yīng)量si，表下方表明各需求地的需求量d j。每一行運(yùn)量之和表示從該供應(yīng)地運(yùn)往各需求地的運(yùn)量之和，它應(yīng)該等于該供應(yīng)地的供應(yīng)量；同樣，每一列運(yùn)量之和表示從各供應(yīng)地運(yùn)往該需求地的運(yùn)量之和，它應(yīng)該等于該需求地的需求量。運(yùn)輸問題及其

9、數(shù)學(xué)模型 運(yùn)輸問題約束矩陣的性質(zhì)分別將A的前m行和后n行相加，得到兩個(gè)相同的mn維向量，其中的元素都是1。即A矩陣的m+n個(gè)行向量是線性相關(guān)的， 因此A矩陣的秩m+n。運(yùn)輸問題分別從供應(yīng)地1、2、m到需求地n的m條邊以及從供應(yīng)地1分別到需求地1、2、n-1的n-1條邊，一共有m+n-1條邊。這m+n-1條邊組成運(yùn)輸問題約束矩陣A中的m+n-1個(gè)列向量，這些列向量在A矩陣中的子矩陣是一個(gè)m+n行， m+n-1列的矩陣 11L1111Lm行LLLL1 11LA= 111O111On行OOOO1 11On列n列n列n列(1,n )1( 2,n) L ( m,n)(1,1) L (1,n-1)11L1

10、m行O刪除矩陣B的最后一行，得到1B=1On行可以看出，這是一個(gè)上三角矩陣，顯然，秩Bm+n-1。由m+n-1=秩B秩A0。由于單純形疊代在每一步都滿足互補(bǔ)松弛條件，因此對(duì)于基變量xij0，相應(yīng)的對(duì)偶約束條件ui+vj cij的松弛變量一定等于0，即ui+vj = cij由于基變量一共有m+n-1個(gè)，因此對(duì)偶問題一共有m+n-1個(gè)等式約束，只要先確定一個(gè)對(duì)偶變量的值，就可以由m+n-1個(gè)等式約束確定其余m+n-1個(gè) 對(duì)偶變量的值。不妨設(shè)vn=0，逐個(gè)遞推求得ui和vj。求出ui、vj的值以后，就可以進(jìn)一步計(jì)算各非基變量的檢驗(yàn)數(shù)zij- cij =ui+vj- cij 。表上作業(yè)法求解運(yùn)輸問題3

11、. 解的改進(jìn)（1） 確定進(jìn)基變量由單純形法原理可以知道，凡檢驗(yàn)數(shù)zij-cij0的非基變量都可以進(jìn)基。通?？偸沁x取檢驗(yàn)數(shù)中最小的對(duì)應(yīng)變量進(jìn)基。（2） 確定離基變量為保證改進(jìn)后的解仍為基本可行解，需要保證所有變量的非負(fù)性。因此，改進(jìn)的方法就是從檢驗(yàn)數(shù)為負(fù)數(shù)的空格出發(fā)，作一條除該空格外其余頂點(diǎn)均為有數(shù)字格組成的閉合回路。在這條閉回路上，按對(duì)運(yùn)量作最大可能的調(diào)整。表上作業(yè)法求解運(yùn)輸問題例 改進(jìn)表中用最小元素法得到的初始基本可行解。由表可知，x34的檢驗(yàn)數(shù)是-2，因此可以作為進(jìn)基變量。選取 變量x34作為進(jìn)基變量，以其所在的空格為出發(fā)點(diǎn)作閉合回路。123430124550342515203184選取變

12、量x34作為進(jìn)基變量相應(yīng)的閉合回路10119151511413121694511819710311413121325表上作業(yè)法求解運(yùn)輸問題將其改進(jìn)為新的基本可行解。 則x34增加的同時(shí)，x14減少， x12增加，x32增加。為保證變量的非負(fù)性，能夠減少的最大數(shù)量為14。此時(shí)，x14減少到0，是出基變量。得到新的基本可行解見下表123410119153012-115152131216945751045118710503453114414131213254222515203184改進(jìn)后的基本可行解表上作業(yè)法求解運(yùn)輸問題上表給出的調(diào)運(yùn)方案是否為最優(yōu)呢？還需要對(duì)這個(gè)方案的空格處（非基變量）求出檢驗(yàn)數(shù)。

13、由于表中x13的檢驗(yàn)數(shù)為-1，因此對(duì)上表進(jìn)行改進(jìn)。得到下表。計(jì)算表中的檢驗(yàn)數(shù)。12341101191530311515131216945265104531187105032016141413121325432225152031最優(yōu)基本可行解84由于檢驗(yàn)數(shù)表2-38中的所有檢驗(yàn)數(shù)大于等于0。因此上表是最優(yōu)方案。表上作業(yè)法求解運(yùn)輸問題最優(yōu)解的目標(biāo)函數(shù)值為z=1015+915+945+820+716+1014+132 5=1427。需要指出的是，有時(shí)在閉合回路調(diào)整中，在需要減小運(yùn)量的地方有兩個(gè)以上相等的最小數(shù)，這樣調(diào)整時(shí)原先空格處填上了這個(gè)最小數(shù)，而有兩個(gè)以上最小數(shù)的地方成了空格。為了保證基變量的個(gè)

14、數(shù)是m+n-1個(gè)，就要把最小數(shù)的空格之一變?yōu)榭崭?，其余均補(bǔ)填0，補(bǔ)填0的格為有數(shù)字格， 對(duì)應(yīng)的變量是基變量。產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用mn1供給大于需求的情況，即 si dii=1i=1mni in+1增加一個(gè)虛設(shè)的需求地，它的需求量為s -d。i=1i=1新增從各供應(yīng)地到該需求地的運(yùn)輸路線（1，n+1），（2，n+1），（m，n+1），這些運(yùn)輸路線上的運(yùn)價(jià)全部等于0，即c1，n+1=c2，n+1=cm，n+1=0， 這樣就將供給大于需求的的問題轉(zhuǎn)化為供求平衡的問題。在新的問題中，從供應(yīng)地i到新設(shè)的需求地n+1的運(yùn)量，實(shí)際上就是存儲(chǔ)在供應(yīng)地i沒有運(yùn)出的數(shù)量。新得到的供求平衡的運(yùn)輸問題的最優(yōu)解，

15、實(shí)際上就是各供應(yīng)地存儲(chǔ)多少、運(yùn)出多少、運(yùn)往何地，使總運(yùn)價(jià)最低。產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用例 設(shè)一個(gè)供求不平衡的運(yùn)輸問題如下左圖。相應(yīng)的供求平衡問題如圖1，2。圖1 供求不平衡的運(yùn)輸問題圖2 供求不平衡的運(yùn)輸問題產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用由于需求地4是虛擬的，因此對(duì)應(yīng)的運(yùn)價(jià)設(shè)為0。供求平衡問題的運(yùn)輸表以及最優(yōu)解如下：123411522510101010調(diào)整后的運(yùn)輸表及最優(yōu)解及檢驗(yàn)數(shù)表85604105371090102510產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用已獲得最優(yōu)解。這個(gè)最優(yōu)解的含義是：從供應(yīng)地1到需求地2的運(yùn)量為10，到需求地3 的運(yùn)量為5，供應(yīng)量沒有剩余；從供應(yīng)地2 到需求地1的運(yùn)量為10，到需求

16、地3的運(yùn)量為5，供應(yīng)量剩余10；最小運(yùn)費(fèi)為 min z=510+65+710+95=195.mn2供給小于需求的情況，即 si dii=1i =1當(dāng)市場(chǎng)的總需求量大于總供給量時(shí)，可以仿照供給大于需求的情況處理。即增加一個(gè)假想的mn供應(yīng)地，產(chǎn)量等于供應(yīng)不足的部分，即 di- si 。i=1i=1由于假想的供應(yīng)地并不存在，相應(yīng)運(yùn)價(jià)就等于0。不限最高最低507060運(yùn)輸模型的應(yīng)用短缺資源的分配問題自來水分配問題引水管理費(fèi)水庫區(qū)甲乙丙丁供水量16013022017050A14013019015060B19020023050C3070010160110301602 005 021059基 本 需求額 外

17、 需求運(yùn)輸模型的應(yīng)用自來水分配問題的規(guī)范表式運(yùn)輸模型60引水區(qū)管理費(fèi)水庫甲乙丙丁供水量甲1甲2丁1丁2A160 16013022017017050B140 14013019015015060C190 190200230MM50D (虛)M0M0M050需 求 量302070301050210運(yùn)輸模型的應(yīng)用 自來水分配問題的最優(yōu)方案表61分配量區(qū)水庫甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050脫銷302050需求量302070301050210運(yùn)輸模型的應(yīng)用轉(zhuǎn)運(yùn)問題面粉轉(zhuǎn)運(yùn)問題設(shè)有A1、A2、A3三個(gè)面粉加工廠，每天分別將3、4、3噸面粉運(yùn)往B1、B2兩個(gè)糕點(diǎn)廠，而B1

18、、B2每 天分別需要4、6噸面粉。在面粉廠與糕點(diǎn)廠之間有T1、 T2兩個(gè)中繼站。各地間每噸面粉的運(yùn)價(jià)如下表所示。應(yīng)如何調(diào)運(yùn)使總運(yùn)費(fèi)最低？62運(yùn)輸模型的應(yīng)用63終點(diǎn)始點(diǎn)面 粉 廠中繼站糕點(diǎn)廠A1A2A3T1T2B1B2面粉廠A1 A2 A3324223523268137114中繼站T1T23523267252糕點(diǎn)廠B1 B2642399運(yùn)輸模型的應(yīng)用轉(zhuǎn)運(yùn)站既是始點(diǎn)，又是終點(diǎn)的運(yùn)地。轉(zhuǎn)化成為有7個(gè)假想產(chǎn)地Ai 、7個(gè)假想銷地Bj的新問題。虛設(shè)一個(gè)統(tǒng)一轉(zhuǎn)運(yùn)量t，應(yīng)有t max ( ai ， bj)12本例故可取作 ai = bj = 10t = 10假想產(chǎn)地Ai的產(chǎn)量ai+t， Ai 是轉(zhuǎn)運(yùn)站a =ai ，64否則i運(yùn)輸模型的應(yīng)用假想銷地Bj 的銷量bj+t， Bj 是轉(zhuǎn)運(yùn)站b =bj ，否則j本例取作ai = ai + 10bj = bj+ 10虛設(shè) xi