多约束二次0-1背包问题的一个有效算法

摘要

当前我国正处在经济快速发展时期，与此同时，资源消耗也呈高速增长的趋势.如何最合理地利用有限的资源，使生产的消耗最小，利润最大是经营管理者所关心的主要问题.而现实中的有些资源是只能取整数的，特别是很多决策变量只能取0或1.所以对0-1整数规划的研究在理论上和实践上都有着重大意义.本文主要讨论多约束二次0-1背包问题.其数学模型可描述如下： (MQKP)maxf(x)=n∑i=1qiixi+∑1≤i＜j≤nqijxixjs.t.Ax≤b,x∈{0,1}n,其中qij≥0,1≤i≤j≤n,A=(aij)m×n,aij≥0,i=1,...,m,j=1,...,n,b=(b1,...,bm)T,0＜bi＜∑j=1naij,i=1,...,m.我们根据这类问题的特殊性质，提出一个新的分枝定界算法，该算法使用分枝定界策略和拉格朗日对偶来寻找问题的最优解.在算法中，我们把拉格朗日松弛问题转化为最大流网络最优化问题，并使用外逼近方法求解子问题的对偶界.我们还使用替代约束技术搜索问题的可行解以进一步提高算法效率.初步的数值试验表明该算法对求解多约束二次背包问题是有效的. 文章共由五部分组成：第一章简单介绍二次0-1背包问题的提出，研究现状和进展；第二章介绍单约束二次0-1背包问题求上界的几种方法；第三章中我们详细介绍分枝定界算法；第四章我们给出多约束二次0-1背包问题的分枝定界算法；第五章给出了用分枝定界算法求解单约束及多约束二次0-1背包问题的数值结果.

目录

文摘

英文文摘

原创性声明及本论文使用授权说明

第一章前言

第二章几种求上界方法

第三章分枝定界算法

第四章(MQKP)问题的分枝定界方法

第五章数值试验

参考文献

作者在攻读硕士学位期间公开发表的学术论文

致谢