运输问题与指派问题.ppt

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

1、Excel在经济管理中的应用在经济管理中的应用第五讲第五讲 运输问题与指派问题运输问题与指派问题 5.1 运输问题(transportation problem)一、什么是运输问题一、什么是运输问题二、运输问题的分类二、运输问题的分类三、供需均衡运输问题的建模与求解三、供需均衡运输问题的建模与求解四、供需非均衡运输问题的建模与求解四、供需非均衡运输问题的建模与求解五、运输问题的应用一、什么是运输问题一、什么是运输问题在经济建设中，经常碰到大宗物资调运问题，在经济建设中，经常碰到大宗物资调运问题，如煤、钢铁、木材、粮食等等物资。在全国有如煤、钢铁、木材、粮食等等物资。在全国有若干若干生产基地生产

2、基地，根据已有的交通网，应如何制，根据已有的交通网，应如何制定调运方案，将这些物资运到定调运方案，将这些物资运到各消费地点各消费地点，而，而总费用最小总费用最小。例例 ：设有三个化肥厂供应四个地区的农用化肥，：设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同。各化假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表所示，试求出总的地区运送单位化肥的运价如表所示，试求出总的运费最节省的化肥调拨方案。运费最节省的化肥调拨方案。需求地区需求地区化肥厂化肥厂地区地区1 1 地区

3、地区2 2 地区地区3 3地区地区4 4产量产量（万吨）（万吨）厂厂1 116161313222217175050厂厂2 214141313191915156060厂厂3 319192020232310105050需求量需求量（万吨）（万吨）5050707030301010运价：万元运价：万元/万吨万吨1.1.供应节点供应节点：运输的起点，像生产厂商，提供的：运输的起点，像生产厂商，提供的产品数量是有限的。产品数量是有限的。2.2.需求节点：需求节点：运输的终点或目的地，像销售地点运输的终点或目的地，像销售地点或用户所在地，需求量是一个特定的值。或用户所在地，需求量是一个特定的值。3.3.假设

4、：假设：产品不能从一个供应节点运输到另一个产品不能从一个供应节点运输到另一个供应节点，也不能从一个需求节点运输到另一供应节点，也不能从一个需求节点运输到另一个需求节点，只能从供应节点运至需求节点。个需求节点，只能从供应节点运至需求节点。4.4.运输问题：运输问题：在满足供应节点的供应量约束和在满足供应节点的供应量约束和需求节点的需求量约束的条件下，为了使运输需求节点的需求量约束的条件下，为了使运输成本最低，如何安排运输。成本最低，如何安排运输。二、运输问题的分类1 1、供需均衡的运输问题、供需均衡的运输问题 所有供应点的供应量之和等于所有需求点所有供应点的供应量之和等于所有需求点 的的 需求量

5、之和的运输问题。需求量之和的运输问题。2 2、供需非均衡的运输问题、供需非均衡的运输问题 所有供应点的供应量之和不等于所有需求点所有供应点的供应量之和不等于所有需求点 的需求量之和的运输问题。的需求量之和的运输问题。需求地区需求地区化肥厂化肥厂地区地区1 1 地区地区2 2 地区地区3 3地区地区4 4产量产量（万吨）（万吨）厂厂1 116161313222217175050厂厂2 214141313191915156060厂厂3 319192020232310105050需求量需求量（万吨）（万吨）5050707030301010运价：万元运价：万元/万吨万吨 需求地区需求地区化肥厂化肥厂地

6、区地区1 1 地区地区2 2 地区地区3 3地区地区4 4产量产量（万吨）（万吨）厂厂1 116161313222217175050厂厂2 214141313191915158080厂厂3 319192020232310105050需求量需求量（万吨）（万吨）5050707030301010运价：万元运价：万元/万吨万吨 需求地区需求地区化肥厂化肥厂地区地区1 1 地区地区2 2 地区地区3 3地区地区4 4产量产量（万吨）（万吨）厂厂1 116161313222217175050厂厂2 214141313191915156060厂厂3 319192020232310105050需求量需求量（

7、万吨）（万吨）6060707030301010运价：万元运价：万元/万吨万吨三、供需均衡运输问题的建模与求解已知有已知有mm个生产地点个生产地点A Ai i,i=1,2,i=1,2,m,m，可供应可供应某种物资，其供应量分别是某种物资，其供应量分别是a ai i ,i=1,2,i=1,2,m,m，有有n n个销地个销地B Bj j ,j=1,2,j=1,2,n,n，其需要量分别为其需要量分别为b bj j，j=1,2,j=1,2,n,n，从从A Ai i 到到 B Bj j 运输单位物资的运费为运输单位物资的运费为c cij ij （单价）单价），可用一个表格来表示出来。可用一个表格来表示出来

8、。销地销地产地产地 B B1 1 B B2 2 B Bn n产量产量A A1 1A A2 2 A Amm c c11 11 c c12 12 c c1n1n c c21 21 c c22 22 c c2n2n c cm1 m1 c cm2 m2 c cmnmna a1 1a a2 2a amm销量销量 b b1 1 b b2 2 b bn n成本表对于产销平衡的运输问题，有下面的关系式：对于产销平衡的运输问题，有下面的关系式：n n mm bj =aij=1 i=1j=1 i=1 销地销地产地产地 B B1 1 B B2 2 B Bn n产量产量A A1 1A A2 2 A Amm x x11

9、 11 x x12 12 x x1n1n x x21 21 x x22 22 x x2n2n x xm1 m1 x xm2 m2 x xmnmna a1 1a a2 2a amm销量销量 b b1 1 b b2 2 b bn n运量分配表用用x xij ij表示从表示从A Ai i 到到B Bj j 的的运量，在产销平衡的条件下，要运量，在产销平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模型：求得总运费最小的调运方案，可求解以下数学模型：m nm nMin Min z =cij xij i=1 j=1 i=1 j=1s.t.mm xij =bj ，j=1j=1，2 2，n n i=

10、1 i=1 n n xij =ai ，i=1i=1，2 2，mm j=1 j=1 xij0 在这个数学模型中，包含有在这个数学模型中，包含有m m n n个变量，有个变量，有（m+nm+n）个约束方程，约束条件中变量的系数个约束方程，约束条件中变量的系数比较特殊，不是比较特殊，不是1 1就是就是0 0。例例 5.2.1 5.2.1 海华设备厂均衡运输问题海华设备厂均衡运输问题 海华设备厂下设三个位于不同地点的分厂海华设备厂下设三个位于不同地点的分厂A A、B B、C C，该三个分厂生产同一种设备，设每该三个分厂生产同一种设备，设每月的生产能力分别为月的生产能力分别为2020台、台、3030台和

11、台和4040台。海华台。海华设备厂有四个固定用户，该四个用户下月的设设备厂有四个固定用户，该四个用户下月的设备需求量分别为备需求量分别为2020台、台、1515台、台、2323台和台和3232台。设台。设各分厂的生产成本相同，从各分厂至各用户的各分厂的生产成本相同，从各分厂至各用户的单位设备运输成本如表单位设备运输成本如表4.2.14.2.1所示，所示，表表5.2.1 5.2.1 海华设备厂运输成本表海华设备厂运输成本表分厂分厂名称名称运输成本（元运输成本（元/台）台）月生月生产能产能力力（台）（台）用户用户1 1用户用户2 2用户用户3 3用户用户4 4分厂分厂A A707040408080

12、60602020分厂分厂B B707010010011011050503030分厂分厂C C8080707013013040404040下月设下月设备需求备需求量（台）量（台）20201515232332329090而且各分厂本月末的设备库存量为零。问该厂应而且各分厂本月末的设备库存量为零。问该厂应如何安排下月的生产与运输，才能在满足四个用如何安排下月的生产与运输，才能在满足四个用户需求的前提下，使总运输成本最低。户需求的前提下，使总运输成本最低。解：可用一个网络图来描述解：可用一个网络图来描述A AB BC C4 43 32 21 170704040808060607070100100110

13、11050508080707013013040402020303040402020151523233232总供应量总供应量=20+30+40=90=20+30+40=90（台），（台），总需求量总需求量=20+15+23+32=90=20+15+23+32=90（台），（台），供应量之和等于需求量之和，供需均衡。供应量之和等于需求量之和，供需均衡。决策变量是下月各分厂为各用户生产与运输决策变量是下月各分厂为各用户生产与运输的设备数量。可设：的设备数量。可设：分厂分厂A A下月为四个用户生产和运输的设备数量下月为四个用户生产和运输的设备数量分别为分别为A A1 1，A A2 2 ，A A3 3

14、，A A4 4 （台）；台）；分厂分厂B B下月为四个用户生产和运输的设备数量分下月为四个用户生产和运输的设备数量分别为别为B B 1 1，B B 2 2 ，B B 3 3 ，B B 4 4 （台）；台）；分厂分厂C C下月为四个用户生产和运输的设备数量分下月为四个用户生产和运输的设备数量分别为别为C C 1 1，C C 2 2 ，C C 3 3 ，C C 4 4 （台）。台）。目标函数是总运输成本最小化，目标函数是总运输成本最小化，总运输成本总运输成本=70A=70A1 1+40 A+40 A2 2+80 A+80 A3 3 60 A 60 A4 4+70B 70B1 1+100 B+100

15、 B 2 2+110 B +110 B 3 3+50 B +50 B 4 4+80C +80C 1 1+70 C+70 C 2 2 +130 C +130 C 3 3+40 C +40 C 4 4 约束条件有两部分，第一部分是需求约束，各约束条件有两部分，第一部分是需求约束，各用户从各分厂收到的设备总数不得少于它们的用户从各分厂收到的设备总数不得少于它们的需求量：需求量：A A1 1+B+B1 1+C+C1 1=20=20A A2 2+B+B2 2+C+C2 2=15=15A A3 3+B+B3 3+C+C3 3=23=23A A4 4+B+B4 4+C+C4 4=32=32第二部分是生产能力

16、约束，各分厂生产和运输的第二部分是生产能力约束，各分厂生产和运输的设备总数不得超过其生产能力：设备总数不得超过其生产能力：A A1 1+A+A2 2+A+A3 3+A+A4 4=20=20B B 1 1+B+B 2 2+B +B 3 3+B +B 4 4=30=30C C 1 1+C+C 2 2+C +C 3 3+C +C 4 4=40=40最后，还有非负约束：最后，还有非负约束：A A1 1，A A2 2 ，A A3 3 ，A A4 4 ，B B 1 1，B B 2 2 ，B B 3 3 ，B B 4 4 ，C C 1 1，C C 2 2 ，C C 3 3，C C 4 4 0线性规划模型为：

17、线性规划模型为：Min 70AMin 70A1 1+40 A+40 A2 2+80 A+80 A3 3 60 A 60 A4 4+70B+70B1 1+100 B+100 B 2 2+110 +110 B B 3 3+50 B +50 B 4 4+80C +80C 1 1+70 C+70 C 2 2+130 C +130 C 3 3+40 C +40 C 4 4 s.t.As.t.A1 1+B+B1 1+C+C1 1=20=20 A A2 2+B+B2 2+C+C2 2=15=15 A A3 3+B+B3 3+C+C3 3=23=23 A A4 4+B+B4 4+C+C4 4=32=32A A

18、1 1+A+A2 2+A+A3 3+A+A4 4=20=20B B 1 1+B+B 2 2+B +B 3 3+B +B 4 4=30=30C C 1 1+C+C 2 2+C +C 3 3+C +C 4 4=40=40A A1 1，A A2 2 ，A A3 3 ，A A4 4 ，B B 1 1，B B 2 2 ，B B 3 3 ，B B 4 4 ，C C 1 1，C C 2 2 ，C C 3 3，C C 4 4 0四、供需非均衡运输问题的建模与求解1 1、当供给大于需求时，即、当供给大于需求时，即 n n mm bj aij=1 i=1j=1 i=1 销地销地产地产地 B B1 1 B B2 2

19、 B Bn n产量产量A A1 1A A2 2 A Amm c c11 11 c c12 12 c c1n1n c c21 21 c c22 22 c c2n2n c cm1 m1 c cm2 m2 c cmnmna a1 1a a2 2a amm销量销量 b b1 1 b b2 2 b bn n成本表成本表 销地销地产地产地 B B1 1 B B2 2 B Bn n产量产量A A1 1A A2 2 A Amm x x11 11 x x12 12 x x1n1n x x21 21 x x22 22 x x2n2n x xm1 m1 x xm2 m2 x xmnmna a1 1a a2 2a a

20、mm销量销量 b b1 1 b b2 2 b bn n运量分配表运量分配表用用x xij ij表示从表示从A Ai i 到到B Bj j 的运量，在产销非平衡的条件下，要的运量，在产销非平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模型：求得总运费最小的调运方案，可求解以下数学模型：m nm nMin Min z =cij xij i=1 j=1 i=1 j=1s.t.mm xij =bj ，j=1j=1，2 2，n n i=1 i=1 n n xij ai i=1i=1，2 2，mm j=1 j=1 xij02 2、当供给小于需求时，即、当供给小于需求时，即n n mm bj ai

21、j=1 i=1j=1 i=1 销地销地产地产地 B B1 1 B B2 2 B Bn n产量产量A A1 1A A2 2 A Amm c c11 11 c c12 12 c c1n1n c c21 21 c c2222 c c2n2n c cm1 m1 c cm2 m2 c cmnmna a1 1a a2 2a amm销量销量 b b1 1 b b2 2 b bn n成本表成本表 销地销地产地产地 B B1 1 B B2 2 B Bn n产量产量A A1 1A A2 2 A Amm x x11 11 x x12 12 x x1n1n x x21 21 x x22 22 x x2n2n x xm

22、1 m1 x xm2 m2 x xmnmna a1 1a a2 2a amm销量销量 b b1 1 b b2 2 b bn n运量分配表运量分配表用用x xij ij表示从表示从A Ai i 到到B Bj j 的运量，在产销非平衡的条件下，要的运量，在产销非平衡的条件下，要求得总运费最小的调运方案，可求解以下数学模型：求得总运费最小的调运方案，可求解以下数学模型：m nm nMin Min z =cij xij i=1 j=1 i=1 j=1s.t.mm xij bj ，j=1j=1，2 2，n n i=1 i=1 n n xij=ai i=1i=1，2 2，mm j=1 j=1 xij0例例

23、 5.2.1 5.2.1 海华设备厂非均衡运输问题海华设备厂非均衡运输问题若例若例4.2.14.2.1中的三个分厂经技术改造，每月的生产中的三个分厂经技术改造，每月的生产能力均增加了能力均增加了5 5台，即分别从台，即分别从2020台、台、3030台、台、4040台台增加为增加为2525台、台、3535台、台、4545台，其他条件不变为应该台，其他条件不变为应该如何安排下月的生产与运输，才能在满足四个用如何安排下月的生产与运输，才能在满足四个用户的前提下使总运输成本最低。户的前提下使总运输成本最低。A AB BC C4 43 32 21 1707040408080606070701001001

24、101105050808070701301304040解：可用一个网络图来描述解：可用一个网络图来描述2525353545452020151523233232总供应量总供应量=25+35+45=105=25+35+45=105（台），（台），总需求量总需求量=20+15+23+32=90=20+15+23+32=90（台），（台），供应量之和大于需求量之和，供需不均衡。需供应量之和大于需求量之和，供需不均衡。需求节点收到的产品总数等于其总需求量，而各求节点收到的产品总数等于其总需求量，而各供应节点发出的产品总数则小于其供应能力。供应节点发出的产品总数则小于其供应能力。模型变为：模型变为：Min

25、 70AMin 70A1 1+40 A+40 A2 2+80 A+80 A3 3 60 A 60 A4 4+70B+70B1 1+100 B+100 B 2 2 +110 B+110 B 3 3+50 B +50 B 4 4+80C +80C 1 1+70 C+70 C 2 2+130 C +130 C 3 3+40 C +40 C 4 4 s.t.As.t.A1 1+B+B1 1+C+C1 1=20=20 A A2 2+B+B2 2+C+C2 2=15=15 A A3 3+B+B3 3+C+C3 3=23=23 A A4 4+B+B4 4+C+C4 4=32=32A A1 1+A+A2 2+

26、A+A3 3+A+A4 4 25 25B B 1 1+B+B 2 2+B +B 3 3+B +B 4 4 35 35C C 1 1+C+C 2 2+C +C 3 3+C +C 4 4 45 45A A1 1，A A2 2 ，A A3 3 ，A A4 4 ，B B 1 1，B B 2 2 ，B B 3 3 ，B B 4 4 ，C C 1 1，C C 2 2 ，C C 3 3，C C 4 4 0五、运输问题的应用例例 :北方飞机制造公司为全世界的航空公司生产各北方飞机制造公司为全世界的航空公司生产各 种商务飞机。制造过程的最后一步是生产喷气种商务飞机。制造过程的最后一步是生产喷气发动机并把它们安装

27、到已经完成的飞机框架之发动机并把它们安装到已经完成的飞机框架之中去。按照公司的一些订单合同，不久公司要中去。按照公司的一些订单合同，不久公司要交付使用相当多数量的飞机。所以有必要现在交付使用相当多数量的飞机。所以有必要现在为未来四个月这些飞机喷气发动机的生产制定为未来四个月这些飞机喷气发动机的生产制定计划。计划。北方飞机制造公司问题的生产进度安排数据月月份份计划计划安装安装量量最大产量最大产量单位生产成本（百单位生产成本（百万美元）万美元）单位存单位存储成本储成本(百万百万美元美元)正常时间正常时间 加班时间加班时间 正常时间正常时间 加班时间加班时间1 11010202010101.081.

28、081.101.100.0150.0152 21515303015151.111.111.121.120.0150.0153 32525252510101.101.101.111.110.0150.0154 420205 510101.131.131.151.15 生产管理人员需要制定出一个每月生产多少发生产管理人员需要制定出一个每月生产多少发动机的计划动机的计划,使制造和存储的总成本达到最小。使制造和存储的总成本达到最小。例 产品分配计划n n求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造。就哪个工厂生产哪种产品做决策,使总成本达到最小。公司的产品数据 单位成本单位成本 可

29、用能力可用能力 产品产品 1 2 3 4 1 2 3 4 工厂工厂 1$41$27$28$24 751$41$27$28$24 75 2 40 29 -23 75 2 40 29 -23 75 3 37 30 27 21 45 3 37 30 27 21 45要求产量要求产量 20 30 30 4020 30 30 40 单位利润单位利润 顾客顾客:1 2 3 4 :1 2 3 4 生产能力生产能力工厂工厂 1$55$42$46$53 8,0001$55$42$46$53 8,000 2 37 18 32 48 5,000 2 37 18 32 48 5,000 3 29 59 51 35 7

30、,000 3 29 59 51 35 7,000最少购买力最少购买力 7000 3000 2000 07000 3000 2000 0最大购买力最大购买力 7000 9000 6000 80007000 9000 6000 8000例 产品销售计划目标n n决定向每位顾客销售多少单位的产品以及为实现最大利润。5.2指派问题(assignment problem)一、什么是指派问题二、指派问题的一般数学模型三、指派问题在电子表格中的建模与求解一、什么是指派问题有有n n项任务，恰好有项任务，恰好有n n个人可承担这些任务，个人可承担这些任务，要求要求每项任务必须且只能有一个承担者完成，每个承每项

31、任务必须且只能有一个承担者完成，每个承担者必须且只能承担一项任务担者必须且只能承担一项任务，每个人的专长不，每个人的专长不同，各人完成任务所费的时间不同，效率也不同，同，各人完成任务所费的时间不同，效率也不同，于是产生派哪个人去完成哪项任务，使得完成于是产生派哪个人去完成哪项任务，使得完成n n项任务的总效率最高，或者是所需的时间最短？项任务的总效率最高，或者是所需的时间最短？这类问题称为指派问题或分派问题。这类问题称为指派问题或分派问题。例例 ：有一份中文说明书，需译成英、日、德、：有一份中文说明书，需译成英、日、德、俄四种文字，分别记作俄四种文字，分别记作E E、J J、G G、R R，现

32、有甲、现有甲、乙、丙、丁四人。他们将中文说明书翻译成乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表所示，问应不同语种的说明书所需时间如表所示，问应指派何人去完成何工作，使所需总时间最少指派何人去完成何工作，使所需总时间最少？任务任务人员人员E EJ JG GR R甲甲2 2151513134 4乙乙10104 414141515丙丙9 9141416161313丁丁7 78 811119 9单位：小时单位：小时又如：有又如：有n n项加工任务，怎样指派到项加工任务，怎样指派到n n台台机床机床上分别完成的问题，有上分别完成的问题，有n n条航线，怎样指定条航线，怎样指定n

33、n艘船去艘船去航行的问题等等都是指派问题。航行的问题等等都是指派问题。二、指派问题的数学模型设决策变量为设决策变量为x xij ij，其值只能取其值只能取1 1或或0 0，并令，并令X Xij ij=1 =1 当指派第当指派第i i人去人去完成第完成第j j项任务项任务 0 0 当不指派第当不指派第i i人去完成第人去完成第j j项任务项任务设设c cij ij为系数矩阵中的任一元素为系数矩阵中的任一元素，则它的一般数学则它的一般数学模型为：模型为：任务任务人员人员 B B1 1 B B2 2 B Bn n分配的分配的任务任务A A1 1A A2 2 A An n c c11 11 c c12

34、 12 c c1n1n c c21 21 c c2222 c c2n2n c cn1 n1 c cn2 n2 c cnnnn1 11 11 1要完成的要完成的任务任务 1 1 1 1 1 1 任务任务人员人员 B B1 1 B B2 2 B Bn n分配的分配的任务任务A A1 1A A2 2 A An n x x11 11 x x12 12 x x1n1n x x21 21 x x2222 x x2n2n x xn1 n1 x xn2 n2 x xnnnn1 11 11 1要完成的要完成的任务任务 1 1 1 1 1 1 n n n nMin Min z =cij xij i=1 j=1 i

35、=1 j=1s.t.n n xij =1，j=1j=1，2 2，n n i=1 i=1 n n xij =1，i=1i=1，2 2，n n j=1 j=1 X Xij ij=1=1 或或 0 0一般的模型为：最初的指派问题任务数与人员数相同，后来指最初的指派问题任务数与人员数相同，后来指派问题进行了扩展，要完成的任务数和人员数派问题进行了扩展，要完成的任务数和人员数可以不同，而且可附加其他条件，具体情况具可以不同，而且可附加其他条件，具体情况具体分析。体分析。例例 ：有一份中文说明书，需译成英、日、德、：有一份中文说明书，需译成英、日、德、俄四种文字，分别记作俄四种文字，分别记作E E、J J

36、、G G、R R，现有甲、现有甲、乙、丙、丁四人。他们将中文说明书翻译成乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表所示，问应不同语种的说明书所需时间如表所示，问应指派何人去完成何工作，使所需总时间最少指派何人去完成何工作，使所需总时间最少？任务任务人员人员E EJ JG GR R甲甲2 2151513134 4乙乙10104 414141515丙丙9 9141416161313丁丁7 78 811119 9单位：小时单位：小时1.1.有一些被指派者并不能进行某一些的任务。2.2.任务比被指派者多。3.3.被指派者比要完成的任务多。指派问题的变形指派问题的变形 指派问题的

37、变形指派问题的变形4.4.每个被指派者可以同时被指派给多于一个的任务。5.5.每一项任务都可以由多个被指派者共同完成。例例5.2.15.2.1金工车间任务指派问题金工车间任务指派问题某金工车间要加工四种零件，现有五台机器某金工车间要加工四种零件，现有五台机器可以使用，表可以使用，表4.3.14.3.1给出了各台机器加工各种给出了各台机器加工各种零件所需的时间。若每台机器最多只能承担零件所需的时间。若每台机器最多只能承担一种零件。问应如何分配任务，才能使得完一种零件。问应如何分配任务，才能使得完成四种零件加工任务的总时间最短。成四种零件加工任务的总时间最短。表表4.3.14.3.1金工车间加工零

38、件时间表（单位：小时）金工车间加工零件时间表（单位：小时）机器机器零件零件1 1零件零件2 2零件零件3 3零件零件4 41 110103 38 86 62 23 312127 75 53 37 78 85 59 94 44 44 46 67 75 55 55 54 48 8例：分配甲、乙、丙、丁四人去完成五项任务。例：分配甲、乙、丙、丁四人去完成五项任务。每人完成各项任务时间如表所示，由于任务数每人完成各项任务时间如表所示，由于任务数多于人数，故规定其中有一个人可见完成两项多于人数，故规定其中有一个人可见完成两项任务，其余三人每人完成一项。试确定总花费任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。时间为最少的指派方案。任务任务人人A AB BC CD DE E甲甲25252929313142423737乙乙39393838262620203333丙丙34342727282840403232丁丁24244242363623234545