周洪涛-物流系统规划-第2章设施选址ppt课件.ppt

资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值第第2章章 设施选址设施选址周洪涛周洪涛华中科技大学系统工程研究所华中科技大学系统工程研究所18971300086zht730yahoo 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值p 2.1 设施选址概述 p 2.2 设施选址的影响因素与选址程序 p 2.设施选址方法 p 2.4 设施选址评价方法 主要内容主要内容资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 2 设施选址概述 2 21 11 1 设施的定义设施的定义 “设施”是指一个企业生产系统或服务系统运行所拥有的有形资产，可分为以下四个部分：实体建筑 机器设备 物品资料 工作人员 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 2 设施选址概述 2 21 12 2 设施选址设施选址 设施选址(Facility Location)是确定在何处建厂或建立服务设施，是指运用科学的方法决定设施的地理位置，使之与企业的整体经营运作系统有机结合，以便有效、经济地达到企业的经营目的。设施选址包括两个层次的问题:选位 选择什么区域设置设施；定址在已选定的地区内选定一片土地作为设施的具体位置。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值从设施功能的全面性的角度考虑，设施选址包括：n小型单一设施的选址 根据已有产品，新增产品，生产规模来确定，不考虑竞争力、设施间需求分配、设施成本与数量的关系。主要考虑运输成本。n复合型设施的网络选址 为一个企业所属的多个工厂、仓库、分销服务中心选择合适的地址，对这些设施数量、位置和规模进行优化。设施选址规划的3个方案：扩张当前设施；保留当前设施，同时另地增建新设施；放弃现有地点。2 设施选址概述 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 2 设施选址概述 2 21 13 3 设施选址的意义设施选址的意义 设施选址是建立和管理企业的第一步，科学选址的重要性体现在以下几个方面：p设施选址影响企业的运营成本，从而影 响企业的竞争优势；p设施选址影响企业制定后续经营策略；p设施选址影响设施布置以及投产后的产品和服务质量。选址问题与企业未来息息相关，著名咨询公司麦肯锡甚至提出：企业选址企业选址是决定公司战略成败的因素之一是决定公司战略成败的因素之一。选址决策 就是确定要选择的设施数量、位置和分配方案。设施主要是指物流网络中的节点（制造商、供应商、仓库、配送中心、零售商网点）。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 22 设施选址的影响因素与选址程序 2 22 21 1 影响因素影响因素地区选址应考虑的因素（考虑宏观因素）：销售目标市场及客户分布 资源市场及供应商分布条件 交通便利条件 土地条件 自然条件 人力资源条件 社会环境与政策条件 其他基础设施 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 22 设施选址的影响因素与选址程序 2 22 21 1 影响因素影响因素具体地点选择应考虑的因素：城市的大小 地价、用地的政策限制与发展 与外部的衔接 设施周边自然地理环境 居民的态度 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 22 设施选址的影响因素与选址程序 2 22 21 1 影响因素影响因素影响选址决策的内部因素：组织的性质 制造业（成本最小化）还是服务业（收入最大化）？制造业（成本最小化）还是服务业（收入最大化）？组织的战略目标 新市场（目标市场的潜力），旧市场（降低成本，新市场（目标市场的潜力），旧市场（降低成本，着重考察人力成本和目标地点的物流效率）。着重考察人力成本和目标地点的物流效率）。企业投资的具体项目和所生产的产品 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 22 设施选址的影响因素与选址程序 2 22 21 1 影响因素影响因素 影响设施选址的经济因素和非经济因素：经济经济因素因素非非经济经济因素因素经济经济因素因素非非经济经济因素因素1.运输费用1.当地政策法规4.燃料价格4.人文环境2.土地成本和建设费用2.经济发展水平5.水、电等资源成本5.气候条件3.原材料供应价格3.环境保护标准6.劳动力价格资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 22 设施选址的影响因素与选址程序 2 22 21 1 影响因素影响因素施选择影响因素分析示例 P32-33：某工厂厂区必要面积为某工厂厂区必要面积为6065公顷，经选址小组工作决定，图公顷，经选址小组工作决定，图2.3所示所示A、B、C三个厂址为候选位置。如何运用分析法来确定最佳厂址。三个厂址为候选位置。如何运用分析法来确定最佳厂址。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 22 设施选址的影响因素与选址程序 2 22 22 2 选址程序选址程序准备阶段准备阶段（选址目标要求，如产品、生产规模，运输条件，物料和人（选址目标要求，如产品、生产规模，运输条件，物料和人力资源等；选址所需的技术经济指标，如年供电量、运输量和用水量等）力资源等；选址所需的技术经济指标，如年供电量、运输量和用水量等）地区选择阶段地区选择阶段（收集资料，如征询选址意见，对可供选择的地区内进（收集资料，如征询选址意见，对可供选择的地区内进行调查，比较候选地区，提出地区选择初步意见）行调查，比较候选地区，提出地区选择初步意见）具体地点选择阶段具体地点选择阶段（对若干候选地址深入调查和勘测，查阅相关历史（对若干候选地址深入调查和勘测，查阅相关历史统计资料，收集各种现有资料，提出数个候选场址。阶段报告，最终报统计资料，收集各种现有资料，提出数个候选场址。阶段报告，最终报告及资料，图形资料）告及资料，图形资料）资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 22 设施选址的影响因素与选址程序 2 22 23 3 设施选址报告设施选址报告 场址选择的依据（如批准文件等）建设地区的概况及自然条件 设施规模及概略技术经济指标 各厂址方案的比较 对各场址方案的综合分析和结论 当地有关部门的意见 附件，包括各项协议文件的抄件、区域位置图，如设施所选位置、用地、交通路线、各类管线走向等，以及设施初步总平面布置图。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 23 设施选址方法 1、单设施选址模型 2、多设施选址模型3、动态仓库选址模型资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 23 设施选址方法 2 23 31 1 单设施选址单设施选址 单设施选址模型，又称重心模型，比较常用，可可用用于于工工厂厂、车站、仓库或零售服务设施选址车站、仓库或零售服务设施选址。该模型选址因素一般只包括运运输输费费率率和货货物物运运输输量量，所以方法相对简单。数学上，该模型可被归为静静态态连连续续选选址址模模型型，它是一种最常用的模型，可解决连续区域直线距离的单点选址问题连续区域直线距离的单点选址问题。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 23 设施选址方法 2 23 31 1 单设施选址单设施选址 重心模型式选址问题中最常用的一种模型，可解决连续区域直线距离的单点选址问题。1.问题：设有n个客户（收货单位）P1，P2，Pn分布在平面上，其坐标分别为（xi，yi），客户的需求量为wi，费用函数为设施（配送中心）与客户之间的直线距离乘以需求量。试确定设施试确定设施P0的位置（的位置（x0，y0），使总运输费用最小。），使总运输费用最小。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 23 设施选址方法 2 23 31 1 单设施选址单设施选址 2.建立模型 记：j配送中心到收货点Pj每单位量、单位距离所需运费。wjPj的需货量。djP0到Pj的直线距离。则总运费H为求H的极小值点 。由于式（2.1）为凸函数，最优解的必要条件为满足 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值19 令 得 资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值20 上式右端dj中仍含有未知数x0，y0，故不能一次求得显式解，但可以导出关于x和y的迭代公式：应用上述迭代公式，可采用逐步逼近算法求得最优解，该算法称为不动点算法，主要步骤如下：3.算法（单一配送中心选址的不动点算法）资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值21 输入：n客户数；（xi，yi）各客户点的坐标，i1，2，n；i，wi各客户点的单位运费和运量，i1，2，n。输出：设施坐标；H总运费。第第1 1步步：设取一个初始的迭代点 ，如：.然后计算A到各客户点的直线距离dj和费用H0：第第2 2步步：令 ，转第3步。第第3 3步步：若 ,运费已无法减小，输出最优解 和 ，否则，转第4步。第第4 4步步：令 转第2步。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 还有一些其他的单设施选址模型和方法，如图表技术(Graphical Techniques)、近似法(Approximating Methods)等。它们的差别主要体现符合现实情况的程度、计算的速度和难度、得出最优解的能力等方面，一般说来，没有任何模型具有某一选址问题所希望的所有特点，也不可能以模型解直接作为最终决策。单设施选址模型的评述与推广单设施选址模型的评述与推广资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值单设施选址模型的评述与推广单设施选址模型的评述与推广单设施选址模型的一些简化的假设条件：1、模型假设需求集中一点，实际需求来自分散的多个消费点，市场的重心通常被当作需求的集聚地，导致计算误差；2、单设施选址模型一般根据可变成本选址；3、总运输成本假设运价随运距比例增加。起码运费+运价分段；4、直线距离假设；5、静态模型。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值例例2-32-3 设某制造厂的工厂设某制造厂的工厂P P1010和需货地和需货地P P1 1P P9 9的位置及需求货物量如表的位置及需求货物量如表2 22 2所示，现要从工厂将产品送到需货地，试在需货地附近设置一个配送所示，现要从工厂将产品送到需货地，试在需货地附近设置一个配送中心，使运费最小，并与工厂直送方式相比，哪种方式最经济？中心，使运费最小，并与工厂直送方式相比，哪种方式最经济？已知：从工厂到配送中心每吨货物运输费已知：从工厂到配送中心每吨货物运输费a a10101818（元），吨货直接（元），吨货直接配送费配送费a aj j4040（元）（元）（j=1,2,9j=1,2,9），配送中心的费用每吨），配送中心的费用每吨180180元，若采元，若采用直送方式，从工厂到需要地每吨运费用直送方式，从工厂到需要地每吨运费r rj j4040元。元。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值25需货地和工厂需货地和工厂坐标坐标需求量需求量w wj jP P1 1(150,60)(150,60)1515P P2 2(130,90)(130,90)5 5P P3 3(60,130)(60,130)1818P P4 4(100,130)(100,130)7 7P P5 5(70,60)(70,60)1212P P6 6(30,90)(30,90)1515P P7 7(50,40)(50,40)1313P P8 8(65,140)(65,140)1010P P9 9(110,120)(110,120)5 5P P1010(工厂工厂)(150,190)(150,190)100100表表22 工厂和需货地的位置及需求量工厂和需货地的位置及需求量资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值26 解：解：1.1.求配送中心最优地址求配送中心最优地址设初始解设初始解令令 因为因为H H1 1HH0 0，令，令H H0 0=H=H1 1=386163.1=386163.1，资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值27计算同理，再进行迭代7次，有：计算 因为H1H0，令H0=H1=385960.5，计算资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值28因为H1=H0，H0已最小，输出最优解：(x0,y0)=(96.2,125.3),H=385960.5 2.与工厂直送方式成本比较 由配送中心配送方式的运输费为：T1=工厂到配送中心的运费+配送中心到需要地的运费+配送中心本身费用=385960.5+100*180=403960.5(元)工厂直送方式费用为：T2=工厂到需要地的运费 （元）因为T1T2，所以，经过配送中心方式是经济的。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 23 设施选址方法 2 23 32 2 多设施选址多设施选址 一般地，多数企业可能都有几处物流设施，可能要同时决定两个或多个设施的选址，这样，问题就变得比较复杂了，但却更实际，更普遍。由于不能将这些物流设施看成经济上相互独立的要素，因此问题自然十分复杂。l网络覆盖模型p 集合覆盖模型p 最大覆盖模型l线性规划模型l系统仿真模型资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值l 网络覆盖模型网络覆盖模型 覆覆盖盖模模型型，是是对对于于需需求求已已知知的的一一些些需需求求点点，确确定定一一组组服服务务设设施施来来满满足足这这些些需需求求点点的的需需求求。在在这这个个模模型型中中，需需要要确确定定服服务设施的最小数量和合适的位置务设施的最小数量和合适的位置。该该模模型型适适用用于于商商业业物物流流系系统统，如如零零售售点点的的选选择择问问题题、加加油油站站的的选址、配送中心的选址问题等。选址、配送中心的选址问题等。根据解决问题的方法的不同，可以分为两种不同的主要模型：根据解决问题的方法的不同，可以分为两种不同的主要模型：集合覆盖模型集合覆盖模型，用最小数量的设施去覆盖所有的需求点；，用最小数量的设施去覆盖所有的需求点；最大覆盖模型最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需，在给定数量的设施下，覆盖尽可能多的需求点。求点。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值l集合覆盖模型集合覆盖模型 1.1.问题问题 集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点。集合覆盖模型的目标是用尽可能少的设施去覆盖所有的需求点。已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中 选择若干个位置作为物流设施网点（如配送中心、仓库等），在满 足各需求点的服务需求的条件下，使所投建的设施点数目为最小。如图所示：集合覆盖模型资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值2.2.建立模型建立模型设：N区域中的需求点（客户）集合，N1,2,n；M区域中可建设设施的候选点集合，M1,2,m；di第i个需求点的需求量；Dj若第j个候选点选中时，该设施点的服务能力；A(j)设施节点j所覆盖的需求点i的集合；i的集合 B(i)可以覆盖需求节点i的设施节点j的集合；j的集合 1 在j点建立设施；jM xjxj 0 否则。yij节点需求i中被分配给设施点j的部分。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值则数学模型可表示为（25）s.t.（26）（27）式（25）最小化设施的数目；式（26）保证每个需求点的需求得到完全的满足；式（27）是对每个提供服务的服务网点的服务能力的限制，变量的0-1约束和非负约束保证一个地方最多只能投建一个设施，而且允许一个设施只提供部分的需求。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 3.3.模型的求解模型的求解 集合覆盖模型是NP困难问题，当规模较小时，可设计枚举法或隐枚举法（如分支定界法等）。但在实际问题中，存在需求点数n和可供选择的候选点数m较大的情况（也可能n=m），这时需要设计近似算法来对模型进行求解。下面给出一个最少点覆盖的启发式算法，该算法是最常用也是最简单的一个近似算法，主要步骤如下：第一步：初始化。第一步：初始化。令所有的y00，xj0，（已分配的需求），并确定集合A(j)和集合B(i)；资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值35 第二步：选择下一个设施点。第二步：选择下一个设施点。在M中选择xj0，且A(j)的模为最大的点j为设施点，即 ，令 ，并在M集合中剔除节点j，即 。第三步：确定节点第三步：确定节点j的覆盖范围。的覆盖范围。将A(j)中的元素按B(i)的规模从小到大的顺序指派给j，直至j的容量为Dj0或A(j)为空。其中对于iA(j)且，yi1，将i指派给j的方法为：若 ，则令yij1yi，DjDjdi(1yi)，yi1，在A(j)和N中剔除需求点i。若 ，则令 第四步：若N或M为空，停止；否则，更新集合A(j)和集合B(i)，转第二步。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值3617849256322434143233211 图26 小区居民点位置图例例24 在某区域需规划建设若干个农贸市场为将来该区9个主要居民点提供服务，除第6居民点外，其他各点均有建设市场的条件，如图26所示。已知市场的最大服务直径为3km，为保护该区域的环境，希望尽可能少地建造农贸市场。问应如何规划？解：N1,2,3,4,5,6,7,8,9，M1,2,3,4,5,7,8,9，由图26两点间的最短距离，根据最大服务半径为3km的约束及第6居民点不适合建市场的要求，可确定集合A(j)和B(i)。如表23所示，值得指出的是本问题没有需求量和容量，故无需考虑约束式（27）。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值37居民点号居民点号A(j)B(i)11,2,3,41,2,3,421,2,31,2,331,2,3,4,51,2,3,4,541,3,4,5,6,71,3,4,5,753,4,5,63,4,564,5,7,874,6,7,84,7,886,7,8,97,8,998,98,9表23 候选点服务范围 因为A(4)=1,3,4,5,6,7，|A(4)|=6为最大，故首先选取j4。由于无容量约束故依次指派5,7,1,6,3,4点归节点4服务。此时，N2,8,9,M1,2,3,5,7,8,9,更新集合A(j)和集合B(i)后如表24所示。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值38居民点号居民点号A(j)B(i)12222324567888,98,998,98,9表24 候选点服务范围 因为A(8)8,9，|A(8)|2为最大，故首先选取j8，并且8，9两点归节点8服务。同理，再迭代一次，得j2，居民点2归节点2服务。因此，计算结果为（4,8,2）。本例最优解（3,8）资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值39l最大覆盖模型最大覆盖模型 1.1.问题问题 已知若干个需求点（客户）的位置和需求量，需从一组候选的地点中 选择p个位置作为物流设施网点（如配送中心、仓库等），使得尽可能 多地满足需求点的服务。最大覆盖模型的目标是对有限的服务网点进行选址，为尽可能多的对象 提供服务，如图2-7所示。图2-7 最大覆盖模型资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值40 2.2.建立模型建立模型 设：N区域中的需求点（客户）集合，N1,2,n；M区域中可建设设施的候选点集合，M1,2,m；di第i个需求点的需求量；Dj若第j个候选点选中时，该设施点的服务能力；p允许建设的设施的数目；A(j)设施节点j所覆盖的需求点i的集合；B(i)可以覆盖需求节点i的设施节点j的集合；1 在j点建立设施；jM xjxj 0 否则。yij节点需求i中被分配给设施点j的部分。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值412.2.建立模型建立模型 则数学模型可以表示为：（28）（29）（210）（211）式（2-8）表示最大可能地为需求提供服务；式（2-9）是需求的限制，服务不可能大于当前的总和；式（2-10）是对每个服务网点的服务功能的限制；式（2-11）是问题本身的限制，最多可能投建设施的数量为P。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值l集合覆盖模型与最大覆盖模型数学模型比较集合覆盖模型与最大覆盖模型数学模型比较集合覆盖模型集合覆盖模型最大覆盖模型最大覆盖模型p集合覆盖是满足所有的需求点；p最大覆盖模型只覆盖有限的需求点；p两种模型的应用情况取决于设施资源是否充足。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值43 3.3.模型的求解模型的求解 同样可以设计近似算法进行求解，最常用的方法是Richard Church和 Charles Re Velle设计的贪婪算法，该算法是一个空集合作为原始的解集合，然后在剩下的所有的其他候选点中选择一个具有最大满足能力的候选点加 入到原来的候选集合中。如上往复，直到到了设施数目的限制或者全部的 需求都得到满足为止。集合覆盖模型要满足所有的需求点，而最大覆盖模型则只覆盖有限的需 求点，两种模型的应用情况取决于设施的资源充足与否。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值442.2.线性规划模型线性规划模型 解决物流网络设计中的大型、复杂的选址问题。解决物流网络设计中的大型、复杂的选址问题。目标规划法；目标规划法；树形搜索法；树形搜索法；动态规划法及其他方法。动态规划法及其他方法。当前最有前景的方法是混合当前最有前景的方法是混合整数线性规划法（整数线性规划法（p p中值法），中值法），是商业选址模型中最受欢迎的方法，是商业选址模型中最受欢迎的方法，主要优点是能够把固主要优点是能够把固定成本以最优的方式考虑进去定成本以最优的方式考虑进去，但其代价也是很大的，除，但其代价也是很大的，除非利用个别问题的特殊属性，一般求解计算量很大。非利用个别问题的特殊属性，一般求解计算量很大。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值P-中值法中值法数学建模数学建模例例2-5 从多个候选的地点中选择若干个位置作为物流设施网点从多个候选的地点中选择若干个位置作为物流设施网点（如仓库配送中心、仓库等），使得从已知若干个资源点（如（如仓库配送中心、仓库等），使得从已知若干个资源点（如工厂），经过这几个设施网点（配送中心、工厂），经过这几个设施网点（配送中心、仓库等），向若干仓库等），向若干个客户运送多种产品时，总的运输成本为最小。个客户运送多种产品时，总的运输成本为最小。问题特点：问题特点：1.候选点、供应地及供应能力、需求及需求量已知；候选点、供应地及供应能力、需求及需求量已知；2.归属运筹学中的混合归属运筹学中的混合整数规划，又称整数规划，又称P-中值法。中值法。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值P-中值法中值法数学建模数学建模解:不妨设物流设施均为物流仓库h-产品（1,2,p）；i-工厂（1,2.,q）；j-仓库（1,2.,r）；k客户（1,2.s）；从工厂i到仓库j运送产品h的单位运费 从仓库j到客户k运送产品h的单位运费 从工厂i经过仓库j向客户k运送产品h的数量资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值P-中值法中值法数学建模数学建模 在仓库j期间的平均固定管理费 在仓库j中为保管产品h而产生的部分可变费用（管理费、保管费、税金以及投资的利息等）；资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值p中值法中值法数学建模数学建模资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值p中值法中值法数学建模数学建模资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值p中值法中值法数学建模数学建模这是一种利用混合-整数规划的选址方法，又称P-中值法，该方法通过协调点来确定需求和供给点的位置。在给定数量和位置的需求集合和一个候选设施位置的集合下，分别为P个设施找到合适的位置，并指派每个需求点到一个特定的设施，使设施与需求点之间的运输费用最低。一般适用于工厂、仓库或配送中心的选址问题。资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值p中值法中值法数学建模数学建模图2.8说明了P=3的P-中值模型的一个可行解。物流设施可以是物流园区、物流中心、配送中心、工厂、