教师培训课件：数学建模中的指派

指派问题合理利用人力资源的方法各装卸队完成各车装卸的时间（分配装卸任务）车装卸 队1 2 3 4 5A 4 5 7 3 6B 1 3 5 8 4C 2 6 5 7 2D 3 5 6 3 6E 9 3 4 3 4招聘翻译、文书、项目经理、广告策划成 绩人 员外 语 计 算机管理学传 媒学A 84 81 77 83B 83 82 85 85C 78 76 75 77D 86 85 87 86典型问题l 有 n 件工作要完成l 有 n 个人可以调用l 每件工作可以指派任何人做，但效率不同l 一件工作只能由一个人做l 一个人只能做一件工作l 如何指派可使效率最高例：各装卸队完成各车装卸的时间（分配装卸任务）车装卸 队1 2 3 4 5A 4 5 7 3 6B 1 3 5 8 4C 2 6 5 7 2D 3 5 6 3 6E 9 3 4 3 4指派的要求 -通过表格表示l 每行取 一个数且只取一个数 （一个人做一件工作且只做一件工作）l 每列取一个数且只取一个数 （每件工作必须有人做且只由一个人）l 在表中共取出五个数，分别在不同行不同列上 （指派工作的一种方案）l 这五个数的和表示该方案的效率在所有的方案中找到和为最小（效率最好）的方案工作人1 2 3A 4 5 7B 1 3 5C 2 6 5如果某件工作由任何人完成都要增加（或减少）相同的时间，则最优方案不变6 3 4工作人1 2 3A 4 5 7B 1 3 5C 2 6 5如果某个人完成任何工作都要增加（或减少）相同的时间，则最优方案不变1 2 41 2 3A 4 5 7B 1 3 5C 2 6 51 2 3A 0 1 3B 0 2 4C 0 4 31 2 3A 0 0 0B 0 1 1C 0 3 01 2 3A 0 0 0B 0 1 1C 0 3 0A 做第 2 件工作， B 做第 1 件工作， C 做第 3 件工作在不同行、不同列上有三个零，总和为零，对应最佳方案工作人I II III IV VA 4 5 7 3 6B 1 3 5 8 4C 2 6 5 7 2D 3 3 6 3 6E 9 5 4 3 4练习 （表中为时间）工作人I II III IV VA 1 2 3 0 3B 0 2 3 7 3C 0 4 2 5 0D 0 0 2 0 3E 6 2 0 0 1答案 （找最佳方案）更 复杂的情况演地演出 团1 2 3 4 5A 4 5 7 3 6B 1 3 5 8 4C 2 6 5 7 2D 3 5 6 3 6E 9 3 4 3 44 5 7 3 61 3 5 8 42 6 5 7 23 5 6 3 69 3 4 3 41 2 4 0 30 2 4 7 30 4 3 5 00 2 3 0 36 0 1 0 11 2 3 0 30 2 3 7 30 4 2 5 00 2 2 0 36 0 0 0 11 2 3 0 30 2 3 7 30 4 2 5 00 2 2 0 36 0 0 0 1表中每 行、每列都有零 但是没有不在同一行、同一列的五个零1 2 3 0 30 2 3 7 30 4 2 5 00 2 2 0 36 0 0 0 11 2 3 0 30 2 3 7 30 4 2 5 00 0 2 0 36 2 0 0 1要划去表中所有的零，至少要五条直线段（横线或竖线）表中有五个在不同行、不同列的零划去 所有零的最少线段数： 41 2 3 0 30 2 3 7 30 4 2 5 00 2 2 0 36 0 0 0 1 1 0 1 21 2 0 1 5 1 2 2 0 3 2 2 0 0 214 2 2 2 11 0 1 0 10 0 1 7 10 2 0 5 20 0 0 0 16 2 2 0 11 0 1 0 10 0 1 7 12 4 2 7 00 0 0 0 18 0 0 2 11 2 3 0 30 2 3 7 30 4 2 5 00 2 2 0 36 0 0 0 11 0 1 0 10 0 1 7 12 4 2 7 00 0 0 0 18 0 0 2 1未划去的数减去 2在交叉点上的数加上 2划去的数但不在交叉点上的数不变练习： 划去下表中的所有零最少的线段？是几条？1 2 3 0 30 2 3 7 35 0 2 0 00 1 2 0 36 1 0 0 1练习： 划去下表中的所有零最少的线段？是几条？1 2 0 0 30 2 0 7 35 0 2 0 00 1 0 0 06 1 0 0 1把 方法应用到更多的问题中去l 人数和工作数不相等l 求最大值（不是求最小值）人数和工作数不相等待卸 车装卸 组1 2 3 4 5A 4 5 7 3 6B 1 3 5 8 4C 2 6 5 7 2D 3 5 6 3 6人数和工作数不相等工作人 员1 2 3 4 5A 4 5 7 3 6B 1 3 5 8 4C 2 6 5 7 2D 3 5 6 3 6E 0 0 0 0 0求 最大值（招聘翻译、文书、项目经理、广告策划）成 绩人 员外 语 计 算机管理学传 媒学A 84 81 77 83B 83 82 85 85C 78 76 75 77D 86 85 87 86成 绩人 员外语计 算机管理学传 媒学A 16 19 23 17B 17 18 15 15C 22 24 25 23D 14 15 13 14成 绩人 员外语计 算机管理学传 媒学A 84 81 77 83B 83 82 85 85C 78 76 75 77D 86 85 87 86成 绩人 员