运筹第4章运输问题.ppt

1 第四章特殊的线性规划 运输问题 模型及其特点求解思路及相关理论求解方法 表上作业法运输问题的推广产销不平衡的运输问题转运问题 2 4 1运输问题模型与性质 一 运输问题的数学模型1 运输问题的一般提法 某种物资有若干产地和销地 现在需要把这种物资从各个产地运到各个销地 产量总数等于销量总数 已知各产地的产量和各销地的销量以及各产地到各销地的单位运价 或运距 问应如何组织调运 才能使总运费 或总运输量 最省 3 单位根据具体问题选择确定 表4 1有关信息 4 2 运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量 i 1 m j 1 n 由于从Ai运出的物资总量应等于Ai的产量ai 因此xij应满足 5 同理 运到Bj的物资总量应该等于Bj的销量bj 所以xij还应满足 总运费为 6 运输问题的数学模型 7 二 运输问题的特点与性质 1 约束方程组的系数矩阵具有特殊的结构 写出系数矩阵A 形式如下 8 矩阵的元素均为1或0 每一列只有两个元素为1 其余元素均为0 列向量Pij 0 0 1 0 0 1 0 0 T 其中两个元素1分别处于第i行和第m j行 将该矩阵分块 特点是 前m行构成m个m n阶矩阵 而且第k个矩阵只有第k行元素全为1 其余元素全为0 k 1 m 后n行构成m个n阶单位阵 9 2 运输问题的基变量总数是m n 1 写出增广矩阵 10 定义4 1凡是能排成或形式的变量集合称为一个闭回路 并称式中变量为该闭回路的顶点 其中互不相同 互不相同 3 m n 1个变量构成基变量的充要条件是它们不构成闭回路 11 例4 1设m 3 n 4 决策变量xij表示从产地Ai到销地Bj的调运量 列表如下 给出闭回路在表中的表示法 用折线连接起来的顶点变量 12 练习4 1请给出闭回路和在表中的表示法 13 练习4 2下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路 为什麽 表中的折线构成一条封闭曲线 且所有的边都是水平或垂直的 为什麽 表中的每一行和每一列由折线相连的闭回路的顶点只有两个 为什麽 14 三 运输问题求解 表上作业法 一 表上作业法的基本思想是 先设法给出一个初始方案 然后根据确定的判别准则对初始方案进行检查 调整 改进 直至求出最优方案 如图4 1所示 表上作业法和单纯形法的求解思想完全一致 但是具体作法更加简捷 15 图4 1运输问题求解思路图 16 表4 2运输问题作业表 产销平衡表 17 1 初始基本可行解的确定找到m n 1个不构成闭回路的基变量 较常用的方法有西北角法 最小元素法和伏格尔法 二 产销平衡问题 表上作业法步骤 18 西北角法 甲 乙两个煤矿供应A B C三个城市用煤 各煤矿产量及各城市需煤量 各煤矿到各城市的运输距离见表3 4 求使总运输量最少的调运方案 19 用西北角法确定例4 2初始调运方案 100 100 100 50 50 200 200 20 得到初始调运方案为 x11 100 x12 100 x22 50 x23 200运输费用为34250 21 用最小元素法确定例3 2初始调运方案 150 100 100 100 100 100 100 22 得到初始调运方案为 x11 100 x13 100 x22 150 x23 100 运输费用为36250 23 用伏格尔法确定例3 2初始调运方案 50 50 200 150 50 50 50 24 得到初始调运方案为 x11 50 x12 150 x21 50 x23 200 运输费用为34000 25 2 最优性检验 检查当前调运方案是不是最优方案的过程就是最优性检验 检查的方法 计算非基变量 未填上数值的格 即空格 的检验数 也称为空格的检验数 若全部大于等于零 则该方案就是最优调运方案 否则就应进行调整 26 闭回路法 以确定了初始调运方案的作业表为基础 以一个非基变量作为起始顶点 寻求闭回路 该闭回路的特点是 除了起始顶点是非基变量外 其他顶点均为基变量 对应着填上数值的格 可以证明 如果对闭回路的方向不加区别 对于每一个非基变量而言 以其为起点的闭回路存在且唯一 27 约定作为起始顶点的非基变量为偶数次顶点 其它顶点从1开始顺次排列 那麽 该非基变量xij的检验数 现在 在用最小元素法确定例4 2初始调运方案的基础上 计算非基变量X12的检验数 28 例4 2初始调运方案中以X12 X21 为起点的闭回路 29 非基变量X12的检验数 非基变量X21的检验数 c12 c23 c13 c22 70 75 100 65 20 c21 c13 c11 c23 80 100 90 75 15 经济含义 在保持产销平衡的条件下 该非基变量增加一个单位运量而成为基变量时目标函数值的变化量 30 位势法 以例4 2初始调运方案为例 设置位势变量和 在初始调运方案表的基础上增加一行和一列 见下页表格 然后构造下面的方程组 3 7 31 例4 2初始调运方案位势变量对应表 32 方程组的特点 方程个数是m n 1 2 3 1 4个 位势变量共有m n 2 3 5个 通常称ui为第i行的位势 称vj为第j列的位势 初始方案的每一个基变量xij对应一个方程 所在行和列对应的位势变量之和等于该基变量对应的运距 或运价 ui vj cij 方程组恰有一个自由变量 可以证明方程组中任意一个变量均可取作自由变量 33 12 c12 u1 v2 70 0 90 20 21 c21 u2 v1 80 25 90 15与前面用闭回路法求得的结果相同 34 位势法计算非基变量xij检验数的公式 ij cij ui vj 闭回路上偶数次顶点运距或运价之和 闭回路上奇数次顶点运距或运价之和 闭回路法计算非基变量xij检验数的公式 复习比较检验数计算的两种方法 35 3 方案调整 当至少有一个非基变量的检验数是负值时 说明作业表上当前的调运方案不是最优的 应进行调整 若检验数 ij小于零 则首先在作业表上以xij为起始变量作出闭回路 并求出调整量 min 该闭回路中奇数次顶点调运量xij ij 36 继续上例 因 12 20 画出以x12为起始变量的闭回路 37 计算调整量 Min 100 150 100 按照下面的方法调整调运量 闭回路上 奇数次顶点的调运量减去 偶数次顶点 包括起始顶点 的调运量加上 闭回路之外的变量调运量不变 得到新的调运方案 38 重复上面的步骤 直至求出最优调运方案 39 40 结果 最优调运方案是 x11 50 x12 150 x21 50 x23 200 相应的最小总运输量为 Zmin 90 50 70 150 80 50 75 200 34000 吨公里 41 三 产销不平衡的运输问题 增加虚拟销地 增加虚拟产地 产销平衡的运输问题 对应的运距 或运价 42 1 产量大于销量 增加虚拟销地虚拟销地的销量 运价 43 运价见下表 产地产量分别为7 5 7t 销地销量分别为2 3 4 6t 试决定总运费最少的调运方案 44 45 2 产量小于销量 增加虚拟产地虚拟产地的产量 运价 46 运价见下表 产地产量分别为7 5 2t 销地销量分别为2 3 4 6t 试