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

发布时间：2021-05-18 09:17

　　背包问题是一类经典的组合优化问题,它不仅是计算机科学中很多算法的重要组成部分,更是在商业、组合数学、计算复杂性理论、密码学和应用数学等领域中有着重要应用。背包问题的模型是已知一个固定容量的背包,以及一系列物品,每个物品有自己的尺寸和权重,目标是在不超过背包容量的前提下,使装入背包中的物品的总收益（权重）最大。经典的背包问题为离线问题,即在最开始已知所有物品的信息。与离线所对应的即为本文研究的在线背包问题,即物品是按照一定顺序一个接着一个到来的,在决定当前物品去留之前,无法知道未来物品的信息。对于在线背包问题,前人已经做了一定的研究,并取得一定成果,例如线性函数下在线背包问题以及凸函数下在线背包问题,但是在此之前没有人研究凹函数下在线背包问题。本文研究的主要内容是物品的大小和权重之间满足凹函数关系的在线背包问题,因为是物品的属性之间存在的函数关系,所以该模型下的在线背包问题并不是相应凸函数问题的简单翻转,也无法用凸函数模型下的在线算法解决该模型下的问题。而在此之前没有人研究过凹函数下的在线背包问题,同时这一类问题在很多领域中有重要应用。本文主要工作是通过学习和研究其他类型背包问题,并结合... 

【文章来源】：大连理工大学辽宁省 211工程院校 985工程院校 教育部直属院校

【文章页数】：57 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 背景
    1.2 中外研究现状
    1.3 研究凹函数下在线背包问题的意义
    1.4 论文结构
2 背景知识
    2.1 背包问题相关背景知识
        2.1.1 经典背包问题
        2.1.2 在线背包问题
    2.2 在线问题相关背景知识
        2.2.1 竞争分析
        2.2.2 竞争比
    2.3 凹函数相关背景知识
    2.4 本章小结
3 凹函数模型下竞争比下界
    3.1 一般情况的下界
    3.2 特殊情况的下界
    3.3 本章小结
4 凹函数模型下的在线算法
    4.1 竞争比为f'(0)/f(1/q)的在线算法
    4.2 竞争比为f'(0)/f(1)+1的在线算法
    4.3 分段线性实例的竞争比
    4.4 本章小结
5 背包问题以及在线背包问题的应用
    5.1 背包问题在最短路径、VRP、定向问题中的应用
        5.1.1 背包与带有资源约束的基础最短路径问题
        5.1.2 背包问题与VRP问题
        5.1.3 背包与定向问题
    5.2 凹函数下的在线背包问题在经济学中的应用
        5.2.1 效用
        5.2.2 在线背包与效用最大化
    5.3 凹函数下的在线背包问题在广告投放中的应用
        5.3.1 查询竞价
        5.3.2 关键字拍卖
    5.4 本章小结
结论
参考文献
攻读硕士学位期间发表学术论文情况
致谢



本文编号：3193542