發(fā)布時間：2017-12-26 22:19

  本文關(guān)鍵詞：圖上的路選址問題與連通p-中心和p-中位問題　出處：《上海大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 選址問題 樹 區(qū)間圖 P-中心問題 P-中位問題 魯棒優(yōu)化

【摘要】：選址問題是運籌學(xué)中重要的問題之一.設(shè)施選址問題的應(yīng)用十分廣泛,從城市,產(chǎn)業(yè)帶,經(jīng)濟技術(shù)開發(fā)區(qū)到機場,水利設(shè)施,銷售網(wǎng)點以及倉庫都涉及到選址問題,涉及經(jīng)濟,政治,社會,管理,心理及工程地質(zhì)等多門學(xué)科.本文主要研究了一些特殊圖上路選址問題,連通p-中心和p-中位選址問題.人們已經(jīng)證明路選址問題和連通p-中心和p-中位選址問題在一般圖上都是NP-困難問題,因此考慮這些問題在某些圖類上的多項式算法就成為有意義的問題.本文著重討論了樹(tree),區(qū)間圖(interval graph),圓弧圖(circular-arc graph)和塊圖(block-graph)等重要圖類上的算法設(shè)計問題.首先,我們介紹了選址問題的背景和本文涉及的相關(guān)記號及術(shù)語,并提出了本文研究的主要問題.本文所做的主要研究工作如下：第二章,研究了樹上的半?yún)拹盒蚿-路選址問題.當(dāng)p=2時,即樹上的半?yún)拹盒?-路選址問題,對該問題的MWD模型和WMD模型,分別設(shè)計了O(n2)和O(n3)時間算法.對p2時,考慮相交p-路和不相交p-路這兩種特殊的情形.樹上的半?yún)拹盒拖嘟籶-路問題的MWD模型和WMD模型都可以轉(zhuǎn)化為樹上的k-子樹核心問題,由此可證明該問題可以在多項式時間內(nèi)求解.對樹上的半?yún)拹盒筒幌嘟籶-路選址問題的MWD模型,我們設(shè)計了O(np+1)時間算法；而對于該問題的WMD模型,給出了其最優(yōu)解得一些性質(zhì).第三章,應(yīng)用魯棒優(yōu)化理論研究了帶區(qū)間權(quán)重的樹上的魯棒核心選址問題,其中允許頂點的權(quán)重為負數(shù).對絕對魯棒核心選址問題設(shè)計了O(n2)時間算法.對偏差魯棒核心選址問題,證明了該問題的計算復(fù)雜性為O(n3).第四章,討論區(qū)間圖和圓弧圖上的連通p-中心和p-中位選址問題.在區(qū)間圖上,證明了連通p-中心問題和連通p-中位問題的計算復(fù)雜性都是O(n).在圓弧圖上,證明了連通p-中心問題可以在O(n)時間內(nèi)求解,而連通p-中位問題可以在O(n2)時間內(nèi)求解.第五章,討論了塊圖上的連通p-中心和p-中位選址問題.對連通p-中心問題給出了O(mn logn)時間算法,對連通p-中位問題,證明了該問題線性時間可解.對雙目標規(guī)劃：連通p-中心-中位問題,證明了該問題的計算復(fù)雜性為O(n2),并且帕雷托最優(yōu)解的個數(shù)不超過n個.對厭惡型連通p-中心和p-中位問題分別給出了O(mn)時間算法和O(p2mn)的擬多項式時間算法.最后給出了需要進一步研究的問題.
[Abstract]:The location problem is one of the important problems in operational research. The application of the facility location problem is very wide, from the city, industrial zone, economic and Technological Development Zone to the airport, water conservancy facilities, warehouse and sales outlets are related to the location problem, involving economic, political, social, management, psychology and many other disciplines. The main engineering geology study on some special graphs on the site, p- and p- in a connected center location problem. It was proved that the road location problem and connected p- center and p- in a location problem in general graphs is NP- hard problem, so consider these problems in some classes of Graphs of the polynomial algorithm becomes a significant problem. This paper focuses on the tree (tree), interval graph (interval graph), arc (circular-arc graph) and block diagram (block-graph) and other important classes of graphs the algorithm design problems. First, we introduce the location problem. Mark and related background and terminology related to this article, and put forward the main problem in this paper. The main research work is as follows: the second chapter studies the tree semi averse p- road location problem. When p=2, the tree half averse 2- road location problem, MWD model and WMD the model of this problem, we have designed a O (N2) and O (N3) time algorithm. On P2, consider the intersection of p- road and p- Road intersection of the two special cases. MWD model and WMD model of p- Road intersection of half averse tree can be transformed into a tree the k- subtree is the core problem, which can prove that the problem can be solved in polynomial time. MWD model of semi averse tree disjoint p- road location problem, we design a O (np+1) time algorithm; and the WMD model of this problem is given, some properties of the optimal solution is third. Chapter, with robust optimization The theory of robust core with interval weight tree location problem, which allows for the negative weight vertex. The location problem of robust core design of O (N2) time algorithm of robust deviation. The core location, proved that the computational complexity of this problem is O (N3). The fourth chapter discusses connected p- the center and p- interval graphs and circular arc graphs the median location problem. On interval graphs, and proves the complexity of connected p- center problem and connected p- problems are O (n). In the arc, proved that connected p- center problem in O (n) time solution. The connected p- median problem in O (N2) time. The fifth chapter discusses the connected p- center and p- block on the map in a location problem. Given the O of p- Center (Mn logn connectivity) time algorithm on a connected p-, it is proved that the linear time the solution of binocular standards. Row: p- connectivity Center - median problem, proved that the computational complexity of this problem is O (N2), and the number of Pareto optimal solutions of no more than n. The aversion connected p- center and p- are presented respectively in O (MN) and O (p2mn) time algorithm for quasi polynomial time the algorithm is given. The problems that need further study.
【學(xué)位授予單位】：上海大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O22

【相似文獻】

相關(guān)期刊論文 前10條

1 周兵;關(guān)于圖的面服務(wù)型選址問題[J];上海機械學(xué)院學(xué)報;1982年03期

2 馬云峰;楊超;張敏;郝春艷;;基于時間滿意的最大覆蓋選址問題[J];中國管理科學(xué);2006年02期

3 劉文博;;固定容量設(shè)備選址問題的求解算法研究[J];遼寧省交通高等�？茖W(xué)校學(xué)報;2006年04期

4 代文強;徐寅峰;何國良;;占線中心選址問題及其競爭算法分析[J];系統(tǒng)工程理論與實踐;2007年10期

5 胡丹丹;楊超;;在競爭環(huán)境中的擁塞設(shè)施截流選址問題[J];系統(tǒng)工程理論與實踐;2010年01期

6 陳開周;王效俐;;選址問題的新研究[J];系統(tǒng)工程;1990年01期

7 劉汝臣;選址問題研究[J];沈陽工程學(xué)院學(xué)報(自然科學(xué)版);2005年04期

8 華國偉;楊豐梅;黎建強;;兩個雙目標競爭選址問題模型[J];系統(tǒng)工程理論與實踐;2007年01期

9 馬云峰;劉勇;楊超;;一類帶時間和容量約束的截流選址問題[J];武漢科技大學(xué)學(xué)報(自然科學(xué)版);2007年02期

10 譚素平;易斌;;設(shè)施選址問題綜述[J];科技信息;2012年22期

相關(guān)會議論文 前8條

1 趙一新;;淺談博物館的選址問題[A];浙江省博物館學(xué)會2001年學(xué)術(shù)研討會文集[C];2001年

2 王文峰;郭波;劉新亮;;多級覆蓋設(shè)施選址問題建模及求解方法研究[A];第九屆中國管理科學(xué)學(xué)術(shù)年會論文集[C];2007年

3 張敏;楊s，

本文編號：1339093