塊圖的中位問題與中心問題.pdf

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

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

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