本文選題：限制性多重背包問題 + 匹配��； 參考：《云南大學》2015年博士論文

【摘要】：背包問題是組合最優(yōu)化理論研究中的一個經(jīng)典問題,也是一個重要問題。近些年,背包問題及其各種變形與推廣問題都是研究熱點。經(jīng)典背包問題及其推廣形式都是NP-難的,它們在存儲空間的分配、項目選擇以及下料等實際問題上有很好的應用。本文研究了背包問題的幾類變形問題,并且設計出了解決相應問題的一些近似算法或者最優(yōu)算法。全文分為七章內(nèi)容：在第一章中,介紹了圖論與運籌學的一些相關背景、背包問題,以及本文得到的主要研究成果。在第二章中,介紹了圖論、組合最優(yōu)化的相關概念和幾類相關的優(yōu)化問題。在第三章中,介紹了匹配的一些基本知識,特別是介紹了匈牙利算法的基本思想方法。對于一般圖的最優(yōu)k匹配問題,設計了一個時間復雜性是O(n3)的最優(yōu)算法,這里n為圖中頂點數(shù)。在第四章中,研究了k元素限制的廣義多重背包問題(簡記為k-GMK),根據(jù)所求目標形式不同,分別研究了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)的最優(yōu)算法來解決這兩個問題,這里n為物品數(shù)量,m為背包數(shù)量。在第五章中,研究了限制在圖上的多重背包問題(簡記為k-MKRG)。根據(jù)目標形式不同,分別研究了Max-Sum k-MKRG問題和Max-Min k-MKRG問題。k-MKRG問題(k≥2)在上述兩種目標下都是NP-難的,當k=2時,對于這兩個問題,我們分別設計了1/2-近似算法。在第六章中,考慮了在背包容量一致情況下的k-MKRG問題,稱為統(tǒng)一背包限制問題(簡記為k-UKRG)。根據(jù)目標形式不同,分別研究了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)的最優(yōu)算法,這里n為物品數(shù)量,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