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

2、 m+n1個基變量。,12,.重復(fù)、步，直到找到最優(yōu)解為止。,步驟：,.用最小元素等方法求出初始基可行解（初始調(diào)運方案，m+n-1個數(shù)字格）。,.求出各非基變量的檢驗數(shù)，判別是否達(dá)到最優(yōu)解。如果是則停止計算，否則轉(zhuǎn)入下一步。用位勢法等方法計算。,.用閉回路調(diào)整法改進(jìn)當(dāng)前的基本可行解（確定換入、換出變量）。,二、表上作業(yè)法,13,例一、某運輸資料如下表所示：,1、求初始方案：,14,.西北角法（或左上角法） 此法是純粹的人為的規(guī)定，沒有理論依據(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,總的運費(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īng)（調(diào)運），然后次小，直到最后供完為止。,總的運輸費用（31）（64） （43）（12）（310）（35）86元,16,(3).伏格爾法： 基本思想是一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小運費，這就有個差額。差額越大，說明不

4、能按最小運費調(diào)運時，運費增加越多。因此對差額最大處，就應(yīng)該采用最小運費調(diào)運。,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 （因為目標(biāo)函數(shù)要求最小化） 表格中有調(diào)運量的地方為基變量，空格處為非基變量?；兞康臋z驗數(shù)ij0。,2、最優(yōu)解的判別（檢驗數(shù)的求法） .閉回路法：,20,從每一空格出發(fā)一定存在和可以找到唯一的閉回路。因(m+n-1)個數(shù)字格(基變量)對應(yīng)的系數(shù)向量是一個基。任一空格(非基變量)對應(yīng)的系數(shù)向量是這個基的線性組合。,21,（1）,（1）,計算如下：空格處（ A1

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

6、ui+vj) 0 據(jù)此可以求出ui , vj,.位勢法,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) 計算檢驗數(shù)，并以ij0 檢驗。,cij,(ui+vj),表中還有負(fù)數(shù)，說明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)整基可行解。,ij,31,閉回路調(diào)整法（原理和單純形法一樣）,接上例：,3,1,3,4,6,3,（）,（）,（）,（）,3、改進(jìn)的方法,32,33,經(jīng)檢驗,所有ij0 得到最優(yōu)解

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