第七章 运输问题之表上作业法.ppt

第七章 运输问题之表上作业法 一、运输问题模型及其求解思路 二、确定初始基本可行解 三、最优性检验 四、方案调整 五、几种特殊情况 一、运输问题模型及其求解思路 1、问题的提出： 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3。 各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。 问：应如何调运可使总运输费用最小？ 一、运输问题模型及其求解思路 一、运输问题模型及其求解思路 2、产销平衡运输问题模型的特点 从模型的建立可知： 列数为2（产地数）×3（销地数）＝6； 行数为2（产地数）+3（销地数）＝5； 再观察模型的系数矩阵： 一、运输问题模型及其求解思路 一、运输问题模型及其求解思路 对于产销平衡的运输问题，若产地为m个，销地为n个， 则变量个数为m×n个，线性无关的约束条件个数为m+n-1， 故基本解中的基变量个数为m+n-1。 一、运输问题模型及其求解思路 3、运输问题求解思路——表上作业法 由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。 人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。 一、运输问题模型及其求解思路 一、运输问题模型及其求解思路 表上作业法的总体思路和单纯形法类似： 一、运输问题模型及其求解思路 例：某食品公司下属的A1、A2、A3 ，3个厂生产方便食品，要运输到B1、B2、B3、B4 ，4个销售点，数据如下表，求最优运输方案。 二、确定初始基本可行解 1、西北（左上）角法 每次找最西北角的元素，让其运输量尽可能的满足一个约束条件。 二、确定初始基本可行解 二、确定初始基本可行解 二、确定初始基本可行解 2、最小元素法 每次找到剩下的最小运价，让其对应的运输量尽可能的满足一个约束条件。 二、确定初始基本可行解 二、确定初始基本可行解 二、确定初始基本可行解 为保证基变量的个数有m+n-1个，注意： 1、每次填完数，只能划去一行或一列，只有最后一个格子例外。 2、用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩下的空格中标上0。（退化的基本可行解） 二、确定初始基本可行解 二、确定初始基本可行解 三、最优性检验 检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。 运输问题中目标函数值要求最小化，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则不是。 下面介绍两种计算检验数的方法： 三、最优性检验 1、闭回路法 闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，只有碰到基变量，才能向右或向左转90o (当然也可以不改变方向）继续前进。 这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回路。 三、最优性检验 每一个非基变量都有唯一的闭回路 三、最优性检验 观察x24的闭回路： 若让第一个顶点非基变量x24的取值变为1，为了保持产销平衡，其闭回路上的顶点运量都要调整，基数顶点+1，偶数顶点-1。 上述调整使总的运输费用发生的变化为 8 – 10 + 3 – 2 ＝ -1 ，这就说明原方案还不是最优方案，需要进行调整。 三、最优性检验 三、最优性检验 如果规定作为起始顶点的非基变量xij为第 1 个顶点，其闭回路上的其他顶点依次为第 2 个顶点、第 3 个顶点……，那么就有该非基变量的检验数： ?ij = (闭回路上的奇数顶点运价之和) - (闭回路上的偶数顶点运价之和) 最优标准：所有检验数≥0 三、最优性检验 三、最优性检验 2、位势法 闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。 位势法：设产地Ai对应的位势量为ui ，销地Bj对应的位势量为vj， 检验数?ij =cij –ui-vj。 三、最优性检验 三、最优性检验 根据基变量xij 的检验数?ij =0 ，对应基变量的运价cij可以分解为ui 和vj，即cij =ui+vj 。 因为位势量ui ,vj的总数为m + n 个，而限定方程只有m+n-1个（基变量个数），所以位势量（ ui ,vj ）有无穷多组解，其中总有一个自由变量。 故可以任意取一个位势量赋以定值，从而确定其它位势量的值，一般取u1 ＝0。 三、最优性检验 检验数计算总结 1、闭回路法计算式： ?ij = (闭回路上的奇数顶点运价之和) - (闭回路上的偶数顶点运价之和) 2、位势法计算式： ?ij = cij - ui – vj 四、方案调整 四、方案调整 四、方案调整 经过一次基变换，所有?ij ≥ 0，已得到最优解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6,