塊圖的中位問(wèn)題與中心問(wèn)題.pdf

1、網(wǎng)絡(luò)選址問(wèn)題作為運(yùn)籌學(xué)的一個(gè)重要分支，在運(yùn)輸、通信以及計(jì)算科學(xué)等諸多領(lǐng)域發(fā)揮著巨大作用．1909年德國(guó)經(jīng)濟(jì)學(xué)家Weber發(fā)表的工業(yè)區(qū)位選址論文標(biāo)志著選址問(wèn)題進(jìn)入到了科學(xué)研究的時(shí)代．然而19世紀(jì)60年代中期以前，大多數(shù)研究?jī)?nèi)容比較零散，直到1964年，Hakimi發(fā)表了第一篇關(guān)于網(wǎng)絡(luò)多設(shè)施選址問(wèn)題的論文，選址理論才得以系統(tǒng)化．在該文中，Hakimi分別從效益性和公平性原則出發(fā)，提出了兩種最小化目標(biāo)函數(shù)，即最小和問(wèn)題與極小化最大問(wèn)題．此后多

2、年中，許多著名學(xué)者開(kāi)始致力于該領(lǐng)域的研究，并建立了多類(lèi)模型．
　　 經(jīng)典p-中位問(wèn)題與p-中心問(wèn)題是網(wǎng)絡(luò)選址問(wèn)題中的兩類(lèi)基本模型．p-中位問(wèn)題是指在網(wǎng)絡(luò)中放置p個(gè)設(shè)施，使得所有客戶到離其最近設(shè)施的(加權(quán))距離之和最小．而p-中心問(wèn)題是指在網(wǎng)絡(luò)中放置p個(gè)設(shè)施，使得所有客戶到離其最近設(shè)施的最大(加權(quán))距離最?。?br>　　 經(jīng)典中位問(wèn)題和中心問(wèn)題以方便客戶為目的，使設(shè)施到客戶間的距離越近越好.然而有些設(shè)施，如核電站、垃圾處理廠等卻

3、令所有客戶都感到厭惡，到客戶間的距離則越遠(yuǎn)越好．研究該類(lèi)設(shè)施的問(wèn)題稱(chēng)為“厭惡型設(shè)施選址問(wèn)題”．更一般的情況為“半?yún)拹盒驮O(shè)施選址問(wèn)題”，即所要放置的設(shè)施只令一部分客戶厭惡．
　　 本文主要研究塊圖的中位問(wèn)題與中心問(wèn)題，相應(yīng)的結(jié)果總結(jié)為如下兩部分:
　　 第一，證明了即使客戶是子圖結(jié)構(gòu)，而非圖的頂點(diǎn)，一般圖上的經(jīng)典p-中位問(wèn)題仍滿足頂點(diǎn)最優(yōu)性．此外還對(duì)塊圖上以子圖為客戶的半?yún)拹盒?-中位問(wèn)題進(jìn)行了研究，證明了若塊圖的邊長(zhǎng)為1