北邮运筹学ch3-3 表上作业法ppt课件

1、3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 1 of 36njijijmixcz11minnjmixnjbxmiaxijjmiijnjiij, 1;, 1,0, 1, 111设平衡运输问题的数学模型为：设平衡运输问题的数学模型为：3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 2 of 36表上作业法也称为运输单纯形法，是直接在运价表上求最优解的一种方法，它的步骤是： 第一步：求初始基行可

2、行解初始调运方案，常用的方法有最小元素法、元素差额法Vogel近似法、左上角法。 第二步：求检验数并判别能否得到最优解，常用求检验的方法有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最优解，假设存在检验数lk0，阐明还没有到达最优，转第三步。 第三步：调整运量，即换基，选一个变量出基，对原运量进展调整得到新的基可行解，转入第二步。3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 3 of 363.3.1初始基可行解初始基可行解1.最小元素法 最小元素法的思想是就近优先运送，即最小运价C

3、ij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。jiijbax,min3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 4 of 36【例3】求表36所示的运输问题的初始基可行解。表36 销 地产地B1B2B3产量A186730A243545A374825销 量6030101003.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page

4、 5 of 36B1B2B3可发量A186730A243545A374825未满足量6030101000 00【解】301510252015452020000产地销地3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 6 of 36【例4】求表37给出的运输问题的初始根本可行解。 B1B2B3B4aiA1311447A277384A3121069bj365620表373.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Prob

5、lem Page 7 of 36【解】 B1B2B3B4aiA1311447A277384A3121069bj365620360416在x12、x22、x33、x34中任选一个变量作为基变量，例如选x12表表383.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 8 of 36初始根本可行解可用以下矩阵表示634610表38中，标有符号 的变量恰好是3+41=6个且不包含闭回路，是一组基变量，其他标有符号的变量是非基变量， 323123141312,xxxxxx3.3 表上作业法表上作业法Tran

6、sportation Simplex MethodCh3 Transportation Problem Page 9 of 362运费差额法运费差额法Vogel近似法最小元素法只思索了部分运输费用近似法最小元素法只思索了部分运输费用最小，对整个产销系统的总运输费用来说能够离最优值较远。有时最小，对整个产销系统的总运输费用来说能够离最优值较远。有时为了节省某一处的运费，而在其它处能够运费很大。运费差额法对为了节省某一处的运费，而在其它处能够运费很大。运费差额法对最小元素法进展了改良，思索到产地到销地的最小运价和次小运价最小元素法进展了改良，思索到产地到销地的最小运价和次小运价之间的差额，假设差额

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 表上作业法表上作业法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对应行或列的最小运价处优先调运； 第三步：这时必有一列或一行调运终了，在剩下的运价中再求最大差额，进展第二次调运，依次进展下去，直到最后全部调运终了，就得到一个初始调运方案。 用运费差额法求得的根本可行解更接近最优解，所以也称为近似方案。3.3 表上作业法表上作业法Tra

9、nsportation Simplex MethodCh3 Transportation Problem Page 11 of 36【例5】用运费差额法求表39运输问题的初始根本可行解。 B1B2B3B4aiA15891215A2672425A311013820bj201052560表表393.3 表上作业法表上作业法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 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 13 of 36 销地产地B1B2B3B4aiuiA1 5 8 9 1215A2 1 7 2 425A36 10 13 820bj201052560 vj 54143322003.3 表上作业法表上作业法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 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 15 of 36根本可行解为205205100X总运费Z=108+201+52+208=270。求运输问题的初始方案还有很多方法，如左上角法、右上角法等。常用的方法是Vogel近似法、最小元素法。3.3 表上作业法表上作业法T

12、ransportation Simplex MethodCh3 Transportation Problem Page 16 of 363.3.2求检验数求检验数求出一组基可行解后，判别能否为最优解，依然是用检验数来判别，求出一组基可行解后，判别能否为最优解，依然是用检验数来判别，记记xij的检验数为的检验数为ij由第一章知，求最小值的运输问题的最优判别准由第一章知，求最小值的运输问题的最优判别准那么是：那么是：一切非基变量的检验数都非负，那么运输方案最优即为最优解。一切非基变量的检验数都非负，那么运输方案最优即为最优解。求检验数的方法有两种，闭回路法和位势法。1闭回路法求检验数闭回路法求检验

13、数 求某一非基变量的检验数的方法是：在根本求某一非基变量的检验数的方法是：在根本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开场，分别在顶点上交替标上代数符号条闭回路，由起点开场，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。变量的检验数。3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 17

14、of 36【解】用最小元素法得到以下一组根本可行解【例6】求以下运输问题的一个初始根本可行解及其检验数。矩阵中的元素为运价Cij ，矩阵右边的元素为产量ai ，下方的元素为销量bj 。304060102050702910215674839101030201060X20507010 60 40 303.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 18 of 36矩阵中打“的位置是非基变量，其他是基变量，这里只求非基变量的检验数。求11，先找出x11的闭回路 ，对应的运价为再用正负号分别交替乘以运

15、价有直接求代数和得31331311,xxxx31331311,CCCC31331311,CCCC829893133131111CCCC3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 19 of 36同理可求出其它非基变量的检验数：3951269831063856929570851433232434343313123232121323222231332321211323244114CCCCCCCCCCCCCCCCCCCC这里340，阐明这组根本可行解不是最优解。只需求得的基变量是正确的且数目为m

16、+n1，那么某个非基变量的闭回路存在且独一，因此检验数独一。3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 20 of 362位势法求检验位势法求检验 位势法求检验数是根据对偶实际推导出来的一种位势法求检验数是根据对偶实际推导出来的一种方法。方法。设平衡运输问题为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 表上作业法表上作业法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的检验数是对偶问题的松弛变量ij当i，j 时ij=0，因此有IIjivuCIjiCvujiijjiijii).(),(（解上面第一个方

18、程，将ui、vj代入第二个方程求出ij。3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 22 of 36【例7】用位势法求例7给出的初始根本可行解的检验数。【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。 101030201060X20507010 60 40 30333331132442233213311221CvuCvuCvuCvuCvuCvu 921583331342323121vuvuvuvuvuvu令u1=0得到位势的解为130321uuu48314321vvvv3.3

19、表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 23 of 36再由公式 求出检验数，其中Cij是非基变量对应的运价。)(jiijjivuC3)41 (2)(6)31 (10)(6)33(6)(9) 13(7)(0)40(4)(8) 10(9)(433434233232222222122121411414111111vuCuuCvuCvvCvuCvuC计算结果与例7结果一样。3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Pr

20、oblem Page 24 of 36【例8】求下表所示运输方案的检验数。 销地产地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 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 25 of 363.3.3调整运量前面讲过

21、，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改良原运输方案，使总运输减少，改良运输方案的步骤是：第一步：确定进基变量；进基，ikjijijikix0min)(第二步：确定出基变量，在进基变量xik的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“以示作为非基变量。第三步：调整运量。在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其他变量不变，得到一组新的基可行解，然后求一切非基变量的检验数重新检验。3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transporta

22、tion Problem Page 26 of 36【例9】求下表所示的运输问题的最优解。表36 B1B2B3产量A186730A243545A374825销 量603010100产地销地3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 27 of 36B1B2B3产量A186730A243545A374825销量603010100【解】3015102520-1前面已得到此题的初始可行解，如今接着做下去。前面已得到此题的初始可行解，如今接着做下去。用闭回路法求检验数如下：用闭回路法求检验数如下：

23、产地销地3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 28 of 36 B1B2B3产量A186730A243545A374825销量60301010030151020-1225产地销地【解】前面已得到此题的初始可行解，如今接着做下去。前面已得到此题的初始可行解，如今接着做下去。用闭回路法求检验数如下：用闭回路法求检验数如下：3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 29 of 36B

24、1B2B3产量A186730A243545A374825销量60301010030151020-1225-2产地销地【解】前面已得到此题的初始可行解，如今接着做下去。前面已得到此题的初始可行解，如今接着做下去。用闭回路法求检验数如下：用闭回路法求检验数如下：3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 30 of 36B1B2B3产量A186730A243545A374825销量60301010030151020-1225-2产地销地2【解】前面已得到此题的初始可行解，如今接着做下去。前面已

25、得到此题的初始可行解，如今接着做下去。用闭回路法求检验数如下：用闭回路法求检验数如下：3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 31 of 36B1B2B3A1867A2435A374830151020-1225-2产地销地由于有个负检验数，所以这组根本可行解不是最优解。取非基变量x32进基,用闭回路法调整如下闭回路如上图，标负号的运量是：x31=25、x22 =30，取其最小值25作为调整量，在闭回路上x21、x32分别加上25，x31、x22分别减去25，调整后得到一组新的基可行解。25 40 5 3.3 表上作业法表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 32 of 36B1B2B3产量A186730A243545A374825销量603010100540102520-1 2 2再检验表中括号中