運籌學之運輸問題-表格法網(wǎng)上找的PPT

1、運 輸 問題(Transportation Problem)例：某運輸問題的資料如下：單位 銷地 運價產(chǎn)地產(chǎn)量2910291342584257銷量3846一、運輸問題的數(shù)學模型 數(shù)學模型的一般形式 已知資料如下：單 銷 產(chǎn) 量產(chǎn)地產(chǎn)量銷 量當產(chǎn)銷平衡時，其模型如下：當產(chǎn)大于銷時，其模型是：當產(chǎn)小于銷時，其模型是： 特征： 1、平衡運輸問題必有可行解，也必有最優(yōu)解； 2、運輸問題的基可行解中應包括 m+n1 個基變量。這是平衡的運輸問題的數(shù)學模型，包含mn個變量， mn個約束方程。系數(shù)矩陣如下：m行n行 .重復. ，直到找到最優(yōu)解為止。步驟： .找出初始基本可行解（初始調(diào)運方案，一般m+n-1個

2、數(shù)字格），用西北角法、最小元素法、伏格爾法（Vogel） ； .求出各非基變量的檢驗數(shù)，判別是否達到最優(yōu)解。如果是停止計算，否則轉(zhuǎn)入下一步，用位勢法計算； .改進當前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整； 二、表上作業(yè)法例一、某運輸資料如下表所示：單位 銷地 運價 產(chǎn)地產(chǎn)量311310719284741059銷量36561、求初始方案： 此法是純粹的人為的規(guī)定，沒有理論依據(jù)和實際背景，但它易操作，特別適合在計算機上編程計算，因而受歡迎。西北角法（或左上角法）西北角法（或左上角法）1、先確定左上角變量的值，令它取盡可能的值。將這個值填入該變量對應位置，并在該數(shù)字上畫上圈。畫圈格子

3、的對應的變量是基變量。2、在畫圈格子所在的行或列應取0值的變量處填上號。當畫圈格子所在行和列的其余變量都應取0時，則或者只對行打，不能同時對行或列都打。打格子對應的變量是非基變量。3、對表中尚未畫圈和打的部分，重復1、2的手續(xù)。若遇左上角變量取0值，則在該位置填0，并且同樣畫上圈，對應變量仍是基變量。B1B2B3B4產(chǎn)量A17A2 4A39銷量3656311310192741058341633 .最小元素法： 基本思想是就近供應，即從運價最小的地方開始供應（調(diào)運），然后次小，直到最后供完為止。總的運輸費用（31）（64） （43）（12）（310）（35）86元最小元素法1、先確定運價最小的格

4、子所對應的變量值。若有幾個格子同時達到最小運價，則可任取一個。令該變量取盡可能大的值。將此值填入該變量對應位置并畫圈。畫圈的格子對應的變量是基變量。2、在畫圈格子所在的行或列應取0值的變量處填上號。當畫圈格子所在行和列的其余變量都應取0時，則或者只對行打，不能同時對行或列都打。打格子對應的變量是非基變量。3、對表中尚未畫圈和打的部分，重復1、2的手續(xù)。當表剩余部分僅是一行或一列時，確定其最小運價對應變量后，不管其余元素是否取零值，都不能打，應作剩余部分處理。閉回路性質(zhì)：回路中的頂點必是偶數(shù)，在運輸表中，回路遇到頂點必須轉(zhuǎn)90度與另一頂點連接。集合中的變量稱為閉回路的頂點，相鄰兩個變量的連線為閉

5、回路的邊。X43X41A4X33X32A3A2X12X11A1B3B2B1在運輸問題中，若變量組含有閉回路，則變量所對應的列向量線性相關。m+n-1個變量構(gòu)成基變量的充要條件是他不包含任何閉回路。B1B2產(chǎn)量A18510A22120銷量1515最小元素法：Z1=105另一方案：Z=8501101225132-1301-2-1201-2-1- (3)伏格爾法（Vogel）： 基本思想：同時考慮每一產(chǎn)地到每一銷地和每一銷地來自每一產(chǎn)地的最小運價和次小運價，若兩者差額大，說明若不能按最小運價供應，就有可能按次小運價供應，從而運費很高。因此，應先對最大差額所在的行或列，按最小元素確定供銷關系。一般講，

6、按此法所得可行解較最小元素法所得可行解更接近最優(yōu)解。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A178143A226535A314278銷量2176 ij0 （因為目標函數(shù)要求最小化） 表格中有調(diào)運量的地方為基變量，空格處為非基變 量?；兞康臋z驗數(shù)ij0，非基變量的檢驗數(shù)ij0。 ij 0 表示運費增加。2、最優(yōu)解的判別（檢驗數(shù)的求法）： .閉合回路法： B1B2B3B4產(chǎn)量A17A24A39銷量3656313463（1）（1）（1）（1） 計算如下：空格處（ A1 B1 ） (13) (1)3 (12) (1)1 1 此數(shù)即為該空格處的檢驗數(shù)。1檢驗數(shù)就是閉回路中所有增加1個運量處的單位運價之和減去所

7、有減少1個運量處的單位運價之和。（經(jīng)濟解釋）閉回路畫法：從某一空格出發(fā)，橫向或縱向畫直線，在適當?shù)臄?shù)字格轉(zhuǎn)向以回到出發(fā)的空格。從每一個空格出發(fā)一定存在和可以找到唯一的閉回路。因（m+n-1）個數(shù)字格（基變量）對應的系數(shù)向量是一個基。于是，任意一個空格（非基變量）對應系數(shù)向量是這個基的線性組合。B1B2B3B4產(chǎn)量A17A24A39銷量365631363124B1B2B3B4產(chǎn)量A17A24A39銷量36563136312-14B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-14B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-1124B1B2B3B4產(chǎn)量A

8、17A24A39銷量365631363121-112104 檢驗數(shù)中有負數(shù)，說明原方案不是最優(yōu)解。B1B2B3B4產(chǎn)量A17A24A39銷量365600000121-112100 運輸問題的約束條件共有m+n個，其中：m是產(chǎn)地產(chǎn)量的限制；n是銷地銷量的限制。 其對偶問題也應有m+n個變量，由對偶性可知CBB-1=（u1,u2,um;v1,v2,vn)，于是有CBB-1Pij= ui+vj。又因為， ij=cij-CBB-1Pij=cij(ui+vj) ,其中前m個計為ui（i=1.2m）,后n個計為vj （j=1.2n） 由單純形法可知，基變量的ij 0 cij(ui+vj) 0 因此ui ,

9、vj可以求出。位勢法接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4B1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令： u10u10 v12u2 1 v2 9u3 5 v3 3 v4 10 (ui+vj) 按ij=cij(ui+vj) 計算檢驗數(shù)，并以ij0 檢驗，或用(ui+vj) cij 0 檢驗。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+v

10、j)B1B2B3B4A11200A20101A3100120表中還有負數(shù)，說明還未得到最優(yōu)解，應繼續(xù)調(diào)整。ij位勢法步驟：1、確定初始基可行解后，在對應初始方案的數(shù)字格處填入單位運價。2、在表中增加一行一列，在列中填入ui（i=1,2，m），在行中填入vj（j=1,2,n)先令u1=0，接著，通過ui+vj=cij，i，jB來確定ui，vj。3、由 ，計算所有空格的檢驗數(shù)。 閉合回路調(diào)整法（原理同單純形法一樣）接上例：B1B2B3B4產(chǎn)量A17A24A39銷量36563134633、改進的方法B1B2B3B4產(chǎn)量A1527A2314A3639銷量36566563銷量9A34A27A1產(chǎn)量B4B

11、3B2B1313463B1B2B3B4A10200A20210A390120經(jīng)檢驗所有ij0得到最優(yōu)解，最小運費為85元。0v4v3v2v1u354A3u281A2u1103A1B4B3B2B11039355242A328171A2010393A1B4B3B2B1(ui+vj)閉回路調(diào)整法步驟：1、取非基變量中檢驗數(shù)最小的非基變量為入基變量。2、從這個非基變量出發(fā)，尋求一條以基變量為頂點的閉回路（存在且唯一），并將這條閉回路按順時針或逆時針依次編號（該非基變量為第一號）。3、將閉回路中偶序頂點的基變量值最小者取作調(diào)整量 ，并將該基變量選取為離基變量。4、將該閉回路上奇序頂點的值加 ，偶序頂點的

12、值減 ，閉回路外的值一律不變。 .無窮多最優(yōu)解：產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的ij0，則該問題有無窮多最優(yōu)解。 .退化：表格中一般要有(m+n-1)個數(shù)字格。但有時，在分配運量時則需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格。一般可在劃去的行和列的任意空格處加一個 0 即可。4、表上作業(yè)法計算中的問題 1、產(chǎn)大于銷：模型 方法是先將原問題變成平衡問題，需假設一個銷地(Bn+1 )(實際上考慮產(chǎn)地的存量)，三、產(chǎn)銷不平衡的運輸問題及其求解方法 模型為： 2、銷大于產(chǎn)：同樣假設一個產(chǎn)地即可，變化同上。單位運價表中的單位運價為B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5 A121134070A210359050A378120702030406040B1B2B3B4B5 A170A250A370203040604040303020302020用最小元素法求初始方案例題：例如下表所示三個化肥廠供應四個地區(qū)的化肥，求運費最省的調(diào)撥方案。 已知某運輸問題的資料如下表所示B1B2B3B4發(fā)量A12653