《《运筹学教学资料》运筹学第3章第3节.ppt》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第3章第3节.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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运筹学 一、不平衡的运输问题的类型一、不平衡的运输问题的类型一、不平衡的运输问题的类型一、不平衡的运输问题的类型 供过于求供过于求，总产量大于总销量，即：，总产量大于总销量，即：由于总产量大于总销量，某些由于总产量大于总销量，某些产地的产量调运不出去，即调产地的产量调运不出去，即
3、调运量小于其产量；由此可以建运量小于其产量；由此可以建立供过于求的数学模型：立供过于求的数学模型：不不平平衡衡的的运运输输问问题题-4-China University of Mining and Technology运筹学 解决方法解决方法：由于产品供大于求，应考虑把多余的物资就地贮：由于产品供大于求，应考虑把多余的物资就地贮存，做法上即存，做法上即增加一个虚拟销地增加一个虚拟销地Bn+1，虚拟销地虚拟销地Bn+1的总销量的总销量为：为：令令 xi(n+1)是从产地是从产地Ai到虚拟销地到虚拟销地Bn+1的调运量，它相当于产地的调运量，它相当于产地 Ai 的贮存量，不需花运费，因而运价为的贮
4、存量，不需花运费，因而运价为0：在这个意义下把不平衡运输问题化为了平衡运输问题。在这个意义下把不平衡运输问题化为了平衡运输问题。不不平平衡衡的的运运输输问问题题-5-China University of Mining and Technology运筹学 供过于求运输问题的供过于求运输问题的平衡模型平衡模型：具体求解时具体求解时,只在只在运价表右端增加运价表右端增加一列一列Bn+1，运价，运价为零为零,销量为销量为bn+1即可即可不不平平衡衡的的运运输输问问题题-6-China University of Mining and Technology运筹学 B1B2BnBn+1产量产量A1c11
5、c12c1n0a1A2c21c22c2n0a2Amcm1cm2cmn0am销量销量b1b2bnbn+1供过于求运输问题的运价表：供过于求运输问题的运价表：不不平平衡衡的的运运输输问问题题-7-China University of Mining and Technology运筹学 供不应求供不应求，当供不应求时，总产量小于总销量，即：，当供不应求时，总产量小于总销量，即：由于总产量小于总销量，由于总产量小于总销量，某些销地的需求得不到某些销地的需求得不到满足，即调入量小于其满足，即调入量小于其销量；由此可以建立供销量；由此可以建立供不应求的数学模型。不应求的数学模型。不不平平衡衡的的运运输输问
6、问题题-8-China University of Mining and Technology运筹学 由于供不应求，则应设想一个虚拟产地由于供不应求，则应设想一个虚拟产地 Am+1，并让虚拟产地，并让虚拟产地 Am+1 来供给销地来供给销地 Bj 所需物资差额。虚拟产地所需物资差额。虚拟产地 Am+1 的产量为：的产量为：由于销地实际上不能从虚拟产地由于销地实际上不能从虚拟产地Am+1得到供应，故其运价应得到供应，故其运价应该是高额的，令该是高额的，令其中其中 是一个充分大的正数。是一个充分大的正数。不不平平衡衡的的运运输输问问题题-9-China University of Mining a
7、nd Technology运筹学 供不应求运输问题供不应求运输问题平衡模型平衡模型具具体体计计算算时时，在在运运价价表表的的下下方方 增增 加加 一一 行行Am+1，运运价价为为零零。产产 量量 为为am+1即即可可。不不平平衡衡的的运运输输问问题题-10-China University of Mining and Technology运筹学 供不应求运输问题运价表：供不应求运输问题运价表：B1B2Bn产量产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnamAm+1MMMam+1销量销量b1b2bn不不平平衡衡的的运运输输问问题题-11-China Univer
8、sity of Mining and Technology运筹学 电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量507030不限不限设有三个煤矿供应四个电厂的发电用煤设有三个煤矿供应四个电厂的发电用煤.假定各个煤矿的假定各个煤矿的年产量、各个电厂的备用煤量以及单位运价如表所示。年产量、各个电厂的备用煤量以及单位运价如表所示。试求运费最省的煤炭调拔方案。试求运费最省的煤炭调拔方案。例例3不不平平衡衡的的运运输输问问题题-12-China University of Mining and Technol
9、ogy运筹学 这是一个产销不平衡的运输问题，总产量这是一个产销不平衡的运输问题，总产量160个单位，个单位，四个电厂的年最低需求为四个电厂的年最低需求为110个单位。小于产量个单位。小于产量160。根据现有产量，第四个电厂每年最多能再多获得根据现有产量，第四个电厂每年最多能再多获得50个单位个单位的供应量，因此，最高总需求为的供应量，因此，最高总需求为210个单位，大于产量个单位，大于产量160。为了求得平衡，增加假想的煤矿为了求得平衡，增加假想的煤矿D，其年产量为，其年产量为50个单位。个单位。电厂电厂煤矿煤矿产量产量A1613221750B1413191560C192023-50最低需要量
10、最低需要量3070010最高需求量最高需求量507030不限不限解解题题分分析析 1不不平平衡衡的的运运输输问问题题-13-China University of Mining and Technology运筹学 由于各电厂的由于各电厂的需求有两个部分需求有两个部分，如电厂，其最低需求，如电厂，其最低需求30个个单位不能由虚拟产地单位不能由虚拟产地D供应，如要供应，其运价是一个任意大供应，如要供应，其运价是一个任意大的正数的正数M；而另一部分而另一部分20个单位个单位可以满足也可以不满足可以满足也可以不满足，因此可由虚拟，因此可由虚拟产地产地D供应，其运价为供应，其运价为0；其它电厂的需求量也
11、可类似处理。其它电厂的需求量也可类似处理。从而可得到一个平衡的运输问题（单位运价表与产销平衡表）从而可得到一个平衡的运输问题（单位运价表与产销平衡表）电厂厂煤煤矿产量量A1613221750B1413191560C192023-50最低需要量最低需要量3070010最高需求量最高需求量50703060解解题题分分析析 2不不平平衡衡的的运运输输问问题题-14-China University of Mining and Technology运筹学 利用表上作利用表上作业法可以求业法可以求得上述问题得上述问题的最优方案。的最优方案。电厂电厂煤矿煤矿产量产量A1613221750B14131915
12、60C192023-50最低需要量最低需要量3070010最高需求量最高需求量50703060总运费为：总运费为：z=2460.不不平平衡衡的的运运输输问问题题-15-China University of Mining and Technology运筹学 3.4 应 用 举 例由于运输问题的表上作由于运输问题的表上作业法远比一般单纯形算业法远比一般单纯形算法简单，因而人们在解法简单，因而人们在解决一些实际问题时，常决一些实际问题时，常设法将其转化为运输问设法将其转化为运输问题的数学模型求解。题的数学模型求解。-16-China University of Mining and Technol
13、ogy运筹学 某航运公司承担六个城市某航运公司承担六个城市A、B、C、D、E、F的四条航线的的四条航线的物资运输任务。已知各条航线的起点、终点及每天航班数如表物资运输任务。已知各条航线的起点、终点及每天航班数如表1，各城市间的航程如表各城市间的航程如表2。假设各条航线使用相同型号的船只，每条。假设各条航线使用相同型号的船只，每条船只每次装卸货物的时间为船只每次装卸货物的时间为1天。问该航运公司至少应配备多少条天。问该航运公司至少应配备多少条船只才能满足运输要求。船只才能满足运输要求。表表1航线航线起点起点终点终点航班航班/天天1ED32BC23AF14DB1表表2 到到 从从 ABCDEFA0
14、121477B1031388C2301555D14131501720E7851703F7852030应应 用用 举举 例例-17-China University of Mining and Technology运筹学 解：解：解：解：该航运公司所需配备的船只分为两部分：该航运公司所需配备的船只分为两部分：（1）航程周转船只；（）航程周转船只；（2）港口调度船只；）港口调度船只；下面分别计算相应的船只数。下面分别计算相应的船只数。到到 从从 ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030航线航线起点起点终点终点航班航班/天天
15、1ED32BC23AF14DB1航程周转船只航程周转船只如航线如航线1，在港口，在港口E装货装货1天，天，航程航程17天，在天，在D卸货卸货1天，天，总计总计19天；每天天；每天3个航班，个航班，故航线故航线1共需周转船只共需周转船只57条。条。类似计算可得类似计算可得航线航线2共需周转船只共需周转船只10条；航线条；航线3共需周转船只共需周转船只9条；条；航线航线4共需周转船只共需周转船只15条；累计共需周转船只条；累计共需周转船只91条。条。应应 用用 举举 例例-18-China University of Mining and Technology运筹学 周转船只周转船只周转船只周转船
16、只航线航线装货装货天数天数航程航程天数天数卸货卸货天数天数小记小记航班航班数数周转周转船数船数11171193572131521031719194113115115合计周转船只数合计周转船只数91应应 用用 举举 例例-19-China University of Mining and Technology运筹学 到到 从从 ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030航线航线起点起点终点终点航班航班/天天1ED32BC23AF14DB1港口调度船只港口调度船只有些港口每天到达船只多于需要船只，有些港口每天到达船只多于需要
17、船只，如港口如港口D，每天到达，每天到达3条，需要条，需要1条；条；而有些港口每天到达船只少而有些港口每天到达船只少 于需要船只，如港口于需要船只，如港口B，每天，每天 到达到达1条，需要条，需要2条；条；各港口每天调度船只数各港口每天调度船只数计算如下计算如下应应 用用 举举 例例-20-China University of Mining and Technology运筹学 调度船只调度船只调度船只调度船只港口城市港口城市每天到达每天到达每天需求每天需求余缺数余缺数A01-1B12-1C202D312E03-3F101为了使配备的船只数最少，应做到周转的空船数最少。为了使配备的船只数最少，
18、应做到周转的空船数最少。因此建立相应的运输问题模型，即产销平衡表与单位运价表因此建立相应的运输问题模型，即产销平衡表与单位运价表.应应 用用 举举 例例-21-China University of Mining and Technology运筹学 ABE余船余船C2352D1413172F7831缺船缺船113利用表上作业法求出最优调度方案为：利用表上作业法求出最优调度方案为：ABE余船余船C22D112F11缺船缺船11352+13 1+17 1+7 1=47.最优调度船只数最优调度船只数因此，在不考虑维因此，在不考虑维修的情况下，该公修的情况下，该公司至少应配备的船司至少应配备的船只数为
19、只数为91+47=138建建建建立立立立运运运运输输输输问问问问题题题题模模模模型型型型为：为：为：为：应应 用用 举举 例例-22-China University of Mining and Technology运筹学 某某公公司司经经销销某某产产品品，该该公公司司具具有有3个个加加工工厂厂，每每日日的的产产量量分分别别为为：A1(7t),A2(4t),A3(9t).该该公公司司把把这这些些产产品品分分别别运运往往4个个销销售售点点，各各 销销 售售 点点 的的 每每 日日 销销 售售 量量 为为：B1(3t),B2(6t),B3(5t),B4(6t).现现在在假假定定：1、每每个个工工厂
20、厂生生产产的的产产品品不不一一定定直直接接发发运运到到销销售售地地点点，可可以以其其中中几几个个产产地地集集中中一一起起运运；2、运运往往各各销销售售地地点点的的产产品品可可以以先先运运给给其其中中的的一一些些销销地地，再再转转运运给给其其它它销销地地；3、除除了了产产、销销地地之之外外，中中间间还还可可以以设设置置几几个个转转运运站站，作作为为在在产产地地之之间间、销销地地之之间间或或者者产产销销地地之之间间进进行行转转运运。下下表表为为单单位位运运价价表表，问问该该公公司司应应该该如如何何调调运运产产品品，在在考考虑虑直直接接与与非非直直接接运运输输的的各各种种可可能能方方案案下下，以以及
21、满足各地需要量的前提下，使每天的总运费达到最少？及满足各地需要量的前提下，使每天的总运费达到最少？应应 用用 举举 例例-23-China University of Mining and Technology运筹学 单位运位运价表价表产地地中中间转运站运站销地地A1A2A3T1T2T3T4B1B2B3B4产地地A1132143311310A21-35-21928A33-1-2374105中中间转运运站站T12311322846T215-1114527T34-23421824T43232121-26销地地B13172411142B21194858-121B332104222423B410856
22、746213应应 用用 举举 例例-24-China University of Mining and Technology运筹学 解：分析解：分析1、由于问题中所有的产地、中间转运站、销地都既可以看作、由于问题中所有的产地、中间转运站、销地都既可以看作是产地也可以看作是销地，所以这个问题可以看作是具有是产地也可以看作是销地，所以这个问题可以看作是具有11个个产地与销地的扩大的运输问题产地与销地的扩大的运输问题.2、对于扩大的运输问题我们可以建立其对应的运价表，表中、对于扩大的运输问题我们可以建立其对应的运价表，表中将不可能的运输方案的运价标记为任意大的正数将不可能的运输方案的运价标记为任意大
23、的正数M.3、所有中间转运站的产量等于销量，由于总量为、所有中间转运站的产量等于销量，由于总量为20，所以每，所以每一个中转站的运量不会超过一个中转站的运量不会超过20，所以可以规定，所以可以规定T1、T2、T3、T4的产销量均为的产销量均为20。4、由于所有的产销地点均可以作为转运站，所以应该在原来、由于所有的产销地点均可以作为转运站，所以应该在原来的产销量基础上加上的产销量基础上加上20。应应 用用 举举 例例-25-China University of Mining and Technology运筹学 A1A2A3T1T2T3T4B1B2B3B4产量量A1013214331131027
24、A210M35M2192824A33M01M237410529T12310132284620T215M1011452720T34M23402182420T432321201M2620B13172411014220B21194858M102120B332104222420320B410856746213020销量量20202020202020232625260应应 用用 举举 例例-29-China University of Mining and Technology运筹学 某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机
25、。已知该厂各季度的生产能力及生产每台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用每台每积压一个季度需储存、维护等费用0.15万元。试求在完万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。成合同的情况下，使该厂全年生产总费用为最小的决策方案。季度季度生产能力生产能力/台台单位成本单位成本/万元万元2510.83511.130111011.3应应 用用 举举 例例-30-China University of Mining and
26、 Technology运筹学 把第把第 i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第 i 个生产厂的产量；个生产厂的产量；把第把第 j 季度交货的柴油机数目看作第季度交货的柴油机数目看作第 j 个销售点的销量；个销售点的销量；设设cij是第是第i季度生产的第季度生产的第j季度交货的每台柴油机的实际成本，季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：可构造下列产销平衡问题：解：解：设设 xij为第为第 i 季度生产的第季度生产的第 j 季度交货的柴油机数目，那么季度交货的柴油机数目，那么
27、应满足：应满足：交货：交货：x11 =10 生产：生产：x11+x12+x13+x14 25x12+x22 =15 x22+x23+x24 35x13+x23+x33 =25 x33+x34 30 x14+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由于产大于销，加上一个虚拟的销地由于产大于销，加上一个虚拟的
28、销地D，化为平衡问题，化为平衡问题，即可应用表上作业法求解。即可应用表上作业法求解。应应 用用 举举 例例-32-China 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万元。万元。应应 用用 举举 例例