《运筹学教学资料运筹学第3章第3节ppt课件》由会员分享，可在线阅读，更多相关《运筹学教学资料运筹学第3章第3节ppt课件（33页珍藏版）》请在金锄头文库上搜索。
1、-1-China University of Mining and Technology运筹学 3.3 不平衡的运输问题-2-China University of Mining and Technology运筹学 |所所谓不平衡的运不平衡的运输问题是指是指总产量不等于量不等于总销量的运量的运输问题。|前面几前面几节所所讨论的运的运输问题都要求都要求总产量等于量等于总销量，量，因此也称因此也称为平衡的运平衡的运输问题。|在在实践践问题中，中，产销量往往是不平衡的，量往往是不平衡的，为了利用作了利用作业法求解，就往往需求把不平衡的运法求解，就往往需求把不平衡的运输问题化成平衡的运化成平衡的运输问
2、题。|其根本思其根本思绪是引入松弛是引入松弛变量，相当于添加一个虚量，相当于添加一个虚拟的的产地或地或销地。地。不不平平衡衡的的运运输输问问题题-3-China University of Mining and Technology运筹学 一、不平衡的运一、不平衡的运一、不平衡的运一、不平衡的运输问题输问题的的的的类类型型型型 供供过于求，于求，总产量大于量大于总销量，即：量，即：由于由于总产量大于量大于总销量，某些量，某些产地的地的产量量调运不出去，即运不出去，即调运量小于其运量小于其产量；由此可以建量；由此可以建立供立供过于求的数学模型：于求的数学模型：不不平平衡衡的的运运输输问问题题-4
3、-China University of Mining and Technology运筹学 处理方法：由于理方法：由于产品供大于求，品供大于求，应思索把多余的物思索把多余的物资就地就地储存，做法上即添加一个虚存，做法上即添加一个虚拟销地地Bn+1，虚，虚拟销地地Bn+1的的总销量量为：令令 xi(n+1) 是从是从产地地Ai到虚到虚拟销地地Bn+1的的调运量，它相当于运量，它相当于产地地 Ai 的的储存量，不需花运存量，不需花运费，因此运价，因此运价为0：在在这个意个意义下把不平衡运下把不平衡运输问题化化为了平衡运了平衡运输问题。不不平平衡衡的的运运输输问问题题-5-China Univers
4、ity of Mining and Technology运筹学 供过于求运输问题的平衡模型：供过于求运输问题的平衡模型：详细求解求解时, ,只在只在运价表右端添加运价表右端添加一列一列Bn+1Bn+1，运价，运价为零零, ,销量量为bn+1bn+1即可即可不不平平衡衡的的运运输输问问题题-6-China University of Mining and Technology运筹学 B1B2BnBn+1产量产量A1c11c12c1n0a1A2c21c22c2n0a2Amcm1cm2cmn0am销量销量b1b2bnbn+1供过于求运输问题的运价表：供过于求运输问题的运价表：不不平平衡衡的的运运输输
5、问问题题-7-China University of Mining and Technology运筹学 供不供不应求，当供不求，当供不应求求时，总产量小于量小于总销量，即：量，即：由于由于总产量小于量小于总销量，量，某些某些销地的需求得不到地的需求得不到满足，即足，即调入量小于其入量小于其销量；由此可以建立供量；由此可以建立供不不应求的数学模型。求的数学模型。不不平平衡衡的的运运输输问问题题-8-China University of Mining and Technology运筹学 由于供不由于供不应求，那么求，那么应想象一个虚想象一个虚拟产地地 Am+1，并，并让虚虚拟产地地 Am+1 来
6、供来供应销地地 Bj 所需物所需物资差差额。虚。虚拟产地地 Am+1 的的产量量为：由于由于销地地实践上不能从虚践上不能从虚拟产地地Am+1得到供得到供应，故其运价，故其运价应该是高是高额的，令的，令其中其中 是一个充分大的正数。是一个充分大的正数。不不平平衡衡的的运运输输问问题题-9-China University of Mining and Technology运筹学 供不应求运输问题平衡模型供不应求运输问题平衡模型详详细细计计算算时时，在在运运价价表表的的下下方方 添添 加加 一一 行行Am+1， 运运 价价为为零零。产产量量为为a m + 1即即 可可 。不不平平衡衡的的运运输输问问
7、题题-10-China University of Mining and Technology运筹学 供不应求运输问题运价表：供不应求运输问题运价表：B1B2Bn产量产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnamAm+1MMMam+1销量销量b1b2bn不不平平衡衡的的运运输输问问题题-11-China University of Mining and Technology运筹学 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量507030不限不限设有三个煤矿供应四
8、个电厂的发电用煤设有三个煤矿供应四个电厂的发电用煤. 假定各个煤矿的假定各个煤矿的年产量、各个电厂的备用煤量以及单位运价如表所示。年产量、各个电厂的备用煤量以及单位运价如表所示。 试求运费最省的煤炭调拔方案。试求运费最省的煤炭调拔方案。例例3不不平平衡衡的的运运输输问问题题-12-China University of Mining and Technology运筹学 这是一个是一个产销不平衡的运不平衡的运输问题，总产量量160个个单位，位，四个四个电厂的年最低需求厂的年最低需求为110个个单位。小于位。小于产量量160。根据根据现有有产量，第四个量，第四个电厂每年最多能再多厂每年最多能再多获
9、得得50个个单位位的供的供应量，因此，最高量，因此，最高总需求需求为210个个单位，大于位，大于产量量160。为了求得平衡，添加假想的煤了求得平衡，添加假想的煤矿D，其年，其年产量量为50个个单位。位。 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量507030不限不限解解题题分分析析 1不不平平衡衡的的运运输输问问题题-13-China University of Mining and Technology运筹学 由于各由于各电厂的需求有两个部分，如厂的需求有两个部分，如电厂，其最低需求厂，其最低
10、需求30个个单位不能由虚位不能由虚拟产地地D供供应，如要供，如要供应，其运价是一个恣意大，其运价是一个恣意大的正数的正数M；而另一部分而另一部分20个个单位可以位可以满足也可以不足也可以不满足，因此可由虚足，因此可由虚拟产地地D供供应，其运价，其运价为0；其它其它电厂的需求量也可厂的需求量也可类似似处置。置。从而可得到一个平衡的运从而可得到一个平衡的运输问题单位运价表与位运价表与产销平衡表平衡表 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量50703060解解题题分分析析 2不不平平衡衡的的运运输
11、输问问题题-14-China University of Mining and Technology运筹学 利用表上作利用表上作业法可以求法可以求得上述得上述问题的最的最优方案。方案。 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量50703060总运运费为：z = 2460.不不平平衡衡的的运运输输问问题题-15-China University of Mining and Technology运筹学 3.4 应 用 举 例由于运由于运输问题的表上作的表上作业法法远比普通比普通单纯形算形算法法简单
12、，因此人，因此人们在在处理一些理一些实践践问题时，常，常设法将其法将其转化化为运运输问题的数学模型求解。的数学模型求解。-16-China University of Mining and Technology运筹学 某航运公司承当六个城市某航运公司承当六个城市A、B、C、D、E、F的四条航线的的四条航线的物资运输义务。知各条航线的起点、终点及每天航班数如表物资运输义务。知各条航线的起点、终点及每天航班数如表1，各城市间的航程如表各城市间的航程如表2。假设各条航线运用一样型号的船只，每条。假设各条航线运用一样型号的船只，每条船只每次装卸货物的时间为船只每次装卸货物的时间为1天。问该航运公司至少
13、应配备多少条天。问该航运公司至少应配备多少条船只才干满足运输要求。船只才干满足运输要求。表表1航线航线起点起点终点终点航班航班/天天1ED32BC23AF14DB1表表2 到到 从从 ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030运运 用用 举举 例例-17-China University of Mining and Technology运筹学 解：解：该航运公司所需配航运公司所需配备的船只分的船只分为两部分：两部分：1航程周航程周转船只；船只；2港口港口调度船只；度船只；下面分下面分别计算相算相应的船只数。的船只数。 到
14、到 从从 ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030航线航线起点起点终点终点航班航班/天天1ED32BC23AF14DB1航程周航程周转船只船只如航如航线1，在港口，在港口E装装货1天，天， 航程航程17天，在天，在D卸卸货1天，天， 总计19天；每天天；每天3个航班，个航班， 故航故航线1共需周共需周转船只船只57条。条。类似似计算可得算可得航航线2共需周共需周转船只船只10条；航条；航线3共需周共需周转船只船只9条；条；航航线4共需周共需周转船只船只15条；累条；累计共需周共需周转船只船只91条。条。运运 用用 举举
15、 例例-18-China University of Mining and Technology运筹学 周转船只周转船只航线航线装货装货天数天数航程天数卸货卸货天数天数小记小记航班航班数数周转周转船数船数11171193572131521031719194113115115合计周转船只数合计周转船只数91运运 用用 举举 例例-19-China University of Mining and Technology运筹学 到到 从从 ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030航线航线起点起点终点终点航班航班/天天1ED3
16、2BC23AF14DB1港口调度船只港口调度船只有些港口每天到达船只多于需求船只，有些港口每天到达船只多于需求船只，如港口如港口D，每天到达，每天到达3条，需求条，需求1条；条；而有些港口每天到达船只少而有些港口每天到达船只少 于需求船只，如港口于需求船只，如港口B，每天，每天 到达到达1条，需求条，需求2条；条；各港口每天各港口每天调度船只数度船只数计算如下算如下运运 用用 举举 例例-20-China University of Mining and Technology运筹学 调度船只调度船只港口城市港口城市每天到达每天到达每天需求每天需求余缺数余缺数A01- 1B12- 1C202D3
17、12E03- 3F101为了使配了使配备的船只数最少，的船只数最少，应做到周做到周转的空船数最少。的空船数最少。因此建立相因此建立相应的运的运输问题模型，即模型，即产销平衡表与平衡表与单位运价表位运价表.运运 用用 举举 例例-21-China University of Mining and Technology运筹学 ABE余船余船C2352D1413172F7831缺船缺船113利用表上作利用表上作业法求出最法求出最优调度方案度方案为：ABE余船余船C22D112F11缺船缺船11352+13 1+17 1+7 1=47.最最优调度船只数度船只数因此，在不思索维因此，在不思索维修的情况下
18、，该公修的情况下，该公司至少应配备的船司至少应配备的船只数为只数为91+47=建建建建立立立立运运运运输输问问题题模模模模型型型型为为：运运 用用 举举 例例-22-China University of Mining and Technology运筹学 某某公公司司经销某某产品品，该公公司司具具有有3个个加加工工厂厂，每每日日的的产量量分分别为：A1(7t), A2(4t), A3(9t).该公公司司把把这些些产品品分分别运运往往4个个销售售点点，各各销售售点点的的每每日日销售售量量为： B1(3t), B2(6t), B3(5t), B4(6t). 如如今今假假定定： 1、每每个个工工厂厂
19、消消费的的产品品不不一一定定直直接接发运运到到销售售地地点点，可可以以其其中中几几个个产地地集集中中一一同同运运；2、运运往往各各销售售地地点点的的产品品可可以以先先运运给其其中中的的一一些些销地地，再再转运运给其其它它销地地；3、除除了了产、销地地之之外外，中中间还可可以以设置置几几个个转运运站站，作作为在在产地地之之间、销地地之之间或或者者产销地地之之间进展展转运运。下下表表为单位位运运价价表表，问该公公司司应该如如何何调运运产品品，在在思思索索直直接接与与非非直直接接运运输的的各各种种能能够方方案案下下，以以及及满足足各各地地需需求求量量的的前前提提下下，使使每每天天的的总运运费到到达达
20、最最少少？运运 用用 举举 例例-23-China University of Mining and Technology运筹学 单位运单位运价表价表产地产地中间转运站中间转运站销地销地A1A2A3T1T2T3T4B1B2B3B4产产地地A1132143311310A21-35-21928A33-1-2374105中中间间转转运运站站T12311322846T215-1114527T34-23421824T43232121-26销销地地B13172411142B21194858-121B332104222423B410856746213运运 用用 举举 例例-24-China Universi
21、ty of Mining and Technology运筹学 解：分析解：分析1、由于、由于问题中一切的中一切的产地、中地、中间转运站、运站、销地都既可以看作地都既可以看作是是产地也可以看作是地也可以看作是销地，所以地，所以这个个问题可以看作是具有可以看作是具有11个个产地与地与销地的地的扩展的运展的运输问题.2、对于于扩展的运展的运输问题我我们可以建立其可以建立其对应的运价表，表中的运价表，表中将不能将不能够的运的运输方案的运价方案的运价标志志为恣意大的正数恣意大的正数M.3、一切中、一切中间转运站的运站的产量等于量等于销量，由于量，由于总量量为20，所以每，所以每一个中一个中转站的运量不会
22、超越站的运量不会超越20，所以可以，所以可以规定定T1、T2、T3、T4的的产销量均量均为20。4、由于一切的、由于一切的产销地点均可以作地点均可以作为转运站，所以运站，所以应该在原来在原来的的产销量根底上加上量根底上加上20。运运 用用 举举 例例-25-China University of Mining and Technology运筹学 A1A2A3T1T2T3T4B1B2B3B4产量产量A1013214331131027A210M35M2192824A33M01M237410529T12310132284620T215M1011452720T34M23402182420T432321
23、201M2620B13172411014220B21194858M102120B332104222420320B410856746213020销量销量20202020202020232625260运运 用用 举举 例例-29-China University of Mining and Technology运筹学 某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。知该厂各季度的消费才干及消费每台台同一规格的柴油机。知该厂各季度的消费才干及消费每台柴油机的本钱如右表。假设消费出来的柴油机当季不交货，每柴油机的本钱如右表。假设
24、消费出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用台每积压一个季度需储存、维护等费用0.15万元。试求在完成万元。试求在完成合同的情况下，使该厂全年消费总费用为最小的决策方案。合同的情况下，使该厂全年消费总费用为最小的决策方案。季度季度生产能力生产能力/台台单位成本单位成本/万元万元2510.83511.130111011.3运运 用用 举举 例例-30-China University of Mining and Technology运筹学 把第把第 i 季度消费的柴油机数目看作第季度消费的柴油机数目看作第 i 个消费厂的产量；个消费厂的产量；把第把第 j 季度交货的柴油机数目
25、看作第季度交货的柴油机数目看作第 j 个销售点的销量；个销售点的销量；设设cij是第是第i季度消费的第季度消费的第j季度交货的每台柴油机的实践本钱，季度交货的每台柴油机的实践本钱，应该等于该季度单位本钱加上储存、维护等费用。应该等于该季度单位本钱加上储存、维护等费用。可构造以下产销平衡问题：可构造以下产销平衡问题：解：解： 设设 xij为第为第 i 季度消费的第季度消费的第 j 季度交货的柴油机数目，那么季度交货的柴油机数目，那么应满足：应满足：交交货： x11 = 10 消消费： x11 + x12 + x13 + x14 25x12 + x22 = 15 x22 + x23 + x24 3
26、5x13 + x23 + x33 = 25 x33 + x34 30x14 + x24 + x34 + x44= 20 x44 10运运 用用 举举 例例-31-China University of Mining and Technology运筹学 ji产量产量10.810.9511.111.2525M11.1011.2511.4035MM11.0011.1530MMM11.3010销量销量10152520 10070由于产大于销，加上一个虚拟的销地由于产大于销，加上一个虚拟的销地D，化为平衡问题，化为平衡问题，即可运用表上作业法求解。即可运用表上作业法求解。运运 用用 举举 例例-32-C
27、hina University of Mining and Technology运筹学 该问题的数学模型：该问题的数学模型：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 jiD产量产量10.810.9511.111.25025M11.1011.2511.40035MM11.0011.15030MMM11.30010销量销量1015252030 100100运运 用用 举举 例例-33-China University of Mining and Technology运筹学 jiD产量产量1015025053035255301010销量销量1015252030 100100最优消费决策如下表，最小费用最优消费决策如下表，最小费用z773万元。万元。运运 用用 举举 例例
