1、求解方法：轉(zhuǎn)化為產(chǎn)銷平衡問題，加松弛變量，使之成為miaxxiinnjij, 2 , 111第三節(jié)第三節(jié) 產(chǎn)銷不平衡的運輸問題及其解法產(chǎn)銷不平衡的運輸問題及其解法然后，虛擬一個銷地Bn+1，設(shè)它的銷量為njjmiinbab111將松弛變量xin+1看成是從產(chǎn)地Ai運往銷地Bn+1的數(shù)量，而運費Cin+1=0，I=1,2,m，（儲存起來）。2. 銷大于產(chǎn)的情況, 即njjmiiba11其數(shù)學(xué)模型為 0, 2 , 1, 2 , 1.min1111ijmijijnjiijminjijijxnjbxmiaxtsxcZ對銷量大于產(chǎn)量的情況, 其解法與產(chǎn)大于銷量的解法類似（假想一個產(chǎn)地）。例：求下列運輸問

2、題的最優(yōu)運輸方案。 收點發(fā)點B1B2B3B4發(fā)量A1362470A2522480A3175265收量40307060產(chǎn)銷及運價表變成產(chǎn)銷平衡的運輸問題發(fā) 收B1B2B3B4B5發(fā)量A13624070A25224080A31752065收量4030706015 利用伏格爾法、位勢表可得最優(yōu)方案如下：平衡表 單位：噸收點發(fā)點B1B2B3B4B5發(fā)量A17070 A23003515 80A3402565收量4030706015銷地產(chǎn)地B1 B2 B3 B4A1A2A3 2 11 3 4 10 3 5 9 7 8 1 2練習(xí)：設(shè)有A1，A2，A3，三個產(chǎn)地生產(chǎn)某種物質(zhì)，其產(chǎn)量分別為7，5，7，B1，B

3、2，B3，B4四個銷地需要該物資，銷量分別為2，3，4，6，又已知各產(chǎn)銷地之間的運價如表2，確定總運費最少的調(diào)運方案。表2 單位運價表 例2 設(shè)有三個化肥廠供應(yīng)四個地區(qū)化肥。其具體數(shù)據(jù)如下表，單位為萬噸、萬元/萬噸，試求總運費最省的化肥調(diào)運方案。 需求地區(qū) 化肥廠 B1 B2 B3 B4 產(chǎn)量 A1 16 13 22 17 50 A2 14 13 19 15 60 A3 19 20 23 - 50 最低需求 最高需求 30 50 70 70 0 30 10 不限 解：這是一個產(chǎn)銷不平衡問題。總產(chǎn)量160最低需求110。B4地最多可分配到60萬噸化肥。整個四個地區(qū)的最高需求總量為210萬噸，此時

4、，需求量大于總產(chǎn)量。為了平衡在產(chǎn)銷平衡表中增加一個假想的化肥廠A4，其產(chǎn)量為50萬噸。由于各地區(qū)的需求量包含兩部分，如地區(qū)B1，30萬噸 是最低需求，故必須實際得到滿足，不能由假想的化肥廠提供，令其運價為M（任意大的正數(shù)），另一部分20萬噸可滿足或不滿足都行，因此可由假想的化肥廠A4供給，可令其運價為0（相當(dāng)于目標(biāo)函數(shù)來說不影響，運不運都行）。等價于然后，按產(chǎn)銷平衡問題的表上作業(yè)法去作。這個問題的最優(yōu)方案為下表。 需求地區(qū) 化肥廠 B1 B*1 B2 B3 B4 B*4 產(chǎn)量 A1 16 16 13 22 17 17 50 A2 14 14 13 19 15 15 60 A3 19 19 20

5、 23 M M 50 A4 M 0 M 0 M 0 50 銷量 30 20 70 30 10 50 注1：B3地區(qū)的最小需求為0，故不用分別按兩個地區(qū)考慮。 2：運價表中運費為0，就意味著運與否都可以，對目標(biāo)函數(shù)沒有影響。 運費為M的，就意味著不允許運。 需求地區(qū)化肥廠B1B*1B2B3B4B*4產(chǎn)量A15050A220103060A33020050A4302050銷量302070301050第四節(jié)：運輸問題舉例第四節(jié)：運輸問題舉例例1 某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如下表。又如果生產(chǎn)出來的柴油機

6、當(dāng)季度不交貨，每臺積壓一個季度的儲存費用為0.15萬元。要求在完成合同的情況下，做出使該廠全年生產(chǎn)費用最小的決策。季度生產(chǎn)能力單位成本（萬元）12342535301010.811.111.011.31 2 3 4產(chǎn)量123410.8 10.95 11.10 11.25 11.10 11.25 11.40 11.0 11.15 11.3025353010銷量10 15 25 20D000030MMMMMM例2 某航運公司承擔(dān)六個港口城市ABCDEF的四條航線，已知各航線的起終點及每天的航班數(shù)如表1，各城市間的航程天數(shù)如表2，每次裝卸各需要1天，問航運公司至少配備多少條船，才能滿足需要？航線起點終

7、點每天航班1234EBADDCFB3211表1從 到ABCDEFABCDEF0102301413 1507 851707852030表21.周轉(zhuǎn)船只2.調(diào)度船只城市到達(dá)需求余缺數(shù)ABCDEF012301120130-1-122-31ABE剩余CDF214731385173221缺少113例3假定：每個工廠生產(chǎn)的糖果不一定直接發(fā)運到銷售點，可以幾個產(chǎn)地集中在一起運；運給各銷地的糖果可以先運給其中幾個銷地，再轉(zhuǎn)運給其他銷地；除產(chǎn)、銷點之外，中間還可有幾個轉(zhuǎn)運站，在產(chǎn)地間、銷地間或在產(chǎn)地與銷地間轉(zhuǎn)運。問：產(chǎn)銷地之間的直接運輸和非直接運輸?shù)母鞣N可能的方案中，如何使總的費用最少。產(chǎn)地、銷地、中間轉(zhuǎn)運站及

8、相互之間每噸糖果的運價。解：從表中看出這是擴大的運輸問題，特點：由于問題中所有產(chǎn)地、中間轉(zhuǎn)運站、銷地都可以看作產(chǎn)地，又可看作銷地。 建立單位運價表。方法不可能的運輸方案的運價用任意大的正數(shù)M代替。所有中間轉(zhuǎn)運站的產(chǎn)量等于銷量?？梢砸?guī)定T1,T2,T3,T4的產(chǎn)量和銷量均為20噸，每個約束條件中增加一個松弛變量xii,xii相當(dāng)于一個虛構(gòu)的轉(zhuǎn)運站,(20-xii）就是每個轉(zhuǎn)運站的實際轉(zhuǎn)運量，運價cii=0。擴大的運輸問題中原來的產(chǎn)地與銷地因為也有轉(zhuǎn)運站的作用，所以同樣在原來產(chǎn)量與銷量的數(shù)字上加20噸。A1到B2每噸糖果的直接費用為11元，如從A1經(jīng)A3運往 B2，每噸運價是3+4=7元，從A1經(jīng)T2運往B2只需1+5=6元而從A1到B2運費最少的路徑是從A1經(jīng)A2，B1到B2，每噸糖果的運費只需1+1+1=3元?？梢姰a(chǎn)地到銷地之間的運輸方案是很多的。作一般的運輸問題來處理，可以這樣做：求解過程：求解過程：確定問題的單位運價表；得到產(chǎn)銷平衡表計算最優(yōu)方案；當(dāng)變量多時可進(jìn)行計算機編程運算，結(jié)果略。 表 3-25 產(chǎn)地銷地A1A2A3T1T2T3T4B1B2B3B4產(chǎn)量A1A2A301310M3M023115M4M2323317119432101085272429T1T2T3T4