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

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

【摘要】：選址問(wèn)題是運(yùn)籌學(xué)中重要的問(wèn)題之一.設(shè)施選址問(wèn)題的應(yīng)用十分廣泛,從城市,產(chǎn)業(yè)帶,經(jīng)濟(jì)技術(shù)開(kāi)發(fā)區(qū)到機(jī)場(chǎng),水利設(shè)施,銷售網(wǎng)點(diǎn)以及倉(cāng)庫(kù)都涉及到選址問(wèn)題,涉及經(jīng)濟(jì),政治,社會(huì),管理,心理及工程地質(zhì)等多門(mén)學(xué)科.本文主要研究了一些特殊圖上路選址問(wèn)題,連通p-中心和p-中位選址問(wèn)題.人們已經(jīng)證明路選址問(wèn)題和連通p-中心和p-中位選址問(wèn)題在一般圖上都是NP-困難問(wèn)題,因此考慮這些問(wèn)題在某些圖類上的多項(xiàng)式算法就成為有意義的問(wèn)題.本文著重討論了樹(shù)(tree),區(qū)間圖(interval graph),圓弧圖(circular-arc graph)和塊圖(block-graph)等重要圖類上的算法設(shè)計(jì)問(wèn)題.首先,我們介紹了選址問(wèn)題的背景和本文涉及的相關(guān)記號(hào)及術(shù)語(yǔ),并提出了本文研究的主要問(wèn)題.本文所做的主要研究工作如下：第二章,研究了樹(shù)上的半?yún)拹盒蚿-路選址問(wèn)題.當(dāng)p=2時(shí),即樹(shù)上的半?yún)拹盒?-路選址問(wèn)題,對(duì)該問(wèn)題的MWD模型和WMD模型,分別設(shè)計(jì)了O(n2)和O(n3)時(shí)間算法.對(duì)p2時(shí),考慮相交p-路和不相交p-路這兩種特殊的情形.樹(shù)上的半?yún)拹盒拖嘟籶-路問(wèn)題的MWD模型和WMD模型都可以轉(zhuǎn)化為樹(shù)上的k-子樹(shù)核心問(wèn)題,由此可證明該問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)求解.對(duì)樹(shù)上的半?yún)拹盒筒幌嘟籶-路選址問(wèn)題的MWD模型,我們?cè)O(shè)計(jì)了O(np+1)時(shí)間算法；而對(duì)于該問(wèn)題的WMD模型,給出了其最優(yōu)解得一些性質(zhì).第三章,應(yīng)用魯棒優(yōu)化理論研究了帶區(qū)間權(quán)重的樹(shù)上的魯棒核心選址問(wèn)題,其中允許頂點(diǎn)的權(quán)重為負(fù)數(shù).對(duì)絕對(duì)魯棒核心選址問(wèn)題設(shè)計(jì)了O(n2)時(shí)間算法.對(duì)偏差魯棒核心選址問(wèn)題,證明了該問(wèn)題的計(jì)算復(fù)雜性為O(n3).第四章,討論區(qū)間圖和圓弧圖上的連通p-中心和p-中位選址問(wèn)題.在區(qū)間圖上,證明了連通p-中心問(wèn)題和連通p-中位問(wèn)題的計(jì)算復(fù)雜性都是O(n).在圓弧圖上,證明了連通p-中心問(wèn)題可以在O(n)時(shí)間內(nèi)求解,而連通p-中位問(wèn)題可以在O(n2)時(shí)間內(nèi)求解.第五章,討論了塊圖上的連通p-中心和p-中位選址問(wèn)題.對(duì)連通p-中心問(wèn)題給出了O(mn logn)時(shí)間算法,對(duì)連通p-中位問(wèn)題,證明了該問(wèn)題線性時(shí)間可解.對(duì)雙目標(biāo)規(guī)劃：連通p-中心-中位問(wèn)題,證明了該問(wèn)題的計(jì)算復(fù)雜性為O(n2),并且帕雷托最優(yōu)解的個(gè)數(shù)不超過(guò)n個(gè).對(duì)厭惡型連通p-中心和p-中位問(wèn)題分別給出了O(mn)時(shí)間算法和O(p2mn)的擬多項(xiàng)式時(shí)間算法.最后給出了需要進(jìn)一步研究的問(wèn)題.
[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é)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O22

【相似文獻(xiàn)】

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

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

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

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

4 代文強(qiáng);徐寅峰;何國(guó)良;;占線中心選址問(wèn)題及其競(jìng)爭(zhēng)算法分析[J];系統(tǒng)工程理論與實(shí)踐;2007年10期

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

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

7 劉汝臣;選址問(wèn)題研究[J];沈陽(yáng)工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2005年04期

8 華國(guó)偉;楊豐梅;黎建強(qiáng);;兩個(gè)雙目標(biāo)競(jìng)爭(zhēng)選址問(wèn)題模型[J];系統(tǒng)工程理論與實(shí)踐;2007年01期

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

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

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

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

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

3 張敏;楊s，

本文編號(hào)：1339093