论文部分内容阅读
设施选址问题是运筹学的经典问题之一，在经济，管理，交通运输等领域都有着非常广泛的应用.单设施选址问题和多设施选址问题一直是设施选址问题的研究热点.求解单设施选址问题和多设施选址问题最常用的算法是Weiszfeld算法和Cooper-Weiszfeld算法.本文对这两种问题分别提出了具有收敛性且收敛速度更快的新算法：Weiszfeld-Newton算法和Cooper-Weiszfeld-Newton算法；并推广了单设施选址问题，提出了广义单设施选址问题.论文的具体内容如下：在第一章绪论中介绍了本课题的研究背景，课题的研究现状以及本文的主要工作.第二章介绍了三种连续设施选址问题:单设施选址问题，多设施选址问题和广义单设施选址问题.第三章给出了本文涉及的五种基本算法：Weiszfeld算法，改进的Weiszfeld算法，Newton算法，最近中心再分配算法，Projection and Contraction算法.第四章，针对Weiszfeld算法在全局收敛和收敛速度方面的局限性，结合了改进的Weiszfeld算法的全局收敛性和Newton算法的局部二阶收敛率，提出了Weiszfeld-Newton算法.此算法不仅具有全局收敛性并且大大地加快了收敛速度.数值实验中通过和其它算法进行比较，表明了Weiszfeld-Newton算法的优越性.第五章，多设施选址问题非凸且是NP-难的，求解它的经典算法是Cooper-Weiszfeld算法（交替选址-分配算法），通过在选址过程中使用Weiszfeld-Newton算法，本文提出了一种叫做Cooper-Weiszfeld-Newton算法去求解多设施选址问题.通过数值实验可以看出本章算法的有效性.并且，通过在选址过程中选取上一次迭代的最优点作为下一次迭代的初始点将Cooper-Weiszfeld-Newton算法稍作改进，加快了算法的收敛速度.第六章中通过引入不对称尺度，将单设施选址问题推广，提出了的广义单设施选址问题.推广模型与经典的单设施选址模型的不同在于：1）距离度量尺度是非对称的；2）推广模型是带约束的.广义单设施选址问题实际上是非凸最优化问题，求解的主要困难是当需求点和新设施位于分界线两侧时，如何在分界线上找到一个穿越点，使得需求点到这个穿越点的距离与这个穿越点到新设施的距离之和最小.本章采用的方法不是直接找穿越点，而是通过等价变换，将它转化成线性变分不等式，然后用Projection and Contraction算法进行求解.最后总结全文并提出以后可行的研究方向.