第7章 运输问题ppt课件.pptVIP

§4*　运输问题的表上作业法 2.最小元素法 西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=min(4,3)=3，把A2的产量改为1，B1的销量改为0，并把B1列划去。在剩下的3×3矩阵中再找最小运价，同理可得其他的基本可行解。 一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。 * 销地 产地 B1 B2 B3 B4 产量 A1 4 3 7 3 0 A2 3 1 4 1 0 A3 6 3 9 3 0 销量 3 0 6 0 5 4 0 6 3 0 20 20 3 11 3 10 8 5 10 2 9 4 7 1 §4*　运输问题的表上作业法 在求初始基本可行解时要注意的两个问题： 1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。 2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。 * §4*　运输问题的表上作业法 二、最优解的判别 1.闭回路法 所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。 所谓闭回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。 * §4*　运输问题的表上作业法 从非基变量x11出发，找到一个闭回路如上表所示。回路有四个顶点，除x11外，其余都为基变量。现在把x11的调运量从零增加为1吨，运费也增加了3百元，为了使A1产量平衡，x13必须减少1吨，运费减少3百元。为了B3的销量平衡，x23必须增加1吨，运费增加2百元。同理把x21减少1吨，运费减少1百元。调整后，总运费增加了3-3+2-1=1（百元）。说明如果让x11为基变量，运费就会增加，把运费增加值1作为x11的检验数，为了区别调整量，我们把1加圈。 用同样的方法可以找出所有空格（即非基变量）的检验数。 * 销地 产地 B1 B2 B3 B4 产量 A1 1 4 7 A2 3 1 4 A3 9 销量 3 6 5 6 3 11 3 10 8 5 10 2 9 4 7 1 §4*　运输问题的表上作业法 2.位势法 所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋 予一个数值vj，它们的数值是由基变量xij的检验数 所决 定的，则非基变量xij的检验数就可以用公式 求出。 我们先给u1赋个任意数