运筹学第四章运输问题和指派问题

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

2、售点的需求量的前提下，使总运费为最小。为最小。运输的单位成本运输的单位成本供需平衡供需平衡运输问题的求解方法运输问题的求解方法计算过程：计算过程：1 1寻找初始可行解；寻找初始可行解；2 2检查是否已达到最优。若已是最优或无可行解，检查是否已达到最优。若已是最优或无可行解，则结束；则结束；3 3进一步改善目前的解；进一步改善目前的解；寻找初始可行解的方法寻找初始可行解的方法（1）西北角方法；）西北角方法；（2）最小元素法。）最小元素法。求平衡运输问题初始解方法求平衡运输问题初始解方法西北角方法西北角方法西北角方法西北角方法 2423 3311321974101085求初始解求初始解311321

3、974101085 6首先满足西北角上空格的需求初始解初始解求平衡运输问题初始解方法求平衡运输问题初始解方法西北角方法西北角方法西北角方法西北角方法1112222333343,4,2,2,3,6xxxxxx其余为其余为0 0。311321974101085求平衡运输问题初始解方法求平衡运输问题初始解方法最小元素法最小元素法求初始解求初始解最小元素法最小元素法311321974101085311321974101085134633首先满足运费最小的空格初始解初始解求平衡运输问题初始解方法求平衡运输问题初始解方法最小元素法最小元素法最小元素法最小元素法1314212332344,3,3,1,6,3

4、xxxxxx其余为其余为0 0。 311321974101085两种方法结果比较两种方法结果比较最小元素法最小元素法西北角方法西北角方法311321974101085311321974101085 1112222333343,4,2,2,3,6xxxxxx1314212332344,3,3,1,6,3xxxxxx最优解的检验最优解的检验闭回路法闭回路法p要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量各非基变量（对应于运输表格中的空格）的检验数，若有某空格若有某空格 的检验数为负，则说明将的检验数为负，则说明将 变为基变量将使运费减少，故当前这个解不是最优解变为基

5、变量将使运费减少，故当前这个解不是最优解；若所有空格的检验数全非负，则不管怎样变换解均不能使运输费用减少，即为最优解。(,)ijA Bi jx311321974101085闭回路法闭回路法以最小元素法得到的解为初始可行解以最小元素法得到的解为初始可行解1-1-11检验第一个空格此时，引起的运费变化为：3-1+2-3=10说明：该空格可以保持不变，即该运输路线不用安排运输1-112432存在检验数0的空格，该解不是最优解311321974101085检验数检验数0表示：例如（表示：例如（A2,B4）如果增加）如果增加A2到到B4的的1单单位产品，将会降低位产品，将会降低1单位的运费，所以，该解不

6、是最优解。单位的运费，所以，该解不是最优解。解的改进解的改进p（1）以 为换入变量，找出它在运输表中的闭回路；p（2）以空格 为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点一次编号；p（3）在闭回路上的所有偶数顶点中，找出运输量最小 的顶点（格子），以该格中的变量为换出变量；p（4）以 为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案；p（5）然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤，直到有最优解。ijx(,)ijA B( )minijL ex( )minijL ex3+1+1

7、-1-1124510311219741031085此时，总费用为：此时，总费用为：5*3+2*10+3*1+1*8+6*4+3*5=8586接下来，继续用闭回路法对新求得的解进行检验，如果还不是最优解，进行改进，如此循环往复直至得到最优解 总费用为总费用为85运输问题的建模和运输问题的建模和Excel规划求解规划求解某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每日的产量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如表。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最小。单位运输成本供给=需求一般运输问题的基本原则一般运输问题的基本原则p最小化所有运输费用

8、之和最小化所有运输费用之和p供给供给= =需求需求p产品是离散计量的产品是离散计量的p要求运输量是整数个单位产品要求运输量是整数个单位产品p线性约束线性约束先讨论先讨论产销平衡产销平衡的运输问题的运输问题总供应量总供应量=总需求量总需求量运输问题的一般模式运输问题的一般模式 0. .min11ijjmiijinjijijijxdxsxtsxc目标函数供给约束需求约束非负约束n表示物资的n个销地m表示物资的m个产地问题分析问题分析p决策变量决策变量p目标函数目标函数p约束条件：产量约束、销量约束、非负约束条件：产量约束、销量约束、非负决策变量决策变量非负约束非负约束需求约束需求约束供给约束供给约

9、束根据一般模式求解上述运输问题根据一般模式求解上述运输问题p得到：11121334111213142122232431323334112131122232132333142434min311357493. .6560(1,2,3;1,2,3,4)ijzxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxij注意：由于供应量和需求量都是整数，任何有可行解的注意：由于供应量和需求量都是整数，任何有可行解的运输问题就必然有所有决策变量都是整数的最优解，运输问题就必然有所有决策变量都是整数的最优解，所以无需设置有关整数解的约束条件所以无需设置有关整数解的约束条件p实际中，产销往往是不平衡的。

10、可有两种情况：实际中，产销往往是不平衡的。可有两种情况： 总产量小于总销量（供不应求）总产量小于总销量（供不应求） 总产量大于总销量（供大于求）总产量大于总销量（供大于求）产销不平衡的运输问题产销不平衡的运输问题总产量小于总销量（供不应求）总产量小于总销量（供不应求）1111min(1,2.,)(). .(1,2., )()0(1,2.,;1,2., )mnijijijnijijmijjiijzc xxaimstxbjnxim jn产量约束销量约束总产量大于总销量（供大于求）总产量大于总销量（供大于求）1111min(1,2.,)(). .(1,2., )()0(1,2.,;1,2., )mn

11、ijijijnijijmijjiijzc xxaimstxbjnxim jn产量约束销量约束例例4.2 自来水输送问题自来水输送问题p某市有甲乙丙丁四个居民区，自来水有A、B、C三个水库供应。四个居民区每天必须得到保证的基本生活用水量分别为30、70、10、10千吨，但由于水源紧张，三个水库每天最多只能分别供应50、60、50千吨自来水。由于地理位置的差别，自来水公司从各水库每天向各居民区供水所需付出的引水管理费用不同（见表格，其中水库C与丁区之间没有输水管道），其他管理费用都是450元/千吨。根据公司规定，各居民区用户按照统一标准900元/千吨收费。此外，四个居民区都向公司申请了额外用水量，

12、分别为每天50、70、20、40千吨。问：（1）该公司应如何分配供水量，才能获利最多？（2）为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加多少问题分析问题分析p决策变量决策变量p目标函数目标函数p约束条件约束条件使用使用Excel求解送水问题求解送水问题1供不应求的问题供不应求的问题使用使用Excel求解送水问题求解送水问题2最大供水量增倍供大于求的问题供大于求的问题4.3 运输问题的变形运输问题的变形p总供应量大于总需求p总供应量小于总需求p一个目的地同时存在着最小需求量和最大需求量，于是所有在这两个数值之间的数

13、量都是可以接受的p在运输中不能使用特定的出发地目的地组合p目标是使与运输量有关的总利润最大而不是使总成本最小例例4.3 某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。现在需要决定的是在哪个工厂生产那种产品，可以使总成本最小？某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力

14、以每天生产的任意种产品的数量来衡量（见表格最右列）。而每种产品每天有一定的需求量（见表格最后一行）。除了工厂2不能生产产品3之外，每个工厂都可以生产这些产品。然而，每种产品在不同工厂中的单位成本是有差异的（见表）。现在需要决定的是在哪个工厂生产那种产品，可以使总成本最小？问题分析问题分析p供大于求的问题供大于求的问题p决策变量p目标函数p约束条件使用使用Excel求解求解例例4.4 需求量存在最小需求量和最大需求需求量存在最小需求量和最大需求量的问题。量的问题。某公司在三个工厂中专门生产一种产品。在未来的四个月中，四个处于国内不同区域的潜在顾客很有可能有大量订购。顾客1是公司最好的顾客，所以他

15、的订单要全部满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为至少要满足他们订单的1/3；对于顾客4，营销经理认为并不需要特殊考虑。由于运输成本上的差异，销售一个产品得到的利润也不同，利润很大程度上取决于哪个工厂供应哪个顾客（见表格）。问应向每个顾客供应多少产品，才能使公司的总利润最大？例例4.4 问题分析问题分析p该问题要求满足不同顾客的需求（订购量），解决办法是： 实际供应量最少供应量 实际供应量要求订购量但条件是： 最少供应量（7000+3000+2000+0=12000） 总产量（8000+5000+7000=20000） 要求订购总量（7000+9000+6000+8000=

16、30000）问题分析问题分析p决策变量决策变量p目标函数目标函数p约束条件约束条件使用使用Excel求解求解4.5 指派问题指派问题p问题的提出n有n项不同的任务需要完成，而恰好有n个人（或n台设备）可以分别完成其中的一项工作，但由于任务的性质和个人的专长不同，因而不同的人去完成不同的工作的时间（或产生的效率）就不一样。那么，应派哪一个人去完成哪一项工作才能使总的时间最短（或效率最高）？ p问题模型j.i, 1 0 , 2 , 1 , 1 , 2 , 1 , 1 . .min1111对一切或ijnjijniijninjijijxnixnjxtsxcp平衡指派问题的假设：平衡指派问题的假设：1.

17、人的数量和任务的数量相等2.每个人只能完成一项任务3.每项任务只能由一个人来完成4.每个人和每项任务的组合都会有一个相关的成本5.目标是要确定如何指派才能使总成本最小指派问题应用举例指派问题应用举例p某市计划在今年内修建4座厂房：发电厂、化肥厂、机械厂、食品厂，分别记为B1，B2，B3，B4。该市有4个大的建筑队A1，A2，A3，A4都可以承担这些厂房的建造任务。但由于各个建筑队的技术水平、管理水平等不同，它们完成每座厂房所需要的费用也不一样。为计算简单，设有关数据如下表所示。又因希望尽早把这4座厂房都建造好，故需把这4个建筑队都动用起来，即每个队分配一项任务。市政府经费紧张，于是提出研究下述

18、问题：究竟应该指派哪个队修建哪个厂，才能使建造4座厂房所花的总费用最少？ 各建筑队完成每座厂房所需费用（万元） 匈牙利解法的关键：匈牙利解法的关键：利用了指派问题最优解的以下性质：若从指派问题的系数矩阵 的某行（或某列）各元素分别减去一个常数 ，得到一个新的矩阵 ，则以 和 为系数矩阵的两个指派问题有相同的最优解nnijcC)(k()ijnnCcCC 指派问题的匈牙利算法指派问题的匈牙利算法 BC33011024120203201330210251203032134526635546967582543系数矩阵每行元素中减去该行的最小元素每列元素中减去该列的最小元素 设 是一个系数矩阵， nni

19、jcC)( 对于前面的例子，得到如下的效率矩阵：(3)3301102412020320(1)(2)(3)3301102412020320(1)(2)3301102412020320(1)(2)指派问题的匈牙利算法（续）指派问题的匈牙利算法（续） 划去C中所有0元素所需要的最少直线数等于C中不同行不同列上0元素的个数 2200103401010330(2)(1)(4)(3)2200103401010330(2)(1)(4)(3)1 在所有未划去数中找出最小数，设为d；2 将所有未画去的数都减去d，而对位于两直线交点处的数则加上d。3 得出最优指派方案。 注：注：最优解不一定唯一！最优解最优解*0

20、001010000101000X在系数矩阵中已经有4个独立零元素，故可确定指派问题的最优指派方案。本例的最优解为：最优指派方案是：最优指派方案是：最少费用为：2+5+4+5=16运用运用Excel求解求解例例4.7p某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘四个人，每个人负责完成一项任务：A、B、C和D。 由于每人完成每项任务的时间和工资不同。问公司应指派何人去完成任务，才能使总成本最少？j.i, 1 0 , 2 , 1 , 1 , 2 , 1 , 1 . .min1111对一切或ijnjijniijninjijijxnixnjxtsxc分析问题分析问题p决策变量决策变量p目标函数目标函数p约束条件约束条件1111222233334444111122223333min35 1441 1427 1440 1447 1245 1232 1251 1239 1356 1336 1343 1332 1551 1525 1546 1511. .ABCDABCDABCDABCDABCDABCDABCzxxxxxxxxxxxxxxxxxxxxxxxxxxxxst444412341234123412