集成网络与装箱的一类新型组合优化问题

发布时间：2017-12-24 00:01

  本文关键词：集成网络与装箱的一类新型组合优化问题　出处：《杭州电子科技大学》2016年硕士论文　论文类型：学位论文

  更多相关文章： 装箱 网络优化 近似算法 (渐近)最坏情况界

【摘要】：众所周知,装箱和网络优化都是经典的组合优化问题,在运筹学领域里至关重要。最优化理论的深入发展不仅丰富了这些问题本身的理论成果,而且也促使它们在经济管理、交通运输、信息与网络技术等生产实践中得以广泛应用。一般来说,对经典组合优化问题的研究是相互独立的,而本文主要研究一类集成装箱和网络优化的新型组合优化问题。给定赋权有向网络D,需要寻找D的一个具有某种特殊结构的子网络,使得子网络中的各条弧在按照一定规则切割成长为L的分段时所需的分段数尽可能小。本文给出了相关问题的近似算法和最坏情况分析。全文将分成四章进行阐述。第一章,首先给出装箱和网络优化问题的基本模型与定义,接着介绍计算复杂性理论以及近似算法、(渐近)最坏情况界等概念。第二章,研究了子网络结构限定为s-t有向路或者强连通支撑子网络的问题,分别设计了渐近最坏情况界为61/36和61/18的近似算法,改进了已有的结果。第三章集中考虑网络的弧权重至少是L的特殊情形,若子网络结构限定为st有向路,设计了最坏情况界为4/3和渐近最坏情况界为95/72的两个近似算法。若结构限定为强连通支撑子网络,则对应的算法界分别为8/3和95/36。第四章总结全文,并给出主要结论及可能研究方向。
【学位授予单位】：杭州电子科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;O224

【相似文献】

相关期刊论文 前10条

1 何幼林;欧福军;魏华实;徐健;张雍吉;;蚁群算法的原理及其在组合优化中的应用[J];黑龙江科技信息;2008年01期

2 洪大威;;从制定侦破方案说起——组合优化一例[J];科学;1986年03期

3 越民义;;组合优化介绍[J];运筹学杂志;1988年01期

4 王宇平,徐晨;解组合优化的一种新方法的收敛性[J];西安电子科技大学学报;1997年04期

5 彭胜志;王福胜;;高阶投资组合优化问题的研究述评[J];财会研究;2012年01期

6 陈盛双,武华,李亮;企业管理组合优化的数学模型及遗传算法[J];武汉汽车工业大学学报;2000年06期

7 王贞;刘三阳;孔翔宇;;投资组合优化问题情景生成方法的比较[J];兰州大学学报(自然科学版);2011年03期

8 马玉洁;;产品组合优化决策方法分析[J];财会月刊;2013年17期

9 曹家明;;一类组合优化问题与非凸二次规划的等价[J];西南交通大学学报;1993年01期

10 汪祖柱,程家兴;求解组合优化问题的一种方法—分枝定界法[J];安徽大学学报(自然科学版);2004年01期

相关会议论文 前4条

1 于晓义;吴毅;王达达;杨昆;;基于负荷均衡的工作中心任务组合优化分配研究[A];2010年云南电力技术论坛论文集（优秀论文部分）[C];2010年

2 何洋林;叶春明;;CEPGA算法在网络计划组合优化问题中的应用[A];全国第十届企业信息化与工业工程学术年会论文集[C];2006年

3 徐俊明;;网络分析中几个组合优化问题[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

4 李彦苍;索娟娟;;基于熵和信息素的自适应GA及其在组合优化中的应用[A];Well-off Society Strategies and Systems Engineering--Proceedings of the 13th Annual Conference of System Engineering Society of China[C];2004年

相关重要报纸文章 前3条

1 程建平;发掘资源的最大价值[N];中国特产报;2003年

2 安徽 朱宝贵;Office 2000与XP组合优化安装技巧[N];电子报;2005年

3 薛梅;柜面劳动组合优化应多管齐下[N];中国城乡金融报;2014年

相关博士学位论文 前6条

1 王军强;基于约束理论的产品组合优化决策研究[D];西北工业大学;2006年

2 王正元;基于状态转移的组合优化方法研究[D];国防科学技术大学;2004年

3 彭胜志;基于高阶矩的投资组合优化研究[D];哈尔滨工业大学;2012年

4 吴t熇，

本文编号：1326009