摘要 指派问题是现实生活中经常遇到的一类组合优化问题,应用十分广泛。优化指派方案就是要求使完成任务的效率最高(或所需时间最小或所需费用最低)。本文提出了用分支定界算法优化指派问题,分支定界算法采用了类似分而治之的算法策略, 在分析一个组合最优化问题的一切可行解的过程中, 采取了必要的限制条件, 设法排除可行域中大量非最优解区域,从而简化了求解过程。分支定接算法是一种解决指派问题的新方法,在工作应用中有一定实际意义。
关键词 分支定界算法;指派问题;优化指派方案
中图分类号 O22 文献标识码 A 文章编号 1674-6708(2009)07-0111-02
1 指派问题模型
设=(i、j=1,2,n),则标准指派问题的数学模型可表示如下:
模型中,表示第i人做第j事所需的时间,约束条件(a)表示每件事有且只有一个人去做,约束条件(b)表示每个人做且只做一件事。
2 算法思想
分支定界算法(Branch and Bound Method,B&B) 的思想是把给定问题分解为若干个较小的子问题,每个子问题又可继续分解,直到子问题不能再分解或不能产生最优解,根据问题的特点和不同的策略,把问题分解为子问题的过程称为分支。在分支过程中,为每一子问题估算对应的目标值的界限称为定界。定界的目的是为了测定界的趋势,留下有价值的或尚不能判定的分支。删除肯定不存在的最优解的分支称为剪支,以达到加速收敛、简化运算的目的。对问题进行分解,确定子问题的解值界限,减去非优的子问题,再进行新的分支,这样由分支到定界到剪支再到分支等反复的过程是分支定界法的基本算法步骤。
根据分支定界算法思想求解指派问题时,暂时不考虑指派问题中每个人只能指派一项任务,即每个人可以完成多个任务,这样将原问题模型(1)变成如下松弛模型:
此时,松弛模型(2)可行解区域包含了原问题模型(1)可行解的集合,因而松弛模型的最优解要优于原问题的最优解。通过松弛模型的解求得原问题最优解的步骤如下:
设原问题的一个解集合为A,松弛模型的一个解集合为B。
Step1:不考虑每个人只能完成一项任务,找出完成各项任务时间最少(效率最高或费用最低)的人员,安排其完成该任务。
Step2:如果得到的解是每个人只完成一项任务,则求解结束,该解也是原问题的最优解。否则,得到的解只是原问题的最优解的一个下界。
Step3:从第一项任务开始固定指派不同人员,而后不考虑该任务及人员重复Step1,求得松弛模型的一个解集合C。如果集合C中的某个解是每个人只完成一项任务,则该解是原问题的一个解,也是原问题最优解的一个上界,将该解加入集合A,其它解加入集合B。
Step4:比较集合B中的解对应的总时间(效率或费用),选择最小者固定指派该人员,该任务不再考虑其它指派。回到Step3,直到完成最后一项任务的指派,得到一个原问题的解,加入集合A。
Step5:比较集合A中解对应的总时间(效率或费用),最小者对应解记作。
Step6:比较与集合B中解对应的总时间(效率或费用),若集合B中存在对应的总时间(效率或费用)比对应的小,对解重复Step3、4,求得的原问题的解与进行比较,总时间(效率或费用)最小者对应的解就是原问题的最优解。
3 实例分析
某单位有4项任务需要完成,要求每个人只能完成一项任务,每个人完成各项任务的时间见下表,问如何安排人员使得完成任务的总时间最少。
暂时不考虑每个人只能完成一项任务,则可行解个数有4!=24个。
求解过程如下:
step1:各列取最小进行指派人员。
在此,22为所有可行解的下界。
Step2:检验是否已得完全指派(题目要求的指派),若可得完全指派,则该解为原问题的最优解。若否 (如上表右下角标注Not yet),固定一个指派,删除该指派所对应的时间表,回step1,计算后找出总计时间最小者。
在指定A做任务1之后,表中第1列的数据在后续计算中不再考虑。
在指定B做任务1之后,表中第2列的数据在后续计算中不再考虑。
在指定C做任务1之后,表中第3列的数据在后续计算中不再考虑。
在指定D做任务1之后,表中第四列的数据在后续计算中不再考虑。
表2~5中,表5总时间最小,在此,28为新的下界,由此处继续。
Step3: 固定下一个指派,删除该指派所对应的时间表,回到step1,计算后找出总计时间最小者。
表6~8中表7总时间最小,在此,28为新的下界,由此处继续。
Step4:
表9与10均符合完全指派,较小值32为原问题所有可行解的上界,任何表之值大于32者均可忽略。
Step5:比较其它分支的表,检验是否有低于32之值,表2、3、4、6、8、10中只有表2低于32,予以进一步分支。
表12为可行解,但其值仍大于表9之值,表11之值虽然等于32,但由此分支下去的也一定大于等于32,并不会低于表9,所以,表9为最优解。
参考文献
[1]胡运权.运筹学教程[M].北京:清华大学出版社,1998.
[2]《运筹学》教材编写组.运筹学[M].北京:清华大学出版社,2003.
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文