運(yùn)籌學(xué)——4.運(yùn)輸問(wèn)題.ppt

1、1,上機(jī)實(shí)驗(yàn)時(shí)間：第8、11、13周周五5、6節(jié) 地點(diǎn)：7A204，205,2,運(yùn) 籌 學(xué),運(yùn) 輸 問(wèn)題,運(yùn)輸問(wèn)題的數(shù)學(xué)模型 表上作業(yè)法 產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題,3,例：某運(yùn)輸問(wèn)題的資料如下：,一、運(yùn)輸問(wèn)題的數(shù)學(xué)模型,4,5,6,數(shù)學(xué)模型的一般形式：,7,該系數(shù)矩陣中對(duì)應(yīng)于變量xij的系數(shù)向量Pij，其分量中除第i個(gè)和第m+j個(gè)為1以外，其余的都為零。即 Pij=(0, ,1,0,0,1,0,0)T=ei+em+j,8,當(dāng)產(chǎn)銷(xiāo)平衡時(shí)，其模型如下：,9,當(dāng)產(chǎn)大于銷(xiāo)時(shí)，其模型是：,10,當(dāng)產(chǎn)小于銷(xiāo)時(shí)，其模型是：,11,特征： 1、平衡運(yùn)輸問(wèn)題必有可行解，也必有最優(yōu)解； 2、運(yùn)輸問(wèn)題的基可行解中應(yīng)包括

2、 m+n1個(gè)基變量。,12,.重復(fù)、步，直到找到最優(yōu)解為止。,步驟：,.用最小元素等方法求出初始基可行解（初始調(diào)運(yùn)方案，m+n-1個(gè)數(shù)字格）。,.求出各非基變量的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果是則停止計(jì)算，否則轉(zhuǎn)入下一步。用位勢(shì)法等方法計(jì)算。,.用閉回路調(diào)整法改進(jìn)當(dāng)前的基本可行解（確定換入、換出變量）。,二、表上作業(yè)法,13,例一、某運(yùn)輸資料如下表所示：,1、求初始方案：,14,.西北角法（或左上角法） 此法是純粹的人為的規(guī)定，沒(méi)有理論依據(jù)和實(shí)際背景，但它易操作，特別適合在計(jì)算機(jī)上編程計(jì)算，因而受歡迎。方法如下：,3 6 5 6,7 4 9,3,4 4 9,0 6 5 6,4,0 4 9,0

3、 2 5 6,2,0 2 9,0 0 5 6,2,0 0 9,0 0 3 6,3 6,0 0 0 0,0 0 0,3 4 0 0 0 2 2 0 0 0 3 6,總的運(yùn)費(fèi)(33)(411)(29)(22)(310)(65)135元,15,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,.最小元素法： 基本思想是從運(yùn)價(jià)最小的地方開(kāi)始供應(yīng)（調(diào)運(yùn)），然后次小，直到最后供完為止。,總的運(yùn)輸費(fèi)用（31）（64） （43）（12）（310）（35）86元,16,(3).伏格爾法： 基本思想是一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有個(gè)差額。差額越大，說(shuō)明不

4、能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多。因此對(duì)差額最大處，就應(yīng)該采用最小運(yùn)費(fèi)調(diào)運(yùn)。,6,列差額 2 5 1 3,行 差額 0 1 1,17,6,列差額 2 1 3,行 差額 0 1 2,3,18,3,1,3,5,6,2,19,判別準(zhǔn)則：ij0 （因?yàn)槟繕?biāo)函數(shù)要求最小化） 表格中有調(diào)運(yùn)量的地方為基變量，空格處為非基變量?；兞康臋z驗(yàn)數(shù)ij0。,2、最優(yōu)解的判別（檢驗(yàn)數(shù)的求法） .閉回路法：,20,從每一空格出發(fā)一定存在和可以找到唯一的閉回路。因(m+n-1)個(gè)數(shù)字格(基變量)對(duì)應(yīng)的系數(shù)向量是一個(gè)基。任一空格(非基變量)對(duì)應(yīng)的系數(shù)向量是這個(gè)基的線性組合。,21,（1）,（1）,計(jì)算如下：空格處（ A1

5、B1 ） (13) (1)3 (12) (1)1 1 此數(shù)即為該空格處的檢驗(yàn)數(shù)。,1,（1）,（1）,22,2,1,23,-1,2,1,24,1,1,-1,2,1,25,12,1,-1,2,1,26,-1,10,檢驗(yàn)數(shù)中有負(fù)數(shù)，說(shuō)明原方案不是最優(yōu)解。,12,1,2,1,27,0,0,0,0,0,1,2,1,-1,12,10,0,28,運(yùn)輸問(wèn)題的約束條件共有m+n個(gè)，其中：m個(gè)產(chǎn)地產(chǎn)量的約束，n個(gè)銷(xiāo)地銷(xiāo)量的約束。 其對(duì)偶問(wèn)題也應(yīng)有m+n個(gè)變量，據(jù)此： ij=cij(ui+vj)，其中前m個(gè)變量為ui（i=1,2,m），后n個(gè)為vj （j=1,2, n） 由單純形法可知，基變量的ij 0 cij(

6、ui+vj) 0 據(jù)此可以求出ui , vj,.位勢(shì)法,29,接上例：,成本表,u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令： u10,u10 v12 u2 1 v2 9 u3 5 v3 3 v4 10,(ui+vj),30,按ij=cij(ui+vj) 計(jì)算檢驗(yàn)數(shù)，并以ij0 檢驗(yàn)。,cij,(ui+vj),表中還有負(fù)數(shù)，說(shuō)明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)整基可行解。,ij,31,閉回路調(diào)整法（原理和單純形法一樣）,接上例：,3,1,3,4,6,3,（）,（）,（）,（）,3、改進(jìn)的方法,32,33,經(jīng)檢驗(yàn),所有ij0 得到最優(yōu)解

7、， 最小運(yùn)費(fèi)為85元。,0,34,無(wú)窮多最優(yōu)解：產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題必定存最優(yōu)解。如果非基變量的ij0，則該問(wèn)題有無(wú)窮多最優(yōu)解。如上例：（1，1）中的檢驗(yàn)數(shù)是 0，經(jīng)過(guò)調(diào)整，可得到另一個(gè)最優(yōu)解。,4、表上作業(yè)法計(jì)算中的問(wèn)題,35,例1：無(wú)窮多最優(yōu)解,0,檢驗(yàn)數(shù),36,退化：（1）表格中一般要有(m+n-1)個(gè)數(shù)字格。但有時(shí)，在分配運(yùn)量時(shí)則需要同時(shí)劃去一行和一列，這時(shí)需要補(bǔ)一個(gè)0，以保證有(m+n-1)個(gè)數(shù)字格。一般可在劃去的行和列的任意空格處加一個(gè) 0 即可。,4、表上作業(yè)法計(jì)算中的問(wèn)題,37,3,6,例2：退化,38,退化 (2) 在用閉回路法調(diào)整時(shí)，在閉回路上出現(xiàn)兩個(gè)或兩個(gè)以上的具有(-)標(biāo)記的相等的最小值。這時(shí)只能選擇其中一個(gè)作為調(diào)入格，經(jīng)調(diào)整后得到退化解。這時(shí)與該方格運(yùn)量相等的其他數(shù)字格必須填入0，表明它是基變量。當(dāng)出現(xiàn)退化解后，并作改進(jìn)調(diào)整時(shí)，可能在某閉回路上有標(biāo)記為(-)的運(yùn)量為0的數(shù)字格，這時(shí)應(yīng)取調(diào)整量=0。,39,1、產(chǎn)大于銷(xiāo)的模型：,方法是先將原問(wèn)題變成平衡問(wèn)題，需假設(shè)一個(gè)銷(xiāo)地(Bn+1 ) (實(shí)際上為多余產(chǎn)量的存量),三、產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及其求解方法,40,模型為：,2、銷(xiāo)大于產(chǎn)：同樣假設(shè)一個(gè)產(chǎn)地即可，變化同上。,單位運(yùn)價(jià)表中的單位運(yùn)價(jià)為,41,40,30,30,20,30,20,20,最優(yōu)方案,例題：,42,已知某