《运筹学教学资料》运筹学第3章第3节.ppt

3 3不平衡的运输问题 所谓不平衡的运输问题是指总产量不等于总销量的运输问题 前面几节所讨论的运输问题都要求总产量等于总销量 因而也称为平衡的运输问题 在实际问题中 产销量往往是不平衡的 为了利用作业法求解 就往往需要把不平衡的运输问题化成平衡的运输问题 其基本思路是引入松弛变量 相当于增加一个虚拟的产地或销地 不平衡的运输问题 一 不平衡的运输问题的类型 供过于求 总产量大于总销量 即 由于总产量大于总销量 某些产地的产量调运不出去 即调运量小于其产量 由此可以建立供过于求的数学模型 不平衡的运输问题 解决方法 由于产品供大于求 应考虑把多余的物资就地贮存 做法上即增加一个虚拟销地Bn 1 虚拟销地Bn 1的总销量为 令xi n 1 是从产地Ai到虚拟销地Bn 1的调运量 它相当于产地Ai的贮存量 不需花运费 因而运价为0 在这个意义下把不平衡运输问题化为了平衡运输问题 不平衡的运输问题 供过于求运输问题的平衡模型 具体求解时 只在运价表右端增加一列Bn 1 运价为零 销量为bn 1即可 不平衡的运输问题 供过于求运输问题的运价表 不平衡的运输问题 供不应求 当供不应求时 总产量小于总销量 即 由于总产量小于总销量 某些销地的需求得不到满足 即调入量小于其销量 由此可以建立供不应求的数学模型 不平衡的运输问题 由于供不应求 则应设想一个虚拟产地Am 1 并让虚拟产地Am 1来供给销地Bj所需物资差额 虚拟产地Am 1的产量为 由于销地实际上不能从虚拟产地Am 1得到供应 故其运价应该是高额的 令 其中 是一个充分大的正数 不平衡的运输问题 供不应求运输问题平衡模型 具体计算时 在运价表的下方增加一行Am 1 运价为零 产量为am 1即可 不平衡的运输问题 供不应求运输问题运价表 不平衡的运输问题 设有三个煤矿供应四个电厂的发电用煤 假定各个煤矿的年产量 各个电厂的备用煤量以及单位运价如表所示 试求运费最省的煤炭调拔方案 例3 不平衡的运输问题 这是一个产销不平衡的运输问题 总产量160个单位 四个电厂的年最低需求为110个单位 小于产量160 根据现有产量 第四个电厂每年最多能再多获得50个单位的供应量 因此 最高总需求为210个单位 大于产量160 为了求得平衡 增加假想的煤矿D 其年产量为50个单位 解题分析1 不平衡的运输问题 由于各电厂的需求有两个部分 如电厂 其最低需求30个单位不能由虚拟产地D供应 如要供应 其运价是一个任意大的正数M 而另一部分20个单位可以满足也可以不满足 因此可由虚拟产地D供应 其运价为0 其它电厂的需求量也可类似处理 从而可得到一个平衡的运输问题 单位运价表与产销平衡表 解题分析2 不平衡的运输问题 利用表上作业法可以求得上述问题的最优方案 总运费为 z 2460 不平衡的运输问题 3 4应用举例 由于运输问题的表上作业法远比一般单纯形算法简单 因而人们在解决一些实际问题时 常设法将其转化为运输问题的数学模型求解 某航运公司承担六个城市A B C D E F的四条航线的物资运输任务 已知各条航线的起点 终点及每天航班数如表1 各城市间的航程如表2 假设各条航线使用相同型号的船只 每条船只每次装卸货物的时间为1天 问该航运公司至少应配备多少条船只才能满足运输要求 表1 表2 应用举例 解 该航运公司所需配备的船只分为两部分 1 航程周转船只 2 港口调度船只 下面分别计算相应的船只数 航程周转船只 如航线1 在港口E装货1天 航程17天 在D卸货1天 总计19天 每天3个航班 故航线1共需周转船只57条 类似计算可得航线2共需周转船只10条 航线3共需周转船只9条 航线4共需周转船只15条 累计共需周转船只91条 应用举例 周转船只 应用举例 港口调度船只 有些港口每天到达船只多于需要船只 如港口D 每天到达3条 需要1条 而有些港口每天到达船只少于需要船只 如港口B 每天到达1条 需要2条 各港口每天调度船只数计算如下 应用举例 调度船只 为了使配备的船只数最少 应做到周转的空船数最少 因此建立相应的运输问题模型 即产销平衡表与单位运价表 应用举例 利用表上作业法求出最优调度方案为 5 2 13 1 17 1 7 1 47 最优调度船只数 建立运输问题模型为 应用举例 某公司经销某产品 该公司具有3个加工厂 每日的产量分别为 A1 7t A2 4t A3 9t 该公司把这些产品分别运往4个销售点 各销售点的每日销售量为 B1 3t B2 6t B3 5t B4 6t 现在假定 1 每个工厂生产的产品不一定直接发运到销售地点 可以其中几个产地集中一起运 2 运往各销售地点的产品可以先运给其中的一些销地 再转运给其它销地 3 除了产 销地之外 中间还可以设置几个转运站 作为在产地之间 销地之间或者产销地之间进行转运 下表为单位运价表 问该公司应该如何调运产品 在考虑直接与非直接运输的各种可能方案下 以及满足各地需要量的前提下 使每天的总运费达到最少 应用举例 应用举例 解 分析1 由于问题中所有的产地 中间转运站 销地都既可以看作是产地也可以看作是销地 所以这个问题可以看作是具有11个产地与销地的扩大的运输问题 2 对于扩大的运输问题我们可以建立其对应的运价表 表中将不可能的运输方案的运价标记为任意大的正数M 3 所有中间转运站的产量等于销量 由于总量为20 所以每一个中转站的运量不会超过20 所以可以规定T1 T2 T3 T4的产销量均为20 4 由于所有的产销地点均可以作为转运站 所以应该在原来的产销量基础上加上20 应用举例 应用举例 运输悖论 在运输问题中 有一种奇怪现象 多运了物资 运费反而下降 这种称为 运输悖论 的现象是与不平衡运输问题有关的 考虑下面的运输问题 请分析一下 在什么情况下才会出现 运输悖论 呢 应用举例 这是一个产销平衡问题 利用表上作业法可得它的一个最优解 基变量取值为 对应的运费是444 应用举例 如果允许产地多运出一些物资 销地可以多运进物资 如给出下述方案 即产地A1 A3都多运出了5个单位物资 销地B2多运进了10个单位物资 这个方案对应总运费是409 应用举例 某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如右表 如果生产出来的柴油机当季不交货 每台每积压一个季度需储存 维护等费用0 15万元 试求在完成合同的情况下 使该厂全年生产总费用为最小的决策方案 应用举例 把第i季度生产的柴油机数目看作第i个生产厂的产量 把第j季度交货的柴油机数目看作第j个销售点的销量 设cij是第i季度生产的第j季度交货的每台柴油机的实际成本 应该等于该季度单位成本加上储存 维护等费用 可构造下列产销平衡问题 解 设xij为第i季度生产的第j季度交货的柴油机数目 那么应满足 交货 x11 10生产 x11 x12 x13 x14 25 x12 x22 15x22 x23 x24 35 x13 x23 x33 25x33 x34 30 x14 x24 x34 x44 20 x44 10 应用举例 由于产大于销 加上一个虚拟的销