北京交通大学 高级运筹学-指派问题.ppt

§5 指派问题AssignmentProblem有n项任务，恰好n个人承担，第i人完成第j项任务的花费(时间或费用等)为cij，如何指派使总花费最省？第j项工作由一个人做第i人做一项工作例7有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？已知条件可用系数矩阵（效率矩阵）表示为：其可行解也可用每行仅有一个1，每列也仅有一个1的矩阵表示，如：-2-4-9-7若某行(列)已有0元素，那就不必再减了。例7的计算为： 匈牙利法解题步骤：10使系数矩阵各行、各列出现零元素作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。(因一行中xij取值一个1，其余为0，cij同时减去一常数不影响xij取值)。-4-220试求最优解。如能找出n个位于不同行不同列的零元素，独立0令对应的xij=1，其余xij=0，得最优解，结束；否则下一步。作法：由独立0元素的行（列）开始，独立0元素处画标记，在有的行列中划去其它0元素；再在剩余的0元素中重复此做法，直至不能标记为止。例8．求表中所示效率矩阵的指派问题的最小解。任务人ABCDE甲127979乙89666丙71712149丁15146610戊4107109?再按上述步骤运算，得到：所画0元素少于n，未得到最优解。???30作能覆盖所有0元素的最少数直线集合作法：(1)对没有的行打?号；(2)对已打?号的行中所有0元素的所在列打?号；(3)再对打有?号的列中0元素的所在行打?号；(4)重复(2),(3)直到得不出新的打?号的行(列)为止；(5)对没有打?号的行画一横线，对打?号的列画一纵线，这就得到覆盖所有0元素的最少直线数未被直线覆盖的最小元素为cij,在未被直线覆盖处减去cij,在直线交叉处加上cij。Cij=2解为：思考：此题是否还有别的最优解？对于最大化指派问题如何处理？任务数与人数不等时如何处理？