第三章选址模型及应用

,FP&D,单击此处编辑母版标题样式,第三章 选址模型及应用,双击添加标题文字,3.1,选址的意义,3.2,选址决策的影响因素,3.3,选址模型的分类,3.4,选址中的距离计算,3.5,选址模型,3.6,实例分析,3.1,选址的意义,选址在整个物流系统中占有非常重要的地位，主要属于物流管理战略层的研究问题。,选址决策就是要确定所要分配的设施的数量、位置以及分配方案。这些设施主要指物流系统中的节点，如制造商、供应商、仓库、配送中心、零售商网点等。,3.1,选址的意义,设施数量与客户响应时间,快速响应客户需求是竞争因素之一,快速响应客户需求与节点设施设置的数量有关,期望的,响应时间,设施数量,3.1,选址的意义,选址与库存、运输成本存在密切联系，选址就是要在设施数量和成本中求得最佳。,设施数量,库存成本,设施数量,运输成本,设施数量,设施成本,设施数量,总成本,响应时间,3.1,选址的意义,就供应链系统而言，核心企业的选址决策会影响所有供应商物流系统的选址决策。,3.2,选址的影响因素,选址决策影响因素大致可分为外部因素及内部因素两大类,选址决策影响因素,外部因素,宏观政治因素,政权、法制、政策等,宏观经济因素,税收、关税、汇率等,基础设施,交通设施、通信设施,自然环境与社会环境,如劳动力成本与质量,市场环境,竞争对手、供应商、客户等,内部因素,企业发展战略,如制造业企业选择劳动密集,/,技术密集发展战略；,如商业服务业选择连锁便利店,/,超市的发展战略,3.2,选址的影响因素,选址决策包括地区选择和地点选择，二者需要考虑的因素有所不同。地区选择要考虑的是宏观因素；地点选择要考虑的是微观因素。,选址决策影响因素,地区选择,（,1,）政策导向,（,2,）市场情况,（,3,）社会环境,（,4,）资源条件,（,5,）基础设施和配套供应,（,6,）上下游企业关系,地点选择,（,1,）区域规划,（,2,）地形地貌,（,3,）面积与外形,（,4,）外部衔接,（,5,）地质条件,（,6,）气象及辐射,（,7,）地下水与洪水,（,8,）地震,3.2,选址的影响因素,按照影响因素的性质的不同，可把影响因素分成两大类：即成本因素和非成本因素。还可以根据因素对设施选址的重要性，分为：关键因素、重要因素、次要因素等,。,3.3,选址模型的分类,在建立一个选址模型之前，我们需要清楚以下问题：,（,1,）选址的对象是什么？（,2,）选址的目标区域是怎样的？,（,3,）选址目标和成本函数是什么？（,4,）有什么样的一些约束？,体选址,面选址,线选址,高维选址,单一设施选址,多设施选址,连续选址,网络选址,离散选址,可行性,/,最优性,Minisum/Minimax,Maximin,高次目标函数,确定性与随机性,静态与动态,有能力约束,无能力约束,有不可行区域,无不可行区域,设施维度及数量,选址目标区域,选址成本,选址约束,固定权重,/,可变权重,3.4,选址问题中的距离计算,在选址问题模型中，最基本的一个参数是各个节点之间的距离。,有两种方法计算节点之间的距离：,直线距离，也叫欧几里德距离（,Euclidean Metric,）；,折线距离（,Rectilinear Metric,），也叫城市距离（,Metropolitan Metric,）。,3.5,选址模型,简单模型：,在一条直线上（街道）选择一个有效位置（商店），即一种设施，让这条街道上的所有顾客到达商店的平均距离最短。,假设街道上顾客分布的概率（密度）为,则目标函数为：,简单模型,大街上第,i,个位置到所选地址的距离,选择投资的位置,3.5,选址模型,定积分求导：,定积分求导,（,1,）,其中， 被假设为在时间区间 中具有连续导数 。,莱布尼兹法则,关于一个变量（它既不是积分变量，也不进入积分上下限）求导定积分，可以简单地穿过积分符号直接关于该变量求导被积函数。,3.5,选址模型,定积分求导：,定积分求导,（,2,）,有微商公式：,定积分关于积分上限,b,的导数等于被积函数在,t=b,处的取值；,定积分关于积分下限,a,的导数等于被积函数在,t=a,处的取值的负数；,3.5,选址模型,定积分求导：,定积分求导,（,3,）,有微商公式：,右边第一项来自对被积函数中变量的求导，右边第二项来自对积分上限的求导，而且基于下列链式求导：,其中,x,不仅进入被积函数，而且影响积分上限,对以下函数求导,3.5,选址模型,对目标函数求导，,令一阶导数为零，得：,简单模型,求解结果表明，所开设的新店面需要设置在权重的中点，即两面的权重都是,50%,。,3.5,选址模型,连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。,交叉中值模型（,Cross Median,）,通过交叉中值的方法对单一设施平面选址问题的加权城市距离进行最小化。其目标函数为：,交叉中值模型,第,i,个点对应的权重，例如需求；,需求点的总数目,第,i,个需求点的坐标；,服务设施的坐标；,3.5,选址模型,交叉中值模型的目标函数可以用两个互不相干的部分来表达：,交叉中值模型,是,x,方向所有权重的中值点；,是,y,方向所有权重的中值点；,惟一值,某一范围,惟一值,点,线段,某一范围,线段,区域,3.5,选址模型,例,1,报刊亭选址,一个报刊连锁公司想在一个地区开设一个新的报刊亭零售点，主要的服务对象是附近的,5,个住宿小区的居民，他们是新开设报刊亭零售点的主要顾客源。下图坐标系中确切地表达了这些需求点的位置，下表为各个需求点对应的权重。权重代表每个月潜在的顾客需求总量，基本可以用小区中总的居民数量来近似。经理希望通过这些信息来确定一个合适的报刊零售点的 位置，要求每个月顾客到报刊零售点所行走的距离总和最小。,交叉中值模型,需求点,x,坐标,y,坐标,权重,1,3,1,1,2,5,2,7,3,4,3,3,4,2,4,3,5,1,5,6,3.5,选址模型,首先，确定中值，,需求点,沿,x,轴的位置,w,从左到右,5,1,6,4,2,6+3=9,1,3,6+3+1=10,3,4,2,5,从右到左,2,5,7,3,4,7+3=10,1,3,4,2,5,1,交叉中值模型,需求点,沿,y,轴的位置,w,从上到下,5,5,6,4,4,6+3=9,3,3,6+3+3=12,2,2,1,1,从下到上,1,1,1,2,2,1+7=8,3,3,1+7+3=11,4,4,5,5,3.5,选址模型,选址结果：,交叉中值模型,位置,A,（,3,，,3,）,位置,B,（,4,，,3,）,需求点,距离,权重,总和,需求点,距离,权重,总和,1,2,1,2,1,3,1,3,2,3,7,21,2,2,7,14,3,1,3,3,3,0,3,0,4,2,3,6,4,3,3,9,5,4,6,24,5,5,6,30,56,56,3.5,选址模型,连续点选址问题指的是在一条路径或者一个区域里面的任何位置都可以作为选址的问题。,精确重心法（,Exact Gravity,）,交叉中值模型使用城市距离，适合小范围城市内选址问题；,精确重心法使用直线距离，适合大范围城市间选址问题，目标函数为，,精确重心法,与第,i,个点对应的权重，例如需求；,需求点的总数目,第,i,个需求点的坐标；,服务设施的坐标；,3.5,选址模型,精确重心法目标函数为双变量系统，分别对,x,s,和,y,s,求偏导，并令导数为零，求得隐含最优解的等式，,精确重心法,3.5,选址模型,迭代法：,利用已知的点（,x,s,(k-1), y,s,(k-1),）,求出,d,is,(k-1),，再求出新的点（,x,s,(k), y,s,(k),）,依次求解，直到求得符合要求的解。,精确重心法,迭代公式：,(1),其中：,(2),3.5,选址模型,精确重心法,迭代法步骤：,（,1,）初始值的确定；,（,2,）迭代；,（,3,）中止准则；,初始值的确定：,a,、任意选择一个点作为初始值；,b,、按照,简化公式,选择初始值；,3.5,选址模型,中止准则的确定：,a,、直接设置一个确定的迭代次数,N,；,b,、判断两次迭代的差值是否小于设定的阈值；,C,、判断总费用是否减小或两次迭代差值小于设定值,精确重心法,3.5,选址模型,精确重心法应用于报刊亭选址问题：,精确重心法,第,一,次,迭,代,初始位置,(x,0,y,0,),3,3,需求点,1,2,3,4,5,(x,i,y,i,),3,1,5,2,4,3,2,4,1,5,权重,w,i,1,7,3,3,6,距离,d,is,(0),2,2.236067977,1,1.414213562,2.828427125,w,i,x,i,/d,is,(0),；,w,i,y,i,/d,is,(0),1.5,0.5,15.65248,6.26099,12,9,4.2426,8.4852,2.1213,10.606,w,i,/d,is,(0),；,w,i,/d,is,(0),0.5,3.130495168,3,2.121320344,2.121320344,迭代位置,(x,1,y,1,),3.266439171,3.205411382,中止判断（,Z,1,）,41.86567928,3.5,选址模型,精确重心法应用于报刊亭选址问题：,精确重心法,第二次迭代,初始位置,(x,1,y,1,),3.266439171,3.205411382,需求点,1,2,3,4,5,(x,i,y,i,),3,1,5,2,4,3,2,4,1,5,权重,w,i,1,7,3,3,6,距离,d,is,(1),2.221447545,2.111456783,0.76177774,1.495071653,2.890898619,w,i,x,i,/d,is,(1),；,w,i,y,i,/d,is,(1),1.3504,0.4501,16.576,6.6304,15.752,11.814,4.0131,8.0263,2.0754,10.37,w,i,/d,is,(1),；,w,i,/d,is,(1),0.450156927,3.315246637,3.938156554,2.006592791,2.075479216,迭代位置,(x,2,y,2,),3.374277642,3.16477612,中止判断（,Z,2,）,41.11758492,3.5,选址模型,精确重心法应用于报刊亭选址问题：,精确重心法,第三次迭代,初始位置,(x,2,y,2,),3.374277642,3.16477612,需求点,1,2,3,4,5,(x,i,y,i,),3,1,5,2,4,3,2,4,1,5,权重,w,i,1,7,3,3,6,距离,d,is,(2),2.196893125,1.999919147,0.647054587,1.608178463,3.000873375,w,i,x,i,/d,is,(2),；,w,i,y,i,/d,is,(2),1.3655,0.4551,17.500,7.0002,18.545,13.909,3.7309,7.4618,1.9994,9.997,w,i,/d,is,(2),；,w,i,/d,is,(2),0.455188279,3.500141499,4.636393993,1.865464604,1.999417919,迭代位置,(x,3,y,3,),3.463398811,3.116707741,中止判断（,Z,3,）,40.96726655,3.5,选址模型,中止准则的使用：,若（,1,）,N=2,；（,2,）坐标值阈值为,0.2,；坐标值变化幅度小于,4%,；（,3,）总费用阈值为,0.2,；总费用相对变化幅度小于,1%,。,精确重心法,总费用,2.64%,，,-1.52%,3.30%,，,-1.27%,8.88%,，,6.85%,相对差值,40.8438,40.9673,41.1176,41.8657,0.0891,，,-0.0481,0.1078,，,-0.0406,0.2664,，,0.2054,绝对差值,坐标点迭代差值,总费用迭代差值,坐标点,迭代,次数,3.1167,3.1648,3.2054,y,3.4634,3.3743,3.2664,x,0.1235,0.1503,0.7481,绝对差值,1.79%,1,0.37%,2,0.30%,3,相对差值,3.5,选址模型,补充例题：有四个零售点，其坐标、物资需求量及运输费用如下表所示，请用重心法为配送中心选址。,零售点,物资需求量,q,i,运输费用,r,i,坐标,x,i,y,i,1,2,5,2,2,2,3,5,11,3,3,2.5,5,10,8,4,1,5,4,9,精确重心法,第一步，按照简化公式确定初始值，,3.5,选址模型,精确重心法,第二步，以点（,7.8,，,4.9,）作为配送中心，计算距离与总费用，,第三步，计算改善的配送中心选址，,3.5,选址模型,精确重心法,第四步，以点（,8.6,，,5.1,）作为配送中心，计算距离与总费用，,第五步，计算改善的配送中心选址，,3.5,选址模型,精确重心法,第六步，以点（,9.0,，,5.2,）作为配送中心，计算距离与总费用，,此时，,Z(2)=Z(1)=191,，虽然结果是取小数而得，但二者已经非常接近，所以可认为最佳点为（,9.0,，,5.2,）或（,8.6,，,5.1,）。,3.5,选址模型,交叉中值模型与精确重心法,交叉中值模型,精确重心法,城市距离（折线距离）；,适合于小范围的城市内选址问题；,目标使对加权的城市距离最小化；,属于单一设施连续点选址问题。,欧几米德距离（直线距离）；,适合于大范围城市间选址问题；,目标是使加权的直线距离最小化；,属于单一设施的连续点选址问题。,3.5,选址模型,离散点选址问题指的是在有限的候选位置里面，选取最为合适的一个或一组位置为最优方案，相应的模型称为离散点选址模型。,离散点选址模型与连续点选址模型的区别在于：它所拥有的候选方案只有有限个元素。,对于离散点选址问题，目前主要有两种模型，分别是覆盖模型和,P-,中值模型。覆盖模型常用的又有集合覆盖模型和最大覆盖模型两种。,覆盖模型（,Covering,）,覆盖模型，是对于需求已知的一些需求点，确定一组服务设施来满足这些需求点的需求。在这个模型中，需要确定服务设施的最小数量和合适的位置。该模型适用于商业物流系统，如零售点的选择问题、加油站的选址、配送中心的选址问题等。,离散点选址问题,3.5,选址模型,根据解决问题的方法的不同，覆盖模型可以分为两种不同的主要模型：,集合覆盖模型，用最小数量的设施去覆盖所有的需求点；,最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求或需求点。,覆盖模型,3.5,选址模型,集合覆盖模型,集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点。,数学模型为：,集合覆盖模型,N,区域中的需求点（客户）集合，,N=1,2,n,；,M,区域中可建设设施的候选点集合，,M=1,2,m,；,D,j,第,i,个需求点的需求量；,C,i,设施点,j,的服务能力；,A(i),设施节点,i,可以覆盖的需求点,j,的集合；,B(j),可以覆盖需求节点,j,的设施节点,i,的集合；,y,i,为,0-1,变量，,y,i,=1,在,i,点建立设施；,y,i,=0,不在,i,点建立设施，,iM,x,ij,节点,j,需求中被分配给设施点,i,的部分。,3.5,选址模型,集合覆盖模型启发式算法：,第一步：初始化。令所有的,x,j,0,，,y,i,0,， （已分配的需求），并确定集合,A(i),和集合,B(j),；,第二步：选择下一个设施点。在,M,中选择,y,i,0,，且,A(i),的规模为最大的点,i,为设施点，即 ，令 ，并在,M,集合中剔除节点,i,，即,第三步：确定节点,i,的覆盖范围。将,A(i),中的元素按,B(j),的规模从小到大的顺序指派给,i,，直至,i,的容量为,C,i,0,或,A(i),为空。其中对于,j,A(i),且，,x,j,D,j,，将,j,支配给,i,的方法为：若 ，则令,x,ij,=D,j,x,j,，,C,i,=C,i,-(D,j,-x,j,),，,x,j,1,，在,A(i),和,N,中剔除需求点,j,。若 ，则令,第四步：若,N,或,M,为空，停止；否则，更新集合,A(i),和集合,B(j),，转第二步。,集合覆盖模型启发式算法,3.5,选址模型,例：在某区域需规划建设若干个农贸市场为将来该区,9,个主要居民点提供服务，除第,6,居民点外，其他各点均有建设市场的条件，如下图所示。已知市场的最大服务直径为,3km,，为保护该区域的环境，希望尽可能少地建造农贸市场。问应如何规划？,解：,N,1,2,3,4,5,6,7,8,9,，,M,1,2,3,4,5, 7,8,9,，由图两点间的最短距离，根据最大服务半径为,3km,的约束及第,6,居民点不适合建市场的要求，可确定集合,A(j),和,B(i),。如下表所示，值得指出的是本问题没有需求量和容量，故无需考虑服务能力约束式。,集合覆盖模型启发式算法,1,7,8,4,9,2,5,6,3,2,2,4,3,4,1,4,3,2,3,3,2,1,1,图 小区居民点位置图,3,3.5,选址模型,集合覆盖模型启发式算法,第一步，初始化,居民点号,A(i),B(j),1,1,2,3,4,1,2,3,4,2,1,2,3,1,2,3,3,1,2,3,4,5,6,1,2,3,4,5,4,1,3,4,5,6,7,1,3,4,5,7,5,3,4,5,6,3,4,5,6,3,4,5,7,8,7,4,6,7,8,4,7,8,8,6,7,8,9,7,8,9,9,8,9,8,9,第二步，确定一个设施点。因为,A(4)=1,3,4,5,6,7,，,|A(4)|=6,为最大，故首先选取,i,4,。由于无容量约束故依次指派,5,7,1,6,3,4,点归节点,4,服务。,第三步，更新。此时，,N,2,8,9,M,1,2,3,5,7,8,9,更新集合,A(i),和集合,B(j),后如下表所示。,3.5,选址模型,集合覆盖模型启发式算法,居民点号,A(i),B(j),1,2,1,2,3,2,2,1,2,3,3,2,1,2,3,5,4,1,3,5,7,5,3,5,6,3,5,7,8,7,8,7,8,8,8,9,7,8,9,9,8,9,8,9,第四步，确定一个设施点。因为,A(8),8,9,，,|A(8)|,2,为最大，故首先选取,i,8,，并且,8,，,9,两点归节点,8,服务。,第五步，更新。此时，,N,2,M,1,2,3,5,7,9,更新集合,A(i),和集合,B(j),后如下表所示。,3.5,选址模型,集合覆盖模型启发式算法,第六步，确定一个设施点。,因为,A(2),2,，,|A(2)|,1,为最大，故首先选取,i,2,，并且,2,点归节点,2,服务,。,第七步，更新。此时，,N,M,1,3,5,7,9,结束。,因此，计算结果为（,4,8,2,）。,居民点号,A(i),B(j),1,2,1,2,3,2,2,1,2,3,3,2,1,2,3,5,4,1,3,5,7,5,3,5,6,3,5,7,7,7,8,7,9,3.5,选址模型,集合覆盖模型整数规划,y,i,为,0-1,变量，,y,i,=1,在,i,点建立设施；,y,i,=0,不在,i,点建立设施，,iM,x,ij,节点,i,供给量中被分配给需求点,j,的部分。,居民点号,A(i),B(j),1,1,2,3,4,1,2,3,4,2,1,2,3,1,2,3,3,1,2,3,4,5,6,1,2,3,4,5,4,1,3,4,5,6,7,1,3,4,5,7,5,3,4,5,6,3,4,5,6,3,4,5,7,8,7,4,6,7,8,4,7,8,8,6,7,8,9,7,8,9,9,8,9,8,9,3.5,选址模型,集合覆盖模型整数规划,整数规划模型：,3.5,选址模型,集合覆盖模型整数规划,Lingo,软件求解：,3.5,选址模型,最大覆盖模型,已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中选择,p,个位置作为物流设施网点（如配送中心、仓库等），使得尽可能多地满足需求点的服务。,最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象提供服务，如下图所示。,最大覆盖模型,最大覆盖模型,3.5,选址模型,最大覆盖数学模型为：,最大覆盖模型,N,区域中的需求点（客户）集合，,N=1,2,n,；,M,区域中可建设设施的候选点集合，,M=1,2,m,；,d,i,第,i,个需求点的需求量；,D,j,设施点,j,的服务能力；,p,允许建设的设施的数目；,A(j),设施节点,j,可以覆盖的需求点,i,的集合；,B(i),可以覆盖需求节点,i,的设施节点,j,的集合；,X,j,为,0-1,变量，,x,j,=1,在,j,点建立设施；,x,j,=0,不在,j,点建立设施，,jM,y,ij,节点,i,需求中被分配给设施点,j,的部分,(,比例,),。,3.5,选址模型,集合覆盖模型与最大覆盖模型数学模型比较,最大覆盖模型,集合覆盖模型,最大覆盖模型,3.5,选址模型,最大覆盖模型整数规划,3.5,选址模型,集合覆盖模型整数规划,Lingo,软件求解：,3.5,选址模型,P,中值模型,P,中值模型是指在一个给定数量和位置的需求集合和一个给数量和候选位置的设施集合的前提下，分别为,P,个设施找到合适的位置并指派每个需求点到一个特定的设施，使之达到在设施与需求点之间的运输费用最低。,如下图所示。,P,中值模型,3.5,选址模型,P,中值数学模型为：,P,中值模型,N,区域中的需求点（客户）集合，,N=1,2,n,；,M,区域中可建设设施的候选点集合，,M=1,2,m,；,d,i,第,i,个需求点的需求量；,c,ij,从需求点,i,到设施点,j,的单位运输费用；,p,允许建设的设施的数目，,pm,；,x,j,为,0-1,变量，,x,j,=1,在,j,点建立设施；,x,j,=0,不在,j,点建立设施，,jM,y,ij,为,0-1,变量，,y,ij,=1,表示需求点,i,由节点,j,提供服务；,y,ij,=0,表示需求点,i,不由节点,j,提供服务； 。,3.5,选址模型,例,3,：某饲料公司的仓库选址问题,某饲料公司在某新地区经过一段时间的宣传广告后，得到了,8,个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建,2,个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地调查之后，已有,4,个候选地址，如下图所示；各候选地址到不同超市的运输成本、各个超市的需求量如下表所示。,P,中值模型,1,2,3,4,5,6,7,8,1,2,3,4,i,j,d,i,1,2,3,4,c,ij,1,4,12,20,6,100,2,2,10,25,10,50,3,3,4,16,14,120,4,6,5,9,2,80,5,18,12,7,3,200,6,14,2,4,9,70,7,20,30,2,11,60,8,24,12,6,22,100,3.5,选址模型,P,中值,贪婪取走启发式算法,（,Greedy Dropping Heuristic Algorithm,）,:,P,中值模型贪婪取走启发式算法,第一步，初始化，令循环数,k=m,，将所有,m,个候选位置都选中，然后将每个需求点分配给离其最近的一个侯选位置。,1,2,3,4,5,6,7,8,1,2,3,4,400,100,360,600,160,140,120,600,设施点,费用,1,860,2,140,3,720,4,760,总费用,2480,3.5,选址模型,P,中值模型贪婪取走启发式算法,第二步，选择并取走一个位置点，满足以下条件：假如将它取走并将它的客户重新指派后，总费用增加量最小，然后令,k=k-1,。,1,2,3,4,5,6,7,8,2,3,4,600,160,140,120,600,需求点,移走位置,1,后总费用增加量,1,+200,2,+400,3,+120,总费用增加量,+720,600,500,480,3.5,选址模型,P,中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,1,3,4,400,100,360,600,160,280,120,600,需求点,移走位置,2,后总费用增加量,6,+140,总费用增加量,+140,移走位置,2,：,3.5,选址模型,P,中值模型贪婪取走启发式算法,需求点,移走位置,2,后总费用增加量,7,+540,8,+600,总费用增加量,+1140,移走位置,3,：,1,2,3,4,5,6,7,8,1,2,4,400,100,360,600,160,140,660,1200,3.5,选址模型,P,中值模型贪婪取走启发式算法,需求点,移走位置,2,后总费用增加量,4,+240,5,+800,总费用增加量,+1040,移走位置,4,：,1,2,3,4,5,6,7,8,1,2,3,400,100,360,1400,400,140,120,600,因此，移走位置,2,，总费用为,2620,，令,k=k-1=3.,3.5,选址模型,P,中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,3,4,600,500,1680,600,160,280,120,600,第三步，重复步骤二。,移走位置,1,：,需求点,移走位置,1,后总费用增加量,1,+200,2,+400,3,+1320,总费用增加量,+1920,3.5,选址模型,P,中值模型贪婪取走启发式算法,1,2,3,4,5,6,7,8,1,4,400,100,360,600,160,630,2200,660,移走位置,3,：,需求点,移走位置,1,后总费用增加量,6,+350,7,+540,8,+1600,总费用增加量,+2490,3.5,选址模型,P,中值模型贪婪取走启发式算法,移走位置,4,：,需求点,移走位置,1,后总费用增加量,4,+320,5,+800,总费用增加量,+1120,1,2,3,4,5,6,7,8,1,3,400,100,360,1400,480,280,120,600,因此，移走位置,4,，总费用为,3740,，令,k=k-1=2.,此时,k=p,，计算结束。,3.5,选址模型,P,中值模型贪婪取走启发式算法,Lingo,软件求解：,model:,data:,M=4;,N=8;,p=?;,enddata,sets:,warehouse/1.M/:x;,supermarket/1.N/:d;,cost(supermarket,warehouse):c,y;,endsets,min=sum(cost(i,j):c(i,j)*y(i,j)*d(i);,for(supermarket(i):,sum(warehouse(j):y(i,j)=1);,p=sum(warehouse(k):x);,for(cost(i,j):y(i,j)=x(j);,for(cost(i,j):bin(y(i,j);,for(warehouse(i):bin(x(i);,data:,d=100 50 120 80 200 70 60 100;,c=4 12 20 6,2 10 25 10,3 4 16 14,6 5 9 2,18 12 7 3,14 2 4 9,20 30 2 11,24 12 6 22;,enddata,end,