運籌說 第39期 | 運輸問題經典例題講解
運輸問題是針對生產與需求之間的關系，如何使供應鏈可以高效率低成本地進行與控制的問題。說到底這也是一個求最優(yōu)解的問題，即如何在多種方案之中找到最優(yōu)的一種方案。
通過前面的學習，我們了解到運輸問題是一類特殊的線性規(guī)劃問題，將單純型法的思想用到運輸問題的求解里，便得到了運輸問題的表上作業(yè)法。首先確定初始方案，可選用西北角法、最小元素法或伏格爾法；其次進行解的最優(yōu)性檢驗，有閉回路法和位勢法兩種基本方法；最后進行解的調整優(yōu)化，直至求得最優(yōu)解。
本期，小編選取五個運輸問題的經典例題，包括產銷平衡問題、產大于銷問題、產小于銷問題、彈性需求問題和中間轉運問題進行詳細講解。
#1產銷平衡的運輸問題
1.問題描述
某公司下屬有甲、乙、丙三個工廠，分別向A、B、C、D四個銷地提供產品，產量、需求量及工廠到銷售地的運價（單位：元/噸）如下表所示，求使費用最少的最佳運輸方案。
2.問題解析
總產量=18+18+19=55
總銷量=16+15+7+17=55
產量等于銷量，即這是產銷平衡的運輸問題。直接采用表上作業(yè)法進行求解。
3.問題求解
（1）運用最小元素法確定初始方案，如下表所示。
（2）運用位勢法對上述運輸方案進行檢驗，檢驗數(shù)表如下。
因為存在檢驗數(shù)-2小于0，所以當前方案不是最優(yōu)方案。
（3）進行解的調整優(yōu)化，改進方案表如下所示。
用位勢法對改進方案進行檢驗，得到改進方案的檢驗數(shù)表如下表。
此時所有非基變量的檢驗數(shù)都大于等于0，則當前方案是最優(yōu)方案，最優(yōu)方案如下表所示。
#2產大于銷的運輸問題
1.問題描述
有三個牧業(yè)基地向4個城市提供鮮奶，4個城市每日的鮮奶需求量、3個基地的每日鮮奶供應量以及運送每千升鮮奶的費用如下表所示，試確定最經濟的鮮奶運輸方案。
2.問題解析
總供應量=30+40+50=120
總需求量=16+30+24+30=100
供過于求，即產量大于銷量，這是一個產大于銷的運輸問題。要將問題轉化為產銷平衡的運輸問題，需進行以下幾個方面的調整。
（1）增加一個虛擬銷地E，使其總需求量為120-100=20。
（2）由于銷地是虛擬的，實際上是產量過剩的物資在產地就地儲存，所以不會產生實際的運輸，即不會產生運費。
因此新的供需量及單位運價表如下所示。
3.問題求解
（1）運用最小元素法確定初始方案，如下表所示。
易錯點：線②和③同時劃，出現(xiàn)退化現(xiàn)象，此時應該補一個值為0的基解。
（2）運用位勢法對上述運輸方案進行檢驗，檢驗數(shù)表如下。
因為所有非基變量的檢驗數(shù)都大于等于0，則當前方案是最優(yōu)方案，最優(yōu)方案如下表所示。
#3產小于銷的運輸問題
1.問題描述
某三個煤炭廠供應4個地區(qū)，假定等量的煤炭在這些地區(qū)使用效果相同，已知各煤炭廠年產量，各地區(qū)的需要量及從各煤炭廠到各地區(qū)的單位運價表如下所示，試決定最優(yōu)的調運方案。
2.問題解析
總產量=90+40+70=200
總銷量=30+50+100+40=220
產量小于銷量，即這是一個產小于銷的運輸問題。要將問題轉化為產銷平衡的運輸問題，需進行以下幾個方面的調整。
（1）增加一個虛擬產地，使其總產地為220-200=20。
（2）由于產地是虛擬的，所以不會產生實際的運輸，也就不會產生運費。
因此新的供需量及單位運價表如下所示。
3.問題求解
（1）運用伏格爾法確定初始可行解。
易錯點：線④和⑤同時劃，出現(xiàn)退化現(xiàn)象，此時應該補一個值為0的基解。
（2）運用位勢法對上述運輸方案進行檢驗，檢驗數(shù)表如下。
因為檢驗數(shù)都大于等于0，則當前方案是最優(yōu)方案，最優(yōu)方案如下表所示。
#4彈性需求的運輸問題
1.問題描述
設有三個化肥廠供應四個地區(qū)的農用化肥，假定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產量，各地區(qū)的需要量及從各化肥廠到各地區(qū)的單位運價表如下所示，試決定總運費最少的調運方案。
2.問題解析
地區(qū)Ⅳ的最高需求是當其他地區(qū)最低需求被滿足時，供給給產地Ⅳ的數(shù)量。
地區(qū)Ⅳ的最高需求=50+60+50-30-70=60
總產量=50+60+50=160
最低需求=30+70+10=110
最高需求=50+70+30+（160-30-70）=310
這是一個具有需求彈性的運輸問題，要將問題轉化為產銷平衡問題進行求解，需進行以下幾個方面的調整。
（1）將地區(qū)劃分為剛性需求地區(qū)和彈性需求地區(qū)，剛性需求地區(qū)要滿足該地區(qū)的最低需求，彈性需求地區(qū)需要滿足彈性需求，運價不變。
（2）增加一個虛擬化肥廠D，使其產銷平衡。
（3）剛性需求地區(qū)的需求必須滿足因此，虛擬化肥廠不能向剛性需求地區(qū)運輸花費，即設虛擬化肥廠到剛性需求地區(qū)的運費為無限大的M。
因此新的產銷量及單位運價表如下所示。
3.問題求解
（1）運用伏格爾法確定初始可行解。
易錯點：線⑥和⑦同時劃，出現(xiàn)退化現(xiàn)象，此時應該補一個值為0的基解。
（2）運用位勢法對上述運輸方案進行檢驗，檢驗數(shù)表如下。
因為所有非基變量的檢驗數(shù)都大于等于0，則當前方案是最優(yōu)方案，最優(yōu)方案如下表所示。
#5中間轉運的運輸問題
1.問題描述
某糖果公司下設三個工廠，每日產量分別為：A1—7噸、A2—4噸、A3—9噸。該公司將這些產品運往四個門市部，各門市部每日銷量為：B1—3噸、B2—6噸、B3—5噸、B4—6噸。
假定：①每個工廠生產的糖果不一定直接發(fā)送到銷售點，可以將其中幾個產地的糖果集中一起運；②運往各銷地的糖果可以先運給其中幾個銷地，再轉運給其他銷地；③除產、銷地之外，中間還有幾個轉運站，在產地之間、銷地之間或產銷地之間轉運。已知各產地、銷地、中間轉運站及相互之間每噸糖果的運價如下表，問在考慮到產銷地之間直接運輸和非直接運輸?shù)母鞣N可能方案的情況下，如何將三個廠每天生產的糖果運往銷售地，使總的運費最少？
2.問題解析
這是一個具有中轉運輸?shù)倪\輸問題，要將問題轉化為產銷平衡問題進行求解，需進行以下幾個方面的調整。
（1）由于問題中所有產地、中間轉運站、銷地都可以看作產地，又可以看作銷地。因此把整個問題當作有11個產地和11個銷地的擴大的運輸問題。
（2）對擴大的運輸問題建立單位運價表，方法是將不可能的運輸方案運價用任意大的正數(shù)M代替。
（3）所有中間轉運站的產量等于銷量，由于運費最少時不可能出現(xiàn)一批物資來回倒運的現(xiàn)象，所以每個轉運站的運數(shù)不超過20?？梢砸?guī)定中間轉運站的產銷量均為20，由于實際轉運量不超過各自的產量和銷量，所以在每個約束條件中增加一個松弛變量xi，相當于自己運給自己，對應運價為0。
（4）擴大的運輸問題中原來的產地與銷地因為也起中間轉運站的作用，所以，同樣在原來的產量與銷量的數(shù)字上加20，即三個糖果廠產量改為27、24、29，銷量均為20；四個銷售點銷量改為23、26、25、26，產量均為20，同時引進xii作為松弛變量。
因此新的產銷量及單位運價表如下所示。
3.問題求解
應用LINDO軟件求解，最優(yōu)方案如下表所示。
以上就是本節(jié)運輸問題案例的全部內容啦，通過對這一節(jié)的學習，大家是否掌握了運輸問題的各種形式和表上作業(yè)法呢？動動小手做一做，收獲會有大不同哦！
運籌說
作者｜何洋洋 裴傳濤 陳志昂
責編｜何洋洋
審核｜徐小峰
