选址模型

选址模型是用于求解最优选址问题的运筹学模型。

选址模型详细介绍

选址模型是用于求解最优选址问题的运筹学模型。

选址模型最优选址

最优选址问题是指：已知若干现有设施的地址，确定一个或几个新设施的地址；或已知需要被服务的节点，建立一个最优设施点，以使其为节点最好地服务。在这里设施的含意是广义的，可以指提供服务的设施，也可以指需要服务的设施。最优选址问题的典型例子有:已知工厂和用户的位置,确定新仓库的最优地址；已知供电区域，选择发电厂的最优地址；已知一组油井的位置，确定炼油厂的最优地址；已知读者服务区域，选择图书馆的最优地址等。最优选址问题分单源选址问题和多源选址问题。单源选址问题是已知若干个现有设施，选择一个新设施的最优地址。多源选址问题则是已知若干个现有设施，选择两个或多个新设施的最优地址。多源选址问题还要确定哪个新设施应为哪些现有设施服务，或哪些现有设施应为哪个新设施服务。这里包含着分配问题，所以又称为选址－分配问题。选址问题还可以分为连续型选址问题和离散型选址问题。连续型选址问题是假定待选区域中任一点的地位均与其他点的地位相同，因而在数学上就有无限多个可能的地点存在。离散型选址问题则是假定待选区域内只有有限多个事先已经知道的位置。

选址模型单源选址

设(xj，yj)是需要供应或服务的已知点在平面上的坐标,(x，y)是待求的源的坐标；cj是单位货物发送单位距离的运价；bj是各需求点对货物的需求量(j=1,2,…,n)。从(x，y)到任一需求点(xj，yj)的运费是bjcj【(x-xj)2+(y-yj)2】1/2,如令dj=【(x-xj)2+(y-yj)2】1/2,则运费为bjcjdj。因此,从(x，y)到所有需求点的总运费。求此函数关于x和y的偏导数,并使其等于0，即可求得它的极小值。即

它们无法用显式解出，只有用迭代法求解。即

d忋=【(x-xj)2+(yk-yj)2】1/2。式中上指标k表示第k次迭代，上指标k+1表示第(k+1)次迭代。初始值可取

当两个相继得出的解(xk，yk)和(x,y)充分接近时，迭代就停止进行。这种迭代过程可在计算机上进行。

选址模型多源选址

多源选址问题的一般提法是：已知各个终点的位置和需求量以及该区域内的运价，求源的个数、各个源的位置、如何将终点划分给各个源和各个源的容量。为了使问题简化，通常假定各个源许可的容量不受限制，单位运价与源的总输出量无关。多源连续型选址问题比较复杂，现有两种适用于大型多源选址问题的近似解法：交替选址-分配法和随机终点法。

选址模型交替选址

交替选址-分配法是一种单调下降的收敛过程。它的基本步骤是:

①将n个终点组成的集合划分成元素个数大致相等的子集。

②对 m个子集中的每一个子集求解单源选址问题。

③检查每一个终点，如果它离

②中求出的某一个源比分配给它的那个源靠得更近，则重新分配各终点。

④如果要重新分配，则回到

②，否则计算即可终止。

选址模型随机终点法

它的基本步骤是：

①根据1到n各个整数的均匀分布产生m个随机数。这里n是终点数,m是源数。

②将标号为这m个整数的终点看作源，而把其余n-m个终点分配给费用最小的源。设(xs，ys)是所考虑的源,分配时应使 bjcj【(xs-xj)2+(ys-yj)2】1/2取极小值。

③重复

①和

②，直到满足终止准则为止，每次重复均保留费用最小的解。

④求解m个单源选址问题,看结果有无改进,以求得最优解。根据一个事先确定的数或行之有效的简单方法即可终止这种随机地产生尝试解的求解过程。