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

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