【摘要】：選址問(wèn)題是運(yùn)籌學(xué)領(lǐng)域的經(jīng)典問(wèn)題,在生產(chǎn)、物流管理、網(wǎng)絡(luò)設(shè)計(jì)等實(shí)際問(wèn)題中有非常廣泛的應(yīng)用.設(shè)施選址問(wèn)題和k-中位問(wèn)題是兩個(gè)最基本的選址問(wèn)題.這兩個(gè)問(wèn)題可以做為聚類問(wèn)題,在數(shù)據(jù)挖掘領(lǐng)域發(fā)揮重要的作用.關(guān)聯(lián)聚類是另一種聚類問(wèn)題,適合類別個(gè)數(shù)未知的問(wèn)題.這些問(wèn)題都是NP-難的,在近似算法領(lǐng)域有大量的研究.本論文研究這些問(wèn)題的重要變形,包括n次方度量的帶線性懲罰的設(shè)施選址問(wèn)題、帶線性懲罰的k-設(shè)施選址問(wèn)題、平方度量的k-設(shè)施選址問(wèn)題、和帶權(quán)圖上的關(guān)聯(lián)聚類問(wèn)題.使用線性規(guī)劃舍入、局部搜索、半定規(guī)劃舍入等技術(shù)給出這些問(wèn)題的近似算法和近似比的分析.在n次方度量的帶線性懲罰的設(shè)施選址問(wèn)題(簡(jiǎn)稱MnFLPLP)中,顧客與設(shè)施的連接費(fèi)用是n次方度量的(滿足非負(fù)性、對(duì)稱性、和n次方三角不等式).顧客如果未被任何設(shè)施服務(wù),則需要付相應(yīng)的懲罰費(fèi)用.線性懲罰是指,一個(gè)可行解的懲罰費(fèi)用等于每個(gè)顧客支付的懲罰費(fèi)用之和.此問(wèn)題是度量的設(shè)施選址問(wèn)題的推廣,因此也是NP-難的.我們將針對(duì)度量的帶線性懲罰的設(shè)施選址問(wèn)題的1.5148-近似算法應(yīng)用到此問(wèn)題上,并分析出近似比的隱式表達(dá)式.通過(guò)數(shù)值計(jì)算,給出n=2,…,10對(duì)應(yīng)的常數(shù)近似比,以及n= 2和10對(duì)應(yīng)的雙因子近似比曲線,并與近似比的下界進(jìn)行比較.我們發(fā)現(xiàn)n越小,近似比與其下界的間隙越小.另外,雙因子近似比曲線與下界曲線在一定范圍內(nèi)也是非常接近的.在帶線性懲罰的k-設(shè)施選址問(wèn)題(k-FLPLP)中,顧客與設(shè)施的連接費(fèi)用是度量的(滿足非負(fù)性、對(duì)稱性、和三角不等式),問(wèn)題帶有線性懲罰和設(shè)施的基數(shù)約束(即設(shè)施的開(kāi)設(shè)個(gè)數(shù)不能超過(guò)給定的常數(shù)k).此問(wèn)題是經(jīng)典的設(shè)施選址問(wèn)題與k-中位問(wèn)題的一般化.因此是NP-難的.本論文將由添加,刪除,和交換設(shè)施三種局部操作定義的局部搜索算法應(yīng)用于k-FLPLP上.在算法的分析中,我們將“懲罰”視作虛擬設(shè)施,連接費(fèi)用即為懲罰費(fèi)用,以使對(duì)顧客的懲罰可以參與到局部操作的構(gòu)造中.我們分析出算法的近似比與k-設(shè)施選址問(wèn)題的相同,均為2 +(?)+ ε,說(shuō)明對(duì)于這種局部搜索算法,懲罰費(fèi)用沒(méi)有對(duì)近似比造成影響.我們研究的第三種變形是平方度量的k-設(shè)施選址問(wèn)題(簡(jiǎn)稱SM-k-FLP).在此問(wèn)題中,設(shè)施和顧客的位置在一個(gè)度量空間中,顧客與設(shè)施的連接費(fèi)用等于兩者距離的平方.與M2FLPLP的不同之處在于,SM-k-FLP沒(méi)有懲罰費(fèi)用,但是有設(shè)施的基數(shù)約束.這個(gè)問(wèn)題是k-設(shè)施選址問(wèn)題的一般化,所以也是NP-難的.我們使用局部搜索和放縮技術(shù)給出此問(wèn)題的(22 +(?)+ε)-近似算法.通過(guò)數(shù)值實(shí)驗(yàn),我們發(fā)現(xiàn)算法的實(shí)際效果很好.論文的最后一個(gè)研究問(wèn)題是帶權(quán)圖上的關(guān)聯(lián)聚類問(wèn)題.在此問(wèn)題中,每條邊有兩類權(quán)重,分別代表兩端點(diǎn)的正、負(fù)相關(guān)性.我們需要將點(diǎn)集V進(jìn)行聚類,目標(biāo)是最大相同性,即最大化屬于某個(gè)類的邊的第一類權(quán)重之和加上在兩個(gè)不同類之間的邊的第二類權(quán)重之和.該問(wèn)題是NP-難的,我們利用外部旋轉(zhuǎn)技術(shù)將現(xiàn)有的半定規(guī)劃舍入0.75-近似算法改進(jìn),可以分析出依賴于實(shí)例的近似比.雖然不能將近似比0.75提高,但是對(duì)于大多數(shù)實(shí)例,近似比要好于0.75.
【學(xué)位授予單位】：北京工業(yè)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP301.6
【圖文】：

ａ）７／Ｇ［ｌ，３］邐ｂ）７／Ｇ邋［１．９８，２．１］逡逑圖３－２算法４７／；（對(duì)Ｍ２ＦＬＰＬＰ的雙因子近似比曲線逡逑Ｆｉｇ．邋３－２邋Ｔｈｅ邋ｃｕｒｖｅ邋ｏｆ邋ｂｉ－ｆａｃｔｏｒ邋ａｐｐｒｏｘｉｍａｔｉｏｎ邋ｒａｔｉｏ邋ｏｆ邋＾（７／）邋ｆｏｒ邋Ｍ２ＦＬＰＬＰ逡逑４０邋邐１邐１邐１邐１邐１邐１邐１邐？逡逑３５邋－邐＼邐－逡逑Ｓ３０．邋＼邐——算法ａ（ｙ：）的近似比曲線Ｉ邋＿逡逑Ｓ邐＼邐－－－近似比的下界曲線逡逑盟邐＼邐0邋（８．９１７１，８．９１７１）逡逑Ｓ？邋２Ｑ邋■邐＼邐－逡逑ｍ邐＼逡逑ｍ１５＇邐＼邐＇逡逑

本文編號(hào)：2731641