第7章运筹学 运输问题ppt课件

1 第七章运输问题 1运输模型 2运输问题的计算机求解 3运输问题的应用 4 运输问题的表上作业法 2 3 4 5 6 7 8 9 10 11 第四季度可以加班生产 生产能力为10台 加班费用1万元每台 原有库存15台 年末需要留有10台库存 12 生产与存储问题 13 某造船厂根据合同需连续三年提供五艘大型货轮给客户 该厂三年内的生产情况如表所示 加班生产比正常生产高出10 每艘货轮积压一年的损失为60万元 签合同时 该厂已积压两艘货轮 该厂希望在三年后有一艘备用 问应该如何安排生产 总的费用最小 14 生产问题 某机床厂定下一年合同分别于各季度末交货 已知各季度生产成本不同 允许存货 存储费0 12万元 台季 三 四季度可以加班生产 加班生产能力8台 季 加班费用3万元 台问如何安排生产使得总费用最低 15 分析 可用线性规划 但用运输问题更简单要决策的问题是各季度生产量和交货量设xij表示第i季度生产第j季度交货的台数因加班时间生产成本不同 故要区别开来 三四季度可加班 视同增加两个季度需求量合计115台 生产能力合计126台 供需不平衡 因此 增加一个虚拟的需求点 16 建模 17 结果 18 19 三 转运问题 例8 腾飞公司有1 2两个分厂生产产品 1 2分厂每月分别生产400台和600台 有3 4两个分销商负责四个城市的供应 运输网络和运输费用如图 单位是百元 问应该如何调运仪器 可使总运输费用最低 20 三 转运问题 解 设xij为从i到j的运输量 可得到有下列特点的线性规划模型 目标函数 Minf 所有可能的运输费用 运输单价与运输量乘积之和 约束条件 对产地 发点 i 输出量 输入量 产量对转运站 中转点 输入量 输出量 0对销地 收点 j 输入量 输出量 销量 21 三 转运问题 目标函数 Minf 2x13 3x14 3x23 x24 4x28 2x35 6x36 3x37 6x38 4x45 4x46 6x47 5x48约束条件 s t x13 x14 600 1分厂供应量限制 x23 x24 x28 400 2分厂供应量限制 x13 x23 x35 x36 x37 x38 0 3转运站 x14 x24 x45 x46 x47 x48 0 4转运站 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 22 三 转运问题 用 管理运筹学 软件求得结果 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百元如何把转运问题转化为运输问题 23 举例说明表上作业法 例1 某部门三个工厂生产同一产品的产量 四个销售点的销量及单位运价如下表 24 第一步 确定初始基可行解 最小元素法 伏格尔法 最小元素法思路 按单位运价的大小决定供应的先后 优先满足单位运价最小者的供销要求 即从单价中最小运价确定供应量 逐步次小 直至得到m n 1个数字格 25 最小元素法举例 8 2 2 0 10 10 0 6 14 8 6 8 0 0 0 0 6 0 26 最小元素法举例 最小元素法缺点 有时为了优先考虑某一最小元素 却可能使其他供销点的运输费用大大增加 会出现顾此失彼 考虑运价差 27 罚数 即差额 次小运价 最小运价罚数 或差额 的解释 差额大 则不按最小运费调运 运费增加大 差额小 则不按最小运费调运 运费增加不大 对差额最大处 采用最小运费调运 伏格尔法思路 28 结合例1说明这种方法 0 4 4 0 第一次 29 结合例1说明这种方法 1 3 2 1 第一次 30 结合例1说明这种方法 1 第一次 31 结合例1说明这种方法 4 2 2 2 1 5 3 第一次 32 结合例1说明这种方法 14 8 0 优先安排销地 否则运价会更高 下次不考虑该列 第一次 33 第二次 结合例1说明这种方法 优先安排销地 否则运价会更高 8 0 6 下次不考虑该行 34 结合例1说明这种方法 下次不考虑该列 8 0 2 第三次 35 结合例1说明这种方法 4 12 0 下次不考虑该列 第四次 36 结合例1说明这种方法 4 2 0 0 0 第五次 37 例1用伏格尔法得到的初始基可行解 目标函数值 用最小元素法求出的目标函数z 246 一般说来 伏格尔法得出的初始解的质量最好 常用来作为运输问题最优解的近似解 38 第二步 解的最优性检验 闭回路法思路 计算空格 非基变量 的检验数 若令则 如何求检验数 分析 即增加1个单位的检验数 相应的运费增量 39 从初始表分析 要保证产销平衡 则 称为闭回路 1 1 1 1 40 2 1 41 检验数表 2 1 1 1 10 12 表中的解不是最优解 42 第三步 解的调整 从检验数为负值的格出发 做一条除该空格外其余顶点均为有数字格组成的闭回路 在这条闭回路上对空格的运量作最大可能的调整 2 2 2 2 43 调整后的解为 此时的解为最优解 最优解不唯一 44 运输问题练习1 求解运输问题 45 运输问题练习2 有甲乙丙三个商品产地 商品的运出量分别为25t 18t 5t ABCD四个销售地 运入量分别为16t 20t 5t 7t 运输费用与各地之间的运输距离成正比 运输距离和运输量如下表所示 求合理的调运方案及最小吨公里 46 2 位势法所谓位势法 我们对运输表上的每一行赋予一个数值ui 对每一列赋予一个数值vj 它们的数值是由基变量xij的检验数所决定的 则非基变量xij的检验数就可以用公式求出 4 8 7 5 3 6 9 4 5 4 5 3 最优解的判定 47 四 如何找多个最优方案 识别是否有多个最优解的方法 只需看最优方案中是否存在非基变量的检验数