運(yùn)輸問(wèn)題的變體

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

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

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

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

：具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行Am+1，運(yùn)價(jià)為零。產(chǎn)量為am+1即可。02九月2023B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因?yàn)橛校嚎匆粋€(gè)例題：求下列表中極小化運(yùn)輸問(wèn)題的最優(yōu)解。02九月2023

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

（1）總產(chǎn)量為180，B1，…，B4的最低需求量20+50+35+45=150，這時(shí)屬產(chǎn)大于銷；（2）B1，…，B4的最高需求是60+70+35+45=210，這時(shí)屬銷大于產(chǎn)；（3）虛設(shè)一個(gè)產(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)某需求地的運(yùn)價(jià)用大M表示，A5到、的運(yùn)價(jià)為零。得到下表的產(chǎn)銷平衡表。02九月2023B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到這樣的平衡表后，即可應(yīng)用QSB軟件計(jì)算得到最優(yōu)方案。02九月2023

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545

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

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

j1234110.810.9511.111.252

11.111.2511.43

11.011.154

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

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

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

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

252

5

30353

2010

304

10

10銷量1015252030

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