7运输问题(清华2).ppt

1、3-3 非平衡调运及其他问题 当供应大于需求时，就在初始表上加一列，可以认为增加一个收点，其收量等于供应量与需求量之差。这个收点认为是一个仓库（虚拟的销售区），其收量为库存量。,当供应小于需求时，就在初始表上加一行，可以认为增加一个发点，其发量等于需求量与供应量之差。这个发点认为是一个虚拟的生产单位，其发量实际为缺货量。,无论增加行还是列，都增加了变量，假定增加的变量所对应的运费为零。 经过上述处理后，任何非平衡问题都化成平衡问题。,例3-2（例3-1） 某石油公司设有四个炼油厂，它们生产普通汽油，并为七个销售区服务，需求变化情况如下：,从炼油厂运往第j个销售区每公升汽油平均运费（单位：角/公

2、升），应如何调运，使运费最省。,解：现在变成供应小于需求的问题，增加一个发点5。用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,用最小元素法求初始方案。,计算检验数,（1，7）闭回路,调整运量=10，得到新的调运方案。,计算检验数。,（4，5）闭回路。,得到新的调运方案。,计算检验数全非正，得到最优方案。,得到最优方案，最小运费=4150000（角）=41000（元）。,销售区4，6分

3、别缺货15万升，20万升。,例3-3 某印刷厂收到了印刷五批标准规格的广告单的订货。五批所需数量分别为12000张，18000张，25000张，30000张，20000张。现有三台印刷机，每天分别可印刷60000张，80000张，50000张。在各台印刷机上印刷每批订货的每千张的费用如下（单位元/千张）如何分配印刷机的印刷任务，使印刷费用最低？,解：供大于求的问题，广告单的单位改成千张，,最小元素方法,最小元素方法,最小元素方法,最小元素方法,最小元素方法,最小元素方法,最小元素方法，得到初始方案， 总费用=27680000（元）,计算检验数，全为非正，得到最优方案.,最优方案如下， 总费用=

4、27680000（元）=2768（万元）,例3-4 有四项任务要分配给四个人去完成，每人一项。各人完成工作所需时间如下表。如何安排工作才能使完成工作的总时间最短。,解：设xij表示Ai工作是否指派Bj去做，并约定： xij=1 Ai工作指派Bj去做 xij=0 Ai工作不指派Bj去做 于是得到指派问题的数学模型，它与运输问题相似，所以可用运输问题的方法求解。,指派问题的数学模型： Min S= cijxij i j xij =1 (i=1,2.m) j xij =1 (j=1,2n) i xij=0或1 (i=1,2.m; j=1,2n),用最小元素法求解：,用最小元素法求解：,用最小元素法求

5、解：,用最小元素法求解：,得到初始方案： 总时间=3*1+4*1+15*1+9*1=31小时,计算检验数（A3，B1）为正。,寻找闭回路。,调整分配。得到新的分配方案， 总时间=29（小时）,计算检验数，全为非正，得到最优方案。,最优方案：B1-A3，B2-A2，B3-A4，B4-A1。总时间=29（小时）,例3-5 要在五个不同地区设专卖商店。由于不同地区人们的消费水平及运输费用不同，财会部门经调查提供了有关三个工厂根据自己的产量计划建商店的数目、五个地区的需求量及年利润预算报告如下，应该 如何选择专卖商店地址，使年利润最大？,解：将Cij转换成- Cij ，问题由求利润最大变成求最小费用。

6、,最小元素法。,最小元素法。,最小元素法。,最小元素法。,最小元素法。,最小元素法。,最小元素法，得到初始方案。,计算检验数，（A3，B4）为正。,闭回路,得到新方案。,计算检验数，全为非正。,得到最优方案。 最大利润=196（百万元）,当某个发点Ai由于某种原因不能向某个收点Bj供应产品时，设相应的运费Cij为M（M充分地大），然后进行求最优解。在最优解中，若相应的xij取0值，则此最优解为原问题的最优解；否则，原问题无解。,例3-6 某罐头厂有三个分厂，向三个地区供应其产品，数据如下。其中第二分厂不能向C地供应产品。如何调配，利润最大？,解：设第二分厂运往C地费用为一个充分大的数M，即C2

7、3= -M，利润最大化变成最小。,最小元素法，确定初始方案。,最小元素法，确定初始方案。,最小元素法，确定初始方案。,最小元素法，确定初始方案。,计算检验数：（1，C）为正，而且最大,闭回路,调整供应量=10，得到新方案,计算检验数，全为非正，得到最优方案。,最优方案，最大利润=230（万元）,3-4 转运问题 运输问题中，一般假定产地只输出，销地只输入，在有的运输问题中，产地可以输入，销地可以输出。 在运输问题中还会遇到：由一产地直接到销地A的路程比经过其他产地和销地，甚至中转地到A的路程远。,在转运问题中的假设： 产地兼中转地的输出量超过输入量。比如设运到各产地的输入量都为Q（Q是大于ai

8、总和的一个数），则产地i的输出量为ai+Q。 各销地的输入量超过输出量。比如设各销地的输出量为Q，则销地j的输出量为bj+Q。 。,例3-7 已知从产地A1、A2到销地B1、B2、B3的直接运价表，生产地之间的运价表，销地之间的运价表如下，要制定运费最小的转运方案。,解：由于产地的总产量=120，可以令Q=150,最小元素法,最小元素法,最小元素法,最小元素法,最小元素法,得到初始方案,计算检验数，（B3，B1）为正且最大,调整运量，寻找闭回路。,调整运量=25。,得到新的运输方案,计算检验数，全为非正，得到最优化方案,得到最优化方案,最优调运方案： 生产地 销地 发货量 A1- B3 80

9、A2- B1 5 A2- B2 35 B3- B1 25 总运费=1105（元） 如果不考虑转运方式，直接调运最优方案总费用=1130（元）,3-5 运输问题的悖论 在运输问题中，有一种在若干个产、销地的运价不变的情况下，当调运量增加，总运费反而会下降的奇怪现象。这就是运输问题的悖论,有一位调度员上月做了一个最优调度如下（检验数全为非正）,总运费=6*7+16*4+9*6+13*8+11*5+5*1+4*5+10*10=444（千元） 总运量=46（千吨）,这个月运价不变的前提下，A1，A3的产量增加了5千吨，销地B2的销售量增加了10千吨，其余的产、销地不变，则最优表如下,总运费=6*12+

10、16*4+9*6+13*8+5*11+4*15 =409（千元）（比上月减少35千元） 总运量=56（千吨）（比上月增加10千吨）,为什么会出现这种现象？ 原最优表中存在这样闭回路,空格（A1，B2）存在闭回路（A1，B2）-（A1，B3）-（A3，B3）-（A3，B5）-（A4，B2）有如下特征： （1）空格处的行列位势和为负数，即 u1+v2= -15+9= -6 （2）这条路有奇数个数字格（7，5，1，10，5）被偶数条横线和竖线（三横三竖共6条）依次交错的连接着。,（3）第奇数位数字格的运价减去偶数位数字格运价之代数和为负，即： C13-C33+C35-C45+C42 = 6-11+5-10+4 = -6 （4）第偶数位数字格最小运输量为正。 最小运输量=Min（X33，X45）= 5 满足上述条件的回路称为负费用路。 调整运量5