具有不同价格的装箱问题

发布时间：2017-08-10 00:25

  本文关键词：具有不同价格的装箱问题

  更多相关文章： 不同价格的箱子 (渐近)近似算法 复杂性 MATLAB程序

【摘要】：装箱问题是一种经典的组合优化问题。一维装箱问题是：给定n个尺寸在(0,1]之间的物品序列L,提供容量为1的箱子若干,把L中的物品装入这些箱子中,要求每个箱子所装的物品尺寸之和不超过1,目标是使得所使用箱子个数达到最少。 具有不同价格的装箱问题是一维装箱问题的一种推广形式,具体描述如下：给定n个尺寸在(0,1]之间的物品序列L,提供k种不同容量和不同价格的箱子,每类箱子若干,箱子的容量在(0,1]之间,把L中的物品装入这些箱子中,要求每个箱子所装物品尺寸之和不超过箱子的容量,目标是使得所使用箱子价格总和达到最小。 本论文利用FFD算法思想,设计了一个渐近近似算法来解决具有不同价格的装箱问题,得出的结论是：在一般情况下,该算法的渐近近似值为2；在两种特殊情况下,该算法的渐近近似值都为3/2,并且,算法复杂性为O(nlogn),最后对这个算法进行了MATLAB编程,并利用该程序实现算例。
【关键词】：不同价格的箱子 (渐近)近似算法 复杂性 MATLAB程序
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157
【目录】：

• 摘要3-4
• Abstract4-7
• 第一章 引言7-12
• 1.1 理论背景7-9
• 1.2 相关术语9-10
• 1.3 主要结果10-11
• 1.4 论文结构11-12
• 第二章 预备知识12-22
• 2.1 组合最优化理论12-14
• 2.2 近似算法理论14-16
• 2.3 一维装箱问题及其算法16-18
• 2.4 具有不同容量的装箱问题及其算法18-22
• 第三章 具有不同价格的装箱问题及其算法22-26
• 3.1 问题描述22
• 3.2 解决具有不同价格的装箱问题的算法22-26
• 第四章 FFDL算法及正确性证明26-37
• 4.1 FFDL算法26-27
• 4.2 主要结果及证明27-34
• 4.3 FFDL算法与IFFD算法和FFC算法的比较34
• 4.4 算例34-37
• 结论37-38
• 附录38-41
• 参考文献41-43
• 致谢43

【共引文献】

中国期刊全文数据库 前10条

1 梁伍七;矩阵链乘积最优计算次序问题的算法及其复杂性分析[J];安徽广播电视大学学报;2003年02期

2 毛影;黄明和;徐斌;;对启发式算法实现图着色的优化[J];江西师范大学学报(自然科学版);2009年06期

3 徐振明,刘莉;绘制PERT网络图自动布点算法的研究[J];成都信息工程学院学报;2005年01期

4 曹志光;华容道的广度优先搜索求解——散列查找和启发式搜索的应用[J];电力学报;2005年01期

5 杨元生,张成学;在有向图中寻找哈密顿回路的快速回溯法[J];大连理工大学学报;1989年02期

6 潘大志;张世禄;;一个实用排序算法的构造与实现[J];电脑学习;2007年02期

7 司庆福;程书伟;;表达式求值算法比较[J];电脑学习;2010年01期

8 张代远;快速和高精度的前馈网络学习算法[J];电路与系统学报;2000年02期

9 张哲;高健;;任意长整数无误差运算的研究与实现[J];电脑编程技巧与维护;2011年04期

10 陈宝平;;任意类型的分类数据的快速排序[J];电脑与信息技术;2011年05期

中国重要会议论文全文数据库 前2条

1 苏运霖;;并行编译中的区域调度问题[A];广西计算机学会2004年学术年会论文集[C];2004年

2 徐平;李爱平;缪嘉嘉;吴泉源;;大规模人货混装问题的一种启发遗传算法实现[A];第二十二届中国数据库学术会议论文集（技术报告篇）[C];2005年

中国博士学位论文全文数据库 前10条

1 戴宏钦;球体随机堆积及其堆积结构的研究[D];苏州大学;2011年

2 徐东平;实时动态交互视景仿真[D];武汉理工大学;2002年

3 刘晓建;大规模分布式仿真信息传输延迟技术研究[D];国防科学技术大学;2003年

4 麦永浩;数据仓库和数据挖掘方法研究及其在公安信息建设中的应用[D];华东理工大学;2000年

5 王意洁;面向对象数据库的并行查询处理与事务管理[D];国防科技大学;1998年

6 南春丽;信号交叉口多目标交通组织优化模型及面向智能体仿真[D];长安大学;2007年

7 李小林;平行机环境下批处理机调度问题研究[D];中国科学技术大学;2012年

8 高胜;对称密码中关键组件的设计与分析[D];西安电子科技大学;2012年

9 王星;随机、容错和厌恶型设施选址的算法研究[D];天津大学;2012年

10 王磊;信息系统动态知识更新的矩阵方法研究[D];西南交通大学;2013年

中国硕士学位论文全文数据库 前10条

1 刘崇亮;分布式呼叫中心监控系统的设计与实现[D];西安电子科技大学;2010年

2 桑银邦;Deep Web集成系统中同类主题数据源选择方法研究[D];重庆大学;2011年

3 张江静;一维组合装车问题模型与算法研究[D];上海交通大学;2012年

4 朱立明;高中数学“算法初步”的案例分析[D];东北师范大学;2011年

5 刘君宇;防火墙包过滤规则框架的设计与实现[D];东北大学;2010年

6 周备战;“651改”测控计算机系统设计与实现[D];国防科学技术大学;2001年

7 别锋锋;油田注水系统设规划优化研究[D];大庆石油学院;2004年

8 王Ym;基于网络的计算机通用考试系统的研制[D];长春理工大学;2004年

9 倪崇嘉;数学形态学基础及在图像处理中的应用[D];昆明理工大学;2003年

10 王洪亮;齐鲁石化人力资源管理及预测分析系统[D];北京化工大学;2004年

，

本文编号：648045