表上作业法PPT课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,Page,*,表上作业法,表上作业法的计算步骤：,分析实际问题列出产销平衡表及单位运价表,确定初始调运方案（最小元素法或Vogel法）,求检验数（位势法）,所有检验数0,找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案,得到最优方案，算出总运价,表上作业法,表上作业法是一种求解运输问题的特殊方法，其,实质是单纯形法。,步骤,描述,方法,第一步,求初始基行可行解（初始调运方案）,最小元素法、元素差额法、,第二步,求检验数并判断是否得到最优解当非基变量的检验数,ij,全都非负时得到最优解，若存在检验数,ij,0，说明还没有达到最优，转第三步。,闭回路法和位势法,第三步,调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步,表上作业法,例3.2 某运输资料如下表所示：,单位 销地,运价,产地,产量,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,问：应如何调运可使总运输费用最小？,表上作业法,解：第1步 求初始方案,方法1：最小元素法,基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,B,1,B,2,B,3,B,4,产量,A,1,7,A,2,4,A,3,9,销量,3,6,5,6,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,表上作业法,总的运输费(31)+(64)+(43)+(12)+(310)+(35)=86元,元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。,8,5,10,2,1,20,15,15,15,5,10,总运费是,z,=108+52+151=105,最小元素法：,表上作业法,8,5,10,2,1,20,15,15,5,15,10,总运费,z,=105+152+51=85,后一种方案考虑到,C,11,与,C,21,之间的差额是82=6，如果不先调运,x,21,，到后来就有可能,x,11,0，这样会使总运费增加较大，从而先调运,x,21,，再是,x,22,，其次是,x,12,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,表上作业法,方法2：Vogel法,1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。,B,1,B,2,B,3,B,4,产量,行差额,A,1,7,7,A,2,4,1,A,3,9,1,销量,3,6,5,6,列差额,2,5,1,3,3,11,3,10,1,9,2,7,4,10,5,8,表上作业法,2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。,重复1)和2)，直到找出初始解为至。,B,1,B,2,B,3,B,4,产量,行差额,A,1,7,7,A,2,4,1,A,3,9,1,销量,3,6,5,6,列差额,2,5,1,3,3,11,3,10,1,9,2,7,4,10,5,8,5,表上作业法,单位 销地,运价,产地,产量,行差额,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,列差额,7,1,1,3,5,2,1,5,表上作业法,单位 销地,运价,产地,产量,行差额,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,列差额,7,1,3,5,2,7,5,3,表上作业法,单位 销地,运价,产地,产量,行差额,3,11,3,10,7,1,9,2,8,4,7,4,10,5,9,销量,3,6,5,6,列差额,1,1,3,5,1,5,3,6,3,1,2,该方案的总运费:,(13)(46)(35)(210)(18)(35)85元,表上作业法,第2步 最优解的判别（检验数的求法）,求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记,x,ij,的检验数为,ij,由第一章知，求最小值的运输问题的最优判别准则是：,所有非基变量的检验数都非负，则运输方案最优,求检验数的方法有两种：,闭回路法,位势法（,）,表上作业法,用位势法对初始方案进行最优性检验：,1）由,ij,=C,ij,-（,U,i,+V,j,）计算位势U,i,，V,j,，因对基变量而言有,ij,=0，即C,ij,-（,U,i,+V,j,）=0，令U,1,=0,2）再由,ij,=C,ij,-（,U,i,+V,j,）计算非基变量的检验数,ij,B,1,B,2,B,3,B,4,U,i,A,1,A,2,A,3,Vj,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,0,-1,-5,3,10,2,9,（1）,（2）,（1）,（-1）,（10）,（12）,当存在非基变量的检验数,kl,0，说明现行方案为最优方案，否则目标成本还可以进一步减小。,表上作业法,当存在非基变量的检验数,kl,0 且,kl,=min,ij,时，令X,kl,进基。从表中知可选X,24,进基。,第3步 确定换入基的变量,第4步 确定换出基的变量,以进基变量,x,ik,为起点的闭回路中，标有负号的最小运量作为调整量,，,对应的基变量为出基变量，并打上“”以示换出作为非基变量。,表上作业法,B,1,B,2,B,3,B,4,U,i,A,1,A,2,A,3,Vj,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,(),(),(),(),调整步骤为：,在进基变量的闭回路中标有正号的变量加上调整量,，标有负号的变量减去调整量,，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。,1,2,5,表上作业法,当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：,Z=,(13)(46)(35)(210)(18)(35)85元,B,1,B,2,B,3,B,4,U,i,A,1,A,2,A,3,Vj,3,11,3,10,1,9,2,7,4,10,5,8,5,3,6,3,1,2,0,-2,-5,3,10,3,9,（0）,（2）,（2）,（1）,（12）,（9）,运输问题的应用,3.生产与储存问题,例3.5 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。,季度,生产能力/台,单位成本/万元,25,10.8,35,11.1,30,11,10,11.3,运输问题的应用,解：,设,x,ij,为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：,交货：,x,11,=10,生产：,x,11,+,x,12,+,x,13,+,x,14,25,x,12,+,x,22,=15,x,22,+,x,23,+,x,24,35,x,13,+,x,23,+,x,33,=25,x,33,+,x,34,30,x,14,+,x,24,+,x,34,+,x,44,=20,x,44,10,把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；设cij是第i季度生产的第j季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：,运输问题的应用,解：,设,x,ij,为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：,交货：,x,11,=10,生产：,x,11,+,x,12,+,x,13,+,x,14,25,x,12,+,x,22,=15,x,22,+,x,23,+,x,24,35,x,13,+,x,23,+,x,33,=25,x,33,+,x,34,30,x,14,+,x,24,+,x,34,+,x,44,=20,x,44,10,把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；设cij是第i季度生产的第j季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：,运输问题的应用,该问题的数学模型：,Min f=10.8,x,11,+10.95,x,12,+11.1,x,13,+11.25,x,14,+11.1,x,22,+11.25,x,23,+11.4,x,24,+11.0,x,33,+11.15,x,34,+11.3,x,44,j,i,D,产量,10.8,10.95,11.1,11.25,0,25,M,11.10,11.25,11.40,0,35,M,M,11.00,11.15,0,30,M,M,M,11.30,0,10,销量,10,15,25,20,30,100,100,运输问题的应用,j,i,D,产量,10,15,0,25,0,5,30,35,25,5,30,10,10,销量,10,15,25,20,30,100,100,最优生产决策如下表，最小费用z773万元。,