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

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

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

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

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

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