北郵運籌學(xué)ch3-4 運輸問題的變體.ppt

1、北京郵電大學(xué) 運籌學(xué),2020/12/9,設(shè)數(shù)學(xué)模型為,求極大值問題,北京郵電大學(xué) 運籌學(xué),2020/12/9,第一種方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運價表為C=（Cij）mn，用一個較大的數(shù)M（MmaxCij）去減每一個Cij得到矩陣C/=（Cij）mn ，其中C/ij=MCij0,將C/作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解，目標(biāo)函數(shù)值為,例如，下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤,運輸部門如何安排運輸方案使總利潤最大.,8 14 9,北京郵電大學(xué) 運籌學(xué),2020/12/9,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非負(fù)

2、,得到最優(yōu)運輸方案X,最大利潤Z=89+1010+68+54=240,第二種方法:所有非基變量的檢驗數(shù)ij0時最優(yōu).求初始運輸方案可采用最大元素法.,如上例,用最大元素得到 的初始運輸方案:,8 14 9,求檢驗數(shù):11=8,12=4,21=2,23=2,全部非正,得到最優(yōu)解運輸方案,結(jié)果與第一種方法相同.,北京郵電大學(xué) 運籌學(xué),2020/12/9,不平衡運輸問題 : 當(dāng)總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。,當(dāng)產(chǎn)大于銷時,即,數(shù)學(xué)模型為,北京郵電大學(xué) 運籌學(xué),2020/12/9,由于總產(chǎn)量大于總銷量，

3、必有部分產(chǎn)地的產(chǎn)量不能全部 運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，庫存量 為xi，n+1（i=1，2，m），總的庫存量為,北京郵電大學(xué) 運籌學(xué),2020/12/9,bn+1作為一個虛設(shè)的銷地Bn+1的銷量。各產(chǎn)地Ai到Bn+1的運價為零，即Ci，n+1=0,（i=1，m）。則平衡問題的數(shù)學(xué)模型為：,具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可,北京郵電大學(xué) 運籌學(xué),2020/12/9,當(dāng)銷大于產(chǎn)時,即,數(shù)學(xué)模型為,北京郵電大學(xué) 運籌學(xué),2020/12/9,由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為,xm+1,j 是Am+

4、1運到Bj的運量，也是Bj不能滿足需要的數(shù)量。Am+1到Bj的運價為零,即Cm+1,j=0(j=1,2, ,n),北京郵電大學(xué) 運籌學(xué),2020/12/9,銷大于產(chǎn)平衡問題的數(shù)學(xué)模型為 ：,具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。,北京郵電大學(xué) 運籌學(xué),2020/12/9,因為有：,看一個例題：求下列表中極小化運輸問題的最優(yōu)解。,北京郵電大學(xué) 運籌學(xué),2020/12/9,所以是一個產(chǎn)大于銷的運輸問題。表中A2不可達(dá)B1，用一個很大的正數(shù)M表示運價C21。虛設(shè)一個銷量為b5=180160=20，Ci5=0，i=1，2，3，4。表的右邊增添一列,這樣我們可得新的運

5、價表：,北京郵電大學(xué) 運籌學(xué),2020/12/9,下表為計算結(jié)果。可看出：產(chǎn)地A4還有20個單位沒有運出。,需求量不確定的運輸問題,上例中，假定B1的需要量是20到60之間，B2的需要量是50到70，試求極小化問題的最優(yōu)解。,北京郵電大學(xué) 運籌學(xué),2020/12/9,先作如下分析：（1）總產(chǎn)量為180，B1，B4的最低需求量20+50+35+45=150，這時屬產(chǎn)大于銷；,（2）B1，B4的最高需求是60+70+35+45=210，這時屬銷大于產(chǎn)；,（3）虛設(shè)一個產(chǎn)地A5，產(chǎn)量是210180=30，A5的產(chǎn)量只能供應(yīng)B1或B2。,（4）將B1與B2各分成兩部分， 的需求量是20， 的需求量是4

6、0， 的需求量分別是50與20，因此 必須由A1，A4供應(yīng)， 可由 A1、A5供應(yīng)。,（5）上述A5不能供應(yīng)某需求地的運價用大M表示，A5到 、 的運價為零。得到下表的產(chǎn)銷平衡表。,得到這樣的平衡表后，即可應(yīng)用QSB軟件計算得到最優(yōu)方案。,北京郵電大學(xué) 運籌學(xué),2020/12/9,表324中x131=0是基變量,說明這組解是退化基本可行解,空格處的變量是非基變量。B1，B2，B3，B4實際收到產(chǎn)品數(shù)量分別是50，50，35和45個單位。,北京郵電大學(xué) 運籌學(xué),2020/12/9,【例12】（教材P93例3）,每臺每季度的存儲費為0.15萬元。求全年總費用最小的生產(chǎn)決策。,應(yīng)用,北京郵電大學(xué) 運

7、籌學(xué),2020/12/9,【解】設(shè)xij為第i季度生產(chǎn)的柴油機用于第j季度交貨的數(shù)量（臺），費用表為：,北京郵電大學(xué) 運籌學(xué),2020/12/9,數(shù)學(xué)模型為：,北京郵電大學(xué) 運籌學(xué),2020/12/9,這是一個產(chǎn)大于銷的運輸問題，加一個虛擬銷地D，得到平衡運價表：,北京郵電大學(xué) 運籌學(xué),2020/12/9,最優(yōu)解如下表（最優(yōu)方案不唯一），總費用為773萬元。,北京郵電大學(xué) 運籌學(xué),2020/12/9,用表上作業(yè)法求運輸問題的最優(yōu)解要比用單純法求解簡單，另外有些問題可以用圖上作業(yè)法。,運輸問題總有基本可行解而且有最優(yōu)解，當(dāng)某個非基變量的檢驗數(shù)等于零時，有無窮多個最優(yōu)解。運輸問題的應(yīng)用比較廣泛。,北京郵電大學(xué) 運籌學(xué),2020/12/9,本章介紹了運輸模型的特征；,運輸模型的