第二節(jié) 表上作業(yè)法求解運輸問題 - Copy

1、第二節(jié)第二節(jié) 表上作業(yè)法求解運輸問題表上作業(yè)法求解運輸問題第二節(jié)第二節(jié) 表上作業(yè)法求解運輸問題表上作業(yè)法求解運輸問題本本 節(jié)節(jié) 要要 點點運輸問題初始基可行解的確定運輸問題初始基可行解的確定解的最優(yōu)性檢驗與方案的改進解的最優(yōu)性檢驗與方案的改進運輸單純形法也稱為表上作業(yè)法，是直接在運價表上運輸單純形法也稱為表上作業(yè)法，是直接在運價表上求最優(yōu)解的一種方法，它是一種迭代法，步驟為：求最優(yōu)解的一種方法，它是一種迭代法，步驟為： 第一步：第一步：求初始基本可行解（初始調運方案）。求初始基本可行解（初始調運方案）。 常用常用的方法有最小元素法、元素差額法（的方法有最小元素法、元素差額法（Vogel近似法）

2、、左近似法）、左上角法。上角法。 第二步：第二步：求檢驗數(shù)并判斷是否得到最優(yōu)解。常用求檢求檢驗數(shù)并判斷是否得到最優(yōu)解。常用求檢驗數(shù)的方法有閉回路法和位勢法，當非基變量的檢驗數(shù)驗數(shù)的方法有閉回路法和位勢法，當非基變量的檢驗數(shù) ij全都非負時得到最優(yōu)解，若存在檢驗數(shù)全都非負時得到最優(yōu)解，若存在檢驗數(shù) lk0，說明還說明還沒有達到最優(yōu)，轉第三步。沒有達到最優(yōu)，轉第三步。 第三步：第三步：調整運量，即換基。選最小負檢驗數(shù)所對應調整運量，即換基。選最小負檢驗數(shù)所對應的非基變量作為入基變量，選一個適當?shù)幕兞孔鳛槌龅姆腔兞孔鳛槿牖兞浚x一個適當?shù)幕兞孔鳛槌龌兞?，對原運量進行調整得到新的基可行解，轉

3、入第基變量，對原運量進行調整得到新的基可行解，轉入第二步。二步。一、運輸問題初始基可行解的確定一、運輸問題初始基可行解的確定1. 最小元素法最小元素法 ：最小元素法的思想是就近優(yōu)先運送，即最小運價最小元素法的思想是就近優(yōu)先運送，即最小運價Cij對對應的變量應的變量xij優(yōu)先賦值優(yōu)先賦值然后再在剩下的運價中取最小運價對應的變量賦值并然后再在剩下的運價中取最小運價對應的變量賦值并滿足約束，依次下去，直到最后得到一個初始基可滿足約束，依次下去，直到最后得到一個初始基可行解。行解。jiijbax,min【例例3.3】求表求表34所示的運輸問題的初始基可行解。所示的運輸問題的初始基可行解。表表34 銷銷

4、 地地產地產地B1B2B3產量產量A1A2A3847634758304525銷銷 量量603010100 BjAiB1B2B3產產 量量A186730A243545A374825銷銷 量量603010100表表35【解解】3015102520該運輸問題的初始解：該運輸問題的初始解： x11 =20, x13 =10, x21 =15,x22 =30 ，x31 =25,這時總運費為這時總運費為555(15)(20)(20)【例例3.4】求表求表3-6給出的運輸問題的初始基本可行解給出的運輸問題的初始基本可行解 B1B2B3B4aiA14104420A2773815A31210615bj51025

5、1050表表3-6表表3-7 BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解解】510 0151010當選定最小元素后，該元素所在行的產地產量等于當選定最小元素后，該元素所在行的產地產量等于所在列的銷地的銷量，此時需要在打所在列的銷地的銷量，此時需要在打“”的變量中任的變量中任選一個變量作為基變量，運量等于選一個變量作為基變量，運量等于0填有數(shù)字格填有數(shù)字格2元素差額法（元素差額法（Vogel近似法）近似法）最小元素法只考慮了局部運輸費用最小。有時為了最小元素法只考慮了局部運輸費用最小。有時為了節(jié)省某一處的運費，而在其它處可能運費很大

6、。元節(jié)省某一處的運費，而在其它處可能運費很大。元素差額法對最小元素法進行了改進，考慮到產地到素差額法對最小元素法進行了改進，考慮到產地到銷地的最小運價和次小運價之間的差額，如果差額銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調運，否則會增加總運費。很大，就選最小運價先調運，否則會增加總運費。例如下面兩種運輸方案例如下面兩種運輸方案10515108520211515C10155108520211515C前一種按最小元素法求得，總運費是前一種按最小元素法求得，總運費是Z1=108+52+151=10510515108520211515C10155108520211515C后一種

7、方案考慮到后一種方案考慮到C11與與C21之間的差額是之間的差額是82=6，先調運先調運x21，再是再是x22，其次是其次是x12這時總運費這時總運費Z2=105+152+51=85Z1。罰數(shù)：罰數(shù)：產地到銷地的最小運價和次小運價之間的產地到銷地的最小運價和次小運價之間的差額差額 基于以上思路，元素差額法求初始基本可行解的步驟基于以上思路，元素差額法求初始基本可行解的步驟是：是： 第一步第一步：求出每行次小運價與最小運價之差，記為：求出每行次小運價與最小運價之差，記為ui，i=1,2,m ；同時求出每列次小運價與最小運價之差，同時求出每列次小運價與最小運價之差，記為記為vj，j=1，2，n ；

8、 第二步第二步：找出所有行、列差額的最大值，即：找出所有行、列差額的最大值，即L=maxui，vi，差額差額L對應行或列的最小運價處優(yōu)先調運；對應行或列的最小運價處優(yōu)先調運； 第三步第三步：這時必有一列或一行調運完畢，在剩下的運：這時必有一列或一行調運完畢，在剩下的運價中再求最大差額，進行第二次調運，依次進行下去，價中再求最大差額，進行第二次調運，依次進行下去，直到最后全部調運完畢，就得到一個初始調運方案。直到最后全部調運完畢，就得到一個初始調運方案。 用元素差額法求得的基本可行解更接近最優(yōu)解，所以用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。也稱為近似方案。表表3-8B1B2

9、B3B4aiA15891215A2172425A361013820bj201052560【例例3.5】用元素差額法求表用元素差額法求表38運輸問題的初始基本運輸問題的初始基本【解解】 求行差額求行差額 ui, i=1,2,3及列差額及列差額vj,j=1,2,3,4.計算公計算公 式為式為可行解可行解ui= i行次小運價行次小運價i行最小運價行最小運價vj= j列次小運價列次小運價j例最小運價例最小運價表表3-9 BjAiB1B2B3B4aiui (1) ui (2) ui (3) A158912153A21724251A3610138202bj201052560vj (1) 4174vj (2

10、) vj (3) 200【 】10205總運費總運費Z=108+512+201+52+208=330。初始基可行解：初始基可行解： x11 =0, x12 = 10，x14 =5, x21 =20,x23 =5 ， x34 = 20【 】5414332【 】2244練習練習1：用元素差額法求表用元素差額法求表36運輸問題的初始基本可行解運輸問題的初始基本可行解 B1B2B3B4aiA14104420A2773815A31210615bj510251050表表3-6用元素差額法求表用元素差額法求表36運輸問題的初始基本可行解運輸問題的初始基本可行解 B1B2B3B4aiui (1) ui (2)

11、 ui (3) A14 10 4 (10) 4 (10) 20000A27 7 3 (15)8 15445A31 (5) 2 (10) 10 6 1515bj510251050vj (1) 3512vj (2) 312vj (3) 14表表3-6【 】【 】0【 】總運費總運費Z=104+104+153+51+102=150。練習練習2：用元素差額法求表用元素差額法求表34運輸問題的初始基本可行解運輸問題的初始基本可行解表表3-4 銷銷 地地產地產地B1B2B3產量產量A1A2A3847634758304525銷銷 量量603010100用元素差額法求表用元素差額法求表36運輸問題的初始基本可

12、行解運輸問題的初始基本可行解表表3-6總運費總運費Z=158+65+107+454+254=500。 B1B2B3aiui (1) ui (2) A18 (15) 6 (5)7 (10)3011A24 (45)3 5 451A37 4 (25)8 2533bj603010100 vj (1) 312 vj (2) 121【 】【 】左上角法左上角法(亦稱西北角法亦稱西北角法)是優(yōu)先從運價表的左上角的變量是優(yōu)先從運價表的左上角的變量賦值，當行或列分配完畢后，再在表中余下部分的左上賦值，當行或列分配完畢后，再在表中余下部分的左上角賦值，依次類推，直到右下角元素分配完畢當出現(xiàn)角賦值，依次類推，直到右

13、下角元素分配完畢當出現(xiàn)同時分配完一行和一列時，仍然應在打同時分配完一行和一列時，仍然應在打“”的位置上選的位置上選一個變量作基變量，以保證最后的基變量數(shù)等于一個變量作基變量，以保證最后的基變量數(shù)等于m+n1 3. 左上角法左上角法【例例3.6】求表求表310所示的運輸問題的初始基可行解。所示的運輸問題的初始基可行解。表表310 銷銷 地地產地產地B1B2B3產量產量A1A2A3847634758304525銷銷 量量603010100 BjAiB1B2B3產產 量量A186730A243545A374825銷銷 量量603010100表表3-113030151510【解解】初始基可行解：初始基

14、可行解： x11 =30, x21 =30, x22 =15,x22 =15 ，x23 =10, 這時總運費為這時總運費為545二、解的最優(yōu)性檢驗二、解的最優(yōu)性檢驗求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記驗數(shù)來判斷，記xij的檢驗數(shù)為的檢驗數(shù)為 ij由第一章知，求最小值由第一章知，求最小值的運輸問題的最優(yōu)判別準則是：的運輸問題的最優(yōu)判別準則是：求檢驗數(shù)的方法有兩種，閉回路法和位勢法。求檢驗數(shù)的方法有兩種，閉回路法和位勢法。1閉回路法求檢驗數(shù)閉回路法求檢驗數(shù)所有非基變量的檢驗數(shù)都非負，則運輸方案最優(yōu)（即為所有非基變量的檢驗數(shù)都

15、非負，則運輸方案最優(yōu)（即為最優(yōu)解）最優(yōu)解）調運方案中由一個空格和若干個有數(shù)字格的水平或垂調運方案中由一個空格和若干個有數(shù)字格的水平或垂直線段依次連接構成的一封閉多邊形。直線段依次連接構成的一封閉多邊形。 閉回路：閉回路：閉回路中的頂點必須是基變量閉回路中的頂點必須是基變量表表3-7 BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050510 0151010變量變量x 22不是閉回路的頂點，只是連線的交點。不是閉回路的頂點，只是連線的交點。 每個空格都唯一存在一條封閉回路。每個空格都唯一存在一條封閉回路。 可以證明：可以證明：注：注：一條閉回路中

16、的頂點數(shù)一定是偶數(shù)，回路遇到一條閉回路中的頂點數(shù)一定是偶數(shù)，回路遇到頂點必須轉頂點必須轉90度與另一頂點連接度與另一頂點連接結論：結論：位于閉回路上的一組變量，它們對應的運輸問題約束位于閉回路上的一組變量，它們對應的運輸問題約束條件系數(shù)列向量線性相關，因而在確定運輸問題基可條件系數(shù)列向量線性相關，因而在確定運輸問題基可行解時，除要求非零變量的個數(shù)為行解時，除要求非零變量的個數(shù)為(m+n-1) 外，還要外，還要求運輸表中有數(shù)字的格不構成閉回路。求運輸表中有數(shù)字的格不構成閉回路。前述最小元素法、前述最小元素法、Vogel法和西北角法得到的解滿足法和西北角法得到的解滿足這些條件這些條件在基本可行解矩

17、陣中，以該非基變量為起點，以基變量在基本可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開始，分別在頂點為其它頂點，找一條閉回路，由起點開始，分別在頂點上交替標上代數(shù)符號上交替標上代數(shù)符號+、-、+、-、，以這些符號分別，以這些符號分別乘以相應的運價，其代數(shù)和就是這個非基變量的檢驗數(shù)。乘以相應的運價，其代數(shù)和就是這個非基變量的檢驗數(shù)。求求某一非基變量的檢驗數(shù)的方法：某一非基變量的檢驗數(shù)的方法： BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050510 0151010-11-210437 13231231232121

18、CCCCCC 【解解】用最小元素法得到下列一組基本可行解用最小元素法得到下列一組基本可行解6010702030 501010201060 4030X【例例3.7】求下列運輸問題的一個初始基本可行解及其求下列運輸問題的一個初始基本可行解及其檢驗數(shù)。矩陣中的元素為運價檢驗數(shù)。矩陣中的元素為運價Cij ，矩陣右邊的元素為矩陣右邊的元素為產量產量ai ，下方的元素為銷量下方的元素為銷量bj 。938470765150210922010 6040 30 BjAiB1B2B3B4aiA19384706010A27651502030A321092201010bj10604030831331311,xxxx3

19、1331311,CCCC829893133131111 CCCC 0966-339512 698310 63856929570851433232434343313123232121323222231332321211323244114 CCCCCCCCCCCCCCCCCCCC 這里這里 340，說明這組基本可行解不是最優(yōu)解。說明這組基本可行解不是最優(yōu)解。2位勢法求檢驗（對偶變量法）位勢法求檢驗（對偶變量法）位勢法求檢驗數(shù)是根據(jù)對偶理論推導出來的一種方法。位勢法求檢驗數(shù)是根據(jù)對偶理論推導出來的一種方法。閉回路法判定一個運輸方案是否為最優(yōu)方案，需要閉回路法判定一個運輸方案是否為最優(yōu)方案，需要找出所

20、有空格的閉回路，并計算出其檢驗數(shù)。當運找出所有空格的閉回路，并計算出其檢驗數(shù)。當運輸問題的產地和銷地很多時，空格的數(shù)目很大，計輸問題的產地和銷地很多時，空格的數(shù)目很大，計算檢驗數(shù)的工作十分繁重算檢驗數(shù)的工作十分繁重設平衡運輸問題為設平衡運輸問題為minjjiijxcZ11minnjmixnjbxmiaxijmijijnjiij, 2 , 1, 2 , 1, 0, 2 , 1, 2 , 111；，設前設前m個約束對應的對偶變量為個約束對應的對偶變量為ui,i=1,2,m，后，后n個約束個約束對應的對偶變量為對應的對偶變量為vj,j=1,2,n則運輸問題的對偶問題是則運輸問題的對偶問題是minjj

21、jiivbuaw11maxnjmivunjmiCvujiijji, 2 , 1;, 2 , 1, 2 , 1;, 2 , 1,無約束minjjjiivbuaw11maxnjmivunjmiCvujiijji, 2 , 1;, 2 , 1, 2 , 1;, 2 , 1,無約束線性規(guī)劃問題變量線性規(guī)劃問題變量xj的檢驗數(shù)可表示為的檢驗數(shù)可表示為 j = cj CBB-1Pj = cj YPj由此，運輸問題某變量由此，運輸問題某變量xij的檢驗數(shù)如下：的檢驗數(shù)如下：= cij (u1, u2, ， um, v1, v2, , vn) Pij ij = cij -YPij= cij (ui +vj)對

22、所有基變量對所有基變量 ij =0由于運輸表中每行每列都含有基變量，因此上述由于運輸表中每行每列都含有基變量，因此上述方程組含有方程組含有(m+n)個對偶變量，個對偶變量，顯然，這個方程組有顯然，這個方程組有(m+n-1)個方程個方程故對這組基變量可寫出方程組故對這組基變量可寫出方程組 ssss22221111jijijijijiji CvuCvuCvu故方程組的解不唯一故方程組的解不唯一方程組的解稱為方程組的解稱為位勢位勢ui 、vj分別稱為第分別稱為第i 行和第行和第j列的位勢列的位勢利用利用 ij = cij (ui +vj)可以求出所有非基變量的檢驗數(shù)可以求出所有非基變量的檢驗數(shù)【例例

23、3.8】用位勢法求用位勢法求3.7給出的初始基本可行解的檢驗數(shù)。給出的初始基本可行解的檢驗數(shù)。【解解】第一步求位勢第一步求位勢u1、u2、u3及及v1、v2、v3、v4。 101030201060X20507010 60 40 30333331132442233213311221CvuCvuCvuCvuCvuCvu 921583331342323121vuvuvuvuvuvu令令u1=0得到位勢的解為得到位勢的解為130321uuu48314321vvvv938470765150210922010 6040 30再由公式再由公式 求出檢驗數(shù)，其中求出檢驗數(shù)，其中Cij是非是非基變量對應的運價。

24、基變量對應的運價。)(jiijjivuC 計算結果與例計算結果與例3.7結果相同。結果相同。8)10(9)(111111 vuC 4 8 3 1 13-02 9 10 21 5 6 74 8 3 9 101030201060X20507010 60 40 303)41(2)( 6)31(10)( 6)33(6)(9)13(7)( 0)40(4)(433434233232222222122121414114 vuCvuCvuCvuCvuC 三、調整運量三、調整運量當某個檢驗數(shù)小于零時，基可行解不是最優(yōu)解，總運當某個檢驗數(shù)小于零時，基可行解不是最優(yōu)解，總運費還可以下降，這時需調整運輸量，改進原運輸

25、方案，費還可以下降，這時需調整運輸量，改進原運輸方案，使總運費減少，改進運輸方案的步驟是：使總運費減少，改進運輸方案的步驟是：第一步：確定入基變量第一步：確定入基變量 入基入基，ikjijijikix0min)( 第二步：確定出基變量第二步：確定出基變量 在入基變量在入基變量xik的閉回路中，標的閉回路中，標有負號的最小運量作為調整量有負號的最小運量作為調整量，對應的基變量為出對應的基變量為出基變量，并打上基變量，并打上“”以示作為非基變量。以示作為非基變量。第三步：調整運量第三步：調整運量 在進基變量的閉回路中標有正號的在進基變量的閉回路中標有正號的變量加上調整量變量加上調整量，標有負號的變

26、量減去調整量標有負號的變量減去調整量，其余其余變量不變，得到一組新的基可行解，然后求所有非基變變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗數(shù)重新檢驗。量的檢驗數(shù)重新檢驗。 BjAiB1B2B3B4aiA1589270A2364780A3101214540bj45655030190【例例3.9】求下列運輸問題的最優(yōu)解求下列運輸問題的最優(yōu)解表表3-12【解解】 用最小元素法求得初始基本可行解如表用最小元素法求得初始基本可行解如表3-12304535402515求非基變量的求非基變量的檢驗數(shù)檢驗數(shù),用閉回用閉回路法得：路法得： BjAiB1B2B3B4ai236

27、47804535A31012145402515bj45655030190-48-1214435 12233323211111 CCCCCC -1141289 3323211313 CCCC 44-14126 3233322222 CCCC 112-8121447 14123233322424 CCCCCC -3341410 2123333131 CCCC -112825 3212143434 CCCC 因為有因為有4個檢個檢驗數(shù)小于零，驗數(shù)小于零，所以這組基本所以這組基本可行解不是最可行解不是最優(yōu)解。優(yōu)解。 4,min343113,1111 對應的非基變量對應的非基變量x11進基進基.x11的

28、閉回路是的閉回路是212333321211,xxxxxxx33最小，最小，x33是出基變量，調整量是出基變量，調整量=151545,15,40min,min2133,12xxx BjAiB1B2B3B4aiA1589270-4 40-1 30A2364780454 3511 A3101214540-3 2515-1 bj45655030190 BjAiB1B2B3B4ai23647804535A31012145402515bj45655030190在在x11的閉回路上的閉回路上x11、x32、x23分別加上分別加上15，x12、x33、x21分別減分別減去去15，并且在，并且在x33處打上記號處打上記號“”作為基變量，其余變量不變，作為基變量，其余變量不變，調整后得到一組新的基可行解：調整后得到一組新的基可行解：1525405030 BjAiB1B2B3B4aiA1589270152530A23647803050A310121454040bj45655030190 13=3， 2