求解背包问题约束下下模函数最大值半定松弛算法及性能保证

摘要

在19世纪，人们提出了下模的理论，因为很多组合优化问题的目标函数都具有下模性，所以对于一个组合优化问题来说，重点就是如何解决目标函数的下模性问题。另一方面，考虑到下模性在优化算法设计中的良好性质，使得它在理论计算科学方面具有举足轻重的作用。因此，如何更深层次的了解下模函数的性质以及最值问题的求解是组合优化问题的重中之重。下模集函数最大值问题无论是在理论上还是在实际应用价值上都具有很重要的意义，很多的理论学者对这方面的研究工作从未停止，并得出了不少重要结论。半定规划是19世纪60年代才提出的一个理论，半定规划有线性与非线性之分，它的作用主要表现在以下两个方面：一是很多模型都会转化为半定规划来求解；二是通常在解决组合优化、系统论、控制论等问题时，半定规划会起到事半功倍的作用。半定规划是一个满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极值化的问题，因此它是线性规划的一种推广，这个约束是非线性、非光滑并且是凸的，因而半定规划是一个非光滑凸规划问题。半定规划的模型有很多种，但与已有的众多半定规划模型相比，[-1,1]这个模型能为原问题提供更确切的界，它的原理就是引入特殊变量，使得原问题的约束条件改变，范围变成[-1,1],这个方法最大的特点就是能为原问题的解提供很强的稳定性。近似算法有很多种类，其中贪婪算法是解决近似算法中一个有力的工具，它具有简便且快速找到问题近似最优解的特点，可行性很高。贪婪算法只考虑问题每一步的最优，而并不全局优化，这虽然看起来可行性不高，但对于很多大型组合优化问题来说，由于我们实在不方便考虑全局优化问题，况且如果考虑全局最优化会引起时间复杂度严重升高，以至于失去了解题意义，因此在此种情况下利用贪婪算法会是一个不错的选择。
　　本文在利用贪婪算法求解下模函数的进程中，首先是Fujishige提出的贪婪算法，使得性能保证为1-1/e。之后张生改进了原有的方法，提出了改进贪婪算法，使得时间复杂度进一步提升。而对于陈峰、姚恩瑜，他们利用了半定松弛规划以及[-1,1]二次规划对背包问题的条件进行约束，求得的结果会随着σ的不同而有所不同。本文的灵感来源于此，对背包约束下下模函数的最值问题做进一步的讨论，首先将背包问题的约束条件转化成[-1,1]二次规划后再加入松弛变量，之后套用改进贪婪算法，使得算法的性能保证更接近最优值。结果如下：⑴首先将单背包约束下的下模函数带入变量，使其成为[-1,1]模型，然后添加松弛变量，约束为半定松弛规划，最后应用下模函数的改进贪婪算法求解，得出当σ>0.19时，近似算法（3.7）的相似比为0.732。⑵将单背包约束条件扩充到多背包约束条件下，下模函数的半定松弛算法，式（4.2）的多背包问题可以被定义为如下：给出了n个项目的集合和m个背包，每个产品j的利润位pj和重量为w，每个背包i的容量为Ci，目的是寻找一个可行的包装在背包项目的一个子集，使背包所包含的物理利润最大化。本文改进了半定松弛算法目标函数的模型，多项式时间算法近似比优于0.5。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 组合优化问题

1.2 最优化相关理论

1.3 NP——完全理论

1.4 P——类和NP——类问题

1.5 课题的目的意义和在该领域存在的问题

1.6 算法的分类

1.7 算法的规模及复杂性

1.8 本文主要内容和结构安排

2 算法分析

2.1 贪婪算法

2.2 半定规划

2.3 {-1,1}规划模型

2.4 0-1背包问题

2.5 下模函数的基本概念

2.6 下模函数基本性质

3单背包约束下下模函数半定松弛算法

3.1 部分引理的证明

3.2 算法

3.3 算法可靠性分析及证明

3.4 算法的性能保证

4 多背包约束下下模函数半定松弛算法

4.1具体算法：

4.2 若干引理

4.3 性能保证

结论

致谢

参考文献

攻读硕士学位期间的研究成果