运输问题的计算机求解与运用(ppt 28页).ppt

1 第七章运输问题 1运输模型 2运输问题的计算机求解 3运输问题的应用 4 运输问题的表上作业法 2 例1 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 解 产销平衡问题 总产量 总销量设xij为从产地Ai运往销地Bj的运输量 得到下列运输量表 Minf 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 1运输模型 3 1运输模型 一般运输模型 产销平衡A1 A2 Am表示某物资的m个产地 B1 B2 Bn表示某物质的n个销地 si表示产地Ai的产量 dj表示销地Bj的销量 cij表示把物资从产地Ai运往销地Bj的单位运价 设xij为从产地Ai运往销地Bj的运输量 得到下列一般运输量问题的模型 mnMinf cijxiji 1j 1ns t xij sii 1 2 mj 1m xij djj 1 2 ni 1xij 0 i 1 2 m j 1 2 n 变化 1 有时目标函数求最大 如求利润最大或营业额最大等 2 当某些运输线路上的能力有限制时 在模型中直接加入约束条件 等式或不等式约束 3 产销不平衡时 可加入假想的产地 销大于产时 或销地 产大于销时 4 2运输问题的计算机求解 例2 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 解 增加一个虚设的销地运输费用为0 5 2运输问题的计算机求解 例3 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 问 应如何调运可使总运输费用最小 解 增加一个虚设的产地运输费用为0 6 3运输问题的应用 一 产销不平衡的运输问题例4 石家庄北方研究院有一 二 三三个区 每年分别需要用煤3000 1000 2000吨 由河北临城 山西盂县两处煤矿负责供应 价格 质量相同 供应能力分别为1500 4000吨 运价为 由于需大于供 经院研究决定一区供应量可减少0 300吨 二区必须满足需求量 三区供应量不少于1500吨 试求总费用为最低的调运方案 解 根据题意 作出产销平衡与运价表 这里M代表一个很大的正数 其作用是强迫相应的x31 x33 x34取值为0 7 3运输问题的应用 一 产销不平衡的运输问题例5 设有A B C三个化肥厂供应1 2 3 4四个地区的农用化肥 假设效果相同 有关数据如下表 试求总费用为最低的化肥调拨方案 解 根据题意 作出产销平衡与运价表 最低要求必须满足 因此把相应的虚设产地运费取为M 而最高要求与最低要求的差允许按需要安排 因此把相应的虚设产地运费取为0 对应4 的销量50是考虑问题本身适当取的数据 根据产销平衡要求确定D的产量为50 8 3运输问题的应用 二 生产与储存问题例6 某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如右表 如果生产出来的柴油机当季不交货 每台每积压一个季度需储存 维护等费用0 15万元 试求在完成合同的情况下 使该厂全年生产总费用为最小的决策方案 9 3运输问题的应用 解 设xij为第i季度生产的第j季度交货的柴油机数目 那么应满足 交货 x11 10生产 x11 x12 x13 x14 25x12 x22 15x22 x23 x24 35x13 x23 x33 25x33 x34 30 x14 x24 x34 x44 20 x44 10把第i季度生产的柴油机数目看作第i个生产厂的产量 把第j季度交货的柴油机数目看作第j个销售点的销量 成本加储存 维护等费用看作运费 可构造下列产销平衡问题 目标函数 Minf 10 8x11 10 95x12 11 1x13 11 25x14 11 1x22 11 25x23 11 4x24 11 0 x33 11 15x34 11 3x44 10 3运输问题的应用 二 生产与储存问题例7 光明仪器厂生产电脑绣花机是以产定销的 已知1至6月份各月的生产能力 合同销量和单台电脑绣花机平均生产费用见下表 已知上年末库存103台绣花机 如果当月生产出来的机器当月不交货 则需要运到分厂库房 每台增加运输成本0 1万元 每台机器每月的平均仓储费 维护费为0 2万元 在7 8月份销售淡季 全厂停产1个月 因此在6月份完成销售合同后还要留出库存80台 加班生产机器每台增加成本1万元 问应如何安排1 6月份的生产 可使总的生产费用 包括运输 仓储 维护 最少 11 3运输问题的应用 解 这个生产存储问题可化为运输问题来做 考虑 各月生产与交货分别视为产地和销地1 1 6月份合计生产能力 包括上年末储存量 为743台 销量为707台 设一假想销地销量为36 2 上年末库存103台 只有仓储费和运输费 把它列为第0行 3 6月份的需求除70台销量外 还要80台库存 其需求应为70 80 150台 4 1 6表示1 6月份正常生产情况 1 6 表示1 6月份加班生产情况 产销平衡与运价表 12 3运输问题的应用 用 管理运筹学 软件解得的结果是 1 6月最低生产费用为8307 5万元 每月的销售安排如下表所示 13 3运输问题的应用 三 转运问题 在原运输问题上增加若干转运站 运输方式有 产地 转运站 转运站 销地 产地 产地 产地 销地 销地 转运站 销地 产地等 例8 腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器 大连分厂每月生产400台 广州分厂每月生产600台 该公司在上海和天津有两个销售公司负责对南京 济南 南昌 青岛四个城市的仪器供应 另外因为大连距离青岛较近 公司同意大连分厂向青岛直接供货 运输费用如图 单位是百元 问应该如何调运仪器 可使总运输费用最低 图中1 广州 2 大连 3 上海 4 天津 5 南京 6 济南 7 南昌 8 青岛 14 3运输问题的应用 解 设xij为从i到j的运输量 可得到有下列特点的线性规划模型 目标函数 Minf 所有可能的运输费用 运输单价与运输量乘积之和 约束条件 对产地 发点 i 输出量 输入量 产量对转运站 中转点 输入量 输出量 0对销地 收点 j 输入量 输出量 销量例8 续 目标函数 Minf 2x13 3x14 3x23 x24 4x28 2x35 6x36 3x37 6x38 4x45 4x46 6x47 5x48约束条件 s t x13 x14 600 广州分厂供应量限制 x23 x24 x28 400 大连分厂供应量限制 x13 x23 x35 x36 x37 x38 0 上海销售公司 转运站 x14 x24 x45 x46 x47 x48 0 天津销售公司 转运站 x35 x45 200 南京的销量 x36 x46 150 济南的销量 x37 x47 350 南昌的销量 x38 x48 x28 300 青岛的销量 xij 0 i j 1 2 3 4 5 6 7 8 15 3运输问题的应用 用 管理运筹学 软件求得结果 x13 550 x14 50 x23 0 x24 100 x28 300 x35 200 x36 0 x37 350 x38 0 x45 0 x46 150 x47 0 x48 0 最小运输费用为 4600百元例9 某公司有A1 A2 A3三个分厂生产某种物资 分别供应B1 B2 B3 B4四个地区的销售公司销售 假设质量相同 有关数据如下表 试求总费用为最少的调运方案 假设 1 每个分厂的物资不一定直接发运到销地 可以从其中几个产地集中一起运 2 运往各销地的物资可以先运给其中几个销地 再转运给其他销地 3 除产销地之外 还有几个中转站 在产地之间 销地之间或在产地与销地之间转运 16 3运输问题的应用 运价如下表 解 把此转运问题转化为一般运输问题 1 把所有产地 销地 转运站都同时看作产地和销地 2 运输表中不可能方案的运费取作M 自身对自身的运费为0 3 Ai 产量为20 原产量 销量为20 Ti 产量 销量均为20 Bi 产量为20 销量为20 原销量 其中20为各点可能变化的最大流量 4 对于最优方案 其中xii为自身对自身的运量 实际上不进行运作 17 3运输问题的应用 扩大的运输问题产销平衡与运价表 18 4 运输问题的表上作业法 表上作业法是一种求解运输问题的特殊方法 其实质是单纯形法 运输问题都存在最优解 计算过程 假设产销平衡 1 找出初始基本可行解 对于有m个产地n个销地的产销平衡问题 则有m个关于产量的约束方程和n个关于销量的约束方程 由于产销平衡 其模型最多只有m n 1个独立的约束方程 即运输问题有m n 1个基变量 在m n的产销平衡表上给出m n 1个数字格 其相对应的调运量的值即为基变量的值 2 求各非基变量的检验数 即检验除了上述m n 1个基变量以外的空格的检验数判别是否达到最优解 如果已是最优 停止计算 否则转到下一步 3 确定入基变量和出基变量 找出新的基本可行解 在表上用闭回路法调整 4 重复2 3直到得到最优解 19 4 运输问题的表上作业法 例10 喜庆食品公司有三个生产面包的分厂A1 A2 A3 有四个销售公司B1 B2 B3 B4 其各分厂每日的产量 各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示 在表中产量与销量的单位为吨 运价的单位为百元 吨 问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少 这是一个产销平衡的运输问题 因此不需要再设假想产地和销地了 20 4 运输问题的表上作业法 一 确定初始基本可行解为了把初始基本可行解与运价区分开 我们把运价放在每一栏的右上角 每一栏的中间写上初始基本可行解 调运量 1 西北角法 先从表的左上角 即西北角 的变量x11开始分配运输量 并使x11取尽可能大的值 即x11 min 7 3 3 则x21与x31必为零 同时把B1的销量与A1的产量都减去3填入销量和产量处 划去原来的销量和产量 同理可得余下的初始基本可行解 3 11 3 10 8 5 10 2 9 4 7 1 21 4 运输问题的表上作业法 2 最小元素法西北角法是对西北角的变量分配运输量 而最小元素法是就近供应 即对单位运价最小的变量分配运输量 在表上找到单位运价最小的x21 并使x21取尽可能大的值 即x21 min 4 3 3 把A1的产量改为1 B1的销量改为0 并把B1列划去 在剩下的3 3矩阵中再找最小运价 同理可得其他的基本可行解 一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少 这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些 3 11 3 10 8 5 10 2 9 4 7 1 22 4 运输问题的表上作业法 在求初始基本可行解时要注意的两个问题 1 当我们取定xij的值之后 会出现Ai的产量与Bj的销量都改为零的情况 这时只能划去Ai行或Bj列 但不能同时划去Ai行与Bj列 2 用最小元素法时 可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况 此时在这一行或者一列中除去已填上的数外均填上零 不能按空格划掉 这样可以保证填过数或零的格为m n 1个 即保证基变量的个数为m n 1个 23 4 运输问题的表上作业法 二 最优解的判别1 闭回路法所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发 沿水平或垂直方向前进 只有遇到代表基变量的填入数字的格才能向左或右转90度 当然也可以不改变方向 继续前进 这样继续下去 直至回到出发的那个空格 由此形成的封闭折线叫做闭回路 一个空格存在唯一的闭回路 所谓闭回路法 就是对于代表非基变量的空格 其调运量为零 把它的调运量调整为1 由于产销平衡的要求 我们必须对这个空格的闭回路的顶点的调运量加上或减少1 最后我们计算出由这些变化给整个运输方案的总运输费带来的变化 如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零 则已求得最优解 否则继续迭代找出最优解 24 4 运输问题的表上作业法 从非基变量x11出发 找到一个闭回路如上表所示 回路有四个顶点 除x11外 其余都为基变量 现在把x11的调运量从零增加为1吨 运费也增加了3元 为了使A1产量平衡 x13必须减少1吨 运费减少3元 为了B3的销量平衡 x23必须增加1吨 运费增加2元 同理把x21减少1吨 运费减少1元 调整后 总运费增加了3 3 2 1 1元 说明如果让x11为基变量 运费就会增加 其增加值1作为x11的检验数 为了区别调整量 我们把1加圈 用同样的方法可以找出所有空格 即非基变量 的检验数 3 11 3 10 8 5 10 2 9 4 7 1 25 4 运输问题的表上作业法 2 位势法所谓位势法 我们对运输表上的每一行赋予一个数值ui 对每一列赋予一个