1、.1第二節第二節 運輸問題的表上作業法運輸問題的表上作業法 由上節介紹運輸問題的數學模型及其約束方程組的系數矩陣結構的特殊性，本節將由此給出運輸問題的比單純形法更為簡便的求解方法表上作業法。2.單純形法與表上作業法的關系單純形法與表上作業法的關系：（1）找出初始基可行解）找出初始基可行解 （2）求各非基變量的檢驗數）求各非基變量的檢驗數（3）判斷是否最優解）判斷是否最優解計算表中空格檢驗數計算表中空格檢驗數表上給出表上給出m+n-1個數字格個數字格判斷方法相同判斷方法相同3.換基換基:（4）確定換入變量和換出變量找出新）確定換入變量和換出變量找出新的基可行解。的基可行解。（5）重復（）重復（2

2、）、（）、（3）直至求出最優）直至求出最優解。解。表上調整（閉回路調整）表上調整（閉回路調整）（運輸問題必有最優解）（運輸問題必有最優解）停止停止最優解？是是否否4.舉例說明表上作業法舉例說明表上作業法 某部門三個工廠生產同一產品的產量某部門三個工廠生產同一產品的產量,四個四個銷售點的銷量及單位運價如下表：銷售點的銷量及單位運價如下表：41228543961111104814121482210163214321AAABBBB銷量銷量產量產量銷地產地5.第一步：確定初始基可行解第一步：確定初始基可行解 最小元素法、伏格爾法最小元素法、伏格爾法【1】最小元素法思路：最小元素法思路： 就近供應，從單

3、價中就近供應，從單價中最小最小運價運價確定供應量，逐步確定供應量，逐步次小次小，直至得，直至得到到m+n-1個數字格。個數字格。6.最小元素法舉例最小元素法舉例41228543961111104814121482210163214321AAABBBB銷量產量銷地產地8220101006148680000607.最小元素法得到的初始調運方案最小元素法得到的初始調運方案41228543961111104814121482210163214321AAABBBB銷量產量銷地產地821014682466811632410514280z8.練習練習 某部門三個工廠生產同一產品的產量某部門三個工廠生產同一產

4、品的產量,四個銷四個銷售點的銷量及單位運價如下表：售點的銷量及單位運價如下表：311174328510109123412374936562 0BBBBAAA銷量產量銷地產地9.最小元素法練習最小元素法練習31117432851010 9123412374936562 0BBBBAAA銷量產量銷地產地31104 403 633300003010.初始調運方案初始調運方案311174328510109123412374936562 0BBBBAAA銷量產量銷地產地31 4 6330316443123103586z最小元素法缺點：會出現顧此失彼最小元素法缺點：會出現顧此失彼 （運費差額問題）（運費差

5、額問題）考慮考慮運價差運價差11.罰數（即差額）罰數（即差額）=次小次小運價運價-最小最小運價運價對差額最大處，采用最小運費調運。對差額最大處，采用最小運費調運。【2】伏格爾法思路：伏格爾法思路：第一步：確定初始基可行解第一步：確定初始基可行解 最小元素法、伏格爾法最小元素法、伏格爾法12.伏格爾法思路伏格爾法思路罰數（即差額）的解釋：罰數（即差額）的解釋：;差額大，則不按最小運費調運，運費差額大，則不按最小運費調運，運費增加大。增加大。;差額小，則不按最小運費調運，運費差額小，則不按最小運費調運，運費增加不大。增加不大。13.結合例結合例1說明這種方法。說明這種方法。481412148221

6、0163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數04-4=0第一次第一次14.4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數013-2=1第一次第一次15.4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數011第一次第一次16.4814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數011 列 罰 數2153第一次第一次17.4814121

7、482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地行罰數011 列 罰 數21531480優先安排銷地優先安排銷地 ，否則運，否則運價會更高價會更高2B下次不考慮該列下次不考慮該列第一次第一次18.第二次第二次行罰數012 列 罰 數213優先安排銷地優先安排銷地 ，否則運，否則運價會更高價會更高4B84814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地148006下次不考慮該行19.行罰數01 列 罰 數21284814121482210163214321AAABBBB412285

8、4396111110銷量產量銷地銷地產地產地148006下次不考慮該列802第三次第三次20.行罰數76 列 罰 數1284814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地1480068024120下次不考慮該列第四次第四次21.行罰數00 列 罰 數24284814121482210163214321AAABBBB4122854396111110銷量產量銷地銷地產地產地1480068024120004第五次第五次022.例例1用伏格爾法得到的初始基可行解用伏格爾法得到的初始基可行解4814121482210163214321AA

9、ABBBB4122854396111110銷量產量銷地銷地產地產地48148122244685149228114412 z目標函數值目標函數值用最小元素法用最小元素法求出的目標函求出的目標函數數z=246 一般說來，伏格爾法得出的初始一般說來，伏格爾法得出的初始解的質量解的質量最好最好，常用來作為運輸問，常用來作為運輸問題最優解的題最優解的近似解近似解。23. 列 罰 數13521234123749365620BBBBAAA31117432851010 9銷量產量銷地銷地產地產地練習練習行罰數0第一次第一次11優先安排銷地優先安排銷地 ，否則運，否則運價會更高價會更高2B63024.12341

10、23749365620BBBBAAA31117432851010 9銷量產量銷地銷地產地產地行罰數0第二次第二次12 列 罰 數132630優先安排銷地優先安排銷地 ，否則運，否則運價會更高價會更高4B30325.1234123749365620BBBBAAA31117432851010 9銷量產量銷地銷地產地產地行罰數0第三次第三次1 列 罰 數12263030331026.1234123749365620BBBBAAA31117432851010 9銷量產量銷地銷地產地產地行罰數7第四次第四次6 列 罰 數1263030331050227.1234123749365620BBBBAAA31

11、117432851010 9銷量產量銷地銷地產地產地行罰數0第五次第五次0 列 罰 數263030331050212020028.練習題用伏格爾法得到的初始基可行解練習題用伏格爾法得到的初始基可行解311174328510109123412374936562 0BBBBAAA銷量產量銷地產地31 5 6230316453210183585z用最小元素法用最小元素法求出的目標函求出的目標函數數z=8629.第二步：解的最優性檢驗第二步：解的最優性檢驗n思路：計算空格（非基變量）的檢驗數。思路：計算空格（非基變量）的檢驗數。n兩種方法：兩種方法：【1】閉回路法閉回路法 每一空格出發一定存在且可以找

12、到唯一的閉每一空格出發一定存在且可以找到唯一的閉回路。回路。【2】位勢法位勢法 由對偶理論，得檢驗數為由對偶理論，得檢驗數為 。 ()ijijcuv30.【1】閉回路法閉回路法n在給出調運方案的計算表上，從每一空在給出調運方案的計算表上，從每一空格出發找一條閉回路。格出發找一條閉回路。 以某空格為起點，用水平或垂直線以某空格為起點，用水平或垂直線向前劃，當碰到一數字格時，可以轉向前劃，當碰到一數字格時，可以轉90度（也可以越過）后，繼續前進，直到度（也可以越過）后，繼續前進，直到回到起始空格為止。回到起始空格為止。31.每一空格出發每一空格出發一定存在一定存在且可以找且可以找到到唯一唯一的閉回

13、路。的閉回路。 ()()()()m km klijimjimjim klm klm sum sumjiklklslm sm suuusujeeeeeeePeeeeeeeeeeeeeePPPPeP因因m+n-1個數字格（基變量）對應的系數向量是個數字格（基變量）對應的系數向量是一個基。則任一空格（非基變量）對應的系數向一個基。則任一空格（非基變量）對應的系數向量均可由這個基線性表示。量均可由這個基線性表示。32.閉回路法的經濟解釋閉回路法的經濟解釋24242121121211110 xxxxzz1112241101,0 xxxzz若令若令分析：分析：運費的增量運費的增量即 增加1個單位 的檢驗數

14、=相應的運費增量11x11x33.41228543961111104814121482210163214321AAABBBB銷量產量銷地產地821014682460z從初始表分析：從初始表分析：要保證產銷平衡，則要保證產銷平衡，則1, 12344110zz111121231311xxxx 稱為閉回路 21231311xxxx+1-1+1-134.41228543961111104814121482210163214321AAABBBB銷量產量銷地產地82101468256111212156114310222135.檢驗數表檢驗數表41228543961111104814121482210163

15、214321AAABBBB銷量產量銷地產地82101468211-11012,0124表中的解不是最優解。表中的解不是最優解。36.n或稱對偶變量法或稱對偶變量法)(),(11jiijijnmijijijijijijvucPvvuucYPczc【2】位勢法位勢法37.11max,1,;. .1, .,mniijjijijijijza ub vuvcims tjnuv 無約束運輸問題的對偶問題可寫為運輸問題的對偶問題可寫為運輸問題的對偶問題運輸問題的對偶問題對偶變量與原問題檢驗數的關系對偶變量與原問題檢驗數的關系38.jjjBjjjjYPcPBCczc1線性規劃問題變量線性規劃問題變量 的檢驗數

16、為的檢驗數為jx運輸問題的對偶問題運輸問題的對偶問題對偶變量與原問題檢驗數的關系對偶變量與原問題檢驗數的關系)(),(11jiijijnmijijijijijijvucPvvuucYPczc變量變量 的檢驗數為的檢驗數為ijx00100100ijP39.設運輸問題的一組基變量為設運輸問題的一組基變量為1 12 2,1s si ji ji jxxxsmn運輸問題的對偶問題運輸問題的對偶問題對偶變量與原問題檢驗數的關系對偶變量與原問題檢驗數的關系40.由于基變量的檢驗數為零，故有由于基變量的檢驗數為零，故有111 1222 2sss siji jiji jiji juvcuvcuvc運輸問題的對偶

17、問題運輸問題的對偶問題對偶變量與原問題檢驗數的關系對偶變量與原問題檢驗數的關系m+n-1m+n-1個方程個方程m+nm+n個變量個變量有一個自由未知量有一個自由未知量41.方程組有解，且不唯一。方程組有解，且不唯一。求出方程組的求出方程組的（稱為（稱為位勢位勢）)(jiijijvuc而其他變量而其他變量 的檢驗數為的檢驗數為ijx1212( , ,)mmYu uuv vv運輸問題的對偶問題運輸問題的對偶問題對偶變量與原問題檢驗數的關系對偶變量與原問題檢驗數的關系求運輸問題求運輸問題檢驗數的一檢驗數的一種方法種方法42.最小元素法得到的初始基可行解最小元素法得到的初始基可行解3111743285

18、10109123412374936562 0BBBBAAA銷量產量銷地產地31 4 633131421233234,xxxxxx為基變量。則有為基變量。則有43.131313131414141421212121232323233232323234343143403001000100200405000 xcuvuvxcuvuvxcuvuvxcuvuvxcuvuvxcuvuvu 基變量檢驗數令2312341,5,2,9,3,10uuvvvv 44.123412301529310BBBBAAA銷地產地00 0 000iujv311174328510109-11021211存在負檢驗數，存在負檢驗數，

19、說明不是最優解。說明不是最優解。()ijijijcuv檢驗數表檢驗數表45.第三步：解的調整第三步：解的調整n當在表中空格處出現當在表中空格處出現負檢驗數負檢驗數時，表時，表示未得最優解。示未得最優解。n若有兩個和兩個以上的負檢驗數，一般若有兩個和兩個以上的負檢驗數，一般選其中選其中最小的負檢驗數最小的負檢驗數，以它對應的，以它對應的空格為調入格。空格為調入格。n即選擇最小檢驗數對應的非基變量為即選擇最小檢驗數對應的非基變量為換換入變量入變量。46.第三步：解的調整第三步：解的調整 調整位置（調整位置（A2，B4）非空，回路角上的格）非空，回路角上的格至少為空，且保證數字的非負性。至少為空，且

20、保證數字的非負性。41228543961111104814121482210163214321AAABBBB銷量產量銷地產地82101468-1（- ）（- ）（+ ）（+ ）222247.調整后的解為：調整后的解為：41228543961111104814121482210163214321AAABBBB銷量產量銷地產地8212144822091122246244689211441251428, 0zij此時的解為最優解。此時的解為最優解。有無窮多有無窮多最優解最優解48.幾點說明：幾點說明：n當檢驗數為負的變量超過兩個，選擇當檢驗數為負的變量超過兩個，選擇最最小者小者對應的變量換入；對應的變量換入；n在最優解的表中，若有在最優解的表中，若有非基變量的檢非基變量的檢驗數驗數=0，則該運輸問題有，則該運輸問題有無窮多最無窮多最優解優解；49.幾點說明：幾點說明：n退化一退化一 迭代過程中，若某一格填數時需迭代過程中，若某一