运筹学运输问题和指派问题.pptx

《运筹学运输问题和指派问题.pptx》由会员分享，可在线阅读，更多相关《运筹学运输问题和指派问题.pptx（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运输问题提到运输问题，想到什么？服装专卖店的转运问题等快递业的运输问题实际生活中有哪些方面涉及运输问题第1页/共54页 产销平衡和单位运价表产销平衡和单位运价表 销地单位运费产地B1B2B3B4产量产量A13113107A219284A3741059销量量365620运输问题的提出运输问题的提出 某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如下表。量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如下表。问该公司应如何调运产品，在满足各销售点的需求量的前

2、提下，使总运费问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。为最小。运输的单位成本供需平衡第2页/共54页运输问题的求解方法计算过程：计算过程：1 1寻找初始可行解；寻找初始可行解；2 2检查是否已达到最优。若已是最优或无可行解，检查是否已达到最优。若已是最优或无可行解，则结束；则结束；3 3进一步改善目前的解；进一步改善目前的解；寻找初始可行解的方法寻找初始可行解的方法（1）西北角方法；）西北角方法；（2）最小元素法。）最小元素法。第3页/共54页求平衡运输问题初始解方法西北角方法B1B2B3B4产量A17A24A39需求量365620西北角方法B1B2B3B4产量

3、A17A24A39需求量365620 2423 3311321974101085求初始解311321974101085 6首先满足西北角上空格的需求第4页/共54页初始解求平衡运输问题初始解方法西北角方法西北角方法其余为其余为0 0。总运费总运费总运费总运费=3*3+4*11+2*9+2*2+3*10+6*5=135=3*3+4*11+2*9+2*2+3*10+6*5=135（元）（元）（元）（元）B1B2B3B4产量A1 3 47A2 2 24A3 3 69需求量365620311321974101085第5页/共54页求平衡运输问题初始解方法最小元素法求初始解B1B2B3B4产量A17A2

4、4A39需求量365620最小元素法311321974101085B1B2B3B4产量A17A24A39需求量365620311321974101085134633首先满足运费最小的空格第6页/共54页初始解求平衡运输问题初始解方法最小元素法最小元素法其余为其余为0 0。总运费总运费总运费总运费=4*3+3*10+3*1+1*2+6*4+3*5=86=4*3+3*10+3*1+1*2+6*4+3*5=86 （元）（元）（元）（元）B1B2B3B4产量A14 37A2314A36 39需求量365620311321974101085第7页/共54页两种方法结果比较最小元素法西北角方法B1B2B3

5、B4产量A1 3 47A2 2 24A3 3 69需求量365620311321974101085B1B2B3B4产量A14 37A2314A36 39需求量365620311321974101085第8页/共54页西北角法得到初始方案：西北角法得到初始方案：总运费总运费总运费总运费=3*3+4*11+2*9+2*2+3*10+6*5=135=3*3+4*11+2*9+2*2+3*10+6*5=135（元）（元）（元）（元）最小元素法得到初始方案：最小元素法得到初始方案：总运费总运费总运费总运费=4*3+3*10+3*1+1*2+6*4+3*5=86=4*3+3*10+3*1+1*2+6*4+

6、3*5=86（元）（元）（元）（元）第9页/共54页最优解的检验闭回路法要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量（对应于运输表格中的空格）的检验数，若有某空格 的检验数为负，则说明将 变为基变量将使运费减少，故当前这个解不是最优解；若所有空格的检验数全非负，则不管怎样变换解均不能使运输费用减少，即为最优解。第10页/共54页311321974101085闭回路法以最小元素法得到的解为初始可行解B1B2B3B4产量产量A1437A2314A3639销量量3656201-1-11检验第一个空格此时，引起的运费变化为：3-1+2-3=10说明：该空格可以保持不变

7、，即该运输路线不用安排运输第11页/共54页1-112432存在检验数0的空格，该解不是最优解B1B2B3B4产量产量A1437A2314A3639销量量365620311321974101085检验数0表示：例如（A2,B4）如果增加A2到B4的1单位产品，将会降低1单位的运费，所以，该解不是最优解。第12页/共54页解的改进（1）以 为换入变量，找出它在运输表中的闭回路；（2）以空格 为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点一次编号；（3）在闭回路上的所有偶数顶点中，找出运输量最小 的顶点（格子），以该格中的变量为换出变量；（4）以 为调整量，将该闭回路上所有奇

8、数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案；（5）然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤，直到有最优解。第13页/共54页3B1B2B3B4产量产量A17A234A3639销量量365620+1+1-1-1124510311219741031085此时，总费用为：5*3+2*10+3*1+1*8+6*4+3*5=8586接下来，继续用闭回路法对新求得的解进行检验，如果还不是最优解，进行改进，如此循环往复直至得到最优解 总费用为85B1B2B3B4产量产量A1527A2314A3639销量量365620第14页/共54页

9、运输问题的建模和Excel规划求解某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。B1B2B3B4产量产量A13113107A219284A3741059销量量365620单位运输成本供给=需求第15页/共54页一般运输问题的基本原则最小化所有运输费用之和最小化所有运输费用之和供给供给=需求需求产品是离散计量的产品是离散计量的要求运输量是整数个单位产品要求运输量是整数个单位产品线性约束线性约束先讨论产销平衡的运输问题总供应量=总需求量第16页/共5

10、4页运输问题的一般模式 目标函数供给约束需求约束非负约束n表示物资的n个销地m表示物资的m个产地第17页/共54页问题分析决策变量目标函数约束条件：产量约束、销量约束、非负B1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349需求量365620决策变量第18页/共54页非负约束需求约束供给约束根据一般模式求解上述运输问题得到：第19页/共54页注意：由于供应量和需求量都是整数，任何有可行解的运输问题就必然有所有决策变量都是整数的最优解，所以无需设置有关整数解的约束条件第20页/共54页p实际中，产销往往是不平衡的。可有两种情况：总产量小于

11、总销量（供不应求）总产量大于总销量（供大于求）产销不平衡的运输问题第21页/共54页总产量小于总销量（供不应求）第22页/共54页总产量大于总销量（供大于求）第23页/共54页例4.2 自来水输送问题某市有甲乙丙丁四个居民区，自来水有A、B、C三个水库供应。四个居民区每天必须得到保证的基本生活用水量分别为30、70、10、10千吨，但由于水源紧张，三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库每天向各居民区供水所需付出的引水管理费用不同（见表格，其中水库C与丁区之间没有输水管道），其他管理费用都是450元/千吨。根据公司规定，各居民区用户按照统一

12、标准900元/千吨收费。此外，四个居民区都向公司申请了额外用水量，分别为每天50、70、20、40千吨。第24页/共54页甲乙丙丁A160130220170B140130190150C190200230问：（1）该公司应如何分配供水量，才能获利最多？（2）为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加多少第25页/共54页问题分析决策变量目标函数约束条件甲乙丙丁最大供水量AxA1xA2xA3xA4100BxB1xB2xB3xB4120CxC1xC2xC3-100基本用水量30701010额外用水量50702040最

13、大用水量801403050第26页/共54页使用Excel求解送水问题1供不应求的问题第27页/共54页使用Excel求解送水问题2最大供水量增倍供大于求的问题第28页/共54页4.3 运输问题的变形总供应量大于总需求总供应量小于总需求一个目的地同时存在着最小需求量和最大需求量，于是所有在这两个数值之间的数量都是可以接受的在运输中不能使用特定的出发地目的地组合目标是使与运输量有关的总利润最大而不是使总成本最小第29页/共54页例4.3 某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每

14、种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。现在需要决定的是在哪个工厂生产那种产品，可以使总成本最小？单位成本生产能力产品1产品2产品3产品4工厂14127282475工厂240292375工厂33730272145需求量20303040某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以

15、生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。现在需要决定的是在哪个工厂生产那种产品，可以使总成本最小？单位成本生产能力产品1产品2产品3产品4工厂14127282475工厂240292375工厂33730272145需求量20303040第30页/共54页问题分析供大于求的问题决策变量目标函数约束条件单位成本生产能力产品1产品2产品3产品4工厂1x11x12x13x1475工厂2x21x22x23=0 x2475工厂3x31x32x33x3445需求量20303040第31页/共54页使用Excel求解第32页/共54页例4.4 需求量存在最小需求量和最大需求量的问题

16、。某公司在三个工厂中专门生产一种产品。在未来的四个月中，四个处于国内不同区域的潜在顾客很有可能有大量订购。顾客1是公司最好的顾客，所以他的订单要全部满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为至少要满足他们订单的1/3；对于顾客4，营销经理认为并不需要特殊考虑。由于运输成本上的差异，销售一个产品得到的利润也不同，利润很大程度上取决于哪个工厂供应哪个顾客（见表格）。问应向每个顾客供应多少产品，才能使公司的总利润最大？第33页/共54页单位利润（元）产量顾客1顾客2顾客3顾客4工厂1554246538000工厂2371832485000工厂3295951357000最少供应量7000

17、300020000要求订购量7000900060008000例4.4 第34页/共54页问题分析该问题要求满足不同顾客的需求（订购量），解决办法是：实际供应量最少供应量 实际供应量要求订购量但条件是：最少供应量（7000+3000+2000+0=12000）总产量（8000+5000+7000=20000）要求订购总量（7000+9000+6000+8000=30000）第35页/共54页问题分析决策变量目标函数约束条件单位利润（元）产量顾客1顾客2顾客3顾客4工厂1x11x12x13x148000工厂2x21x22x23x245000工厂3x31x32x33x347000最少供应量70003

18、00020000要求订购量7000900060008000第36页/共54页使用Excel求解第37页/共54页4.5 指派问题问题的提出有n项不同的任务需要完成，而恰好有n个人（或n台设备）可以分别完成其中的一项工作，但由于任务的性质和个人的专长不同，因而不同的人去完成不同的工作的时间（或产生的效率）就不一样。那么，应派哪一个人去完成哪一项工作才能使总的时间最短（或效率最高）？问题模型p平衡指派问题的假设：1.人的数量和任务的数量相等2.每个人只能完成一项任务3.每项任务只能由一个人来完成4.每个人和每项任务的组合都会有一个相关的成本5.目标是要确定如何指派才能使总成本最小第38页/共54页

19、指派问题应用举例某市计划在今年内修建4座厂房：发电厂、化肥厂、机械厂、食品厂，分别记为B1，B2，B3，B4。该市有4个大的建筑队A1，A2，A3，A4都可以承担这些厂房的建造任务。但由于各个建筑队的技术水平、管理水平等不同，它们完成每座厂房所需要的费用也不一样。为计算简单，设有关数据如下表所示。又因希望尽早把这4座厂房都建造好，故需把这4个建筑队都动用起来，即每个队分配一项任务。市政府经费紧张，于是提出研究下述问题：究竟应该指派哪个队修建哪个厂，才能使建造4座厂房所花的总费用最少？各建筑队完成每座厂房所需费用（万元）B1B2B3B4A13452A28576A39645A45366第39页/共

20、54页匈牙利解法的关键：利用了指派问题最优解的以下性质：若从指派问题的系数矩阵 的某行（或某列）各元素分别减去一个常数 ，得到一个新的矩阵 ，则以 和 为系数矩阵的两个指派问题有相同的最优解第40页/共54页指派问题的匈牙利算法 系数矩阵每行元素中减去该行的最小元素每列元素中减去该列的最小元素 设 是一个系数矩阵，对于前面的例子，得到如下的效率矩阵：第41页/共54页指派问题的匈牙利算法（续）划去C中所有0元素所需要的最少直线数等于C中不同行不同列上0元素的个数 1 在所有未划去数中找出最小数，设为d；2 将所有未画去的数都减去d，而对位于两直线交点处的数则加上d。3 得出最优指派方案。注：注

21、：最优解不一定唯一！第42页/共54页最优解在系数矩阵中已经有4个独立零元素，故可确定指派问题的最优指派方案。本例的最优解为：第43页/共54页最优指派方案是：B1B2B3B4A11A21A31A41最少费用为：2+5+4+5=16第44页/共54页运用Excel求解第45页/共54页例4.7某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘四个人，每个人负责完成一项任务：A、B、C和D。由于每人完成每项任务的时间和工资不同。问公司应指派何人去完成任务，才能使总成本最少？完成每项任务的时间（小时）每小时工资（

22、元）任务A任务B任务C任务D小张3541274014小王4745325112小李3956364313小刘3251254615第46页/共54页分析问题决策变量目标函数约束条件第47页/共54页运用Excel求解第48页/共54页4.6 指派问题的变形某人不能完成某项任务每个人只能完成一项任务，但任务数比人数多。因此其中有些任务会没人做。每项任务只由一个人完成，但是人数比任务数多，因此其中有些人会没事做。某人可以同时被指派多项任务。某事需要由多人共同完成。目标是与指派有关的总利润最大而不是总成本最小。实际需要完成的任务数不超过总人数也不超过总任务数。第49页/共54页例4.8（例4.3改）某公司

23、决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。问：如何把每个工厂指派给至少一个新品（每个新品只能在一个工厂生产），才能使总成本最少？单位成本生产能力产品1产品2产品3产品4工厂14127282475工厂240292375工厂33730272145需求量20303040第50页/共54页问题分析：如何把运输问题转化成指派问题p单位指派成本：原来的单位成本转化成整批成本（整批成本=单位成本*需求量）p供应量和需求量：三个工厂生产四种新产品，但一种产品只能在一个工厂生产。为“人多事少”的指派第51页/共54页问题分析决策变量目标函数约束条件第52页/共54页运用Excel求解第53页/共54页感谢您的观看！第54页/共54页