运筹学-7(选址分析).ppt

运筹学基础教程 7,黄桐城 主编 赵弘志 改编 主讲,第七章 选址分析,主要内容本教材没有这个内容. 企业位置规划 企业选址模型与方法 选址问题模型 设施选址问题分析 单一物流中心选址方法 多物流中心选址方法（了解） 物流中心选址的决策分析（了解）,6.1 企业设施选址概述,6.1.1 企业设施选址的几项原则 1、有利于物资运输合理化：企业设施是供应物资 运输的终点和销售物质的起点，其布局是否合理将直接影响 到运输的效益。 2、方便用户：物资部门的服务对象是物资或商品的 供需双方，主要是销售需求用户，因此尽可能靠近用户。 3、有利于节省基本建设费用：为节约费用，设施 应该设在地形环境比较有利的位置上。,4、能适应国民经济一定时期发展的需要：应该 对计划区域内生产发展水平和建设规划进行预测，以使节点 布局方案对今后国民经发展有较好的适应能力。 6.1.2 企业选址分类 根据物流设施选址数量，可将物流设施选址分 为：单一物流设施连续点选址、多物流设施连续点 选址和离散型物流设施选址。,6.2 企业选址模型与方法,6.2.1 选址问题模型 选址问题的历史可以追溯到远古时期人类对于 居住洞穴的选择上。经过几千年的发展，关于设施 选址的问题形成了多种多样的模型和理论。选址问 题之所以受到如此多的关注，主要有以下原因： (1)这些设施在不向范围、不同层次上均为个体 (居民、消费者、家庭)与社会集体(社区、地区、国 家)联系和沟通的纽带，是城市大网络上的重要节 点。,(2)从选址问题本身来讲，属于一个系统工程问 题，其合理决策的难度很大。由于选址所涉及的因 素众多，各因素之间的关系难以确定，同时随着社 会的发展以及各地社会发展程度的不同，选址决策 的评价标准、各因素对选址决策的影响也不尽相 同，不同地域、不同类型、不同规模的设施选址问 题可以采用的方法也不同。 Mark Daskin和David Schilling等根据对各国 关于设施选址的研究，就已有的模型做出了总结， 选址问题可以分成8类基本模型。 1距离覆盖模型 (Maximum Distance Models),(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个零售商的分配成本和为最小。,q1,q2,q3,q4,重心法是一种布置单个设施的方法，这种方法 要考虑现有设施之间的距离和要运输的货物量。它 经常用于中间仓库的选择。在最简单的情况下，这 种方法假设运入和运出成本是相等的，它并未考虑 在不满载的情况下增加的特殊运输费用。 重心法首先要在坐标系中标出各个地点的位 置，目的在于确定各点的相对距离。坐标系可以随 便建立。在国际选址中，经常采用经度和纬度建立 坐标。 然后，根据各点在坐标系中的横纵坐标值求出 成本运输最低的位置坐标X和Y，重心法使用的公式 是：,式中X0 重心的x 坐标； Y0 重心的y 坐标； Xi 第i个地点的x坐标；Yi 第i个地点的y坐标； Wi 第i个地点货物量；Ci 第i个地点运输费。 最后，选择求出的重心点坐标值对应的地点作为我们要 布置设施的地点。,案例：某物流园区，每年需要从P1 地运来铸铁，从P3 地 运来煤炭，从P4 地运来日用百货。各地与某城市中心的距 离和每年的材料运量如下表所示：,解：因为运费率相同，故公式可以简化： 所以，该企业应该选址在（25.4, 42.1）Km的 位置上。 下面，我们给同学介绍一个迭代重心法。,什么是迭代法？,迭代法也称辗转法，是一种不断用变量的旧值递推新值 的过程,跟迭代法相对应的是直接法（或者称为一次解 法），即一次性解决问题。迭代法又分为精确迭代和近似迭 代。“二分法”和“牛顿迭代法”属于近似迭代法。 迭代算法是用计算机解决问题的一种基本方法。它利用 计算机运算速度快、适合做重复性操作的特点，让计算机对 一组指令（或一定步骤）进行重复执行，在每次执行这组指 令（或这些步骤）时，都从变量的原值推出它的一个新值。 利用迭代算法解决问题，需要做好以下三个方面的工 作：,一、确定迭代变量。在可以用迭代算法解决的问题 中，至少存在一个直接或间接地不断由旧值递推出新值的变 量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量 的前一个值推出其下一个值的公式（或关系）。迭代关系式 的建立是解决迭代问题的关键，通常可以使用递推或倒推的 方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程？ 这是编写迭代程序必须考虑的问题。不能让迭代过程无休止 地重复执行下去。迭代过程的控制通常可分为两种情况：一 种是所需的迭代次数是个确定的值，可以计算出来；另一种 是所需的迭代次数无法确定。对于前一种情况，可以构建一 个固定次数的循环来实现对迭代过程的控制；对于后一种情 况，需要进一步分析出用来结束迭代过程的条件。,附：单一物流中心选址-迭代重心法,公式：在应用公式求到重心值后 使用下列迭代公式:,说明,由图可知：d为直角三角形的斜边，为两个直角边的平方 开根号。,例1：四个零售店的数据： 第一步：根据重心公式：,故将四个零售店的重心（7.8，4.9）作为初始地点， 用迭代法来改善它，使得总费用最小。 因为 所以: D=(26.5+33.7+2.53.8+15.6) 5=196,根据迭代公式:,再根据得到的改善的地点(8.3, 5.3)计算新的d j 和 D. 得到: 依次得到： d2 = 3.5 d3 = 3.2 d4 = 5.6 。 同样得到： 然后计算得到新的坐标（8.3，5.3）为最佳地点。 当然，我们可以应用理论公式求得精确的最优化结 果，但是我们还得考虑现实环境条件进行修改。,附：迭代重心法另外一本教材中的介绍,公式：X = ( Qi Ri Xi / Di ) / ( Qi Ri / Di ) Y = ( Qi Ri Yi / Di ) / ( Qi Ri / Di ) Di= ( ( Xi X ) + (Yi Y ) ) F = Qi Ri Di 同学注意公式符号变了，内容没有变化。 (Xi , Yi)-现有目标的坐标位置 Qi -运输量 Ri -运输费率 F -总运费 (X , Y)-新仓库的位置坐标 Di -现有目标到新仓库的距离,例2：某企业的两个工厂P1、P2 分别生产 A、B 两种产品，供应三个市场 M1、M2、M3。已知条件如表一所示。现需设置一个中转仓库，A、B 两种产品通过该仓库间接向三个市场供货。请使用迭代重心法求出仓库的最优选址。,解：1求出新仓库的初始坐标,初始坐标：X=32250/625=51.6 Y=32375/625=51.8 2计算各节点与初始坐标的距离Di和初始运输总成本,3进行一次迭代修正,一次迭代后的新坐标： X=1020.095/20.249=50.38 Y=1023.877/20.249=50.56,一次迭代后，新仓库的最优选址坐标为(50.38 , 50.56),2、交叉中值选址方法 先确定权重的中值； 其次，寻找 x 方向上的中值； 再次，寻找 y 方向上的中值； 最后，综合考虑 x 方向 y 方向的影响，决定 选址的最后位置。 3、精确重心选址方法 6.3 多物流设施选址模型（非重点） 6.4 离散型物流设施选址模型（非重点）,复习与课外作业,随着业务的发展，该公司在四个城市都设置了配送中心，并在城市4设置了一个总仓库为四个配送中心送货，各配送中心的位置(Xi,Yi)及其日常送货数量qi（车）如表3所示。由于需求增加过快和成本过高等原因，该公司正在设想将仓库从城市C4搬出，另外选址建设一个仓库。请用重心法确定仓库的具体位置(X,Y)。 表3 配送中心的位置和送货数量,练习 1,答案,练习 2,某厂每年需要从P1地运来钢材，从P2地运来铸铁，从P3地运来焦炭，从P4地运来各种造型材料。据调查分析，今后较长时期内市场对该厂产品的需求量将呈上升趋势，为此该厂拟在原料产地附近地区建一分厂，以降低成本。各地到拟议中的分厂城市中心的距离和每年的材料运量如表1，请用重心法确定分厂厂址，并进行一次迭代修正。 表1 距离运量表,参考答案 1、仓库的初始选址 i Xi Yi Vi Ri ViRi ViRiXi ViRiYi 1 30 40 2000 1 2000 60000 80000 2 50 60 1200 1 1200 60000 72000 3 40 30 1000 1 1000 40000 30000 4 50 10 2500 1 2500 125000 25000 6700 285000 207000 根据上面数据求得： 相应的初始运输成本计算如下表：,=28500/6700= 42.54,=207000/6700= 30.90,进行一次迭代修正如下表：,其中，迭代计算过程如下：,=k(30- 40.36)2+(40- 30.36)21/2=14.15,其中，k表示比例尺，这里为1,我们安排一些有难度的习题，同学可以在空闲 的时候思考如何解习题的解法。不作为必修内容。 1A、B、C、D 四个城市的需求量分别是50、 60、25、30，现有X和Y两个工厂，产量分别为50、 40，从X到四个城市的运输成本是9、8、6、5，从Y 到四个城市的运输成本是9、8、8、0，现准备在Z地 建厂，Z地到四个城市的运输成本是5、3、3、10， 运输方式该如何安排？Z地的产量是多少？,2现有工厂A，A工厂给三个配送中心送货。 A工厂的最大生产能力是400单位，现在三个配送中 心的需求都在