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

《《不平衡的运输问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《不平衡的运输问题》PPT课件.ppt（36页珍藏版）》请在三一办公上搜索。

1、3.3 不平衡的运输问题,所谓不平衡的运输问题是指总产量不等于总销量的运输问题。前面几节所讨论的运输问题都要求总产量等于总销量，因而也称为平衡的运输问题。,在实际问题中，产销量往往是不平衡的，为了利用作业法求解，就往往需要把不平衡的运输问题化成平衡的运输问题。其基本思路是引入松弛变量，相当于增加一个虚拟的产地或销地。,一、不平衡的运输问题的类型,1、供过于求，总产量大于总销量，即：,由于总产量大于总销量，某些产地的产量调运不出去，即调运量小于其产量；由此可以建立供过于求的数学模型：,供过于求运输问题的数学模型：,解决方法：由于产品供大于求，应考虑把多余的物资就地贮存，做法上即增加一个虚拟销地B

2、n+1，虚拟销地Bn+1的总销量为：,令 xi(n+1)是从产地Ai到虚拟销地Bn+1的调运量，它相当于产地 Ai 的贮存量，不需花运费，因而运价为0：,在这个意义下把不平衡运输问题化为了平衡运输问题。,供过于求运输问题的运价表：,供过于求运输问题的平衡模型：,其中：,例1某公司下属有3个造纸厂A1、A2和A3，其纸的产量分别是5吨、8吨、6吨，有四个集中用户B1、B2、B3和B4，其所需用量分别为2吨、4吨、5吨和4吨，每个造纸厂到个用户的单位运价如下表所示，问如何组织运输，才能使总运费最少？,解：该问题由于总产量19吨大于总需求量15吨，故本问题是个产销不平衡问题，增设虚拟销地B5，其需求

3、量为19154吨，这样就得到了一个产销平衡的运输问题，其运价表如下：,应用表上作业法求解该问题，最优方案：x11=2，x14=1，x23=5，x24=3，x32=4。总费用为233。,2、供不应求，当供不应求时，总产量小于总销量，即：,由于总产量小于总销量，某些销地的需求得不到满足，即调入量小于其销量；由此可以建立供不应求的数学模型。,供不应求的运输问题的数学模型：,由于供不应求，则应设想一个虚拟产地 Am+1，并让虚拟产地 Am+1 来供给销地 Bj 所需物资差额。虚拟产地 Am+1 的产量为：,由于销地实际上不能从虚拟产地Am+1得到供应，故其运价应该是高额的，令,其中 是一个充分大的正数

4、。,供不应求运输问题运价表：,供不应求运输问题平衡模型,其中：,例2.设有三个煤矿供应四个电厂的发电用煤.假定各个煤矿的年产量、各个电厂的备用煤量以及单位运价如表所示.试求运费最省的煤炭调拔方案.,解题分析 1,这是一个产销不平衡的运输问题，总产量160个单位，四个电厂的年最低需求为110个单位。小于产量160。根据现有产量，第四个电厂每年最多能再多获得50个单位的供应量，因此，最高总需求为210个单位，大于产量160。为了求得平衡，增加一个假想的煤矿D，其年产量为50个单位。,60,解题分析 2,由于各电厂的需求量包含两个部分，如电厂，其最低需求30个单位不能由虚拟产地D供应，如要供应，其运

5、价是一个任意大的正数M；而另一部分20个单位可以满足也可以不满足，因此可由虚拟产地D供应，其运价为0；其它电厂的需求量也可类似处理。从而可得到一个平衡的运输问题（单位运价表与产销平衡表）,利用表上作业法可以求得上述问题的最优方案。,总运费为：z=2460.,例1：某化肥公司根据现有订单及对市场的预测估计化肥下一年度每个季度的需求量分别为10万吨、25万吨、25万吨、10万吨，其每季度的生产能力分别是20万吨、25万吨、15万吨、10万吨，其生产成本分别250万元、280万元、300万元和250万元。假设在每个季度内产销都是平衡的，又若产品当季保管及维护费用为10万元/万吨，要求在满足需求量的前

6、提下，如何制定生产计划，才能使全年总成本（包括生产成本和存储费用）最低？,3.4应用案例,由于运输问题的表上作业法远比一般单纯形算法简单，因而人们在解决一些实际问题时，常设法将其转化为运输问题的数学模型求解。,表1,250,280,300,250,260,270,280,290,300,310,M,M,M,M,M,M,（1）当月生产当月销售，单位运价=生产成本,（2）前月生产后月销售，单位运价=生产成本+存储成本,（3）后月生产前月销售为不可能，运价为M,解:如果把每个季度的产出看作产地，每个季度的需求看作销地，它就是一个运输问题。从第i个产地到第j个销地的运输价格如下：,由表上作业法求解得最

7、优方案：,最小总费用=19200,例2：某航运公司承担六个城市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条；

8、航线4共需周转船只15条；累计共需周转船只91条。,周转船只,港口调度船只,有些港口每天到达船只多于 需要船只，如港口D，每天 到达3条，需要1条；而有些港口每天到达船只少 于需要船只，如港口B，每天 到达1条，需要2条；各港口每天调度船只数计算如下,调度船只,为了使配备的船只数最少，应做到周转的空船数最少。因此建立相应的运输问题模型，即产销平衡表与单位运价表.,建立运输问题模型为：,利用表上作业法求出最优调度方案为：,52+13 1+17 1+7 1=47.,最优调度船只数,因此，在不考虑维修的情况下，该公司至少应配备的船只数为 91+47=138,例3：某公司经销某产品，该公司具有3个加工

9、厂，每日的产量分别为：A1（7t）,A2（4t）,A3（9t）.该公司把这些产品分别运往4个销售点，各销售点的每日销售量为：B1（3t）,B2（6t）,B3（5t）,B4（6t）.现在假定：1、每个工厂生产的产品不一定直接发运到销售地点，可以其中几个产地集中一起运；2、运往各销售地点的产品可以先运给其中的一些销地，再转运给其它销地；3、除了产、销地之外，中间还可以设置几个转运站，作为在产地之间、销地之间或者产销地之间进行转运。下表为单位运价表，问该公司应该如何调运产品，在考虑直接与非直接运输的各种可能方案下，以及满足各地需要量的前提下，使每天的总运费达到最少？,解：分析1、由于问题中所有的产地

10、、中间转运站、销地都既可以看作是产地也可以看作是销地，所以这个问题可以看作是具有11个产地与销地的扩大的运输问题.2、对于扩大的运输问题我们可以建立其对应的运价表，表中将不可能的运输方案的运价标记为任意大的正数M.3、所有中间转运站的产量等于销量，由于总量为20，所以每一个中转站的运量不会超过20，所以可以规定T1、T2、T3、T4的产销量均为20。4、由于所有的产销地点均可以作为转运站，所以应该在原来的产销量基础上加上20。,作业,教材P130 第1题 表3-25 P131 第3题、第4题,运输悖论,在运输问题中，有一种奇怪现象“多运了物资，运费反而下降”.这种称为“运输悖论”的现象是与不平衡运输问题有关的。考虑下面的运输问题.请分析一下：在什么情况下才会出现“运输悖论”呢？,这是一个产销平衡问题，利用表上作业法可得它的一个最优解,基变量取值为,对应的运费是444,如果允许产地多运出一些物资，销地可以多运进物资。如给出下述方案：,即产地A1、A3都多运出了5个单位物资，销地B2多运进了5个单位物资。这个方案对应总运费是409。,