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

1、精选ppt第七章第七章 运输问题运输问题之表上作业法之表上作业法一、运输问题模型及其求解一、运输问题模型及其求解思路思路二、确定初始基本可行解二、确定初始基本可行解三、最优性检验三、最优性检验四、方案调整四、方案调整五、几种特殊情况五、几种特殊情况精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思路v1、问题的提出：、问题的提出：v某公司从两个产地某公司从两个产地A1、A2将物品运往三将物品运往三个销地个销地B1、B2、B3。v各产地的产量、各销地的销量和各产地各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。运往各销地每件物品的运费如下表所示。v问：应如何调

2、运可使总运输费用最小？问：应如何调运可使总运输费用最小？精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思路B1B2B3产量产量A1646200A2655300销量销量150150200精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思路v2、产销平衡运输问题模型的特点、产销平衡运输问题模型的特点v从模型的建立可知：从模型的建立可知：v列数为列数为2（产地数）（产地数）3（销地数）（销地数）6；v行数为行数为2（产地数）（产地数）+3（销地数）（销地数）5；v再观察模型的系数矩阵：再观察模型的系数矩阵：精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思

3、路 1 1 1 0 0 0 200 0 0 0 1 1 1 300 1 0 0 1 0 0 150 0 1 0 0 1 0 150 0 0 1 0 0 1 200前前2行之和后行之和后3行之和行之和精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思路v对于产销平衡的运输问题，若产地为对于产销平衡的运输问题，若产地为m个，销地为个，销地为n个，个，v则变量个数为则变量个数为mn个，线性无关的约束个，线性无关的约束条件个数为条件个数为m+n-1，v故基本解中的基变量个数为故基本解中的基变量个数为m+n-1。精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思路v3、运输问

4、题求解思路、运输问题求解思路表上作业法表上作业法v由于运输规划系数矩阵的特殊性，如果由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。则无法利用这些有利条件。v人们在分析运输规划系数矩阵特征的基人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的础上建立了针对运输问题的表上作业法表上作业法。精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思路B1B2B3产量产量A1 6 x11 4 x12 6 x13200A2 6 x21 5 x22 5 x23300销量销量150150200v我们关心的量均在运价

5、表和运量表中，我们关心的量均在运价表和运量表中，故将两表和为故将两表和为作业表作业表：精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思路v表上作业法的总体思路和单纯形法类似：表上作业法的总体思路和单纯形法类似：基本可行解基本可行解是否最优解是否最优解结束结束换基换基是是否否每个步骤每个步骤都充分利都充分利用运输表用运输表的特点的特点精选ppt一、运输问题模型及其求解思路一、运输问题模型及其求解思路v例：某食品公司下属的例：某食品公司下属的A1、A2、A3 ，3个厂个厂生产方便食品，要运输到生产方便食品，要运输到B1、B2、B3、B4 ，4个销售点，数据如下表，求最优运输方案。个

6、销售点，数据如下表，求最优运输方案。B1B2B3B4产量产量A13113107A219284A3741059销量销量365620精选ppt二、确定初始基本可行解二、确定初始基本可行解v1、西北（左上）角法、西北（左上）角法v每次找最西北角的元素，让其运输量尽每次找最西北角的元素，让其运输量尽可能的满足一个约束条件。可能的满足一个约束条件。精选ppt二、确定初始基本可行解二、确定初始基本可行解B1B2B3B4产量产量A13113107A219284A3741059销量销量365620342236精选ppt二、确定初始基本可行解二、确定初始基本可行解这样得到的初始基本可行解为：这样得到的初始基本可

7、行解为：x11=3, x12=4, x22=2, x23=2, x33=3, x34=6，其，其余均为余均为0。对应的总运费为：对应的总运费为：33+411+29+22+310+65135精选ppt二、确定初始基本可行解二、确定初始基本可行解v2、最小元素法、最小元素法v每次找到剩下的最小运价，让其对应的每次找到剩下的最小运价，让其对应的运输量尽可能的满足一个约束条件。运输量尽可能的满足一个约束条件。精选ppt二、确定初始基本可行解二、确定初始基本可行解B1B2B3B4产量产量A13113107A219284A3741059销量销量365620343163精选ppt二、确定初始基本可行解二、确

8、定初始基本可行解用最小元素法求出的初始基本可行解为：用最小元素法求出的初始基本可行解为： x21 =3, x22 =1, x13 =4, x32 =6, x34=3, x14 =3,其余均为其余均为0。对应的总运费为：对应的总运费为：31+12+43+64+35+31086精选ppt二、确定初始基本可行解二、确定初始基本可行解v为保证基变量的个数有为保证基变量的个数有m+n-1个，注意：个，注意：v1、每次填完数，只能划去一行或一列，只有、每次填完数，只能划去一行或一列，只有最后一个格子例外。最后一个格子例外。v2、用最小元素法时，可能会出现基变量个数、用最小元素法时，可能会出现基变量个数还差

9、两个以上但只剩下一行或一列的情况，还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩此时不能将剩下行或列按空格划掉，应在剩下的空格中标上下的空格中标上0。（退化的基本可行解）。（退化的基本可行解）精选ppt二、确定初始基本可行解二、确定初始基本可行解B1B2B3B4产量产量A13113108A219283A3741059销量销量365620353063精选ppt二、确定初始基本可行解二、确定初始基本可行解B1B2B3B4产量产量A13113104A219284A3741059销量销量365317340163精选ppt三、最优性检验三、最优性检验v检验数的意义：非基变量

10、增加一个单位，检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。使目标函数值增加的数量。v运输问题中目标函数值要求最小化，因运输问题中目标函数值要求最小化，因此，当所有的检验数都大于或等于零时此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则不是。该调运方案就是最优方案；否则不是。v下面介绍两种计算检验数的方法：下面介绍两种计算检验数的方法：精选ppt三、最优性检验三、最优性检验v1、闭回路法、闭回路法v闭回路：在已给出基本解的运输表上，从一闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，个非基变量出发，沿水平或竖直方向前进，只有碰到基变量，才

11、能向右或向左转只有碰到基变量，才能向右或向左转90o (当当然也可以不改变方向）继续前进。然也可以不改变方向）继续前进。v这样继续下去，总能回到出发的那个非基变这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回路。量，由此路线形成的封闭曲线，叫闭回路。精选ppt三、最优性检验三、最优性检验v每一个非基变量都有唯一的闭回路每一个非基变量都有唯一的闭回路B1B2B3B4产量产量A13113 410 37A21 392 184A374 6105 39销量销量365620精选ppt三、最优性检验三、最优性检验v观察观察x24的闭回路：的闭回路：v若让第一个顶点非基变量若让第一个顶

12、点非基变量x24的取值变为的取值变为1，为了保持产销平衡，其闭回路上的顶点运量为了保持产销平衡，其闭回路上的顶点运量都要调整，基数顶点都要调整，基数顶点+1，偶数顶点，偶数顶点-1。v上述调整使总的运输费用发生的变化为上述调整使总的运输费用发生的变化为 8 10 + 3 2 -1 ，这就说明原方案还不是最优，这就说明原方案还不是最优方案，需要进行调整。方案，需要进行调整。精选ppt三、最优性检验三、最优性检验B1B2B3B4产量产量A13113 410 37A21 392 184A374 6105 39销量销量365620v若让若让x111，则总运费变化：，则总运费变化：33+211 。精选p

13、pt三、最优性检验三、最优性检验v如果规定作为起始顶点的非基变量如果规定作为起始顶点的非基变量xij为第为第 1 个顶点，其闭回路上的其他顶点依次为第个顶点，其闭回路上的其他顶点依次为第 2 个顶点、第个顶点、第 3 个顶点个顶点，那么就有该非基，那么就有该非基变量的检验数：变量的检验数：v ij = (闭回路上的奇数顶点运价之和闭回路上的奇数顶点运价之和) - (闭回闭回路上的偶数顶点运价之和路上的偶数顶点运价之和)v最优标准：所有检验数最优标准：所有检验数0精选ppt三、最优性检验三、最优性检验B1B2B3B4产量产量A13 113 410 37A21 39 2 18 4A37 4 610

14、 5 39销量销量365620v检验数计算如下表：检验数计算如下表：（1）（2）（1）（-1）（10）（12）精选ppt三、最优性检验三、最优性检验v2、位势法、位势法v闭回路法的缺点：当变量个数较多时，寻找闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。闭回路以及计算两方面都容易出错。v位势法：设产地位势法：设产地Ai对应的位势量为对应的位势量为ui ，销地，销地Bj对应的位势量为对应的位势量为vj， 检验数检验数 ij =cij ui-vj。精选ppt三、最优性检验三、最优性检验B1B2B3B4产量产量uiA13 11 3 410 37u1A21 39 2 184u2

15、A37 4 6105 39u3销量销量365620vjv1v2v3v4精选ppt三、最优性检验三、最优性检验v根据基变量根据基变量xij 的检验数的检验数 ij =0 ，对应基变量，对应基变量的运价的运价cij可以分解为可以分解为ui 和和vj，即，即cij =ui+vj 。v因为位势量因为位势量ui ,vj的总数为的总数为m + n 个，而限定个，而限定方程只有方程只有m+n-1个（基变量个数），所以位个（基变量个数），所以位势量（势量（ ui ,vj ）有无穷多组解，其中总有一个）有无穷多组解，其中总有一个自由变量。自由变量。v故可以任意取一个位势量赋以定值，从而确故可以任意取一个位势量赋

16、以定值，从而确定其它位势量的值，一般取定其它位势量的值，一般取u1 0。精选ppt三、最优性检验三、最优性检验10392vj206563销量销量bj-595 310 4 67 A3-148 2 19 1 3A20710 33 411 3 A1ui产量产量aiB4B3B2B1（1）（2）（1）（-1）（10）（12）精选ppt检验数计算总结检验数计算总结v1、闭回路法计算式：、闭回路法计算式：v ij = (闭回路上的奇数顶点运价之和闭回路上的奇数顶点运价之和) - (闭回闭回路上的偶数顶点运价之和路上的偶数顶点运价之和)v2、位势法计算式：、位势法计算式：v ij = cij - ui vj

17、精选ppt四、方案调整四、方案调整B1B2B3B4产量产量A13 （1）11 （2）3 410 37A21 39 （1）2 18 （-1）4A37 （10）4 610 （12）5 39销量销量365620最小检验数最小检验数原则，确定原则，确定进基变量进基变量最小偶点原则，最小偶点原则，确定出基变量和确定出基变量和调整量调整量+1-1+1-1精选ppt四、方案调整四、方案调整B1B2B3B4产量产量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39销量销量bj365620v得到新的基变量：得到新的基变量：x13 = 5, x14 = 2, x21 =

18、3, x24 = 1, x32 = 6, x34 = 3。重新计算检验数。重新计算检验数。（0）（2）（2）（1）（9）（12）精选ppt四、方案调整四、方案调整v经过一次基变换，所有经过一次基变换，所有 ij 0，已得到最优解：，已得到最优解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3，其它为其它为0。v最优值：最优值：vf* =35+102+13+81+46+53 = 85精选ppt四、方案调整四、方案调整闭回路调整法步骤：闭回路调整法步骤：1、入基变量的确定：选负检验数中最小者、入基变量的确定：选负检验数中最小者 rk，那么

19、，那么 xrk 作为进基变量；（使总运费尽作为进基变量；（使总运费尽快减少）快减少）2、出基变量的确定：在进基变量、出基变量的确定：在进基变量xrk 的闭回的闭回路上，选取偶数顶点上调运量最小的值，将路上，选取偶数顶点上调运量最小的值，将其对应的运量作为出基变量。（刚好有一个其对应的运量作为出基变量。（刚好有一个基变量出基，其它基变量都为正）基变量出基，其它基变量都为正）精选ppt四、方案调整四、方案调整即求即求 =Minxij 闭回路上的偶数顶点的闭回路上的偶数顶点的xij= xpq。那么确定那么确定xpq为出基变量，为出基变量， 为调整量；为调整量；3、换基调整：对闭回路的奇数顶点运量调整

20、、换基调整：对闭回路的奇数顶点运量调整为：为：xij+ ，对各偶数顶点运量调整为：，对各偶数顶点运量调整为：xij- ，特别特别 xpq- =0，xpq变为非基变量。变为非基变量。重复以上步骤，直到所有检验数均非负，即重复以上步骤，直到所有检验数均非负，即得到最优解。得到最优解。精选ppt练习题练习题已知如下运价表，用表上作业法求解：已知如下运价表，用表上作业法求解：产销产销地地B1B2B3B4产量产量A165344A244756A376583销量销量243413精选ppt 初始解对应目标值为初始解对应目标值为33+41+42+44+8361产销地产销地B1B2B3B4产量产量uiA16534

21、4A244756A376583销量销量243413vj3421030341334(3)(2)(3)(0)(-1)(-2)精选ppt产销地产销地B1B2B3B4产量产量uiA165344A244756A376583销量销量243413vj4030240341332(3)(2)(3)(2)(1)(2) 已达到最优，最优目标值为已达到最优，最优目标值为44+42+44+5355精选ppt五、运输问题的几种特殊情况五、运输问题的几种特殊情况v1、多个最优方案的情况：、多个最优方案的情况：v若最优表中有非基变量的检验数为若最优表中有非基变量的检验数为0，则为多，则为多个最优方案的情况。个最优方案的情况。v这种情况下，可将检验数为这种情况下，可将检验数为0的非基变量作为的非基变量作为进基变量，即可得到另一个最优方案。进基变量，即可得到另