《07整数规划指派问题.ppt》由会员分享，可在线阅读，更多相关《07整数规划指派问题.ppt（20页珍藏版）》请在三一文库上搜索。
1、例 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？,5 指派问题,Assignment Problem,5 指派问题,Assignment Problem,有n项任务，分派给n个人承担，每人承担一项。第i 人完成第j 项任务的花费(时间或费用等)为cij，如何分派使总花费最省？,第j项工作只由一个人完成,第i人只完成一项工作,5 指派问题,Assignment Problem,已知条件可用系数矩阵（效率矩阵）表示为：,其可行解也可用每行仅有一个1，
2、每列也仅有一个1的矩阵表示，如：,阅读课本内容，了解算法，10分钟！,例7的计算为：,匈牙利法解题步骤：,1 使系数矩阵各行、各列均出现0元素 若某行(列)已有0元素，不必处理，否则： 系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。(因一行中xij 取值一个1，其余为0，cij 同时减去一常数不影响xij取值)。,-4 -2,-2 -4 -9 -7,需要指派的矩阵,效率矩阵,2 试派：（续）,30若同行（列）中0元素均多于1个，把其中任一个0元素加圈，同时把该0元素所在的行和列中的其它0元素划去。 反复执行10，20，30，直到所有0元素均被处理。 记 0 的个数
3、为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。
4、 再重新试派，直至得到最优解。,例8求表中所示效率矩阵的指派问题的最小解。,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,
5、在所有打“”的行中各元素减去a；所有打“”的列中各元素加上a。,a=2,重新试派,解为：,思考：最优值是多少？ 此题是否还有别的最优解？,甲 乙 丙 丁 戊,A B C D E,指派问题及解法（续）,对于最大化指派问题如何处理？,指派问题及解法（续）,指派问题及解法（续）,任务与人员数不等的情况,人少任务多,解：虚设一理想人，其完成各项任务时间为该任务完成的最少时间：,指派问题及解法（续）,指派问题及解法（续）,规定每人只能完成一项任务。由于某种原因， 甲必须被分配一项任务，丁不承担第4项任务，试 确定总花费时间最少的分派方案。,人多任务少,指派问题及解法（续）,解： 虚设任务5，各人完成该项任务时间为0，某人不完成某任务时，取时间M（充分大的时间）,