北郵運籌學ch3-3 表上作業(yè)法ppt課件

1、3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 1 of 36njijijmixcz11minnjmixnjbxmiaxijjmiijnjiij, 1;, 1,0, 1, 111設平衡運輸問題的數(shù)學模型為：設平衡運輸問題的數(shù)學模型為：3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 2 of 36表上作業(yè)法也稱為運輸單純形法，是直接在運價表上求最優(yōu)解的一種方法，它的步驟是： 第一步：求初始基行可

2、行解初始調運方案，常用的方法有最小元素法、元素差額法Vogel近似法、左上角法。 第二步：求檢驗數(shù)并判別能否得到最優(yōu)解，常用求檢驗的方法有閉回路法和位勢法，當非基變量的檢驗數(shù)ij全都非負時得到最優(yōu)解，假設存在檢驗數(shù)lk0，闡明還沒有到達最優(yōu)，轉第三步。 第三步：調整運量，即換基，選一個變量出基，對原運量進展調整得到新的基可行解，轉入第二步。3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 3 of 363.3.1初始基可行解初始基可行解1.最小元素法 最小元素法的思想是就近優(yōu)先運送，即最小運價C

3、ij對應的變量xij優(yōu)先賦值然后再在剩下的運價中取最小運價對應的變量賦值并滿足約束，依次下去，直到最后一個初始基可行解。jiijbax,min3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 4 of 36【例3】求表36所示的運輸問題的初始基可行解。表36 銷 地產地B1B2B3產量A186730A243545A374825銷 量6030101003.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page

4、 5 of 36B1B2B3可發(fā)量A186730A243545A374825未滿足量6030101000 00【解】301510252015452020000產地銷地3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 6 of 36【例4】求表37給出的運輸問題的初始根本可行解。 B1B2B3B4aiA1311447A277384A3121069bj365620表373.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Prob

5、lem Page 7 of 36【解】 B1B2B3B4aiA1311447A277384A3121069bj365620360416在x12、x22、x33、x34中任選一個變量作為基變量，例如選x12表表383.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 8 of 36初始根本可行解可用以下矩陣表示634610表38中，標有符號 的變量恰好是3+41=6個且不包含閉回路，是一組基變量，其他標有符號的變量是非基變量， 323123141312,xxxxxx3.3 表上作業(yè)法表上作業(yè)法Tran

6、sportation Simplex MethodCh3 Transportation Problem Page 9 of 362運費差額法運費差額法Vogel近似法最小元素法只思索了部分運輸費用近似法最小元素法只思索了部分運輸費用最小，對整個產銷系統(tǒng)的總運輸費用來說能夠離最優(yōu)值較遠。有時最小，對整個產銷系統(tǒng)的總運輸費用來說能夠離最優(yōu)值較遠。有時為了節(jié)省某一處的運費，而在其它處能夠運費很大。運費差額法對為了節(jié)省某一處的運費，而在其它處能夠運費很大。運費差額法對最小元素法進展了改良，思索到產地到銷地的最小運價和次小運價最小元素法進展了改良，思索到產地到銷地的最小運價和次小運價之間的差額，假設差額

7、很大，就選最小運價先調運，否那么會添加之間的差額，假設差額很大，就選最小運價先調運，否那么會添加總運費。例如下面兩種運輸方案，總運費。例如下面兩種運輸方案，2010125815510C2010125851510C 15 15 15 15前一種按最小元素法求得，總運費是Z1=108+52+151=105，后一種方案思索到C11與C21之間的差額是82=6，假設不先調運x21，到后來就有能夠x110，這樣會使總運費添加較大，從而先調運x21，再是x22，其次是x12這時總運費Z2=105+152+51=85Z1。3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex Method

8、Ch3 Transportation Problem Page 10 of 36 基于以上想法，運費差額法求初始根本可行解的步驟是： 第一步：求出每行次小運價與最小運價之差，記為ui，i=1,2,m；同時求出每列次小運價與最小運價之差，記為vj，j=1，2，n；第二步：找出一切行、列差額的最大值，即L=maxui，vi，差額L對應行或列的最小運價處優(yōu)先調運； 第三步：這時必有一列或一行調運終了，在剩下的運價中再求最大差額，進展第二次調運，依次進展下去，直到最后全部調運終了，就得到一個初始調運方案。 用運費差額法求得的根本可行解更接近最優(yōu)解，所以也稱為近似方案。3.3 表上作業(yè)法表上作業(yè)法Tra

9、nsportation Simplex MethodCh3 Transportation Problem Page 11 of 36【例5】用運費差額法求表39運輸問題的初始根本可行解。 B1B2B3B4aiA15891215A2672425A311013820bj201052560表表393.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 12 of 36 銷地產地B1B2B3B4aiuiA1 5 8 9 12153A2 1 7 2 4251A36 10 13 8202bj201052560 v

10、j4174 【解】 求行差額 ui, i=1,2,3及列差額vj,j=1,2,3,4.計算公式為 ui= i行次小運價i行最小運價 vj= j列次小運價j例最小運價53.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 13 of 36 銷地產地B1B2B3B4aiuiA1 5 8 9 1215A2 1 7 2 425A36 10 13 820bj201052560 vj 54143322003.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transpo

11、rtation Problem Page 14 of 36 銷地產地B1B2B3B4aiuiA1 5 8 9 1215A2 1 7 2 425A36 10 13 820bj201052560 vj 52002442201053.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 15 of 36根本可行解為205205100X總運費Z=108+201+52+208=270。求運輸問題的初始方案還有很多方法，如左上角法、右上角法等。常用的方法是Vogel近似法、最小元素法。3.3 表上作業(yè)法表上作業(yè)法T

12、ransportation Simplex MethodCh3 Transportation Problem Page 16 of 363.3.2求檢驗數(shù)求檢驗數(shù)求出一組基可行解后，判別能否為最優(yōu)解，依然是用檢驗數(shù)來判別，求出一組基可行解后，判別能否為最優(yōu)解，依然是用檢驗數(shù)來判別，記記xij的檢驗數(shù)為的檢驗數(shù)為ij由第一章知，求最小值的運輸問題的最優(yōu)判別準由第一章知，求最小值的運輸問題的最優(yōu)判別準那么是：那么是：一切非基變量的檢驗數(shù)都非負，那么運輸方案最優(yōu)即為最優(yōu)解。一切非基變量的檢驗數(shù)都非負，那么運輸方案最優(yōu)即為最優(yōu)解。求檢驗數(shù)的方法有兩種，閉回路法和位勢法。1閉回路法求檢驗數(shù)閉回路法求檢驗

13、數(shù) 求某一非基變量的檢驗數(shù)的方法是：在根本求某一非基變量的檢驗數(shù)的方法是：在根本可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開場，分別在頂點上交替標上代數(shù)符號條閉回路，由起點開場，分別在頂點上交替標上代數(shù)符號+、-、+、-、，以這些符號分別乘以相應的運價，其代數(shù)和就是這個非基，以這些符號分別乘以相應的運價，其代數(shù)和就是這個非基變量的檢驗數(shù)。變量的檢驗數(shù)。3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 17

14、of 36【解】用最小元素法得到以下一組根本可行解【例6】求以下運輸問題的一個初始根本可行解及其檢驗數(shù)。矩陣中的元素為運價Cij ，矩陣右邊的元素為產量ai ，下方的元素為銷量bj 。304060102050702910215674839101030201060X20507010 60 40 303.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 18 of 36矩陣中打“的位置是非基變量，其他是基變量，這里只求非基變量的檢驗數(shù)。求11，先找出x11的閉回路 ，對應的運價為再用正負號分別交替乘以運

15、價有直接求代數(shù)和得31331311,xxxx31331311,CCCC31331311,CCCC829893133131111CCCC3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 19 of 36同理可求出其它非基變量的檢驗數(shù)：3951269831063856929570851433232434343313123232121323222231332321211323244114CCCCCCCCCCCCCCCCCCCC這里340，闡明這組根本可行解不是最優(yōu)解。只需求得的基變量是正確的且數(shù)目為m

16、+n1，那么某個非基變量的閉回路存在且獨一，因此檢驗數(shù)獨一。3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 20 of 362位勢法求檢驗位勢法求檢驗 位勢法求檢驗數(shù)是根據(jù)對偶實際推導出來的一種位勢法求檢驗數(shù)是根據(jù)對偶實際推導出來的一種方法。方法。設平衡運輸問題為minjjiijxcZ11minnjmixnjbxmiaxijmijijnjiij, 2 , 1, 2 , 1, 0, 2 , 1, 2 , 111；，設前m個約束對應的對偶變量為ui,i=1,2,m，后n個約束對應的對偶變量為vj,

17、j=1,2,n那么運輸問題的對偶問題是3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 21 of 36minjjjiiubuaw11maxnjmivunjmiCvuiiijii, 2 , 1;, 2 , 1, 2 , 1;, 2 , 1,無約束參與松馳變量ij將約束化為等式ui+vj+ij=cij記原問題基變量XB的下標集合為I，由第二章對偶性質知，原問題xij的檢驗數(shù)是對偶問題的松弛變量ij當i，j 時ij=0，因此有IIjivuCIjiCvujiijjiijii).(),(（解上面第一個方

18、程，將ui、vj代入第二個方程求出ij。3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 22 of 36【例7】用位勢法求例7給出的初始根本可行解的檢驗數(shù)?！窘狻康谝徊角笪粍輚1、u2、u3及v1、v2、v3、v4。 101030201060X20507010 60 40 30333331132442233213311221CvuCvuCvuCvuCvuCvu 921583331342323121vuvuvuvuvuvu令u1=0得到位勢的解為130321uuu48314321vvvv3.3

19、表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 23 of 36再由公式 求出檢驗數(shù)，其中Cij是非基變量對應的運價。)(jiijjivuC3)41 (2)(6)31 (10)(6)33(6)(9) 13(7)(0)40(4)(8) 10(9)(433434233232222222122121411414111111vuCuuCvuCvvCvuCvuC計算結果與例7結果一樣。3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Pr

20、oblem Page 24 of 36【例8】求下表所示運輸方案的檢驗數(shù)。 銷地產地B1B2B3B4aiuiA1 5 8 9 1215A2 1 7 2 425A36 10 13 820bj201052560 vj 5200586120-4-420105位勢法的表上方式位勢法的表上方式9 -0-637 -(-4)-834 -(-4)-12-46 -(-4)-5510 -(-4)-8613 -(-4)-6113.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 25 of 363.3.3調整運量前面講過

21、，當某個檢驗數(shù)小于零時，基可行解不是最優(yōu)解，總運費還可以下降，這時需調整運輸量，改良原運輸方案，使總運輸減少，改良運輸方案的步驟是：第一步：確定進基變量；進基，ikjijijikix0min)(第二步：確定出基變量，在進基變量xik的閉回路中，標有負號的最小運量作為調整量，對應的基變量為出基變量，并打上“以示作為非基變量。第三步：調整運量。在進基變量的閉回路中標有正號的變量加上調整量，標有負號的變量減去調整量，其他變量不變，得到一組新的基可行解，然后求一切非基變量的檢驗數(shù)重新檢驗。3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transporta

22、tion Problem Page 26 of 36【例9】求下表所示的運輸問題的最優(yōu)解。表36 B1B2B3產量A186730A243545A374825銷 量603010100產地銷地3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 27 of 36B1B2B3產量A186730A243545A374825銷量603010100【解】3015102520-1前面已得到此題的初始可行解，如今接著做下去。前面已得到此題的初始可行解，如今接著做下去。用閉回路法求檢驗數(shù)如下：用閉回路法求檢驗數(shù)如下：

23、產地銷地3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 28 of 36 B1B2B3產量A186730A243545A374825銷量60301010030151020-1225產地銷地【解】前面已得到此題的初始可行解，如今接著做下去。前面已得到此題的初始可行解，如今接著做下去。用閉回路法求檢驗數(shù)如下：用閉回路法求檢驗數(shù)如下：3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 29 of 36B

24、1B2B3產量A186730A243545A374825銷量60301010030151020-1225-2產地銷地【解】前面已得到此題的初始可行解，如今接著做下去。前面已得到此題的初始可行解，如今接著做下去。用閉回路法求檢驗數(shù)如下：用閉回路法求檢驗數(shù)如下：3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 30 of 36B1B2B3產量A186730A243545A374825銷量60301010030151020-1225-2產地銷地2【解】前面已得到此題的初始可行解，如今接著做下去。前面已

25、得到此題的初始可行解，如今接著做下去。用閉回路法求檢驗數(shù)如下：用閉回路法求檢驗數(shù)如下：3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 31 of 36B1B2B3A1867A2435A374830151020-1225-2產地銷地由于有個負檢驗數(shù)，所以這組根本可行解不是最優(yōu)解。取非基變量x32進基,用閉回路法調整如下閉回路如上圖，標負號的運量是：x31=25、x22 =30，取其最小值25作為調整量，在閉回路上x21、x32分別加上25，x31、x22分別減去25，調整后得到一組新的基可行解。25 40 5 3.3 表上作業(yè)法表上作業(yè)法Transportation Simplex MethodCh3 Transportation Problem Page 32 of 36B1B2B3產量A186730A243545A374825銷量603010100540102520-1 2 2再檢驗表中括號中