管理运筹学 第七章 运输问题之表上作业法.ppt

第七章运输问题之表上作业法,一、运输问题模型及其求解思路二、确定初始基本可行解三、最优性检验四、方案调整五、几种特殊情况,一、运输问题模型及其求解思路,1、问题的提出：某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3。各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。问：应如何调运可使总运输费用最小？,一、运输问题模型及其求解思路,一、运输问题模型及其求解思路,2、产销平衡运输问题模型的特点从模型的建立可知：列数为2（产地数）3（销地数）6；行数为2（产地数）+3（销地数）5；再观察模型的系数矩阵：,一、运输问题模型及其求解思路,前2行之和后3行之和,一、运输问题模型及其求解思路,对于产销平衡的运输问题，若产地为m个，销地为n个，则变量个数为mn个，线性无关的约束条件个数为m+n-1，故基本解中的基变量个数为m+n-1。,一、运输问题模型及其求解思路,3、运输问题求解思路表上作业法由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。,一、运输问题模型及其求解思路,我们关心的量均在运价表和运量表中，故将两表和为作业表：,一、运输问题模型及其求解思路,表上作业法的总体思路和单纯形法类似：,每个步骤都充分利用运输表的特点,一、运输问题模型及其求解思路,例：某食品公司下属的A1、A2、A3，3个厂生产方便食品，要运输到B1、B2、B3、B4，4个销售点，数据如下表，求最优运输方案。,二、确定初始基本可行解,1、西北（左上）角法每次找最西北角的元素，让其运输量尽可能的满足一个约束条件。,二、确定初始基本可行解,3,4,2,2,3,6,二、确定初始基本可行解,这样得到的初始基本可行解为：x11=3,x12=4,x22=2,x23=2,x33=3,x34=6，其余均为0。对应的总运费为：33+411+29+22+310+65135,二、确定初始基本可行解,2、最小元素法每次找到剩下的最小运价，让其对应的运输量尽可能的满足一个约束条件。,二、确定初始基本可行解,3,4,3,1,6,3,二、确定初始基本可行解,用最小元素法求出的初始基本可行解为：x21=3,x22=1,x13=4,x32=6,x34=3,x14=3,其余均为0。对应的总运费为：31+12+43+64+35+31086,二、确定初始基本可行解,为保证基变量的个数有m+n-1个，注意：1、每次填完数，只能划去一行或一列，只有最后一个格子例外。2、用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩下的空格中标上0。（退化的基本可行解）,二、确定初始基本可行解,3,5,3,0,6,3,二、确定初始基本可行解,3,4,0,1,6,3,三、最优性检验,检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。运输问题中目标函数值要求最小化，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则不是。下面介绍两种计算检验数的方法：,三、最优性检验,1、闭回路法闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，只有碰到基变量，才能向右或向左转90o(当然也可以不改变方向）继续前进。这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回路。,三、最优性检验,每一个非基变量都有唯一的闭回路,三、最优性检验,观察x24的闭回路：若让第一个顶点非基变量x24的取值变为1，为了保持产销平衡，其闭回路上的顶点运量都要调整，基数顶点+1，偶数顶点-1。上述调整使总的运输费用发生的变化为810+32-1，这就说明原方案还不是最优方案，需要进行调整。,三、最优性检验,若让x111，则总运费变化：33+211。,三、最优性检验,如果规定作为起始顶点的非基变量xij为第1个顶点，其闭回路上的其他顶点依次为第2个顶点、第3个顶点，那么就有该非基变量的检验数：ij=(闭回路上的奇数顶点运价之和)-(闭回路上的偶数顶点运价之和)最优标准：所有检验数0,三、最优性检验,检验数计算如下表：,（1）,（2）,（1）,（-1）,（10）,（12）,三、最优性检验,2、位势法闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。位势法：设产地Ai对应的位势量为ui，销地Bj对应的位势量为vj，检验数ij=cijui-vj。,三、最优性检验,三、最优性检验,根据基变量xij的检验数ij=0，对应基变量的运价cij可以分解为ui和vj，即cij=ui+vj。因为位势量ui,vj的总数为m+n个，而限定方程只有m+n-1个（基变量个数），所以位势量（ui,vj）有无穷多组解，其中总有一个自由变量。故可以任意取一个位势量赋以定值，从而确定其它位势量的值，一般取u10。,三、最优性检验,10,3,9,2,vj,20,6,5,6,3,销量bj,-5,9,53,10,46,7,A3,-1,4,8,21,9,13,A2,0,7,103,34,11,3,A1,ui,产量ai,B4,B3,B2,B1,（1）,（2）,（1）,（-1）,（10）,（12）,检验数计算总结,1、闭回路法计算式：ij=(闭回路上的奇数顶点运价之和)-(闭回路上的偶数顶点运价之和)2、位势法计算式：ij=cij-uivj,四、方案调整,最小检验数原则，确定进基变量,最小偶点原则，确定出基变量和调整量,+1,-1,+1,-1,四、方案调整,得到新的基变量：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3。重新计算检验数。,（0）,（2）,（2）,（1）,（9）,（12）,四、方案调整,经过一次基变换，所有ij0，已得到最优解：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3，其它为0。最优值：f*=35+102+13+81+46+53=85,四、方案调整,闭回路调整法步骤：1、入基变量的确定：选负检验数中最小者rk，那么xrk作为进基变量；（使总运费尽快减少）2、出基变量的确定：在进基变量xrk的闭回路上，选取偶数顶点上调运量最小的值，将其对应的运量作为出基变量。（刚好有一个基变量出基，其它基变量都为正）,四、方案调整,即求=Minxij闭回路上的偶数顶点的xij=xpq。那么确定xpq为出基变量，为调整量；3、换基调整：对闭回路的奇数顶点运量调整为：xij+，对各偶数顶点运量调整为：xij-，特别xpq-=0，xpq变为非基变量。重复以上步骤，直到所有检验数均非负，即得到最优解。,练习题已知如下运价表，用表上作业法求解：,初始解对应目标值为33+41+42+44+8361,3,4,2,1,0,3,0,3,4,1,3,3,4,(3),(2),(3),(0),(-1),(-2),4,0,3,0,2,4,0,3,4,1,3,3,2,(3),(2),(3),(2),(1),(2),已达到最优，最优目标值为44+42+44+5355,五、运输问题的几种特殊情况,1、多个最优方案的情况：若最优表中有非基变量的检验数为0，则为多个最优方案的情况。这种情况下，可将检验数为0的非基变量作为进基变量，即可得到另一个最优方案。,五、运输问题的几种特殊情况,如上例中的最优方案就不唯一：,（0）,（2）,（2）,（1）,（9）,（12）,检验数为0者进基,最小偶点为出基变量和调整量,+2,-2,-2,+2,五、运输问题的几种特殊情况,得到另一个最优方案：x11=2,x13=5,x21=1,x24=3,x32=6,x34=3,其余xij=0；最优值仍然为f*=85