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