運輸問題的變體

02九月2023設(shè)數(shù)學(xué)模型為求極大值問題02九月2023第一種方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運價表為C=（Cij）m×n，用一個較大的數(shù)M（M≥max{Cij}）去減每一個Cij得到矩陣C/=（C′ij）m×n

，其中C/ij=M－Cij≥0,將C/作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解，目標(biāo)函數(shù)值為例如，下列矩陣C是Ai（I=1，2，3）到Bj的噸公里利潤,運輸部門如何安排運輸方案使總利潤最大.814902九月2023用最小元素法求初始方案得λ11=8,λ12=4,λ21=2,λ23=2全部非負,得到最優(yōu)運輸方案X,最大利潤Z=8×9+10×10+6×8+5×4=240第二種方法:所有非基變量的檢驗數(shù)λij≤0時最優(yōu).求初始運輸方案可采用最大元素法.如上例,用最大元素得到的初始運輸方案:8149求檢驗數(shù):λ11=－8,λ12=－4,λ21=－2,λ23=－2,全部非正,得到最優(yōu)解運輸方案,結(jié)果與第一種方法相同.02九月2023不平衡運輸問題

:當(dāng)總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。當(dāng)產(chǎn)大于銷時,即數(shù)學(xué)模型為02九月2023由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，庫存量為xi，n+1（i=1，2，…，m），總的庫存量為02九月2023bn+1作為一個虛設(shè)的銷地Bn+1的銷量。各產(chǎn)地Ai到Bn+1的運價為零，即Ci，n+1=0,（i=1，…，m）。則平衡問題的數(shù)學(xué)模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可02九月2023當(dāng)銷大于產(chǎn)時,即數(shù)學(xué)模型為02九月2023由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為xm+1,j

是Am+1運到Bj的運量，也是Bj不能滿足需要的數(shù)量。Am+1到Bj的運價為零,即Cm+1,j=0(j=1,2,…,n)02九月2023銷大于產(chǎn)平衡問題的數(shù)學(xué)模型為

：具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。02九月2023B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：看一個例題：求下列表中極小化運輸問題的最優(yōu)解。02九月2023

所以是一個產(chǎn)大于銷的運輸問題。表中A2不可達B1，用一個很大的正數(shù)M表示運價C21。虛設(shè)一個銷量為b5=180－160=20，Ci5=0，i=1，2，3，4。表的右邊增添一列這樣我們可得新的運價表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj206035452018002九月2023B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表為計算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個單位沒有運出。需求量不確定的運輸問題上例中，假定B1的需要量是20到60之間，B2的需要量是50到70，試求極小化問題的最優(yōu)解。02九月2023先作如下分析：

（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)量是210－180=30，A5的產(chǎn)量只能供應(yīng)B1或B2。（4）將B1與B2各分成兩部分，的需求量是20，的需求量是40，的需求量分別是50與20，因此必須由A1，…，A4供應(yīng)，可由A1、…、A5供應(yīng)。（5）上述A5不能供應(yīng)某需求地的運價用大M表示，A5到、的運價為零。得到下表的產(chǎn)銷平衡表。02九月2023B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到這樣的平衡表后，即可應(yīng)用QSB軟件計算得到最優(yōu)方案。02九月2023

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545

表3－24中x131=0是基變量,說明這組解是退化基本可行解,空格處的變量是非基變量。B1，B2，B3，B4實際收到產(chǎn)品數(shù)量分別是50，50，35和45個單位。02九月2023【例12】（教材P93例3）季度需求量（臺）生產(chǎn)能力（臺）單位成本（萬元）1102510．82153511．13253011．04201011．3

每臺每季度的存儲費為0.15萬元。求全年總費用最小的生產(chǎn)決策。應(yīng)用02九月2023【解】設(shè)xij為第i季度生產(chǎn)的柴油機用于第j季度交貨的數(shù)量（臺），費用表為：i

j1234110.810.9511.111.252

11.111.2511.43

11.011.154

11.302九月2023數(shù)學(xué)模型為：02九月2023這是一個產(chǎn)大于銷的運輸問題，加一個虛擬銷地D，得到平衡運價表：

銷地產(chǎn)地1234D產(chǎn)量110.810.9511.111.250252M11.111.2511.400353MM1111.150304MMM11.3010銷量1015252030

02九月2023最優(yōu)解如下表（最優(yōu)方案不唯一），總費用為773萬元。

銷地產(chǎn)地1234D產(chǎn)量110150

252

5

30353

2010

304

10

10銷量1015252030

02九月2023用表上作業(yè)法求運輸問題的最優(yōu)解要比用單純法求解簡單，另外有些問題可以用圖上作業(yè)法。運輸問題總有基本可行解而且有最優(yōu)解，當(dāng)某個非基變量的檢驗數(shù)等于