1. 研究目的与意义
背包问题（knapsack problem）最早是在20世纪50年代由Tobias Dantzig提出，它包括0-1背包问题、完全背包问题以及分组背包问题等，背包问题在日常的生活中具有十分广阔的应用背景，对于工业工程、金融投资以及计算机决策等领域的库存运输、密码学以及资源合理分配等的组合优化问题的研究[1]，有着十分重要的意义与作用。
背包问题作为经典的NP难题，在实际中存在着大量应用，现实中的很多组合优化的问题都可以转换成背包问题，如材料的切割、资金组合投资问题等，而且背包问题算法的可行性、准确性能够在计算机软件中得到验证，因此对背包问题的解法进行深入的研究具有重大的意义，国内外都有很多关于背包问题及其算法的研究。
2. 研究内容和预期目标
分段线性费用结构PLC（piecewise linear cost function）又称分段线性成本函数。现实生活中，有很多制造商企业需要通过快递服务将产品从生产基地运输到零售商店，它们面临着实际的装箱运输收费以及物流规划问题，由于运输的所有物品都是灵活且不易碎的，因此需要考虑只有他们的重量和体积。在装箱过程中，快递服务商会根据每箱货物的重量向制造商收费，此时的费用结构基本满足分段线性成本函数结构[6]，因此这种货物运输问题不仅可以简化成二维背包问题，而且会应用分段线性成本函数。
这时候所涉及到的分段线性成本函数是指在固定的体积内，快递所需的成本费用会随着承载重量的不同区域段呈现不同的变化，但在任何一段区域内，成本与重量都符合一种非负线性关系，那么就称这种结构为分段线性费用成本结构。
3. 国内外研究现状
目前求解背包问题的算法主要包括启发式算法以及精确算法等。启发式算法中包括禁忌搜索算法、模拟退火算法以及贪心算法等，是基于直观经验而构造的算法，能很快在给定范围内求解出可行解。精确算法包括分支定界算法、动态规划以及分支切割算法等，该类算法主要运用于求解最优解。
启发式算法只需要求出一个可行解，因此速度快，但是却无法解决有较高精确度需求的背包问题，而精确算法虽然耗费的时间精力较多，花费的成本较高，但是能够解决采用启发式算法而导致精确度不足的问题，从而求解出最优解。精确算法作为能够以较高精确度求解背包问题实例最优解的方法，有着很多关于它的研究。
王乐等用Matlab来测算动态规划方法，证实其在解决0-1背包问题上有着更高的运行效率，贺毅朝等进一步用动态规划方法来有效求解随机时变背包问题（RTVPK）[2]。于战科等在求解整数线性规划（ILP）问题的基础上，提出了一种改进的分支定界算法，以此来有效提高求解效率。盛红波等将启发式算法中的拉格朗日松弛和对偶搜索法与精确算法中的分枝定界方法相结合，形成了一种新的精确算法[3]。Qian Hu等人研究了分支定界算法来求解有着分段线性成本函数的二维背包问题[4]。
4. 计划与进度安排
分段线性费用结构的背包问题是一种二维背包问题，二维背包问题就是在0-1背包问题上多增加了一个束缚条件，即背包有一定的非负体积容量V，第j个物品的体积为vj，则放入背包中的物品的总体积为
分段线性成本函数是快递所需的成本费用会随着承载重量的不同区域段呈现一种非负线性关系，对不同的重量区域段进行分支，按照W的分段范围进行划分,W1#206;{0,w1}…Wi#206;{wi-1,wi}。在Wi的范围内，成本函数为f(x)=kiw bi。问题就转化为，应该如何安排使得花费的总成本最低。
5. 参考文献
[1]王熙照;贺毅朝.求解背包问题的演化算法[J].软件学报,2017,v.28,5-20.
[2] 贺毅朝;田海燕;张新禄;王志威;高锁刚.基于动态规划法求解动态0-1背包问题[J].计算机科学,2012,v.39,243-247.
[3] 盛红波;孙娟;孙小玲.0-1多项式背包问题的一种精确算法[J].上海大学学报(自然科学版),2006,62-66.
以上是毕业论文开题报告，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
