整数规划指派问题

《整数规划指派问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§5指派问题AssignmentProblem有n项任务，分派给n个人承担，每人承担一项。第i人完成第j项任务的花费(时间或费用等)为cij，如何分派使总花费最省？第j项工作只由一个人完成第i人只完成一项工作例7有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？已知条件可用系数矩阵（效率矩阵）表示为：其可行解也可用每行仅有一个1，每列也仅有一个1的矩阵表示，如：阅读课本内容，了解算法，10分钟！例7的计算为：匈牙利法解题步骤：1使系数矩

2、阵各行、各列均出现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

3、元素划去，标为“0”；2试派：（续）3确定覆盖全部0元素的最小直线数10对无0的行打“√”；20对打“√”行中0所在的列打“√”；30再对打“√”列中的0所在的行打“√”；重复进行20，30，直至不能打“√”为止。40对所有无“√”的行画一横线；所有打“√”的列画一纵线，记总线数为l30若同行（列）中0元素均多于1个，把其中任一个0元素加圈，同时把该0元素所在的行和列中的其它0元素划去。反复执行10，20，30，直到所有0元素均被处理。记0的个数为l。当l=n时，令所有0对应的xij=1，其余xij=0,得到最优解。当l

4、续）当l=n时，说明试派不成功，重新试派；当l

5、有0元素的所在列打号；(3)再对打有号的列中0元素的所在行打号；(4)重复(2),(3)直到得不出新的打号的行(列)为止；(5)对没有打号的行画一横线，对打号的列画一纵线，得到覆盖所有0元素的最少直线数l4增加0元素的个数设没被直线覆盖的最小元素为a,在所有打“√”的行中各元素减去a；所有打“√”的列中各元素加上a。a=2重新试派解为：思考：最优值是多少？此题是否还有别的最优解？úúúúúúûùêêêêêêëé34140400811053800003420207甲乙丙丁戊ABCDE127979896667171214915146610410710917-121

6、7-717-917-717-917-817-917-617-617-617-717-1717-1217-1417-917-1517-1417-617-617-1017-417-1017-717-1017-9指派问题及解法（续）对于最大化指派问题如何处理？17-1217-717-917-717-917-817-917-617-617-617-717-1717-1217-1417-917-1517-1417-617-617-1017-417-1017-717-1017-951081089811111110053823111171371078指派问题及解法（续）任务人ABCDE甲59

7、112217乙242311518丙14782012丁42216325指派问题及解法（续）任务与人员数不等的情况人少任务多解：虚设一理想人，其完成各项任务时间为该任务完成的最少时间：任务人ABCDE甲59112217乙242311518丙14782012丁42216325戊4丁7丙8丙3丁12丙指派问题及解法（续）人工作甲乙丙丁戊1102315925101524315514715420151368指派问题及解法（续）规定每人只能完成一项任务。由于某种原因，甲必须被分配一项任务，丁不承担第4项任