1第一章線性規(guī)劃2§1-6運輸問題

一.運輸問題的數(shù)學模型二.表上作業(yè)法三.產(chǎn)銷不平衡運輸問題3二.表上作業(yè)法

1.基本步驟

2.尋找初始方案的方法（1）－最小元素法

3.尋找初始方案的方法（2）－最大差值法

4.判斷最優(yōu)解的方法（1）－閉回路法

5.判斷最優(yōu)解的方法（2）－位勢法

6.非最優(yōu)方案的改進－閉回路調(diào)整法

7.多最優(yōu)解的判斷及處理方法45.位勢法用閉回路法求檢驗數(shù)時，需給每一空格找一條閉回路。當產(chǎn)銷點很多的時候，這種計算很麻煩。相比之下，位勢法比較簡便。位勢法求解的具體步驟為：①引入兩組數(shù)，稱為位勢。對于產(chǎn)地Ai的位勢稱為行位勢，用ui表示；對于銷地Bj的位勢稱為列位勢，Vj用表示。分別放在初始方案表的右邊和下面。5②通過數(shù)字格求位勢。首先設定一個位勢值。通常設定行位勢的第一個為0，即u1=0，然后通過公式：

Cij=ui+vj

求出其余行、列位勢。其中cij為數(shù)字格所對應的價值系數(shù)。③通過空格求檢驗數(shù)采用數(shù)字格確定了行、列位勢之后，再通過公式：

σij=Cij－ui－vj

求得所有空格所對應的檢驗數(shù)。其中，Cij為空格所對應的價值系數(shù)。回頭看看前面的例子，按最大差值法得到的初始方案表為：6①設u1=0，對數(shù)字格，按Cij=ui+vj得各行位勢與列位勢如上表所示。②對空格，按：

σij=Cij－ui－vj計算得：B1B2B3B4uiA16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×vj，該初始方案不是最優(yōu)方案。0796-5-811因為：1-10-17576.方案的改進－閉回路調(diào)整法由閉回路法或者位勢法判定出不是最優(yōu)方案以后，接下來要做的就是怎樣調(diào)整現(xiàn)有的方案，讓其向最優(yōu)方案靠近。最優(yōu)方案的調(diào)整通常采用閉回路法。閉回路法的基本步驟為：①選擇檢驗數(shù)為負數(shù)的空格為調(diào)入格（對應的變量為入基變量），如果有兩個以上的檢驗數(shù)為負數(shù)，則選擇絕對值最大的那個負檢驗數(shù)。8②以此空格為出發(fā)點，作一閉回路，根據(jù)前面介紹的閉回路法經(jīng)濟含義的解釋，設起始格每增加一噸礦石，閉回路中其它的格就要據(jù)此調(diào)整，閉回路中各格的調(diào)運量有增有減，以達到新的平衡。③選擇所有減少調(diào)運量的格，即帶有（-1）的格中的最小值，作為調(diào)入格的調(diào)入量θ，則對應的所有帶(-1)格減去θ，而所有帶(+1)的格增加θ，即為調(diào)整之后的新方案。9方案1：（該方案為采用最小元素法所得到的初始方案，調(diào)運費用f＝573）B1B2B3B4A16[8]9[7]12×7[45]A21[42]3×6×1×A35×1[23]3[25]4×

6[8]

9[7]1[42]3×因為：所有帶(-1)的格減去θ1而帶(+1)的格加上θ1的調(diào)整后得方案。調(diào)整過程即結(jié)果見右表。調(diào)整后的運費為：f1’=6×15+9×0+7×45+1×35+3×7+1×23+3×25=559

在該閉回路法進行調(diào)整：前面用閉回路法得到的檢驗數(shù)如表中所示：B1B2B3B4A16[8+7]9[7－7]12×7[45]A21[42－7]3[×+7]6×1×A35×1[23]3[25]4×1-115711因為從此格出發(fā)形成閉回路如圖所示。(+1)(-1)(+1)(-1)該方案不是最優(yōu)方案。10方案2：(采用最大差值法得到的初始方案，f2=566)B1B2B3B4A16[8]9[7]12×7[45]A21[42]3[×]6×1×A35×1[23]3[25]4×(+1)

6[8](-1)

7[45]（-1）1[42](+1)

1×因為：調(diào)整后的運費為：f2’=6×50+9×7+7×3+1×[42-2]+1×42+1×23+3×25=524

選σ24

對應的空格所作的閉回路及其調(diào)整方式如圖所示。前面用位勢法得到的檢驗數(shù)如表中所示：B1B2B3B4A16[8+42]9[7]12×7[45-42]A21[42-42]3[×]6×1[0＋42]A35×1[23]3[25]4×1-10-175因為有：可在σ24和σ22所對應的空格中任選一個做閉回路進行調(diào)整。所有帶(-1)的格減去θ2而帶(+1)的格加上θ2的調(diào)整后得方案。調(diào)整過程即結(jié)果見右表。所以該初始方案也不是最優(yōu)方案。117.新方案的最優(yōu)性檢驗（采用位勢法）方案1：B1B2B3B4uiA16[15]9×12×7[45]0A21[35]3[7]6×1×-5A35×1[23]3[25]4×-7vj68107由數(shù)字格得到：ui＝[0-5-7];vj=[68107]再由空格得到：21-164由于有所以該方案不是最優(yōu)方案。112對于方案2：B1B2B3B4uiA16[50]9[7]12×7[3]0A21×3×6×1[42]-6A35×1[23]3[25]4×-8vj69117由數(shù)字格得到：ui＝[0-6-8];vj=[69117]再由空格得到：10175由于所有的σ均滿足σ≥0，所以該方案為最優(yōu)方案。1138.多最優(yōu)解分析

到此為止，我們已經(jīng)基本掌握了表上作業(yè)法的方法，需要注意的是：和一般單純形法一樣，在表上作業(yè)法中也會常常會出現(xiàn)無窮多最優(yōu)解的情況，那么用什么來判斷出現(xiàn)什么時候會出現(xiàn)最優(yōu)解？

（1）多最優(yōu)解的判別和單純形法一樣，當檢驗數(shù)σ中出現(xiàn)為0的時候，就是具有多最優(yōu)解的時候?？捶桨?中的檢驗數(shù)σ，因為其中有σ22＝0，所以，該方案中具有多最優(yōu)解。14（2）從一個最優(yōu)解到另一個最優(yōu)解的求解過程用閉回路調(diào)整法可以從一個最優(yōu)解調(diào)整到另外一個最優(yōu)解。以例2的最優(yōu)解為例，我們來看看具體的做法。B1B2B3B4uiA16[50]9[7]12×7[3]0A21×3×6×1[42]-6A35×1[23]3[25]4×-8vj69117110175

雖然這時候已經(jīng)是最優(yōu)方案，但因為σ22＝0，有多最優(yōu)解。從σ22出發(fā)進行調(diào)整，調(diào)整方案為：由于θ=min{7,42}=7,新的方案中x22=0+7=7,x12=7-7=0,x14=3+7=10,x24=42-7=35,其余x11=50,x32=23,x33=25不變，則最優(yōu)值f=6×50＋7×10+3×7+1×35+3×25=524。再求檢驗數(shù)，如果還能找到為0的σ值，則還能找出新的最優(yōu)解。(+1)(-1)(+1)(-1)15例：某地區(qū)有三個化肥廠，除供應外地區(qū)需要外，估計每年可供應本地區(qū)的數(shù)字為：化肥廠A－7萬噸；化肥廠B－8萬噸；化肥廠C－3萬噸。本地區(qū)有四個產(chǎn)糧區(qū)需要該種化肥：甲地區(qū)－6萬噸；乙地區(qū)－6萬噸；丙地區(qū)－3萬噸；丁地區(qū)－3萬噸。已知從各化肥廠到各產(chǎn)糧區(qū)的每噸化肥的運價表如下表所示（表中單位：元/噸），試根據(jù)以上資料制定一個使總運費為最少的化肥調(diào)運方案。甲乙丙丁A5873B49107C842916根據(jù)該問題的要求，我們的解題步驟應為：（1）建表；（2）確定初始方案（用最大差值法）；（3）求檢驗數(shù)（用位勢法）；（4）用閉回路法進行調(diào)整，重復（2）（3）以得出最優(yōu)方案。解：（1）建表。在運價表的基礎上，甲乙丙丁A5873B49107C8429bj6633ai783根據(jù)三個化肥廠生產(chǎn)量：化肥廠A－7萬噸；化肥廠B－8萬噸；化肥廠C－3萬噸。以及四個產(chǎn)糧區(qū)需要量：甲地區(qū)－6萬噸；乙地區(qū)－6萬噸；丙地區(qū)－3萬噸；丁地區(qū)－3萬噸。等數(shù)字可得：因為：∑ai＝18＝∑bj，該問題為一產(chǎn)銷平衡問題。1817（2）用最大差值法求初始方案

甲乙丙丁aiA58737B491078C84293bj663318k11454h12322[3]10×7×8×4×9×bj(1)6603ai(1)780k211-4h223-3[3]7×bj(2)6600ai(2)480k311--h335-4[6]5×bj(3)0600ai(3)4208[4]9[2]得初始調(diào)運方案為：x12=4；x14=3；x21=6；x22=2；x33=3；初始調(diào)運費用為：f1=8×4+3×3+4×6+9×2+2×3=8918（3）用位勢法求檢驗數(shù)

甲乙丙丁uiA5×8[4]7×3[3]B4[6]9[2]10×7×C8×4×2[3]9×vj①用數(shù)字格求位勢設u1=0,由cij=ui+vj得：03813到此無法計算下去。？因為根據(jù)表上作業(yè)法所對應的數(shù)學模型特征，7個方程組，必須有6個獨立的基變量，而初始方案中只給了5個基變量，所以，必然有一個基變量對應的調(diào)運量為0。假設x13＝0為基變量：7[0]-57②用空格求檢驗數(shù)根據(jù)：σij=Cij－ui－vj得：因為檢驗數(shù)滿足σ

≥0，所以該調(diào)運方案已經(jīng)是最優(yōu)方案。思考：如果假設x23或者x31或者x32或者x34為基變量，會出現(xiàn)什么樣的情況，應該怎么解決？19三.產(chǎn)銷不平衡運輸問題

前面討論的是產(chǎn)銷平衡的情況，而在實際中經(jīng)常出現(xiàn)的卻是產(chǎn)銷不平衡情況。那么產(chǎn)銷不平衡的時候應該怎么辦？回憶一下前面講到的產(chǎn)銷不平衡的情況主要有兩種：一種是產(chǎn)大于銷，即：另一種是銷大于產(chǎn)，即：20出現(xiàn)了產(chǎn)銷不平衡的情況，怎樣尋找最優(yōu)調(diào)運方案？主要思路：既然產(chǎn)銷平衡問題有了比較完善的解決方法，那么解決產(chǎn)銷不平衡問題的總體思路就應該是把不平衡問題＝>平衡問題，然后依然按產(chǎn)銷平衡的方法來求解。怎樣將不平衡轉(zhuǎn)化成平衡的狀態(tài)？對于產(chǎn)大于銷的情況，可以假設還有一個銷地，用Bn+1表示；而對于銷大于產(chǎn)的情況，則可增加一個假想的銷地Am+1，通過增加假想的“產(chǎn)地”或者“銷地”，使得產(chǎn)銷達到平衡。下面以“產(chǎn)大于銷”的情況為例進行詳細分析。211.產(chǎn)大于銷的運輸問題對于產(chǎn)大于銷的情況，即：其數(shù)學模型可以表示為：

由于總產(chǎn)量大于總銷量，則考慮為多余的物資找一個存儲地。設xi,n+1是產(chǎn)地Ai大于銷地接受量的產(chǎn)量，則可增加一個假想的銷地Bn+1，該假想銷地所需要的產(chǎn)量剛好為xi,n+1

。22根據(jù)這樣的假設，原約束方程可修改為：而：再令各產(chǎn)地到該假想銷地的運價為零，即：23則可得：其中：這又是一個產(chǎn)銷平衡問題，完全可以用我們前面介紹的方法進行求解，然后在最優(yōu)解中刪除所增加的假想銷地，便可得到該問題的最優(yōu)解。24例：

已知一產(chǎn)銷運價表如下所示，試求解最優(yōu)運輸方案。B1B2B3B4aiA120183513180A213162114150A326303170bj8090130140500440解：因為該問題中的總銷售量為440，而總產(chǎn)量為500，因此原問題屬于“產(chǎn)大于銷”的運輸問題。

25

增加假想銷地B5（實際上就是就地庫存多余的產(chǎn)品），B5的銷售量為（產(chǎn)量500）－（銷量440）＝60，因為是就地庫存，所以所有產(chǎn)地到B5的運費均為0，由此得新的產(chǎn)銷平衡運價表如下：

B1B2B3B4B5aiA1201835130180A2131621140150A3263030170bj809013