表423分枝问题的松弛解 问题I 问题I 2 3 9/4 21 问题Ⅲ的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况,则需要两边同时 继续分枝,直到有整数解出现,就可以进行定界过程 当存在很多变量有整数约束时,分枝即广又深,在最坏情 况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题,NP- complete 只有少数特殊问题有好的算法,如任务分配问题、匹配问题
6 表4.2.3 分枝问题的松弛解 问 题 I 问 题 I I x1 2 3 x2 9/4 1 f(x) 2 1 2 2 问题II的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同时 继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情 况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，NP-complete， 只有少数特殊问题有好的算法，如任务分配问题、匹配问题
46任务分配问题 例46.1有四个熟练工人,他们都是多面手,有四项任务要他 们完成。若规定每人必须完成且只完成一项任务,而每人 完成每项任务的工时耗费如表46.1,问如何分配任务使完 成四项任务的总工时耗费最少? 任务 工时、ABCD人员 mif(x)=∑∑anxn 人员 1i=1,2 甲乙丙丁 552 9843—1 77641 87551 ∑x=1j=1,2,…,m 0.1 任务
7 4.6 任务分配问题 例4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他 们完成。若规定每人必须完成且只完成一项任务，而每人 完成每项任务的工时耗费如表4.6.1，问如何分配任务使完 成四项任务的总工时耗费最少？ = = = = = = = = = = 0,1 1 1,2, , 1 1,2, , min ( ) 1 1 1 1 i j m i i j m j i j m i m j i j i j x x j m x i m f x a x 任 务 工 时 A B C D 人 员 人 员 甲 1 0 9 7 8 1 乙 5 8 7 7 1 丙 5 4 6 5 1 丁 2 3 4 5 1 任 务 1 1 1 1