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

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

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

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