整数规划指派问题(1).ppt

例 有一份中文说明书，需译成英、日、德、俄四 种文字。分别记作E、J、G、R。现有甲、乙、丙、 丁四人，他们将中文说明书翻译成不同语种的说明书 所需时间如下表。问应指派何人去完成何工作，使所 需总时间最少？ 5 指派问题 Assignment Problem 5 指派问题 Assignment Problem 有n项任务，分派给n个人承担，每人承担一项。 第i 人完成第j 项任务的花费(时间或费用等)为cij，如 何分派使总花费最省？ 第j项工作只由 一个人完成 第i人只完成一 项工作 5 指派问题 Assignment Problem 已知条件可用系数矩阵（效率矩阵）表示为： 其可行解也可用每行仅有一个1，每列也仅有一个 1的矩阵表示，如： 阅读课本内容，了解算法，10分钟！ 例7的计算为： 匈牙利法解题步骤： 1 使系数矩阵各行、各列均出现0元素 若某行(列)已有0元素，不必处理，否则： 系数矩阵各行元素减去所在行的最小元素，再 从所得矩阵的各列减去所在列最小元素。(因一行中 xij 取值一个1，其余为0，cij 同时减去一常数不影响 xij取值)。 -4 -2 -2 -4 -9 -7 需要指派的矩阵 效率矩阵 2 试派：即找独立0元素 独立0元素：一个0，如果其所在行和列有且仅有这一 个0，则称之为独立0元素。 试派方法： 10对每行检查，若当前行只有一个0，则给它加圈，标 为“ 0 ” ，同时把该0元素所在列的其他0元素划去，标 为 “ 0 ” ； 20对每列检查，若当前列只有一个0（划去的0不算） ，则给它加圈，标为“ 0 ” ，同时把该0元素所在行的其 他0元素划去，标为 “ 0 ” ； 2 试派：（续） 30若同行（列）中0元素均多于1个，把其中任一个0元素 加圈，同时把该0元素所在的行和列中的其它0元素划去。 反复执行10，20，30，直到所有0元素均被处理。 记 0 的个数为m。 当m=n时，令所有 0 对应的xij=1，其余xij=0,得到最优解。 当mn时，转第3步 3 确定覆盖全部0元素的最小直线数 10对无 0 的行打“”； 20对打“”行中 0 所在的列打“”； 30再对打“”列中的 0 所在的行打“”； 重复进行20，30，直至不能打“”为止。 40对所有无“”的行画一横线；所有打“”的列画一 纵线，记总线数为l 3 确定覆盖全部0元素的最小直线数（续） 当l=n时，说明试派不成功，重新试派； 当ln时，转第4步 4 增加0元素的个数，但不出现负元素 设无直线覆盖的元素中最小的元素为a，对 所有打“”的行中各元素减去a； 所有打“”的列中各元素加上a。 再重新试派，直至得到最优解。 例8求表中所示效率矩阵的指派问题的最小解。 任 务务 人 ABCDE 甲127979 乙89666 丙71712149 丁15146610 戊4107109 1 使系数矩阵各行、各列均出现0元素 所有0元素均处理完了，0 小于5，未得到最优解。 转第3步 试派： l5,转转第4步，增加0元素的个数 3 确定覆盖所有0元素的最少数直线数： (1) 对没有 0 的行打 号； (2) 对已打 号的行中所有0元素的所在列打 号； (3) 再对打有 号的列中 0 元素的所在行打 号； (4)重复(2),(3)直到得不出新的打 号的行(列)为止； (5) 对没有打 号的行画一横线，对打 号的列画一 纵线，得到覆盖所有0元素的最少直线数l 4 增加0元素的个数 设没被直线覆盖的最小元素为a,在所有打“”的行 中各元素减去a；所有打“”的列中各元素加上a。 a=2 重新试派 解为 ： 思考：最优值是多少？ 此题是否还有别的最优解？ 3 4 1 4 0 4 0 0 8 11 0 5 3 8 0 0 0 0 3 4 2 0 2 0 7 甲 乙 丙 丁 戊 A B C D E 127979 89666 71712149 15146610 4107109 17-1217- 717- 917- 717- 9 17- 817- 917- 617- 617- 6 17- 717- 1717- 1217- 1417- 9 17- 1517- 1417- 617- 617- 10 17- 417- 1017- 717- 1017- 9 指派问题及解法（续） 对于最大化指派问题如何处理？ 17-1217- 717- 917- 717- 9 17- 817- 917- 617- 617- 6 17- 717- 1717- 1217- 1417- 9 17- 1517- 1417- 617- 617- 10 17- 417- 1017- 717- 1017- 9 5108108 98111111 100538 2311117 1371078 指派问题及解法（续） 任务 人 A B C D E 甲59112217 乙242311518 丙14782012 丁42216325 指派问题及解法（续） 任务与人员数不等的情况 人少任务多 解：虚设一理想人，其完成各项任务时间为该任 务完成的最少时间： 任务 人 A B C D E 甲59112217 乙242311518 丙14782012 丁42216325 戊4丁7丙8丙3丁12丙 指派问题及解法（续） 人 工作 甲 乙 丙 丁 戊 11023159 25101524 315514715 420151368 指派问题及解法（续） 规定每人只能完成一项任务。由于某种原因， 甲必须被分配一项任务，丁不承担第4项任务，试 确定总花费时间最少的分派方案。