運(yùn)輸問題的表上作業(yè)法

1、,第二節(jié) 運(yùn)輸問題的表上作業(yè)法,由上節(jié)介紹運(yùn)輸問題的數(shù)學(xué)模型及其約束方程組的系數(shù)矩陣結(jié)構(gòu)的特殊性，本節(jié)將由此給出運(yùn)輸問題的比單純形法更為簡便的求解方法表上作業(yè)法。,運(yùn)輸問題表上作業(yè)法,單純形法與表上作業(yè)法的關(guān)系： （1）找出初始基可行解 （2）求各非基變量的檢驗(yàn)數(shù) （3）判斷是否最優(yōu)解,運(yùn)輸問題表上作業(yè)法,換基:,（4）確定換入變量和換出變量找出新的基可行解。 （5）重復(fù)（2）、（3）直至求出最優(yōu)解。,停止,運(yùn)輸問題表上作業(yè)法,舉例說明表上作業(yè)法,某部門三個工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量,四個銷售點(diǎn)的銷量及單位運(yùn)價如下表：,運(yùn)輸問題表上作業(yè)法,第一步：確定初始基可行解 最小元素法、伏格爾法,【1】最小

2、元素法思路： 就近供應(yīng)，從單價中最小運(yùn)價確定供應(yīng)量，逐步次小，直至得到m+n-1個數(shù)字格。,運(yùn)輸問題表上作業(yè)法,最小元素法舉例,8,2,2,0,10,10,0,6,14,8,6,8,0,0,0,0,6,0,運(yùn)輸問題表上作業(yè)法,最小元素法得到的初始調(diào)運(yùn)方案,運(yùn)輸問題表上作業(yè)法,練習(xí),某部門三個工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量,四個銷售點(diǎn)的銷量及單位運(yùn)價如下表：,3,11,1,7,4,3,2,8,5,10,10,9,運(yùn)輸問題表上作業(yè)法,最小元素法練習(xí),3,1,1,0,4,4,0,3,6,3,3,3,0,0,0,0,3,0,運(yùn)輸問題表上作業(yè)法,初始調(diào)運(yùn)方案,3,11,1,7,4,3,2,8,5,10,10,9

3、,最小元素法缺點(diǎn)：會出現(xiàn)顧此失彼 （運(yùn)費(fèi)差額問題）,考慮 運(yùn)價差,運(yùn)輸問題表上作業(yè)法,罰數(shù)（即差額）=次小運(yùn)價-最小運(yùn)價,對差額最大處，采用最小運(yùn)費(fèi)調(diào)運(yùn)。,【2】伏格爾法思路：,第一步：確定初始基可行解 最小元素法、伏格爾法,運(yùn)輸問題表上作業(yè)法,伏格爾法思路,罰數(shù)（即差額）的解釋： 差額大，則不按最小運(yùn)費(fèi)調(diào)運(yùn)，運(yùn)費(fèi)增加大。 差額小，則不按最小運(yùn)費(fèi)調(diào)運(yùn)，運(yùn)費(fèi)增加不大。,運(yùn)輸問題表上作業(yè)法,結(jié)合例1說明這種方法。,0,4-4=0,第一次,運(yùn)輸問題表上作業(yè)法,1,3-2=1,第一次,運(yùn)輸問題表上作業(yè)法,1,第一次,運(yùn)輸問題表上作業(yè)法,2,1,5,3,第一次,運(yùn)輸問題表上作業(yè)法,14,8,0,下次不考

4、慮該列,第一次,運(yùn)輸問題表上作業(yè)法,第二次,8,0,6,下次不考慮該行,運(yùn)輸問題表上作業(yè)法,下次不考慮該列,8,0,2,第三次,運(yùn)輸問題表上作業(yè)法,4,12,0,下次不考慮該列,第四次,運(yùn)輸問題表上作業(yè)法,4,2,0,0,4,第五次,0,運(yùn)輸問題表上作業(yè)法,例1用伏格爾法得到的初始基可行解,用最小元素法 求出的目標(biāo)函數(shù)z=246,一般說來，伏格爾法得出的初始解的質(zhì)量最好，常用來作為運(yùn)輸問題最優(yōu)解的近似解。,運(yùn)輸問題表上作業(yè)法,練習(xí),行罰數(shù),0,第一次,1,1,6,3,0,運(yùn)輸問題表上作業(yè)法,行罰數(shù),0,第二次,1,2,1,3,2,6,3,0,3,0,3,運(yùn)輸問題表上作業(yè)法,行罰數(shù),0,第三次,

5、1,1,2,2,6,3,0,3,0,3,3,1,0,運(yùn)輸問題表上作業(yè)法,行罰數(shù),7,第四次,6,1,2,6,3,0,3,0,3,3,1,0,5,0,2,運(yùn)輸問題表上作業(yè)法,行罰數(shù),0,第五次,0,2,6,3,0,3,0,3,3,1,0,5,0,2,1,2,0,2,0,0,運(yùn)輸問題表上作業(yè)法,練習(xí)題用伏格爾法得到的初始基可行解,3,11,1,7,4,3,2,8,5,10,10,9,銷量,產(chǎn)量,銷地,產(chǎn)地,3,1,5,6,2,3,用最小元素法 求出的目標(biāo)函數(shù)z=86,運(yùn)輸問題表上作業(yè)法,第二步：解的最優(yōu)性檢驗(yàn),思路：計(jì)算空格（非基變量）的檢驗(yàn)數(shù)。 兩種方法： 【1】閉回路法 每一空格出發(fā)一定存在且

6、可以找到唯一的閉回路。 【2】位勢法 由對偶理論，得檢驗(yàn)數(shù)為 。,運(yùn)輸問題表上作業(yè)法,【1】閉回路法,在給出調(diào)運(yùn)方案的計(jì)算表上，從每一空格出發(fā)找一條閉回路。 以某空格為起點(diǎn)，用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時，可以轉(zhuǎn)90度（也可以越過）后，繼續(xù)前進(jìn)，直到回到起始空格為止。,運(yùn)輸問題表上作業(yè)法,每一空格出發(fā)一定存在且可以找到唯一的閉回路。,因m+n-1個數(shù)字格（基變量）對應(yīng)的系數(shù)向量是一個基。則任一空格（非基變量）對應(yīng)的系數(shù)向量均可由這個基線性表示。,運(yùn)輸問題表上作業(yè)法,閉回路法的經(jīng)濟(jì)解釋,若令,分析：,運(yùn)輸問題表上作業(yè)法,從初始表分析：,要保證產(chǎn)銷平衡，則,+1,-1,+1,-1,運(yùn)輸問題

7、表上作業(yè)法,2,1,運(yùn)輸問題表上作業(yè)法,檢驗(yàn)數(shù)表,2,1,1,-1,10,12,運(yùn)輸問題表上作業(yè)法,或稱對偶變量法,【2】位勢法,運(yùn)輸問題表上作業(yè)法,運(yùn)輸問題的對偶問題可寫為,運(yùn)輸問題的對偶問題對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系,運(yùn)輸問題表上作業(yè)法,運(yùn)輸問題的對偶問題對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系,運(yùn)輸問題表上作業(yè)法,設(shè)運(yùn)輸問題的一組基變量為,運(yùn)輸問題的對偶問題對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系,運(yùn)輸問題表上作業(yè)法,由于基變量的檢驗(yàn)數(shù)為零，故有,運(yùn)輸問題的對偶問題對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系,m+n-1個方程 m+n個變量,有一個自由未知量,運(yùn)輸問題表上作業(yè)法,方程組有解，且不唯一。 求出方程組的解（稱為位

8、勢）,運(yùn)輸問題的對偶問題對偶變量與原問題檢驗(yàn)數(shù)的關(guān)系,運(yùn)輸問題表上作業(yè)法,最小元素法得到的初始基可行解,3,11,1,7,4,3,2,8,5,10,10,9,運(yùn)輸問題表上作業(yè)法,運(yùn)輸問題表上作業(yè)法,銷地,產(chǎn)地,3,11,1,7,4,3,2,8,5,10,10,9,-1,10,2,12,1,1,存在負(fù)檢驗(yàn)數(shù)， 說明不是最優(yōu)解。,檢驗(yàn)數(shù)表,運(yùn)輸問題表上作業(yè)法,第三步：解的調(diào)整,當(dāng)在表中空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)時，表示未得最優(yōu)解。 若有兩個和兩個以上的負(fù)檢驗(yàn)數(shù)，一般選其中最小的負(fù)檢驗(yàn)數(shù)，以它對應(yīng)的空格為調(diào)入格。 即選擇最小檢驗(yàn)數(shù)對應(yīng)的非基變量為換入變量。,運(yùn)輸問題表上作業(yè)法,第三步：解的調(diào)整,調(diào)整位置（A

9、2，B4）非空，回路角上的格至少為空，且保證數(shù)字的非負(fù)性。,（- ）,（- ）,（+ ）,（+ ）,2,2,2,2,運(yùn)輸問題表上作業(yè)法,調(diào)整后的解為：,有無窮多最優(yōu)解,運(yùn)輸問題表上作業(yè)法,幾點(diǎn)說明：,當(dāng)檢驗(yàn)數(shù)為負(fù)的變量超過兩個，選擇最小者對應(yīng)的變量換入； 在最優(yōu)解的表中，若有非基變量的檢驗(yàn)數(shù)=0，則該運(yùn)輸問題有無窮多最優(yōu)解；,運(yùn)輸問題表上作業(yè)法,幾點(diǎn)說明：,退化一 迭代過程中，若某一格填數(shù)時需同時劃去一行和一列，此時出現(xiàn)退化。為保證m+n-1個非空格，需在上述的行或列中填入數(shù)字0。,運(yùn)輸問題表上作業(yè)法,退化情況一：,某部門三個工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量, 四個銷售點(diǎn)的銷量及單位運(yùn)價如下表：,8,8,0,0,運(yùn)輸問題表上作業(yè)法,幾點(diǎn)說明：,退化二 閉回路上出現(xiàn)兩個或兩個以上的具有（- ）標(biāo)記的相等的最小值。只能選一個作為調(diào)入格，經(jīng)調(diào)整后，得退化解。則在另一數(shù)字格上填入0。,