不平衡的运输问题课件

《不平衡的运输问题课件》由会员分享，可在线阅读，更多相关《不平衡的运输问题课件（36页珍藏版）》请在装配图网上搜索。

1、不平衡的运输问题PPT课件3.3 不平衡的运输问题不平衡的运输问题所谓所谓不平衡的运输问题不平衡的运输问题是指是指总产量不等于总销量总产量不等于总销量的运输问题。的运输问题。前面几节所讨论的运输问题都要求总产量前面几节所讨论的运输问题都要求总产量等于等于总总销量，因而也称为销量，因而也称为平衡的运输问题平衡的运输问题。在实际问题中，产销量往往是不平衡的，为了利在实际问题中，产销量往往是不平衡的，为了利用作业法求解，就往往需要把不平衡的运输问题用作业法求解，就往往需要把不平衡的运输问题化成平衡的运输问题。化成平衡的运输问题。其基本思路是引入，相当于增加一个其基本思路是引入，相当于增加一个虚拟的产

2、地虚拟的产地或销地或销地。不平衡的运输问题PPT课件一、不平衡的运输问题的类型一、不平衡的运输问题的类型1、供过于求供过于求，总产量大于总销量，即：，总产量大于总销量，即：njjmiiba11由于总产量大于总销量，某些产地的产量调由于总产量大于总销量，某些产地的产量调运不出去，即调运量小于其产量；由此可以运不出去，即调运量小于其产量；由此可以建立供过于求的数学模型：建立供过于求的数学模型：不平衡的运输问题PPT课件1111min(1,2,)(1,2, )0mnijijijnijijmijjiijzc xxa imxbjnx供过于求运输问题的数学模型：供过于求运输问题的数学模型：不平衡的运输问题

3、PPT课件解决方法解决方法：由于产品供大于求，应考虑把多余：由于产品供大于求，应考虑把多余的物资就地贮存，做法上即的物资就地贮存，做法上即增加一个虚拟销地增加一个虚拟销地Bn+1，虚拟销地虚拟销地Bn+1的总销量为：的总销量为：111mnnijijbab令令 xi(n+1) 是从产地是从产地Ai到虚拟销地到虚拟销地Bn+1的调运量，的调运量，它相当于产地它相当于产地 Ai 的贮存量，不需花运费，因而的贮存量，不需花运费，因而运价为运价为0：0)1(nic在这个意义下把不平衡运输问题化为了平衡运在这个意义下把不平衡运输问题化为了平衡运输问题。输问题。不平衡的运输问题PPT课件B1B2BnBn+1

4、产量产量A1c11c12c1n0a1A2c21c22c2n0a2Amcm1cm2cmn0am销量销量b1b2bnbn+1供过于求运输问题的运价表：供过于求运输问题的运价表：111mnnijijbab不平衡的运输问题PPT课件供过于求运输问题的平衡模型：供过于求运输问题的平衡模型： minjijijxcz111min111(1,2,)(1,2,1)0nijijmijjiijxa imxbjnx(1)1110,mni nnijijcbab其中：其中：不平衡的运输问题PPT课件 销地销地产地产地B1B2B3B4产量产量A1152030175A2253016108A3181925206销量销量2454

5、例例1某公司下属有某公司下属有3 3个造纸厂个造纸厂A A1 1、A A2 2和和A A3 3，其纸的产，其纸的产量分别是量分别是5 5吨、吨、8 8吨、吨、6 6吨，有四个集中用户吨，有四个集中用户B B1 1、B B2 2、B B3 3和和B B4 4，其所需用量分别为，其所需用量分别为2 2吨、吨、4 4吨、吨、5 5吨和吨和4 4吨，吨，每个造纸厂到个用户的单位运价如下表所示，问如每个造纸厂到个用户的单位运价如下表所示，问如何组织运输，才能使总运费最少？何组织运输，才能使总运费最少？不平衡的运输问题PPT课件解：解：该该问题由于总产量问题由于总产量1919吨大于总需求量吨大于总需求量1

6、515吨，故吨，故本问题是个产销不平衡问题，增设虚拟销地本问题是个产销不平衡问题，增设虚拟销地B B5 5，其，其需求量为需求量为191915154 4吨，这样就得到了一个产销平吨，这样就得到了一个产销平衡的运输问题，其运价表如下：衡的运输问题，其运价表如下： 销地销地产地产地B1B2B3B4B4产量产量A11520301705A22530161008A31819252006销量销量24544应用表上作业法求解该问题，最优方案：应用表上作业法求解该问题，最优方案：x11=2，x14=1，x23=5，x24=3，x32=4。总费用为。总费用为233。不平衡的运输问题PPT课件2、供不应求供不应求

7、，当供不应求时，总产量小于总，当供不应求时，总产量小于总销量，即：销量，即：11mnijijab由于总产量小于总销量，某些销地的需求得不由于总产量小于总销量，某些销地的需求得不到满足，即调入量小于其销量；由此可以建立到满足，即调入量小于其销量；由此可以建立供不应求的数学模型。供不应求的数学模型。不平衡的运输问题PPT课件供不应求的运输问题的数学模型：供不应求的运输问题的数学模型： 0),2, 1(),2, 1(min1111ijmijijnjiijminjijijxnjbxmiaxxcz不平衡的运输问题PPT课件由于供不应求，则应设想一个虚拟产地由于供不应求，则应设想一个虚拟产地 Am+1，并

8、，并让虚拟产地让虚拟产地 Am+1 来供给销地来供给销地 Bj 所需物资差额。所需物资差额。虚拟产地虚拟产地 Am+1 的产量为：的产量为：miinjjmaba111由于销地实际上不能从虚拟产地由于销地实际上不能从虚拟产地Am+1得到供应，得到供应，故其运价应该是高额的，令故其运价应该是高额的，令Mcjm )1(其中其中 是一个充分大的正数。是一个充分大的正数。不平衡的运输问题PPT课件供不应求运输问题运价表：供不应求运输问题运价表：B1B2Bn产量产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnamAm+1MMMam+1销量销量b1b2bnmiinjjmaba1

9、11不平衡的运输问题PPT课件供不应求运输问题平衡模型供不应求运输问题平衡模型111111min(1, 2,1)(1, 2,)0mnijijijnijijmijjiijzc xxaimxbjnx (1)111,nmmjmjijicM aba其中：其中：不平衡的运输问题PPT课件 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量507030不限不限例例2. 设有三个煤矿供应四个电厂的发电用煤设有三个煤矿供应四个电厂的发电用煤. 假定假定各个煤矿的年产量、各个电厂的备用煤量以及单位各个煤矿的年产量、各个电

10、厂的备用煤量以及单位运价如表所示运价如表所示. 试求运费最省的煤炭调拔方案试求运费最省的煤炭调拔方案.不平衡的运输问题PPT课件解题分析解题分析 1n这是一个产销不平衡的运输问题，总产量这是一个产销不平衡的运输问题，总产量160个单位，个单位，n四个电厂的年最低需求为四个电厂的年最低需求为110个单位。小于产量个单位。小于产量160。n根据现有产量，第四个电厂每年最多能再多获得根据现有产量，第四个电厂每年最多能再多获得50个单个单位的供应量，因此，最高总需求为位的供应量，因此，最高总需求为210个单位，大于产个单位，大于产量量160。n为了求得平衡，增加一个假想的煤矿为了求得平衡，增加一个假想

11、的煤矿D，其年产量为，其年产量为50个单位。个单位。 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量507030不限不限60不平衡的运输问题PPT课件解题分析解题分析 2n由于各电厂的由于各电厂的需求量包含两个部分需求量包含两个部分，如电厂，其最，如电厂，其最低需求低需求30个单位不能由虚拟产地个单位不能由虚拟产地D供应，如要供应，供应，如要供应，其运价是一个任意大的正数其运价是一个任意大的正数M；n而另一部分而另一部分20个单位个单位可以满足也可以不满足可以满足也可以不满足，因此可，因此可由虚拟产

12、地由虚拟产地D供应，其运价为供应，其运价为0；n其它电厂的需求量也可类似处理。其它电厂的需求量也可类似处理。n从而可得到一个平衡的运输问题（单位运价表与产销从而可得到一个平衡的运输问题（单位运价表与产销平衡表）平衡表） 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量50703060不平衡的运输问题PPT课件5010307020305000050232019196015151913141450171722131616 销量产量产地销地MMMDMMCBA|利用表上作业法可以求得上述问题的最优方案。利用表

13、上作业法可以求得上述问题的最优方案。 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量50703060不平衡的运输问题PPT课件5010307020305020305002030603010205050 销量产量产地销地DCBA5010307020305000050232019196015151913141450171722131616 销量产量产地销地MMMDMMCBA总运费为：总运费为：z = 2460.不平衡的运输问题PPT课件n例例1：某化肥公司根据现有订单及对市场的预测估：某化肥公司根据现有

14、订单及对市场的预测估计化肥下一年度每个季度的需求量分别为计化肥下一年度每个季度的需求量分别为10万吨、万吨、25万吨、万吨、25万吨、万吨、10万吨，其每季度的生产能力万吨，其每季度的生产能力分别是分别是20万吨、万吨、25万吨、万吨、15万吨、万吨、10万吨，其生万吨，其生产成本分别产成本分别250万元、万元、280万元、万元、300万元和万元和250万万元。假设在每个季度内产销都是平衡的，又若产元。假设在每个季度内产销都是平衡的，又若产品当季保管及维护费用为品当季保管及维护费用为10万元万元/万吨，要求在满万吨，要求在满足需求量的前提下，如何制定生产计划，才能使足需求量的前提下，如何制定生

15、产计划，才能使全年总成本（包括生产成本和存储费用）最低？全年总成本（包括生产成本和存储费用）最低？3.43.4应用案例应用案例由于运输问题的表上作业法远比一般单纯形算法简由于运输问题的表上作业法远比一般单纯形算法简单，因而人们在解决一些实际问题时，常设法将其单，因而人们在解决一些实际问题时，常设法将其转化为运输问题的数学模型求解。转化为运输问题的数学模型求解。不平衡的运输问题PPT课件表表1250280300250260270280290300310MMMMMMI IIIIIIIIIIIIVIV产量产量I I2020IIII2525IIIIII2525IVIV2020销量销量101025252

16、5251010（1）当月生产当月销售，单位运价）当月生产当月销售，单位运价=生产成本生产成本（2）前月生产后月销售，单位运价）前月生产后月销售，单位运价=生产成本生产成本+存储成本存储成本（3）后月生产前月销售为不可能，运价为）后月生产前月销售为不可能，运价为M解解: :如果把每个季度的产出看作产地，每个季度的如果把每个季度的产出看作产地，每个季度的需求看作销地，它就是一个运输问题。从第需求看作销地，它就是一个运输问题。从第i i个产个产地到第地到第j j个销地的运输价格如下：个销地的运输价格如下：I IIIIIIIIIIIIVIV产量产量I I1010102020IIII252525IIII

17、II151515IVIV10101010销量销量1010252525251010由表上作业法求解得最优方案：由表上作业法求解得最优方案：最小总费用最小总费用=19200不平衡的运输问题PPT课件n例例2：某航运公司承担六个城市某航运公司承担六个城市A、B、C、D、E、F的四条的四条航线的物资运输任务。已知各条航线的起点、终点及每天航航线的物资运输任务。已知各条航线的起点、终点及每天航班数如表班数如表1，各城市间的航程如表，各城市间的航程如表2。假设各条航线使用相同。假设各条航线使用相同型号的船只，每条船只每次装卸货物的时间为型号的船只，每条船只每次装卸货物的时间为1天。问该航天。问该航运公司至

18、少应配备多少条船只才能满足运输要求。运公司至少应配备多少条船只才能满足运输要求。表表1航线航线起点城市起点城市终点城市终点城市每天航班数每天航班数1ED32BC23AF14DB1不平衡的运输问题PPT课件表表2 到到 从从 ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030不平衡的运输问题PPT课件解：解： 该航运公司所需配备的船只分为两部分：该航运公司所需配备的船只分为两部分：（1）航程周转船只；）航程周转船只；（2）港口调度船只；）港口调度船只；下面分别计算相应的船只数。下面分别计算相应的船只数。不平衡的运输问题PPT课件航

19、程周转船只航程周转船只n如航线如航线1，在港口，在港口E装货装货1天，天， 航程航程17天，在天，在D卸货卸货1天，天， 总计总计19天；每天天；每天3个航班，个航班， 故航线故航线1共需周转船只共需周转船只57条。条。n类似计算可得类似计算可得n航线航线2共需周转船只共需周转船只10条；航线条；航线3共需周转船只共需周转船只9条；条；n航线航线4共需周转船只共需周转船只15条；累计共需周转船只条；累计共需周转船只91条。条。航线航线起点城市起点城市 终点城市终点城市每天航班数每天航班数1ED32BC23AF14DB1 到到 从从 ABCDEFA0121477B1031388C2301555D

20、14131501720E7851703F7852030不平衡的运输问题PPT课件周转船只周转船只航线航线装货装货天数天数航程航程天数天数卸货卸货天数天数小记小记航班航班数数周转周转船数船数11171193572131521031719194113115115合计周转船只数合计周转船只数91不平衡的运输问题PPT课件港口调度船只港口调度船只n有些港口每天到达船只多于有些港口每天到达船只多于 需要船只，如港口需要船只，如港口D，每天，每天 到达到达3条，需要条，需要1条；条；n而有些港口每天到达船只少而有些港口每天到达船只少 于需要船只，如港口于需要船只，如港口B，每天，每天 到达到达1条，需要条

21、，需要2条；条；n各港口每天调度船只数计算如下各港口每天调度船只数计算如下航线航线起点城市起点城市 终点城市终点城市每天航班数每天航班数1ED32BC23AF14DB1 从从 到到 ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030不平衡的运输问题PPT课件调度船只调度船只港口城市港口城市每天到达每天到达每天需求每天需求余缺数余缺数A01- 1B12- 1C202D312E03- 3F101n为了使配备的船只数最少，应做到周转的空为了使配备的船只数最少，应做到周转的空船数最少。因此建立相应的运输问题模型，船数最少。因此建立相应的

22、运输问题模型，即产销平衡表与单位运价表即产销平衡表与单位运价表.不平衡的运输问题PPT课件建立运输问题模型为：建立运输问题模型为：ABE余船余船C2352D1413172F7831缺船缺船113利用表上作业法求出最优调度方案为：利用表上作业法求出最优调度方案为：ABE余船余船C22D112F11缺船缺船11352+13 1+17 1+7 1=47.最优调度船只数最优调度船只数因此，在不考虑维修的情况下，该公司至少应配因此，在不考虑维修的情况下，该公司至少应配备的船只数为备的船只数为 91+47=138不平衡的运输问题PPT课件例例3：某公司经销某产品，该公司具有：某公司经销某产品，该公司具有3

23、个加工厂，每个加工厂，每日的产量分别为：日的产量分别为：A1（7t）,A2（4t）,A3（9t）.该公司该公司把这些产品分别运往把这些产品分别运往4个销售点，各销售点的每日销个销售点，各销售点的每日销售量为：售量为： B1（3t）,B2（6t）, B3（5t）,B4（6t）.现在假定现在假定：1、每个工厂生产的产品不一定直接发运、每个工厂生产的产品不一定直接发运到销售地点，可以其中几个产地集中一起运；到销售地点，可以其中几个产地集中一起运；2、运、运往各销售地点的产品可以先运给其中的一些销地，再往各销售地点的产品可以先运给其中的一些销地，再转运给其它销地；转运给其它销地；3、除了产、销地之外，

24、中间还可、除了产、销地之外，中间还可以设置几个转运站，作为在产地之间、销地之间或者以设置几个转运站，作为在产地之间、销地之间或者产销地之间进行转运。下表为单位运价表，问该公司产销地之间进行转运。下表为单位运价表，问该公司应该如何调运产品，在考虑直接与非直接运输的各种应该如何调运产品，在考虑直接与非直接运输的各种可能方案下，以及满足各地需要量的前提下，使每天可能方案下，以及满足各地需要量的前提下，使每天的总运费达到最少？的总运费达到最少？不平衡的运输问题PPT课件产地产地中间转运站中间转运站销地销地A1A2A3T1T2T3T4B1B2B3B4产产地地A1132143311310A21-35-21

25、928A33-1-2374105中中间间转转运运站站T12311322846T215-1114527T34-23421824T43232121-26销销地地B13172411142B21194858-121B332104222423B410856746213不平衡的运输问题PPT课件解：分析解：分析1、由于问题中所有的产地、中间转运站、销地都、由于问题中所有的产地、中间转运站、销地都既可以看作是产地也可以看作是销地，所以这个既可以看作是产地也可以看作是销地，所以这个问题可以看作是具有问题可以看作是具有11个产地与销地的扩大的运个产地与销地的扩大的运输问题输问题.2、对于扩大的运输问题我们可以建

26、立其对应的运、对于扩大的运输问题我们可以建立其对应的运价表，表中将不可能的运输方案的运价标记为任价表，表中将不可能的运输方案的运价标记为任意大的正数意大的正数M.3、所有中间转运站的产量等于销量，由于总量为、所有中间转运站的产量等于销量，由于总量为20，所以每一个中转站的运量不会超过，所以每一个中转站的运量不会超过20，所以，所以可以规定可以规定T1、T2、T3、T4的产销量均为的产销量均为20。4、由于所有的产销地点均可以作为转运站，所以、由于所有的产销地点均可以作为转运站，所以应该在原来的产销量基础上加上应该在原来的产销量基础上加上20。不平衡的运输问题PPT课件A1A2A3T1T2T3T

27、4B1B2B3B4 产量产量A1013214331131027A210M35M2192824A33M01M237410529T12310132284620T215M1011452720T34M23402182420T432321201M2620B13172411014220B21194858M102120B332104222420320B410856746213020销量销量20202020202020232625260不平衡的运输问题PPT课件作业作业n教材教材P130 第第1题题 表表3-25 P131 第第3题、第题、第4题题 不平衡的运输问题PPT课件运输悖论运输悖论n在运输问题中，有

28、一种奇怪现象在运输问题中，有一种奇怪现象“多运多运了物资，运费反而下降了物资，运费反而下降”.n这种称为这种称为“运输悖论运输悖论”的现象是与不平的现象是与不平衡运输问题有关的。衡运输问题有关的。n考虑下面的运输问题考虑下面的运输问题.n请分析一下：请分析一下：在什么情况下才会出现在什么情况下才会出现“运输悖论运输悖论”呢？呢？不平衡的运输问题PPT课件1181211415109184126541158181613229167141361514432154321AAAABBBBBn这是一个产销平衡问题，这是一个产销平衡问题，利用表上作业法可得它的利用表上作业法可得它的一个最优解一个最优解,基变

29、量取值为基变量取值为13212224333542457,4,6,8,5,1,5,10 xxxxxxxx11812114151056151886477432154321AAAABBBBB对应的运费是对应的运费是444不平衡的运输问题PPT课件n如果允许产地多运出一些物资，销地可以多运进物资。如果允许产地多运出一些物资，销地可以多运进物资。n如给出下述方案：如给出下述方案：,15,11, 8, 6, 4,12423524222113xxxxxx|即产地即产地A1、A3都多运出了都多运出了5个单位物资，销地个单位物资，销地B2多运进了多运进了5个单位物资。个单位物资。|这个方案对应总运费是这个方案对应总运费是409。1234512347 57 5468186 5 6 55 51015411 512811BBBBBAAAA 12345123477468185165101541112811BBBBBAAAA