連續(xù)設(shè)施選址模型的快速算法研究.pdf

1、設(shè)施選址問題是運籌學(xué)的經(jīng)典問題之一，在經(jīng)濟(jì)，管理，交通運輸?shù)阮I(lǐng)域都有著非常廣泛的應(yīng)用.單設(shè)施選址問題和多設(shè)施選址問題一直是設(shè)施選址問題的研究熱點.
　　求解單設(shè)施選址問題和多設(shè)施選址問題最常用的算法是Weiszfeld算法和Cooper-Weiszfeld算法.本文對這兩種問題分別提出了具有收斂性且收斂速度更快的新算法：Weiszfeld-Newton算法和Cooper-Weiszfeld-Newton算法；并推廣了單設(shè)施選址問題

2、，提出了廣義單設(shè)施選址問題.論文的具體內(nèi)容如下：在第一章緒論中介紹了本課題的研究背景，課題的研究現(xiàn)狀以及本文的主要工作.第二章介紹了三種連續(xù)設(shè)施選址問題:單設(shè)施選址問題，多設(shè)施選址問題和廣義單設(shè)施選址問題.第三章給出了本文涉及的五種基本算法：Weiszfeld算法，改進(jìn)的Weiszfeld算法，Newton算法，最近中心再分配算法，ProjectionandContraction算法.
　　第四章，針對Weiszfeld算法在全局

3、收斂和收斂速度方面的局限性，結(jié)合了改進(jìn)的Weiszfeld算法的全局收斂性和Newton算法的局部二階收斂率，提出了Weiszfeld-Newton算法.此算法不僅具有全局收斂性并且大大地加快了收斂速度.數(shù)值實驗中通過和其它算法進(jìn)行比較，表明了Weiszfeld-Newton算法的優(yōu)越性.
　　第五章，多設(shè)施選址問題非凸且是NP-難的，求解它的經(jīng)典算法是Cooper-Weiszfeld算法（交替選址-分配算法），通過在選址過程中使

4、用Weiszfeld-Newton算法，本文提出了一種叫做Cooper-Weiszfeld-Newton算法去求解多設(shè)施選址問題.通過數(shù)值實驗可以看出本章算法的有效性.并且，通過在選址過程中選取上一次迭代的最優(yōu)點作為下一次迭代的初始點將Cooper-Weiszfeld-Newton算法稍作改進(jìn)，加快了算法的收斂速度.
　　第六章中通過引入不對稱尺度，將單設(shè)施選址問題推廣，提出了的廣義單設(shè)施選址問題.推廣模型與經(jīng)典的單設(shè)施選址模型的

5、不同在于：1）距離度量尺度是非對稱的；2）推廣模型是帶約束的.廣義單設(shè)施選址問題實際上是非凸最優(yōu)化問題，求解的主要困難是當(dāng)需求點和新設(shè)施位于分界線兩側(cè)時，如何在分界線上找到一個穿越點，使得需求點到這個穿越點的距離與這個穿越點到新設(shè)施的距離之和最小.本章采用的方法不是直接找穿越點，而是通過等價變換，將它轉(zhuǎn)化成線性變分不等式，然后用ProjectionandContraction算法進(jìn)行求解.
　　最后總結(jié)全文并提出以后可行的研究方向