限制性多重背包问题的研究

发布时间：2018-06-12 00:29

  本文选题：限制性多重背包问题 + 匹配　； 参考：《云南大学》2015年博士论文

【摘要】：背包问题是组合最优化理论研究中的一个经典问题,也是一个重要问题。近些年,背包问题及其各种变形与推广问题都是研究热点。经典背包问题及其推广形式都是NP-难的,它们在存储空间的分配、项目选择以及下料等实际问题上有很好的应用。本文研究了背包问题的几类变形问题,并且设计出了解决相应问题的一些近似算法或者最优算法。全文分为七章内容：在第一章中,介绍了图论与运筹学的一些相关背景、背包问题,以及本文得到的主要研究成果。在第二章中,介绍了图论、组合最优化的相关概念和几类相关的优化问题。在第三章中,介绍了匹配的一些基本知识,特别是介绍了匈牙利算法的基本思想方法。对于一般图的最优k匹配问题,设计了一个时间复杂性是O(n3)的最优算法,这里n为图中顶点数。在第四章中,研究了k元素限制的广义多重背包问题(简记为k-GMK),根据所求目标形式不同,分别研究了Max-Sum k-GMK问题以及Max-Min k-GMK问题。两个问题都是NP-难的,对于Max-Sum k-GMK问题(k≥4),设计了一个1/2-近似算法,对于Max-Min k-GMK问题(k≥4)设计了一个1/(k-1)-近似算法。当k=2时,我们分别给出了时间复杂性是O(n4)和O(n1/2m2)的最优算法来解决这两个问题,这里n为物品数量,m为背包数量。在第五章中,研究了限制在图上的多重背包问题(简记为k-MKRG)。根据目标形式不同,分别研究了Max-Sum k-MKRG问题和Max-Min k-MKRG问题。k-MKRG问题(k≥2)在上述两种目标下都是NP-难的,当k=2时,对于这两个问题,我们分别设计了1/2-近似算法。在第六章中,考虑了在背包容量一致情况下的k-MKRG问题,称为统一背包限制问题(简记为k-UKRG)。根据目标形式不同,分别研究了Max-Sum k-UKRG问题和Max-Min k-UKRG问题,证明了它们都是NP-难的。对于Max-Sum 3-UKRG问题和Max-Min 3-UKRG问题均设计了2/3-近似算法。对于Max-Sum 2-UKRG问题与Max-Min 2-UKRG问题,分别设计了时间复杂性为O(n3)和O(n(|E|+n log n) log n)的最优算法,这里n为物品数量,E为限制图的边集。在第七章,总结了全文,并对未来工作进行了展望。
[Abstract]:Knapsack problem is a classical and important problem in combinatorial optimization theory. In recent years, the knapsack problem and its variety of deformation and extension problems are the focus of research. The classical knapsack problem and its extension form are both NP-hard, and they have good applications in practical problems such as storage space allocation, project selection and material cutting. In this paper, several kinds of deformable problems of knapsack problem are studied, and some approximate or optimal algorithms for solving the corresponding problems are designed. The paper is divided into seven chapters: in the first chapter, we introduce some related background of graph theory and operational research, knapsack problem, and the main research results obtained in this paper. In the second chapter, the graph theory, the related concepts of combinatorial optimization and several related optimization problems are introduced. In the third chapter, we introduce some basic knowledge of matching, especially the basic ideas and methods of Hungarian algorithm. For the optimal k-matching problem of general graphs, an optimal algorithm with time complexity of ON3) is designed, where n is the number of vertices in a graph. In chapter 4, we study the generalized multi-knapsack problem (k-GMKN) with k-element constraints, and study the Max-Sum k-GMK problem and the Max-Min k-GMK problem, respectively, according to the different forms of the target. Both problems are NP-difficult. For Max-Sum k-GMK problem k 鈮，

本文编号：2007381