《不平衡的运输问题》PPT课件.ppt

3.3 不平衡的运输问题 所谓不平衡的运输问题是指总产量不等于总销量 的运输问题。 前面几节所讨论的运输问题都要求总产量等于总 销量，因而也称为平衡的运输问题。 在实际问题中，产销量往往是不平衡的，为了利 用作业法求解，就往往需要把不平衡的运输问题 化成平衡的运输问题。 其基本思路是引入松弛变量，相当于增加一个虚 拟的产地或销地。 一、不平衡的运输问题的类型 1、供过于求，总产量大于总销量，即： 由于总产量大于总销量，某些产地的产量调 运不出去，即调运量小于其产量；由此可以 建立供过于求的数学模型： 供过于求运输问题的数学模型： 解决方法：由于产品供大于求，应考虑把多余 的物资就地贮存，做法上即增加一个虚拟销地 Bn+1，虚拟销地Bn+1的总销量为： 令 xi(n+1) 是从产地Ai到虚拟销地Bn+1的调运量， 它相当于产地 Ai 的贮存量，不需花运费，因而 运价为0： 在这个意义下把不平衡运输问题化为了平衡运 输问题。 B1B2BnBn+1产量 A1c11c12c1n0a1 A2c21c22c2n0a2 Amcm1cm2cmn0am 销量b1b2bnbn+1 供过于求运输问题的运价表： 供过于求运输问题的平衡模型： 其中： 销销地 产产地 B1B2B3B4产产量 A1152030175 A2253016108 A3181925206 销销量2454 例1某公司下属有3个造纸厂A1、A2和A3，其纸的产 量分别是5吨、8吨、6吨，有四个集中用户B1、B2、 B3和B4，其所需用量分别为2吨、4吨、5吨和4吨， 每个造纸厂到个用户的单位运价如下表所示，问如 何组织运输，才能使总运费最少？ 解：该问题由于总产量19吨大于总需求量15吨，故 本问题是个产销不平衡问题，增设虚拟销地B5，其 需求量为19154吨，这样就得到了一个产销平 衡的运输问题，其运价表如下： 销销地 产产地 B1B2B3B4B4产产量 A11520301705 A22530161008 A31819252006 销销量24544 应用表上作业法求解该问题，最优方案：x11=2 ，x14=1，x23=5，x24=3，x32=4。总费用为 233。 2、供不应求，当供不应求时，总产量小于总 销量，即： 由于总产量小于总销量，某些销地的需求得不 到满足，即调入量小于其销量；由此可以建立 供不应求的数学模型。 供不应求的运输问题的数学模型： 由于供不应求，则应设想一个虚拟产地 Am+1，并 让虚拟产地 Am+1 来供给销地 Bj 所需物资差额。 虚拟产地 Am+1 的产量为： 由于销地实际上不能从虚拟产地Am+1得到供应， 故其运价应该是高额的，令 其中 是一个充分大的正数。 供不应求运输问题运价表： B1B2Bn产量 A1c11c12c1na1 A2c21c22c2na2 Amcm1cm2cmnam Am+1MMMam+1 销量b1b2bn 供不应求运输问题平衡模型 其中： 电厂 煤矿 产量 A1613221750 B1413191560 C192023-50 最低需要量3070010 最高需求量507030不限 例2. 设有三个煤矿供应四个电厂的发电用煤. 假定 各个煤矿的年产量、各个电厂的备用煤量以及单位 运价如表所示. 试求运费最省的煤炭调拔方案. 解题分析 1 n这是一个产销不平衡的运输问题，总产量160个单位 ， n四个电厂的年最低需求为110个单位。小于产量160。 n根据现有产量，第四个电厂每年最多能再多获得50个 单位的供应量，因此，最高总需求为210个单位，大于产 量160。 n为了求得平衡，增加一个假想的煤矿D，其年产量为 50个单位。 电厂 煤矿 产量 A1613221750 B1413191560 C192023-50 最低需要量3070010 最高需求量507030不限 60 解题分析 2 n由于各电厂的需求量包含两个部分，如电厂，其 最低需求30个单位不能由虚拟产地D供应，如要供应，其 运价是一个任意大的正数M； n而另一部分20个单位可以满足也可以不满足，因此 可由虚拟产地D供应，其运价为0； n其它电厂的需求量也可类似处理。 n从而可得到一个平衡的运输问题（单位运价表与产 销平衡表） 电厂 煤矿 产量 A1613221750 B1413191560 C192023-50 最低需要量3070010 最高需求量50703060 |利用表上作业法可以求得上述问题的最优方案。 电厂 煤矿 产量 A1613221750 B1413191560 C192023-50 最低需要量3070010 最高需求量50703060 总运费为：z = 2460. n例1：某化肥公司根据现有订单及对市场的预测 估计化肥下一年度每个季度的需求量分别为10万吨 、25万吨、25万吨、10万吨，其每季度的生产能力 分别是20万吨、25万吨、15万吨、10万吨，其生产 成本分别250万元、280万元、300万元和250万元。 假设在每个季度内产销都是平衡的，又若产品当季 保管及维护费用为10万元/万吨，要求在满足需求量 的前提下，如何制定生产计划，才能使全年总成本 （包括生产成本和存储费用）最低？ 3.4应用案例 由于运输问题的表上作业法远比一般单纯形算法简 单，因而人们在解决一些实际问题时，常设法将其 转化为运输问题的数学模型求解。 表1 250 280 300 250 260270280 290300 310 M MM MMM IIIIIIIV产产量 I 20 II 25 III 25 IV 20 销销量10252510 （1）当月生产当月销售，单位运价=生产成本 （2）前月生产后月销售，单位运价=生产成本+存储成本 （3）后月生产前月销售为不可能，运价为M 解:如果把每个季度的产出看作产地，每个季度的 需求看作销地，它就是一个运输问题。从第i个产 地到第j个销地的运输价格如下： IIIIIIIV产产量 I 10 1020 II 2525 III 1515 IV 10 10 销销量10252510 由表上作业法求解得最优方案： 最小总费用=19200 n例2：某航运公司承担六个城市A、B、C、D、E、F的四 条航线的物资运输任务。已知各条航线的起点、终点及每天航 班数如表1，各城市间的航程如表2。假设各条航线使用相同型 号的船只，每条船只每次装卸货物的时间为1天。问该航运公司 至少应配备多少条船只才能满足运输要求。 表1 航线起点城市终点城市每天航班数 1ED3 2BC2 3AF1 4DB1 表2 到 从 ABCDEF A0121477 B1031388 C2301555 E7851703 F7852030 解：该航运公司所需配备的船只分为两部分 ： （1）航程周转船只； （2）港口调度船只； 下面分别计算相应的船只数。 航程周转船只 n如航线1，在港口E装货1天， 航程17天，在D卸货1天， 总计19天；每天3个航班， 故航线1共需周转船只57条。 n类似计算可得 n航线2共需周转船只10条；航线3共需周转船只9条； n航线4共需周转船只15条；累计共需周转船只91条。 航线起点城市终点城市每天航班数 1ED3 2BC2 3AF1 4DB1 到 从 ABCDEF A0121477 B1031388 C2301555 E7851703 F7852030 周转船只 航线装货 天数 航程 天数 卸货 天数 小记航班 数 周转 船数 1117119357 21315210 3171919 4113115115 合计周转船只数91 港口调度船只 n有些港口每天到达船只多于 需要船只，如港口D，每天 到达3条，需要1条； n而有些港口每天到达船只少 于需要船只，如港口B，每天 到达1条，需要2条； n各港口每天调度船只数计算如下 航线起点城市终点城市每天航班数 1ED3 2BC2 3AF1 4DB1 从 到 ABCDEF A0121477 B1031388 C2301555 E7851703 F7852030 调度船只 港口城市每天到达每天需求余缺数 A01- 1 B12- 1 C202 D312 E03- 3 F101 n为了使配备的船只数最少，应做到周转的 空船数最少。因此建立相应的运输问题模型， 即产销平衡表与单位运价表. 建立运输问题模型为： ABE余船 C2352 D1413172 F7831 缺船113 利用表上作业法求出最优调度方案为： ABE余船 C22 D112 F11 缺船113 52+13 1+17 1+7 1=47.最优调度船只数 因此，在不考虑维修的情况下，该公司至少应 配 备的船只数为 91+47=138 例3：某公司经销某产品，该公司具有3个加工厂，每 日的产量分别为：A1（7t）,A2（4t）,A3（9t）.该公司 把这些产品分别运往4个销售点，各销售点的每日销 售量为： B1（3t）,B2（6t）, B3（5t）,B4（6t）. 现在假定：1、每个工厂生产的产品不一定直接发运 到销售地点，可以其中几个产地集中一起运；2、运 往各销售地点的产品可以先运给其中的一些销地，再 转运给其它销地；3、除了产、销地之外，中间还可 以设置几个转运站，作为在产地之间、销地之间或者 产销地之间进行转运。下表为单位运价表，问该公司 应该如何调运产品，在考虑直接与非直接运输的各种 可能方案下，以及满足各地需要量的前提下，使每天 的总运费达到最少？ 产地中间转运站销地 A1A2A3T1T2T3T4B1B2B3B4 产 地 A1132143311310 A21-35-21928 A33-1-2374105 中 间 转 运 站 T12311322846 T215-1114527 T34-23421824 T43232121-26 销 地 B21194858-121 B332104222423 B410856746213 解：分析 1、由于问题中所有的产地、中间转运站、销地都 既可以看作是产地也可以看作是销地，所以这个 问题可以看作是具有11个产地与销地的扩大的运 输问题. 2、对于扩大的运输问题我们可以建立其对应的运 价表，表中将不可能的运输方案的运价标记为任 意大的正数M. 3、所有中间转运站的产量等于销量，由于总量为 20，所以每一个中转站的运量不会超过20，所以 可以规定T1、T2、T3、T4的产销量均为20。 4、由于所有的产销地点均可以作为转运站，所以 应该在原来的产销量基础上加上20。 A1A2A3T1T2T3T4B1B2B3B4 产量 A1013214331131027 A210M35M2192824 A33M01M237410529 T12310132284620 T215M1011452720 T34M23402182420 T432321201M2620 B13172411014220 B21194858M102120 B332104222420320 B410856746213020 销量20202020202020232625260 作业 n教材P130 第1题 表3-25 P131 第3题、第