运筹学-7(选址分析)

运筹学基础教程7黄桐城主编赵弘志改编主讲第七章选址分析主要内容—本教材没有这个内容.★企业位置规划★企业选址模型与方法——选址问题模型——设施选址问题分析——单一物流中心选址方法——多物流中心选址方法（了解）——物流中心选址的决策分析（了解）6.1企业设施选址概述6.1.1企业设施选址的几项原则1、有利于物资运输合理化：企业设施是供应物资运输的终点和销售物质的起点，其布局是否合理将直接影响到运输的效益。2、方便用户：物资部门的服务对象是物资或商品的供需双方，主要是销售需求用户，因此尽可能靠近用户。3、有利于节省基本建设费用：为节约费用，设施应该设在地形环境比较有利的位置上。4、能适应国民经济一定时期发展的需要：应该对计划区域内生产发展水平和建设规划进行预测，以使节点布局方案对今后国民经发展有较好的适应能力。6.1.2企业选址分类根据物流设施选址数量，可将物流设施选址分为：单一物流设施连续点选址、多物流设施连续点选址和离散型物流设施选址。6.2企业选址模型与方法6.2.1选址问题模型选址问题的历史可以追溯到远古时期人类对于居住洞穴的选择上。经过几千年的发展，关于设施选址的问题形成了多种多样的模型和理论。选址问题之所以受到如此多的关注，主要有以下原因：(1)这些设施在不向范围、不同层次上均为个体(居民、消费者、家庭)与社会集体(社区、地区、国家)联系和沟通的纽带，是城市大网络上的重要节点。(2)从选址问题本身来讲，属于一个系统工程问题，其合理决策的难度很大。由于选址所涉及的因素众多，各因素之间的关系难以确定，同时随着社会的发展以及各地社会发展程度的不同，选址决策的评价标准、各因素对选址决策的影响也不尽相同，不同地域、不同类型、不同规模的设施选址问题可以采用的方法也不同。MarkDaskin和DavidSchilling等根据对各国关于设施选址的研究，就已有的模型做出了总结，选址问题可以分成8类基本模型。1．距离覆盖模型(MaximumDistanceModels)(1)集合覆盖模型(1)集合覆盖模型——其基本思想是寻找最少的能够覆盖所有需求点的设施备选点集合。(2)最大覆盖模型——其目标是选择固定数目的设施使覆盖的需求最大。(3)p中心问题——其目标是假定需求点均由距离它最近的设施提供服务的情况下，开放固定数目的设施备选点，使设施的覆盖距离最小。2．ρ分散模型以上的建模均是考虑需求点和设施之间的关系，而忽略了设施之间的关系。该模型。与以往模型不同之处在于模型考虑的是设施之间的距离关系，其目标是使设施之间的距离达到最大。3．全距离（或平均距离）模型该模型综合考虑了设施与需求点之间的综合里程，这类模型已经具备了适应于供应链管理的一些思想。它有以下几类基本模型：(1)p中值模型——其目标是开放固定数目的设施备选点，使整个系统的配送费用最小。(2)固定费用模型——p中值模型的建模假设中有三个情况与实际情况不符合。第一，模型假定所有设施备选点点固定费用相同；第二，模型假设设施的供应能力无限制；第三，模型假定已知有多少个设施应该被选择。为了改善这种情况，提出了固定费用模型。(3)中心选址问题——它考虑到不是某个节点的需求，而是节点之间的流量。6.2.1设施选址问题分析（一）定性分析法。定性分析法主要是根据选址影响因素和选址原则，依靠专家或管理人员丰富的经验、知识及其综合分析能力，确定配送中心的具体选址。主要有专家打分法、德尔菲法。定性方法的优点是注重历史经验，简单易行。其缺点是容易犯经验主义和主观主义的错误，并且当可选地点较多时，不易做出理想的决策，导致决策的可靠性不高。（二）定量分析法。定量的方法主要包括重心法、鲍莫尔-沃尔夫法、运输规划法、Cluster法、CFLP法、混合0-1整数规划法、双层规划法、遗传算法等。定量方法选址的优点是能求出比较准确可信的解。其中，重心法是研究单个物流配送中心选址的常用方法，这种方法将物流系统中的需求点和资源点看成是分布在某一平面范围内的物流系统，各点的需求量和资源量分别看成是物体的重量，物体系统的重心作为物流网点的最佳设置点。1.运输量—重心法（单设施选址）假设现在要建一座配送中心以向n个零售商供货，令n个零售商在平面上的坐标为（x1,y1）,(x2,y2),…,(xn,yn)，各零售商的装运量分别为q1,q2,…,qn，则依下式算出的配送中心位置（x,y）将可使新工厂到n个零售商的分配成本和为最小。niiniiiqqxX11niiniiiqqyY11q1q2q3q4重心法是一种布置单个设施的方法，这种方法要考虑现有设施之间的距离和要运输的货物量。它经常用于中间仓库的选择。在最简单的情况下，这种方法假设运入和运出成本是相等的，它并未考虑在不满载的情况下增加的特殊运输费用。重心法首先要在坐标系中标出各个地点的位置，目的在于确定各点的相对距离。坐标系可以随便建立。在国际选址中，经常采用经度和纬度建立坐标。然后，根据各点在坐标系中的横纵坐标值求出成本运输最低的位置坐标X和Y，重心法使用的公式是：式中X0—重心的x坐标；Y0—重心的y坐标；Xi—第i个地点的x坐标；Yi—第i个地点的y坐标；Wi—第i个地点货物量；Ci—第i个地点运输费。最后，选择求出的重心点坐标值对应的地点作为我们要布置设施的地点。niiiniiiiniiiniiiicwcwyycwcwxx110110案例：某物流园区，每年需要从P1地运来铸铁，从P3地运来煤炭，从P4地运来日用百货。各地与某城市中心的距离和每年的材料运量如下表所示：解：因为运费率相同，故公式可以简化：所以，该企业应该选址在（25.4,42.1）Km的位置上。下面，我们给同学介绍一个迭代重心法。1.4225001000120020002500201000201200602000704.35250010001200200025005010002012006020002000yx什么是迭代法？迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。附：单一物流中心选址---迭代重心法公式：在应用公式求到重心值后使用下列迭代公式:jjnjJdrWD1jnjjjjnjjjjnjjjjjnjjjjdrWdyrWydrWdxrWx////110110212020)()(jjjyyxxd说明由图可知：d为直角三角形的斜边，为两个直角边的平方开根号。例1：四个零售店的数据：第一步：根据重心公式：9.415.2329185.233228.715.23241105.21132200yx故将四个零售店的重心（7.8，4.9）作为初始地点，用迭代法来改善它，使得总费用最小。因为所以:D=(2×6.5+3×3.7+2.5×3.8+1×5.6)×5=196jjnjJdrWD16.5)99.4()48.7(8.3)89.4()108.7(7.3)39.4()118.7(5.6)29.4()28.7(21224223222212212121dddd根据迭代公式:jnjjjjnjjjjnjjjjjnjjjjdrWdyrWydrWdxrWx////1101103.56.518.35.27.335.7626.5918.385.27.3335.6223.86.518.35.27.335.626.5418.3105.27.31135.6222020yx再根据得到的改善的地点(8.3,5.3)计算新的dj和D.得到:依次得到：d2=3.5d3=3.2d4=5.6。同样得到：然后计算得到新的坐标（8.3，5.3）为最佳地点。当然，我们可以应用理论公式求得精确的最优化结果，但是我们还得考虑现实环境条件进行修改。1.7)23,5()23.8(21221d5.1915)6.512.35.25.331,72(2D附：迭代重心法另外一本教材中的介绍公式：X=(∑QiRiXi/Di)/(∑QiRi/Di)Y=(∑QiRiYi/Di)/(∑QiRi/Di)Di=((Xi–X)²+(Yi–Y)²)½F=∑QiRiDi——同学注意公式符号变了，内容没有变化。(Xi,Yi)----现有目标的坐标位置Qi---运输量Ri----运输费率F----总运费(X,Y)----新仓库的位置坐标Di----现有目标到新仓库的距离例2：某企业的两个工厂P1、P2分别生产A、B两种产品，供应三个市场M1、M2、M3。已知条件如表一所示。现需设置一个中转仓库，A、B两种产品通过该仓库间接向三个市场供货。请使用迭代重心法求出仓库的最优选址。节点运输总量运输费率坐标XiP120000.0530P230000.0580P325000.07520P410000.07560P515000.07580解：1〉求出新仓库的初始坐标节点XiiYiQiRiQiRiQiRiXiP1308020000.051003000P2802030000.0515012000M1205025000.075187.53750M2604010000.075754500M3808015000.075112.59000合计62532250初始坐标：X=32250/625=51.6Y=32375/625=51.82〉计算各节点与初始坐标的距离Di和初始运输总成本节点XiiYiQiRiDiQiRiDiP1308020000.0535.523552P2802030000.0542.636394.5M1205025000.07531.655934.375M2604010000.07514.481086M3808015000.07540.024502.25合计21469.1253〉进行一次迭代修正节点XiiYiQiRiDiQiRi/DiQiRiXi/DiP1308020000.0535.522.81584.459P2802030000.0542.633.519281.492M1205025000.07531.655.924118.483M2604010000.07514.485.180310.773M3808015000.07540.022.811224.888合计20.2491020.095一次迭代后的新坐标：X'=1020.095/20.249=50.38Y'=1023.877/20.249=50.56节点XiYiQiRiDiQiRiDiP1308020000.0535.813581P2802030000.0542.566384M120502