凹函数下在线背包问题的研究

作     者：马宁 

作者单位：大连理工大学 

学位级别：硕士

导师姓名：韩鑫

授予年度：2018年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：背包问题 在线算法 凹函数 

摘      要：背包问题是一类经典的组合优化问题,它不仅是计算机科学中很多算法的重要组成部分,更是在商业、组合数学、计算复杂性理论、密码学和应用数学等领域中有着重要应用。背包问题的模型是已知一个固定容量的背包,以及一系列物品,每个物品有自己的尺寸和权重,目标是在不超过背包容量的前提下,使装入背包中的物品的总收益(权重)最大。经典的背包问题为离线问题,即在最开始已知所有物品的信息。与离线所对应的即为本文研究的在线背包问题,即物品是按照一定顺序一个接着一个到来的,在决定当前物品去留之前,无法知道未来物品的信息。对于在线背包问题,前人已经做了一定的研究,并取得一定成果,例如线性函数下在线背包问题以及凸函数下在线背包问题,但是在此之前没有人研究凹函数下在线背包问题。本文研究的主要内容是物品的大小和权重之间满足凹函数关系的在线背包问题,因为是物品的属性之间存在的函数关系,所以该模型下的在线背包问题并不是相应凸函数问题的简单翻转,也无法用凸函数模型下的在线算法解决该模型下的问题。而在此之前没有人研究过凹函数下的在线背包问题,同时这一类问题在很多领域中有重要应用。本文主要工作是通过学习和研究其他类型背包问题,并结合凹函数的性质,首先利用实例和反证法,证明凹函数下在线背包问题竞争比的下界,之后通过实例说明对于特殊凹函数,下界可以进一步改进;然后通过学习前人思想并结合本问题实际情况,将物品分类,针对不同物品做出不同决策,从而设计出可以很好解决凹函数下在线背包问题的算法。本文首次研究凹函数下在线背包问题,并取得一些开创性的成果。首先,本文给出的凹函数模型下在线算法的竞争比下界首次限定了在线算法在这一模型下能做到的最好程度;其次,本文中设计的在线算法做出的决策质量相对于最优算法而言是有界的,即可以保证对于实时到来的各个物品,决策结果相较于最优决策方案的结果差距是有限的,这意味着在实时情况下应用本文算法可以做出非常优秀的决策策略。通过充分的学习与研究,本文总结并展示了对该问题的贡献及取得的成果。通过严谨的证明与推导,证明下界的正确性,并且在线算法可以在一个合理的竞争比情况下,有效处理凹函数下的在线背包问题。