求解多项目组合选择问题的奔德斯分解算法

随着我国经济的快速发展,项目组合选择问题所面临的待选项目集日益膨胀.而项目组合选择模型通常表示为整数规划或混合整数规划的形式,过多的待选项目会对项目组合选择模型的高效求解带来巨大的挑战.针对这一问题,本文研究了多项目组合选择模型的奔德斯分解算法.将原问题分解成仅考虑从待选项目集中选出最优组合的主问题与对已选项目进行排序的子问题,通过主子问题间的迭代逐步逼近最优解.通过算法性能分析,发现直接使用奔德斯分解算法存在着收敛速度慢,子问题不可行的缺点.为了加速算法的收敛速度,对主问题进行了修正,提出了一种利用潜在的最优项目及有效不等式改进主问题的新思路.最后,通过算例分析,对比了直接使用分支定界法与使用奔德斯分解算法两类求解方法的求解效率,验证了本文所提出方法的有效性与合理性.