《运筹学第四章运输问题和指派问题.ppt》由会员分享，可在线阅读，更多相关《运筹学第四章运输问题和指派问题.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 运输问题和指派问题运输问题和指派问题2021/9/241运输问题运输问题提到运输问题，想到什么？服装专卖店的转运问题等快递业的运输问题实际生活中有哪些方面涉及运输问题2021/9/242 产销平衡和单位运价表产销平衡和单位运价表 销地单位运费产地B1B2B3B4产量产量A13113107A219284A3741059销销量量365620运输问题的提出运输问题的提出 某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如下表。量和各销售点每日的销量，以及从各
2、工厂到销售点的单位产品运价如下表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。为最小。运输的单位成本运输的单位成本供需平衡供需平衡2021/9/243运输问题的求解方法运输问题的求解方法计算过程：计算过程：1 1寻找初始可行解；寻找初始可行解；2 2检查是否已达到最优。若已是最优或无可行解，检查是否已达到最优。若已是最优或无可行解，则结束；则结束；3 3进一步改善目前的解；进一步改善目前的解；寻找初始可行解的方法寻找初始可行解的方法（1）西北角方法；）西北角方法；（2）最小元素法。）最小元素法。2021
3、/9/244求平衡运输问题初始解方法求平衡运输问题初始解方法西北角方法西北角方法B1B2B3B4产量A17A24A39需求量365620西西北北角角方方法法B1B2B3B4产量A17A24A39需求量365620 2423 3311321974101085求求初初始始解解311321974101085 6首先满足西北角上空格的需求2021/9/245初初始始解解求平衡运输问题初始解方法求平衡运输问题初始解方法西北角方法西北角方法西西北北角角方方法法其余为其余为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
4、+6*5=135（元）（元）（元）（元）B1B2B3B4产量A1 3 47A2 2 24A3 3 69需求量3656203113219741010852021/9/246求平衡运输问题初始解方法求平衡运输问题初始解方法最小元素法最小元素法求求初初始始解解B1B2B3B4产量A17A24A39需求量365620最最小小元元素素法法311321974101085B1B2B3B4产量A17A24A39需求量365620311321974101085134633首先满足运费最小的空格2021/9/247初初始始解解求平衡运输问题初始解方法求平衡运输问题初始解方法最小元素法最小元素法最最小小元元素素法法
5、其余为其余为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需求量3656203113219741010852021/9/248两种方法结果比较两种方法结果比较最最小小元元素素法法西西北北角角方方法法B1B2B3B4产量A1 3 47A2 2 24A3 3 69需求量365620311321974101085B1B2B3B4产量A14 37A2314A36 39需求量3656203113219741010852021/9
6、/249西北角法得到初始方案：西北角法得到初始方案：总运费总运费总运费总运费=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+3*5=86（元）（元）（元）（元）2021/9/2410最优解的检验最优解的检验闭回路法闭回路法p要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量各非基变量（对应于运输表格中的
7、空格）的检验数，若有某空格若有某空格 的检验数为负，则说明将的检验数为负，则说明将 变为基变量将使运费减少，故当前这个解不是最优解变为基变量将使运费减少，故当前这个解不是最优解；若所有空格的检验数全非负，则不管怎样变换解均不能使运输费用减少，即为最优解。2021/9/2411311321974101085闭回路法闭回路法以最小元素法得到的解为初始可行解以最小元素法得到的解为初始可行解B1B2B3B4产量产量A1437A2314A3639销销量量3656201-1-11检验第一个空格此时，引起的运费变化为：3-1+2-3=10说明：该空格可以保持不变，即该运输路线不用安排运输2021/9/241
8、21-112432存在检验数0的空格，该解不是最优解B1B2B3B4产量产量A1437A2314A3639销销量量365620311321974101085检验数检验数0表示：例如（表示：例如（A2,B4）如果增加）如果增加A2到到B4的的1单位单位产品，将会降低产品，将会降低1单位的运费，所以，该解不是最优解。单位的运费，所以，该解不是最优解。2021/9/2413解的改进解的改进p（1）以 为换入变量，找出它在运输表中的闭回路；p（2）以空格 为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点一次编号；p（3）在闭回路上的所有偶数顶点中，找出运输量最小 的顶点（格子），以
9、该格中的变量为换出变量；p（4）以 为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案；p（5）然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤，直到有最优解。2021/9/24143B1B2B3B4产量产量A17A234A3639销销量量365620+1+1-1-1124510311219741031085此此时时，总费总费用用为为：5*3+2*10+3*1+1*8+6*4+3*5=8586接下来，继续用闭回路法对新求得的解进行检验，如果还不是最优解，进行改进，如此循环往复直至得到最优解 总费总费用用为为8
10、5B1B2B3B4产量产量A1527A2314A3639销销量量3656202021/9/2415运输问题的建模和运输问题的建模和Excel规划求解规划求解某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。B1B2B3B4产量产量A13113107A219284A3741059销销量量365620单位运输成本供给=需求2021/9/2416一般运输问题的基本原则一般运输问题的基本原则p最小化所有运输费用之和最小化所有运输费用之和p供给供给=需求需求p
11、产品是离散计量的产品是离散计量的p要求运输量是整数个单位产品要求运输量是整数个单位产品p线性约束线性约束先讨论先讨论产销平衡产销平衡的运输问题的运输问题总供应量总供应量=总需求量总需求量2021/9/2417运输问题的一般模式运输问题的一般模式 目标函数供给约束需求约束非负约束n表示物资的n个销地m表示物资的m个产地2021/9/2418问题分析问题分析p决策变量决策变量p目标函数目标函数p约束条件：产量约束、销量约束、非负约束条件：产量约束、销量约束、非负B1B2B3B4产量A1x11x12x13x147A2x21x22x23x244A3x31x32x33x349需求量365620决策变量决
12、策变量2021/9/2419非负约束非负约束需求约束需求约束供给约束供给约束根据一般模式求解上述运输问题根据一般模式求解上述运输问题p得到：2021/9/2420注意：由于供应量和需求量都是整数，任何有可行解的注意：由于供应量和需求量都是整数，任何有可行解的运输问题就必然有所有决策变量都是整数的最优解，运输问题就必然有所有决策变量都是整数的最优解，所以无需设置有关整数解的约束条件所以无需设置有关整数解的约束条件2021/9/2421p实际中，产销往往是不平衡的。可有两种情况：实际中，产销往往是不平衡的。可有两种情况：总产量小于总销量（供不应求）总产量小于总销量（供不应求）总产量大于总销量（供大
13、于求）总产量大于总销量（供大于求）产销不平衡的运输问题产销不平衡的运输问题2021/9/2422总产量小于总销量（供不应求）总产量小于总销量（供不应求）2021/9/2423总产量大于总销量（供大于求）总产量大于总销量（供大于求）2021/9/2424例例4.2 自来水输送问题自来水输送问题p某市有甲乙丙丁四个居民区，自来水有A、B、C三个水库供应。四个居民区每天必须得到保证的基本生活用水量分别为30、70、10、10千吨，但由于水源紧张，三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库每天向各居民区供水所需付出的引水管理费用不同（见表格，其中水库
14、C与丁区之间没有输水管道），其他管理费用都是450元/千吨。根据公司规定，各居民区用户按照统一标准900元/千吨收费。此外，四个居民区都向公司申请了额外用水量，分别为每天50、70、20、40千吨。2021/9/2425甲乙丙丁A160130220170B140130190150C190200230问：（1）该公司应如何分配供水量，才能获利最多？（2）为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加多少2021/9/2426问题分析问题分析p决策变量决策变量p目标函数目标函数p约束条件约束条件甲乙丙丁最大供水量AxA
15、1xA2xA3xA4100BxB1xB2xB3xB4120CxC1xC2xC3-100基本用水量30701010额外用水量50702040最大用水量8014030502021/9/2427使用使用Excel求解送水问题求解送水问题1供不应求的问题供不应求的问题2021/9/2428使用使用Excel求解送水问题求解送水问题2最大供水量增倍供大于求的问题供大于求的问题2021/9/24294.3 运输问题的变形运输问题的变形p总供应量大于总需求p总供应量小于总需求p一个目的地同时存在着最小需求量和最大需求量，于是所有在这两个数值之间的数量都是可以接受的p在运输中不能使用特定的出发地目的地组合p目
16、标是使与运输量有关的总利润最大而不是使总成本最小2021/9/2430例例4.3 某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。现在需要决定的是在哪个工厂生产那种产品，可以使总成本最小？单位成本生产能力产品1产品2产品3产品4工厂14127282475工厂240292375工厂33730272145需求量20303040某公司
17、决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。现在需要决定的是在哪个工厂生产那种产品，可以使总成本最小？单位成本生产能力产品1产品2产品3产品4工厂14127282475工厂240292375工厂33730272145需求量203030402021/9/2431问题分析问题分析p供大于求的问题供大于求的问题p决策变量p目标函数p约束
18、条件单位成本生产能力产品1产品2产品3产品4工厂1x11x12x13x1475工厂2x21x22x23=0 x2475工厂3x31x32x33x3445需求量203030402021/9/2432使用使用Excel求解求解2021/9/2433例例4.4 需求量存在最小需求量和最大需求需求量存在最小需求量和最大需求量的问题。量的问题。某公司在三个工厂中专门生产一种产品。在未来的四个月中，四个处于国内不同区域的潜在顾客很有可能有大量订购。顾客1是公司最好的顾客，所以他的订单要全部满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为至少要满足他们订单的1/3；对于顾客4，营销经理认为并不需要
19、特殊考虑。由于运输成本上的差异，销售一个产品得到的利润也不同，利润很大程度上取决于哪个工厂供应哪个顾客（见表格）。问应向每个顾客供应多少产品，才能使公司的总利润最大？2021/9/2434单位利润（元）产量顾客1顾客2顾客3顾客4工厂1554246538000工厂2371832485000工厂3295951357000最少供应量7000300020000要求订购量7000900060008000例例4.4 2021/9/2435问题分析问题分析p该问题要求满足不同顾客的需求（订购量），解决办法是：实际供应量最少供应量 实际供应量要求订购量但条件是：最少供应量（7000+3000+2000+0=
20、12000）总产量（8000+5000+7000=20000）要求订购总量（7000+9000+6000+8000=30000）2021/9/2436问题分析问题分析p决策变量决策变量p目标函数目标函数p约束条件约束条件单位利润（元）产量顾客1顾客2顾客3顾客4工厂1x11x12x13x148000工厂2x21x22x23x245000工厂3x31x32x33x347000最少供应量7000300020000要求订购量70009000600080002021/9/2437使用使用Excel求解求解2021/9/24384.5 指派指派问题问题p问题的提出n有n项不同的任务需要完成，而恰好有n个
21、人（或n台设备）可以分别完成其中的一项工作，但由于任务的性质和个人的专长不同，因而不同的人去完成不同的工作的时间（或产生的效率）就不一样。那么，应派哪一个人去完成哪一项工作才能使总的时间最短（或效率最高）？p问题模型p平衡指派问题的假设：平衡指派问题的假设：1.人的数量和任务的数量相等2.每个人只能完成一项任务3.每项任务只能由一个人来完成4.每个人和每项任务的组合都会有一个相关的成本5.目标是要确定如何指派才能使总成本最小2021/9/2439指派问题应用举例指派问题应用举例p某市计划在今年内修建4座厂房：发电厂、化肥厂、机械厂、食品厂，分别记为B1，B2，B3，B4。该市有4个大的建筑队A
22、1，A2，A3，A4都可以承担这些厂房的建造任务。但由于各个建筑队的技术水平、管理水平等不同，它们完成每座厂房所需要的费用也不一样。为计算简单，设有关数据如下表所示。又因希望尽早把这4座厂房都建造好，故需把这4个建筑队都动用起来，即每个队分配一项任务。市政府经费紧张，于是提出研究下述问题：究竟应该指派哪个队修建哪个厂，才能使建造4座厂房所花的总费用最少？各建筑队完成每座厂房所需费用（万元）B1B2B3B4A13452A28576A39645A453662021/9/2440匈牙利解法的关键：匈牙利解法的关键：利用了指派问题最优解的以下性质：若从指派问题的系数矩阵 的某行（或某列）各元素分别减去
23、一个常数 ，得到一个新的矩阵 ，则以 和 为系数矩阵的两个指派问题有相同的最优解2021/9/2441指派问题的匈牙利算法指派问题的匈牙利算法 系数矩阵每行元素中减去该行的最小元素每列元素中减去该列的最小元素 设 是一个系数矩阵，对于前面的例子，得到如下的效率矩阵：2021/9/2442指派问题的匈牙利算法（续）指派问题的匈牙利算法（续）划去C中所有0元素所需要的最少直线数等于C中不同行不同列上0元素的个数 1 在所有未划去数中找出最小数，设为d；2 将所有未画去的数都减去d，而对位于两直线交点处的数则加上d。3 得出最优指派方案。注：注：最优解不一定唯一！2021/9/2443最优解最优解在
24、系数矩阵中已经有4个独立零元素，故可确定指派问题的最优指派方案。本例的最优解为：2021/9/2444最优指派方案是：最优指派方案是：B1B2B3B4A11A21A31A41最少费用为：2+5+4+5=162021/9/2445运用运用Excel求解求解2021/9/2446例例4.7p某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘四个人，每个人负责完成一项任务：A、B、C和D。由于每人完成每项任务的时间和工资不同。问公司应指派何人去完成任务，才能使总成本最少？完成每项任务的时间（小时）每小时工资（元）任
25、务A任务B任务C任务D小张3541274014小王4745325112小李3956364313小刘32512546152021/9/2447分析问题分析问题p决策变量决策变量p目标函数目标函数p约束条件约束条件2021/9/2448运用运用Excel求解求解2021/9/24494.6 指派问题的变形指派问题的变形p某人不能完成某项任务p每个人只能完成一项任务，但任务数比人数多。因此其中有些任务会没人做。p每项任务只由一个人完成，但是人数比任务数多，因此其中有些人会没事做。p某人可以同时被指派多项任务。p某事需要由多人共同完成。p目标是与指派有关的总利润最大而不是总成本最小。p实际需要完成的任
26、务数不超过总人数也不超过总任务数。2021/9/2450例例4.8（例（例4.3改）改）某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。问：如何把每个工厂指派给至少一个新品（每个新品只能问：如何把每个工厂指派给至少一个新品（每个新品只能在一个工厂生产），才能使总成本最少？在一个工厂生产），才能使总成本最少？单位成本生产能力产品1产品2产品3产品4工厂14127282475工厂240292375工厂33730272145需求量203030402021/9/2451问题分析：如何把运输问题转化成指派问题问题分析：如何把运输问题转化成指派问题p单位指派成本：原来的单位成本转化成整批成本（整批成本=单位成本*需求量）p供应量和需求量：三个工厂生产四种新产品，但一种产品只能在一个工厂生产。为“人多事少”的指派2021/9/2452问题分析问题分析p决策变量决策变量p目标函数目标函数p约束条件约束条件2021/9/2453运用运用Excel求解求解2021/9/2454