选址问题课件

选址问题（LocationProblem）选址理论--是关于选址问题的模型和算法的理论。选址问题复杂多样，涉及到非常大的方面，如定位一个新的制造企业或者军事基地；也涉及到非常小的方面，如在电路板上印刷完整的电路。按照被定位的对象的空间维数划分，可以分为：立体选址、平面选址、线选址、点选址。第15章选址问题（LocationProblem）15.1概述（Introduction）15.2三维选址问题（Three-DimensionLocationProblem）15.2.1遗传算法实现（GeneticAlgorithm）15.2.2算例（Parexample）15.2.3小结（Summary）15.3集装箱船配载优化方法研究（ResearchontheOptimalMethodsforContainerAboardLoaded）15.3.1集装箱重量分布的优化模型（TheOptimalModelofContainerWeight）15.3.2的确定（Confirm）15.3.3最少压载量的确定（TheMinimumBallast）15.3.4计算实例（Parexample）15.4点选址问题（DotLocationProblem）15.4.1连续点选址问题（ContinuousLocationProblem）15.4.2离散点选址问题（DiscreteLocationProblem）15.5无能力约束设施选址问题（UncapacitiedFacilitesLocationProblem（UFL））15.5.1问题描述（Introduction）15.5.2UFL问题的线性规划模型（LinerModelofUFL）15.5.3对偶问题（Dualproblem）15.5.4UFL的启发式算法（HeuristicMethodsforUFL）15.1概述选址理论——是关于选址问题的模型和算法的理论。选址问题复杂多样，涉及到非常大的方面，如定位一个新的制造企业或者军事基地；也涉及到非常小的方面，如在电路板上印刷完整的电路。为选址问题设计算法和模型时通常要考虑以下因素：（1）被定位的对象具有什么特性，（2）目标选址地区的结构特点是什么，（3）目标和成本参数是什么，（4）其它限制条件是什么。以上因素影响到模型结构和算法设计，可据此对选址问题进行分类。15.1概述按照被定位的对象的空间维数划分，可以分为：立体选址、平面选址、线选址、点选址。立体选址中，物体具三维空间，这类选址问题的例子是集装箱装箱问题。若物体具二维空间，这类选址问题称为平面选址，其例子是工厂或货运站设施布局。若物体具一维空间，这类选址问题称为线选址，其例子是在仓库的巷道两边划出合适的拣选带。若物体是一个点，这类选址问题称为点选址，点选址常被用在物体尺寸相对于目标区域尺寸忽略不计的情况下。这种类型在物流中占绝大多数，最常见的是制造和配送系统的选址，如图15-1维数空间选址的问题是存在的，但是很少见。如果限制条件或者参数随时间而变化，这时需要考虑时间维，这类问题统称为动态选址问题。15.1概述图15-1点选址的例子15.1概述按照目标区域的结构来划分，可分为：连续选址、网格选址、网络选址和离散点选址。连续选址中，候选区域是一个平面或球面并且没有其它任何结构。这时可能选址的数量是无限大的。距离的数值是以一个距离准则来确定的。这些模型在数学上是连续的并且通常都可以采用分析的方法。图15-2连续选址的示意图15.1概述网格选址中，目标区域被划分为许多个单元，要求为对象分配其中若干个单元。例如：在一个大型仓库中为成千上万种不同商品分配存储单元。尽管存储单元是有限的，但是很多。很明显采用离散选址既没有必要，也难以处理。图15-3网格选址示例15.1概述网络选址中，目标选址区域是一个网络,即节点和边的集合。通常而言，如果网络不存在诸如树形等特殊结构时，不存在有效的算法。最佳选址问题是建立在运输网络基础上时，通常都属于这类问题。图15-4网络选址问题15.1概述离散点选址问题中，候选点数量是有限的并且较少。这些模型是现实中最常用的模型，但是相关的计算和数据采集的值都比较大。典型的例子是对企业的配送网络进行详细设计。从目标函数来分类，基本上可以分为中位问题（medianproblem）和中心问题（CenterProblem）两类。中位问题以总成本最小为目标函数。这个指标常用于商业系统，又称最小总和目标（MinisumObjective）。

5-1其中X表示选址方案,表示方案X对于目标j的成本。15.1概述中心问题以服务于各个顾客的最大成本最小化为总目标。这个指标经常被用在军队，公共服务系统和其他紧急情况处理，又称为最小化最大值（MinimaxObjective），目标函数被写成：

5-2例如：假设在一条直线上有4个点分别为0，5，6，7。假定要在直线上选一个中心为上述四个点提供服务。假设服务这些点的成本是与距离严格成比例的。根据最小总和指标，中位问题的最优化选址应该是在5和6之间任何一个点。而根据最小化最大值目标，中心问题的最优化选址应该是，以使最远的服务距离最小化。15.1概述通过观察上述例子可以发现，当被服务点在0和7之间增加若干个时，中位问题的最优解要发生变化，而中心问题则不会，因为中心问题的一个重要特点是，最优解取决于某些极端情形。图15-5中位问题和中心问题的比较15.1概述第三种类型的指标函数是获取最大最小目标值。比如污水处理工厂选址或者某些军事装备选址。这类问题又称为反中心问题（anti-CenterProblem）。其目标函数可写为：式5-3同样以上述例子来讨论，可知反中心问题的最优解是X=2.5。图15-6反中心问题和中心问题的比较15.1概述根据问题中的参数是否与解存在关联，可分为纯选址问题和选址—分配问题。纯选址问题中参数或结构不依赖新建设施而改变，是事先已确定。相反则称为选址--分配问题。例如：指派顾客到最近的配送中心，如果移动了配送中心不但可能增加了与顾客的距离而且有可能使顾客去其它的配送中心。根据问题中的参数是否随时间而改变，可以分为静态选址问题和动态选址问题；根据参数确定性的还是随机性的还可以分为确定性选址问题和随机选址问题。此外，依据候选点是否存在服务能力约束，可以分为无限能力选址和有限能力选址。15.2三维选址问题集装箱装载问题广泛地出现在铁路货车车厢装载、汽车车厢装载、轮船配载、集装箱装载等情况。问题的提法是：将一批待布箱体(长方体)装入长方体容器中，目标是使容器空间利用率和重量利用率达到最高。同时要考虑到的约束有：(1)箱体本身的承重性(易碎性)；(2)箱体搬运的难易性；(3)一些货物必须隔离；(4)不允许超过最大承重量；(5)重心与几何形心偏差不应太大；(6)货物码放的稳定性等等。15.2三维选址问题有关布局问题的综述性工作，其中大部分是研究二维或三维矩形物体在矩形容器中的布局。目前常用的布局优化方法有数学规划法、图论法、启发式方法、人工智能，多为不带约束的简化布局问题。杨传民等人通过全面枚举搜索方法来研究相同大小的立方体的装箱优化问题。Mannchen设计的数搜索算法，理论上对三维箱体布局有效，但由于三维箱体布局属于NP完全问题，随着布局箱体的增多，解空间剧增，因而计算效率较低。H．GEHRING提出按阶段填充，在深度方向按层布局的启发式算法，不仅考虑了空间利用率，而且还考虑了重心平衡。戴佐采用八叉树描述三维物体，并以八叉树为基础设计启发式算法．王金敏以相同尺寸的物体布局为研究对象，特约束处理加入启发式规则中，提出关于约束底盘装载问题的启发式方法。以上求解都建立在简化模型的基础上，而现实生活中存在着大量多目标、多约束的布局，人们在研究集装箱布局时，往往采用简化模型，以回避这一问题。许多实际约束，如装载稳定性、重心平衡使得集装箱布局问题更加复杂(本文定义这种问题为复杂集装箱装载问题)。通常需要将这些约束考虑到启发式规则中，而不能只是先考虑空间利用率，待布局完成后再检查约束，因为有些复杂的布局很难凭经验捡查出是否满足约束。15.2三维选址问题因此，开发实用的综合考虑多种约束，多种目标的集装箱空间规划算法有待于进一步加以研究。由于存在多目标、多约束的空间规划问题的计算复杂性，利用数学规划法和图论法不太有效；启发式方法虽然较为有效，但大多只能解一类问题，局限性较大。因此，本文采用遗传算法作为工具，通过权重系数变化法处理多目标问题，通过罚函数法处理约束，在采用遗传算法处理复杂集装箱装载问题方面做了一些尝试。求解问题的目标包括：①空间利用率最大；②货物总重量最大；③货物总体重心尽量低，以使稳定性最大，搬运方便。其约束包括：①总重量不允许超过集装箱最大承重量；②物体间不允许出现空间干涉。15.2三维选址问题遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。遗传算法在空间规划领域中的应用刚刚开始，集装箱空间规划问题为NP完全问题，而遗传算法本身的鲁棒性、并行性以及在NP完全问题求解中的广泛应用表明，遗传算法是解决复杂集装箱空间规划问题的有效途径。如何将遗传算法应用于集装箱空间规划是值得深入研究的，这对于推广遗传算法在实际空间规划设计中的应用，具有重要的实际意义。15.2.1遗传算法实现15.2三维选址问题1.问题解的数字串表示——编码平面布局一般采用待布物体在平面上的坐标组成解串，但是，坐标值的调整变化仅描述了待布物本身位置的改变，可能会使待布物之间出现干涉，为此需要进行判断，以避免出现干涉，亦即坐标值的变化是受限制的，这不适合于用遗传算法求解。而且，在三维空间布局中，干涉的计算量要大得多。因此，需要构造一种新的、更适合的表示方式。把待布物的编号按排放顾序排列成串，即15.2.1遗传算法实现15.2三维选址问题15.2.1遗传算法实现其中表示待布物的个数；为整数，其值代表盒子的编号。交叉和变异算子对其进行的操作实际上就是改变待布物的排放顺序，从而产生不同的空间规划图（不同的解）。数字串是解的基因型表示，能否简单、快速地将其转化为表现型（即空间规划图），从而求出其有关评价参数，就成为遗传算法能否有效应用的关键，为此，本文提出如下译码算法。15.2三维选址问题2.空间分解算法——译码布局空间分解过程采用三叉树数据结构表示。先对原始布局空间求解，此时，原始布局空间为当前布局空间，对应于三叉树的根结点。按照第15.1节中数字串的先后顺序，从可选布局物体中选择一个相对于当前布局空间为最优的布局物体，其摆放方式通过可行域的形状确定，将其定位于当前布局空间后部的左下角。如图15-1位置所示，并将布入的物体编号从中删除。这样，原布局空间的剩余空间可分为，，这3个子空间，分别对应于三叉树根结点的左、中、右3个子结点。剩余的布局空间就变成3个独立的布局空间，依次将，，当作当前空间，对这3个布局空间重复上述分解过程，直至没有待布局物体满足要求或集装箱没有可利用空间时停止。15.2.1遗传算法实现15.2三维选址问题

这样，数字串就转化为布局图，并且克服了空间干涉约束。由此可见，三叉树结构对于求解复杂集装箱布局的空间分解问题有着明显的优势。但对于具有特殊形状的容器的布局问题，目前还无法很好地应用。图15-7空间分解示意图15.2.1遗传算法实现15.2三维选址问题3.适宜度函数遗传算法对一个解的好坏用适宜度函数值的大小来评价，适宜度的值越大，解的质量超好。在讨论遗传算法的实现之前，应先定义适宜度函数。4.空间利用率函数

其中，表示第个布入的盒子的体积，表示集装箱体积，m为布入的盒子数15.2.1遗传算法实现15.2三维选址问题重量考察函数。其中，表示i第个布入盒子的质量，表示集装箱最大承载重量。超过最大重量，惩罚为0。重心考察函数15.2.1遗传算法实现15.2三维选址问题其中，表示集装箱高度，表示第个盒子的重心高度，通常取盒子高度的一半。表示第个盒子的重量。该函数主要考察码放的稳定性和撒运的难易性。若重物体都在下面，则码放稳定，且易搬运。因此，根据惩罚函数法和处理多目标优化的加权系数法，定义适宜度函数为

其中，为权重，根据经验来选择。15.2.1遗传算法实现15.2三维选址问题5.遗传算子（1）选择算子采用比例选择法和最优保存策略，既能保证适应度较高的个体遗传到下一代，又能保证有较高的全局收敛性。比例选择方法（proponionalmodel）的基本思想是：各个个体被选中的概率与其适应度大小成正比，适应度越高的个体被选中的概率越大；反之，适应度越低的个体被选中的概率小。15.2.1遗传算法实现15.2三维选址问题我们希望适应度最好的个体要尽可能地保留到下一代群体中。为了达到这个目的，可以便用最优保存策略进化模型(elitistmodel)来进行优胜劣汰操作，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。最优保存策略可视为选择操作的一部分。该策略的实施可保证迄今为止所得的最优个体不被交叉、变异等遗传运算所破坏，它是遗传算法以概率1收敛到全局最优解的一个重要保证条件。15.2.1遗传算法实现15.2三维选址问题15.2.1遗传算法实现（2）交叉算子对于本文这种类似于旅行商的以符号编码的基因串，交叉方式有部分映射交叉、顺序交叉、循环交叉等。本文采用部分映射交叉方式。部分映射交叉也称为部分匹配交叉〔patiallymatchedcrossover)。这种交叉操作的主要思想是：整个交叉操作过程由两步来完成，首先对个体编码串进行常规的双点交叉操作，然后根据交叉区域内各个基因值之间的映射关系来修改交叉区域之外的各个基因座的基因值。15.2三维选址问题15.2.1遗传算法实现（3）变异算子本文采用如下变异操作，以较小的概率一对数字串中任意两个基因座和Q之间的基因进行逆排列。5.终止准则进化代以后，停止计算，输出最好的解作为所求得的最优解。15.2三维选址问题6.运算过程（1）初始化，设置进化代数计数器t＝0，设置最大进化代数T＝200，随机生成2*M个个体作为初试群体P(0)，M＝20。（2）个体评价，按前述计算群体P(t)中各个个体的适应度F()。（3）选择运算，将前述的选择算子作用于群体。（4）交叉运算，将前述的交叉算子作用于群体。15.2.1遗传算法实现15.2三维选址问题（5）变异运算，将前述的变异算子作用于群体。（6）群体经过选择、交叉、变异运算之后得到下一代群体，终止条件判断。，则，转到步骤2；若，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。15.2.1遗传算法实现15.2三维选址问题设布局空间为国际标准的20英尺集装箱，尺寸为2.352*2.388*5.899，单位是米，最大载重量为18.07吨，已知其最优解是体积利用率为100％，重量利用率为100％，重心高度为集装箱高度的1／2，重心评价函数为100，总体适宜度函数为100，待布局货物数据，计算结果如图15-8所示，见表15-1。15.2.2算例图15-8集装箱计算结果图15.2三维选址问题15.2.2算例表15-1集装箱计算结果表15.2三维选址问题CH表示在H方向的坐标，CW表示在方向的坐标，W表示在方向的坐标，CD表示在方向盒子的尺寸，D表示在方向盒子的尺寸，表示在方向盒子的尺寸(坐标见图15-7)，共布入18个盒子，体积利用率为95.32％，重量利用率为99.9％，重心高为118.16cm，重心评价函数为100．56，总体适宜度函数为97.48，计算时间为0.1小时，此结果与最优结果相差很小。同一组数据采用中的启发式算法，不考虑约束，空间规划结果如图所示，见表15-2，求得的空间利用率为90.7％p低于本算法，重量利用率为118％，超过最大允许重量，显然，本算法即使考虑约束，结果也优，说明本算法是有效的。15.2.2算例15.2三维选址问题15.2.2算例表15-2空间规划结果15.2三维选址问题空间规划问题大量出现在工程领域，通过集装箱空间规划实验可以看出，利用遗传算法解三维物体空间规划是行之有效的。本文仅以典型约束、优化目标为例，更多的约束或目标可以类似地加人到本算法之中。本文为利用遗传算法求解集装箱空间规划提供了经验和基础，对推广遗传算法在空间规划设计中的应用具有一定的意义。15.2.3小结15.2三维选址问题15.3集装箱船配载优化方法研究

在集装箱船配载设计过程中，充分发挥集装箱船装载能力，保证集装箱船的强度以及适度的稳性和适当的吃水差是积载设计的关键。15.3.1集装箱重量分布的优化模型集装箱重量合理的纵向分布有利于减小船体所受的弯矩，合理的垂向的分布则有利于保证适度的稳性，充分发挥船舶载货能力，减少压载，改善航行性能和减小绑扎设备受力。集装箱重量的纵向分布和垂向分布无关，集装箱船的受力和稳性优化这一多目标优化问题可转化为单目标优化问题。1.集装箱纵向受力优化集装箱船积载时对强度的考虑，主要是船舶的总纵强度、局部强度和扭转强度。在积载时应尽量将各行位内各载荷重量左右对称分布以使转矩最小。对于局部强度，主要是使各部位集装箱的垂向累计重量不超过甲板或舱底的允许负荷，可在纵向受力的优化模型中以约束条件来处理。因此受力优化的关键是纵向受力，即使船体所受的静水弯矩最小。15.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型15.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型为求解方便，可以根据集装箱的纵向分布情况，沿船长方向在船上划分若干个站点，并以集装箱区域的前端剖面作为0号(n＝0)，该处弯矩为此，01行箱的后端剖面为1号(n＝1)，该处弯矩为此，03行位的后端剖面站号为n＝2，该处弯矩为此，依此类推。船体各区段的船体重力，浮力，压载量为，船舶燃油、淡水、备品和船舶常数的重量为，相应行位的集装箱重量为。15.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型设

各区段内的负荷

船体站点处的静水弯矩为15-415.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型式中，为除集装箱以外的其他各项载荷和船体重量产生的弯矩；为前后两站点的间距，m；为对应于的两行箱位之间的空隙，m；为对应于的负荷作用中心点距该区段中点的距离，m，位于中点之后取正。可在船舶空船重量曲线上求得。平均吃水和吃水差由航次具体情况确定。吃水和吃水差确定后，相应各段船体的浮力矩也可通过邦戎曲线(banjean’scurve)求得。如果事先拟定压载方案，可作为常数项，因此只有为随机变量。15.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型由于每一行位集装箱的重量分为甲板和舱内两部分，则，每行箱位集装箱重量的限制为。式中，和分别为在某一行箱位上甲板和舱内所能承载的最大集装箱重量。假设所有的箱位均装有集装箱(如果实际箱数少于总箱位容量，则空余的箱位重量取0，集装箱纵向受力的线型优化模型可表示为

15-515.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型式中，为最轻个集装箱的平均重量；为最重个集装箱的平均重量；为第排(行)集装箱重量为第行的箱位数；为集装箱总行位数。当机舱后部有箱位时，可将机舱范围看成一行，以该范围集装箱重量取零作为约束条件。有时需要指定具体行位的装箱方案，也可在约束条件中实现。式15-5还应受条件的约束(为集装箱的总重量)。求解时，可先按式5—5从01行开始，采用逐行位迭代的方法，求出每一行箱位处集装箱重量的解，然后按线性比例的方法考虑条件的约束，求出每一行箱位处集装箱重量的最优解。15.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型2.集装箱船稳性优化设第层集装箱重心距基线高分别为，第行箱位共有的层数，则全船集装箱的垂向重力力矩为：

式中，。又船舶合重心位置：。令，有：15-615.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型在一定排水量条件下，如果事先拟定压载和油水装载方案，则式中只有一个变量，如果给定的最优值，则可找到相应最优的。在受力优化问题中，可求出使得集装箱船所受总纵弯矩最小的各行位重量分布。现假设各行箱位上集装箱的重量分布服从一级优化的结果，具体分配到各行箱位的最优集装箱垂向重量力矩与各行位集装箱重量呈线性比例。实际装载时，可能要根据情况指定某一行位的某些集装箱必须装于甲板上。根据集装箱到港等情况，设有r只集装箱限定装于第行甲板上，重量为，其合重心距基线高，其它各行均自舱内开始装。15.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型令，有

（m•kN）

15-7式中，当时，。在求出各行箱位集装箱垂向重量矩的基础上，可进一步求出第行第层集装箱的重量分布。其线性优化模型为

15-815.3集装箱船配载优化方法研究15.3.1集装箱重量分布的优化模型式中，为集装箱船第i行、k层的箱位数，和分别为最小和最大个集装箱的平均重量。对于上两式，可从01行开始，求出该行各层的集装箱重量分布优化解。该线性优化问题可利用单纯形法求解。01行的求解后，顺次进入其他各行求解。对于40ft集装箱，则以两个20ft集装箱的重量计算到相邻两行的箱位中。15.3集装箱船配载优化方法研究15.3.2的确定上述优化问题求解时，需要计算，也就是必须首先确定最优重心高度或最优的初稳性高度的值。根据有经验的集装箱船船长的意见，一般具有12列集装箱宽的集装箱船，取=1.0m左右；具有8列集装箱宽的小型集装箱船，取=1.2m左右。但这一结论显得较为粗略，船舶在不同排水量和不同海况条件下，其应该是有所区别的。在确定最优或的值时，应考虑临界初稳性高度(或极限重心高度)、横摇周期、装载能力、绑扎设备设计时设定的最大、航行区域及其风浪情况、船员安全感(如果值偏小，船员安全感差)等要求。15.3集装箱船配载优化方法研究15.3.2的确定在综合考虑上述各项因素的前提下，一般应在保证安全和船员安全感的条件下，尽量取较小的值或较大的值。为此，作者主张在满足临界初稳性高度的前提下适当增加一个安全余量作为最优初稳性高度。在分析实践中经验数据的基础上对的大小提出如下算式。

15-10式中，C为考虑航区风浪及甲板上浪程度的系数，取0.8~1.2，航区风浪大或船较小、受风浪影响大时，取大值，反之取小值。15.3集装箱船配载优化方法研究15.3.2的确定如果根据绑扎设备设计所假定的最大初稳性高度小于根据上述方法确定的值，则可取，即有

15-11如船宽为20.8m的某614TEU集装箱船，的取值范围为0.37~0.66m，其满载时的约为0.96~1.26m，但其绑扎系统允许的初稳性高度为1.04m．航区风浪大时可取＝1.04m．必要时也可取＝1.26m，但有必要对绑扎系统采取加固措施。15.3集装箱船配载优化方法研究15.3.3最少压载量的确定集装箱船的稳性特点决定了它必须依靠压载来保证稳性，但压载会减少船舶的集装箱载重能力，增加航行阻力。这里提供一种通过在预定压载方案下求取稳性范围，并使初稳性上限值接近且略大于的方法来确定最少压载量的方法。的上限值可由将全部承运的集装箱从舱底自下而上按重量由大到小的顺序配船后求得。而的下限值则可按上述相反的顺序将集装箱配船后求得。15.3集装箱船配载优化方法研究15.3.3最少压载量的确定要在配载时能得到与相吻合的值且压载量最少，应有且。如果在预定压载方案下计算的，使得，或比小很多，则可按通过调整压载方案对初稳性的上限值进行调整。根据调整稳性的一般计算公式计算出需要在具体位置调整的压载量。在实际操作时，应修正自由液面的影响。考虑到优化纵向受力、中途油水消耗等需要，应有一定的富裕压载量。15.4点选址问题15.4.1连续点选址问题连续选址分析中，点与点之间的距离计算标准有两种：直线距离准则和距离准则。设平面上两点i和j两点之间的笛卡尔坐标分别是。直线距离准则用公式表达为：，上标E表明是直线距离。折线距离准则用公式表达为：，上标R表明是折线距离。15.4点选址问题15.4.1连续点选址问题在大范围地理空间有关的选址问题中，实际的道路距离通常被近似为直线距离乘上一个近似因子。例如，在美国大陆，因子为1.2，在美国的东南部为1.26。而在城市范围内选址时，由于道路系统多数具有网格特性，此时通常采用折线距离准则。1.直线距离准则下选址关于折线距离准则下选址问题，我们提供重心法和网络流算法。在使用了欧几密德距离之后，目标函数变成了：

15.4点选址问题15.4.1连续点选址问题这是一个双变量系统，分别对和进行求偏微分，并却令其为零，这样就可以得到两个微分等式。应用这两个等式分别对和进行求解，既可以求出下面的一对隐含有最优解的等式：

其中，。15.4点选址问题15.4.1连续点选址问题在上式中，在等式的左右两边都出现了和（在右边包含了项），因此该微分方程组不能直接求解。对于这个问题，可以通过迭代的方法进行求解，这需要提供一组初始值和。然后利用和求出，再用它去求出和，迭代公式如下：

其中，。15.4点选址问题15.4.1连续点选址问题

如果该迭代过程具有收敛性，那么经过无限次的迭代之后，可以得到一个最优解。但是在实际中，可以迭代的次数是有限的，所以在迭代过程中需要确定一个中止准则。设置中止准则由两个方法，其一是：根据经验和以前的实验结果，直接设置一个确定的迭代次数N；其二是：将第一次得到的迭代结果、跟前面一次的迭代结果、 ，当两次的迭代结果变化小于某一个值时，迭代过程结束。15.4点选址问题15.4.1连续点选址问题2.折线距离准则下选址（1）重心法对以总和最小为目标函数的单一设施选址问题求解，可以采用重心法。记n个需求点的笛卡尔坐标分别为，需求量分别为，平面内运输费率保持一致。要确定一个供应点的坐标，使总的运输成本最小化。对于折线距离准则，该问题的模型为：

15.4点选址问题15.4.1连续点选址问题显然，问题可以拆分为两个相似而独立的模型：

即坐标x和y是单独确定的。我们只对x求解第一个模型。观察目标函数，可知它是连续而且分段线性的，分段区间以为界限。并且，随着x的增大，直线的斜率是增加的。（2）网络流算法无论是单一设施选址，还是多设施选址，折线距离准则下的连续选址问题度可以转化为一个图上的最小费用最大流问题，相应的网络流算法在运输问题一章中给出，本节主要介绍转化过程。首先，我们着重介绍单一设施选址问题，进而扩展到多设施选址问题。观察目标函数：为了避免非线性问题，如下定义和：

15.4点选址问题15.4.1连续点选址问题15.4点选址问题15.4.1连续点选址问题从而有：

用上等式，先前的公式将会把非线性的函数变为线性来解决。

上述变换中将约束去掉了，因为目标函数极小化以及等式约束的特点，所以最优解中必然满足该约束。上述变换中等式约束右边的表示对偶问题中该约束对应的对偶变量（以后的表述中我们不再作说明）。15.4点选址问题15.4.1连续点选址问题观察其对偶问题：

定义如下变量：

15-12则可将对偶问题转化为如下极小问题：

再增加下述约束显然不影响对偶问题的可行域。

15.4点选址问题15.4.1连续点选址问题15.4点选址问题15.4.1连续点选址问题该问题实际上就是一个流量为f的最小费用流问题的线性规划模型。、别表示弧j上的流量和单位流量产生的费用。0，2wj分别为弧j上流量的下限和上限。表示该网络流问题的网络图如图15-10。

图15-10单个设施运输网络显然，尽量安排流量流经较小费用弧是最优的。15.4点选址问题15.4.2离散点选址问题1.集覆盖问题(SetCoveringProblemSCP)（1）集覆盖问题及其复杂性给定有限集X及X上的几个子集,集覆盖问题就是要求子集的最小组合满足。X中的元素称为点，一个点称之为被覆盖，当且仅当它属于。若每一个子集有一成本，要求总成本最小的覆盖方案，称为最小成本覆盖问题。求解集覆盖问题时，通常用矩阵A（|X|行，n列）描述覆盖关系，表示点可以（不可以）被覆盖。定义，其中，表示集合是否启用。15.4点选址问题15.4.2离散点选址问题则SCP问题的线性规划模型为：

而最小成本覆盖问题的目标函数为：SCP的应用实例很多，如信息检索方法设计，乘务员排班，最小路径分割问题等。对乘务员排班而言，有个航班，根据航班的要求，其中若干个航班可有一组乘务员完成空乘工作，这样的组合有四组，问如何安排，使所有航班都有乘务员且乘务员组数最少。

以下介绍集覆盖问题的几种算法。SCP是NP难题。对于NP难题既然没有多项式时间算法，那么寻求有效的近似算法就很有必要。近似算法是指就问题的所有实例来说，所获得的解距最优解的相对误差小于某一个固定值。15.4点选址问题15.4.2离散点选址问题（2）矩阵简化法矩阵简化法只是简化问题规模的一种方法，不一定能给出最终解来。其基本思想是：按照基本规则，不断地简化集覆盖问题中覆盖矩阵A，同时增加集合进入。具体步骤如下：算法：集覆盖问题的矩阵简化算法input：覆盖矩阵A（行对应于中的点；离对应于）。Output：以及简化后的覆盖矩阵，的解；为A的解。Step0：可行性检查IfA存在一行，所有元素均为0，Then无可行解，算法终止。End15.4点选址问题15.4.2离散点选址问题（3）贪婪算法以下介绍的贪婪算法是一个近似算法。算法：贪婪算法(思想：在二分图中的候选顶点集中选择顶点度最大的顶点，去掉该点及其覆盖的所有顶点，循环上述步骤，直至该图为空。)input,Xoutput满足；（U表示目前尚未覆盖的点的集合）15.4点选址问题15.4.2离散点选址问题15.4点选址问题15.4.2离散点选址问题

；当，循环以下运算：在尚未入选的集合中选择，使其在中能覆盖的点数最多，即最大，令，

end(while)；outputJ；15.4点选址问题15.4.2离散点选址问题（4）贪婪算法的有效性定理：对于集覆盖问题F={}，，。用以上贪婪法获得的解与最优解Jopt有如下关系：

其中函数（d为正整数），（证明从略）15.4点选址问题15.4.2离散点选址问题（5）最小成本覆盖问题的贪婪算法对于最小成本覆盖问题F={}，，存在成本，用以下贪婪算法同样可获得近似解。input,Xoutput满足；（U表示目前尚未覆盖的点的集合）；15.4点选址问题15.4.2离散点选址问题当，循环以下运算：在尚未入选的集合中选择，使其在中所覆盖点平均成本最小，即满足，令

end(while)；outputJ；2.中心问题与中位问题（1）介绍物流配送中常见的选址问题有如下几类：a.中心问题（Centerproblems）要选择如干个服务点，以便与最远的顾客距离最小。通常应急服务系统选址都属于这类问题。15.4点选址问题15.4.2离散点选址问题b.中位问题(Medianproblems)要选择如干个服务点，以便与所有顾客的距离总和最小。c.无约束工厂选址问题(Uncapacitatedfacilitylocationproblems)从一组被选点中选出如干个用于建设工厂。工厂无生产能力约束，开设工厂有固定成本支出。工厂服务于顾客点有收益，要确定总收入最大的选址方案。15.4点选址问题15.4.2离散点选址问题15.4点选址问题15.4.2离散点选址问题（2）符号表述在离散选址中，常用加权无向图来表述问题。每一节点是一需求点，有非负的需求量。每一条边有服务成本表示边长。问题是在图上选择若干个点作为服务站，为需求点提供某种服务，以便特定的目标函数极大化或极小化。服务站可设在节点上，也可设在边上。定义节点间最短路径长为。若位于边上，用表示点到点的距离，作如下定义：

又，对于点集与，定义，其含义为到集合的最小距离或服务网点服务于顾客的最小成本。15.4点选址问题15.4.2离散点选址问题（3）中心问题中心问题：给定图，对于上任意点集，定义 ，求取一点集，满足使。若，局限为顶点，即，则称为顶点中心问题；若，局限为边上，则称为局部中心问题；若可为图上任意点，则称为绝对中心问题。对于，通常还相应地称为顶点p中心问题；局部p中心问题，绝对p中心问题。15.4点选址问题15.4.2离散点选址问题对于顶点单中心问题，可以计算图的最小距离矩阵，对每行取最大值。最大值中的最小值所在行对应的节点即为顶点单中心问题的最优解。在下图所示顶点单中心问题中，都是最优解。图15-13顶点单中心问题15.4点选址问题15.4.2离散点选址问题（4）中位问题在图中，任意顶点存在非负实数与之对应，存在非负实数。对于任意点集，定义 ，求使，这就是中位问题。中位问题的应用实例很多，如建设若干个中央仓库，以满足各地的物资需求，使总的运输成本最小化，见下图。若约定，称为顶点中位问题。15.4点选址问题15.4.2离散点选址问题图15-17中位问题15.4点选址问题15.4.2离散点选址问题下面给出关于中位问题的一个性质：定理：（Hakimi定理），顶点中位问题的解同时也是中位问题的解；即：中位问题至少存在一个解，所有点都位于顶点上。从而，利用上述定理，可以将中位问题简化为顶点中位问题。15.5无能力约束设施选址问题15.5.1问题描述给定候选点集，顾客集，以及相关的成本收益数据。无能力约束设施选址问题要求在候选点集中选出若干个点作为工厂，满足所有顾客要求，使总收入最大。一般地UFL问题包含以下要素：候选点集，顾客集，由j满足I产生的收益 ，启用j产生的成本，问题是求取，并为每一顾客分配唯一候选点，使净收益最大化。下图是一个例子，UFL也是NP难题。15.5无能力约束设施选址问题15.5.1问题描述图15-19一个UFL问题显然，将最后一个（0，1）约束松弛为如下约束，所得混合整数规划与原问题是等价的。15.5无能力约束设施选址问题15.5.2UFL问题的线性规划模型15.5无能力约束设施选址问题15.5.2UFL问题的线性规划模型若将（）约束条件转换为，称为；显然与有相同的可行解集。

分别将与中约束条件替换为。得到两个松弛问题，分别称为和。显然，的可行解集是 可行解集的子集。实践当中，比求解效果更好，但由于约束数目较多，故计算量大些。15.5无能力约束设施选址问题15.5.3对偶问题

的对偶问题是：

其中，变量:分别对应约束条件 ，；15.5无能力约束设施选址问题15.5.3对偶问题该对偶问题有两种变换：1.第一种变换观察的对偶问题：若给定，为使目标函数最小化，满足 ，应使最小化，且。也就是说，

其中定义为。15.5无能力约束设施选址问题15.5.3对偶问题又 ，从而 ；进而， 。因而的对偶问题可变换为：

15.5无能力约束设施选址问题15.5.3对偶问题2.第二种变换若存在使，即 ；则存在使 。从目标函数看，略微增加ul，目标函数值不变。从而，对任意 的情况，总存在的解具有相同目标函数值。又，由的对偶问题可看出，最优解总满足。15.5无能力约束设施选址问题15.5.3对偶问题因此，可将对偶问题的第一种变换变换为：15.5无能力约束设施选址问题15.5.4UFL的启