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

来源 :杭州电子科技大学 | 被引量 : 0次 | 上传用户:wjh101
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
众所周知,装箱和网络优化都是经典的组合优化问题,在运筹学领域里至关重要。最优化理论的深入发展不仅丰富了这些问题本身的理论成果,而且也促使它们在经济管理、交通运输、信息与网络技术等生产实践中得以广泛应用。一般来说,对经典组合优化问题的研究是相互独立的,而本文主要研究一类集成装箱和网络优化的新型组合优化问题。给定赋权有向网络D,需要寻找D的一个具有某种特殊结构的子网络,使得子网络中的各条弧在按照一定规则切割成长为L的分段时所需的分段数尽可能小。本文给出了相关问题的近似算法和最坏情况分析。全文将分成四章进行阐述。  第一章,首先给出装箱和网络优化问题的基本模型与定义,接着介绍计算复杂性理论以及近似算法、(渐近)最坏情况界等概念。  第二章,研究了子网络结构限定为s-t有向路或者强连通支撑子网络的问题,分别设计了渐近最坏情况界为61/36和61/18的近似算法,改进了已有的结果。  第三章集中考虑网络的弧权重至少是L的特殊情形,若子网络结构限定为s-t有向路,设计了最坏情况界为4/3和渐近最坏情况界为95/72的两个近似算法。若结构限定为强连通支撑子网络,则对应的算法界分别为83和95/36。  第四章总结全文,并给出主要结论及可能研究方向。
其他文献
作为叶菜,不同地方种类各异,小松菜是人们经常吃的蔬菜。春天,它长了花蕾,人们就会摘“菜花”来吃。种植的诀窍播种时尽量均匀地留好间隔,不要让种子聚在一起。叶子长出来后,
本论文主要研究Fock空间之正交补空间上以平方可积函数为符号的对偶Toeplitz算子。给出了对偶Toeplitz算子的紧性和有界性的等价判别条件,研究了对偶Toeplitz代数的结构,以及算
本文主要研究了三类基于T-S模型的区间二型非线性系统的控制器设计问题。讨论了区间二型模糊系统和控制器的隶属函数不匹配情况下的负反馈控制问题。诸类区间二型非线性系统
本文主要提出了一类与非线性微分包含问题密切相关的张量高次特征值互补问题。并研究了此类张量高次特征值互补问题与一类齐次多项式分式规划的等价关系,得到了一个关于张量
树上的随机场是随机过程理论在树一这一最新的数学模型上的应用,它产生于信息理论的编码和译码问题.假设一个序列{Xn},其中的状态和状态序偶出现的频率是否遵从大数定律,直接影