（精选）运输单纯形法(学院轮讲).ppt

设平衡运输问题的数学模型为 运输单纯形法也称为表上作业法 是直接在运价表上求最优解的一种方法 它的步骤是 第一步 求初始基行可行解 初始调运方案 常用的方法有最小元素法 元素差额法 Vogel近似法 左上角法 第二步 求检验数并判断是否得到最优解 常用求检验的方法有闭回路法和位势法 当非基变量的检验数 ij全都非负时得到最优解 若存在检验数 lk 0 说明还没有达到最优 转第三步 第三步 调整运量 即换基 选一个变量出基 对原运量进行调整得到新的基可行解 转入第二步 3 2 1初始基可行解 1 最小元素法最小元素法的思想是就近优先运送 即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束 依次下去 直到最后一个初始基可行解 例3 3 求表3 6所示的运输问题的初始基可行解 表3 6 解 30 15 10 25 20 例3 4 求表3 7给出的运输问题的初始基本可行解 表3 7 解 3 6 0 4 1 6 在x12 x22 x33 x34中任选一个变量作为基变量 例如选x12 表3 8 初始基本可行解可用下列矩阵表示 1 最小元素法的优势与劣势各是什么 参考书 熊伟 运筹学 机械工业出版社 2 用最小元素法求出的调运方案是否接近最优 思考题 2 元素差额法 Vogel近似法 最小元素法只考虑了局部运输费用最小 对整个产销系统的总运输费用来说可能离最优值较远 有时为了节省某一处的运费 而在其它处可能运费很大 元素差额法对最小元素法进行了改进 考虑到产地到销地的最小运价和次小运价之间的差额 如果差额很大 就选最小运价先调运 否则会增加总运费 例如下面两种运输方案 15151515 前一种按最小元素法求得 总运费是Z1 10 8 5 2 15 1 105 后一种方案考虑到C11与C21之间的差额是8 2 6 如果不先调运x21 到后来就有可能x11 0 这样会使总运费增加较大 从而先调运x21 再是x22 其次是x12这时总运费Z2 10 5 15 2 5 1 85 Z1 基于以上想法 元素差额法求初始基本可行解的步骤是 基于以上想法 元素差额法求初始基本可行解的步骤是 第一步 求出每行次小运价与最小运价之差 记为ui i 1 2 m 同时求出每列次小运价与最小运价之差 记为vj j 1 2 n 第二步 找出所有行 列差额的最大值 即L max ui vi 差额L对应行或列的最小运价处优先调运 第三步 这时必有一列或一行调运完毕 在剩下的运价中再求最大差额 进行第二次调运 依次进行下去 直到最后全部调运完毕 就得到一个初始调运方案 用元素差额法求得的基本可行解更接近最优解 所以也称为近似方案 例5 用元素差额法求表3 9运输问题的初始基本可行解 表3 9 解 求行差额ui i 1 2 3及列差额vj j 1 2 3 4 计算公式为ui i行次小运价 i行最小运价vj j列次小运价 j例最小运价 5 5 4 1 4 3 3 2 20 0 5 20 0 2 4 4 2 20 10 5 基本可行解为 总运费Z 10 8 20 1 5 2 20 8 270 求运输问题的初始方案还有很多方法 如左上角法 右上角法等 常用的方法是Vogel近似法 最小元素法 3 2 2求检验数求出一组基可行解后 判断是否为最优解 仍然是用检验数来判断 记xij的检验数为 ij由第一章知 求最小值的运输问题的最优判别准则是 所有非基变量的检验数都非负 则运输方案最优 即为最优解 求检验数的方法有两种 闭回路法和位势法 1 闭回路法求检验数求某一非基变量的检验数的方法是 在基本可行解矩阵中 以该非基变量为起点 以基变量为其它顶点 找一条闭回路 由起点开始 分别在顶点上交替标上代数符号 以这些符号分别乘以相应的运价 其代数和就是这个非基变量的检验数 解 用最小元素法得到下列一组基本可行解 例7 求下列运输问题的一个初始基本可行解及其检验数 矩阵中的元素为运价Cij 矩阵右边的元素为产量ai 下方的元素为销量bj 10604030 矩阵中打 的位置是非基变量 其余是基变量 这里只求非基变量的检验数 求 11 先找出x11的闭回路 对应的运价为再用正负号分别交替乘以运价有直接求代数和得 同理可求出其它非基变量的检验数 这里 34 0 说明这组基本可行解不是最优解 只要求得的基变量是正确的且数目为m n 1 则某个非基变量的闭回路存在且唯一 因而检验数唯一 2 位势法求检验位势法求检验数是根据对偶理论推导出来的一种方法 设平衡运输问题为 设前m个约束对应的对偶变量为ui i 1 2 m 后n个约束对应的对偶变量为vj j 1 2 n则运输问题的对偶问题是 加入松驰变量 ij将约束化为等式 ui vj ij cij 记原问题基变量XB的下标集合为I 由第二章对偶性质知 原问题xij的检验数是对偶问题的松弛变量 ij当 i j 时 ij 0 因而有 解上面第一个方程 将ui vj代入第二个方程求出 ij 例8 用位势法求例7给出的初始基本可行解的检验数 解 第一步求位势u1 u2 u3及v1 v2 v3 v4 10604030 令u1 0得到位势的解为 再由公式求出检验数 其中Cij是非基变量对应的运价 计算结果与例7结果相同 3 2 3调整运量 前面讲过 当某个检验数小于零时 基可行解不是最优解 总运费还可以下降 这时需调整运输量 改进原运输方案 使总运输减少 改进运输方案的步骤是 第一步 确定进基变量 第二步 确定出基变量 在进基变量xik的闭回路中 标有负号的最小运量作为调整量 对应的基变量为出基变量 并打上 以示作为非基变量 第三步 调整运量 在进基变量的闭回路中标有正号的变量加上调整量 标有负号的变量减去调整量 其余变量不变 得到一组新的基可行解 然后求所有非基变量的检验数重新检验 例9 求下列运输问题的最优解 45655030 解 用最小元素法求得初始基本可行解如下 30 45 35 40 25 15 求非基变量的检验数 用闭回路法得 因为有4个检验数小于零 所以这组基本可行解不是最优解 对应的非基变量x11进基 对应的非基变量x11进基 x11的闭回路是标负号的变量是x12 x33 x21 取运量最小值 x33最小 x33是出基量 调整量 15 在x11的闭回路上x11 x32 x23分别加上15 x12 x33 x21分别减去15 并且在x33处打上记号 作为基变量 其余变量不变 调整后得到一组新的基可行解 重新求所有非基变量的检验数得 13 3 22 0 24 7 31 1 33 4 34 1 x34进基 x14出基 调整运量得到下表 再求非基变量的检验数 13 3 14 1 22 0 24 8 31 1 33 4 所有检验