第3章选址模型及应用ppt课件

.,在x方向：左右：,.,例1报刊亭选址一个报刊连锁公司想在一个地区开设一个新的报刊零售点主要的服务对象是附近的5个住宿小区的居民，他们是新开设报刊零售点的主要顾客源。图26苗卡儿坐标系中确切地表达了这些需求点的位置，表21是各个需求点对应的权重。这里，权重代表每个月潜在的顾客需求总量，基本可以用每个小区中的总的居民数量来近似。经理希望通过这些信息来确定一个合适的报刊零售点的位置，要求每个月顾客到报刊零售点所行走的距离总和为最小。,.,.,右左：在y方向：上下：下上：故ys=3最优解为直线AB(A=(3,3),B=(4,3),.,比较A，B两个位置的加权距离,AB根据实际情况，可选A，B之间的任何一点。,.,课堂练习,P58习题1回答：交叉中值模型的最优解为点，还是直线或者其他形状？就像本例中说明的，如果在y方向也是一个范围，那么整个可能的选择范围就是一个区域；如果在x方向也是一个点、那么可选的地点就只有一个点了。利用交叉中值的方法可以为决策提供更多的选择和灵活性。,.,2精确重心法,距离：直线距离类型：单一设施选址问题问题：寻求加权的直线距离的最小化。适用：平面大范围的选址，无受限制直线。,.,其中：各参数和变量的含义同交叉中值模型。,求解：,可得：,.,只能用迭代的方法对上式求近似解。,迭代公式：,其中：,.,应用上述迭代公式，可采用逐步逼近算法求得最优解。,步骤：选取初始迭代点A（xs0,ys0），计算dis0和Z0；,.,令,计算,.,若，或满足其他任一终止准则，则输出最优解（Xs,Ys）、Z及迭代次数j，结束。Xs=Xs(j-1),Ys=Ys(j-1),Z=Zj-1否则，转。,.,终止准则：（1）当，则输出（Xs,Ys）、Z及迭代次数j，结束。否则，继续迭代。（2）取，,若,则迭代过程结束，输出（Xs,Ys）,Z和迭代次数j。否则，继续迭代。,.,（3）根据经验和以前的试验结果，设置迭代次数N；若jN,则输出（Xs,Ys）和Z，结束。否则，继续迭代。例1：若取Xso=3Yso=3，则,.,则,Xs=3，Ys=3,.,由精确重心法得到的最优解只有一个点，由交叉中值法和精确重心法得到的最优解一般不一致。,注：,.,例2：某企业有两个工厂P1，P2生产A,B两种产品，供应三个市场M1,M2,M3，已知条件如表，现在需要设立一个中转仓库。问：应设在何处？,.,P1,C,M1,M2,M3,P2,.,X0，Y0的求法重心法,.,求解初始解,求得X0,Y0,.,求总成本,.,迭代求最优解,.,精确重心法小结,1.由精确重心法得到的最优解只有一个点，由交叉中值法和精确重心法得到的最优解一般不一致。2.若工厂到设施的运费包含在成本中，则可将工厂视为一个客户点xi。3.若直线距离与实际距离有差异，可用一定的修正数来修正差异。,.,5.2离散点选址模型,目标选址区域是一个离散的候选位置的集合。1.覆盖模型问题：对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。在该模型中，需要确定服务设施的最小数量和合适位置。适用范围：商业物流系统：零售点，加油站或配送中心等的选址。公用事业系统：急救中心，预防中心等的选址。计算机与通信系统：有线电视网的基站，无线通信网络基站，计算机网络中的集线器设置等。,.,1）集合覆盖模型问题:已知需求点的位置、需求量以及候选点的位置,求满足各需求点的服务需求的条件下,使所需建的设施数目最小。目标：用最小数量的设施去覆盖所有的需求点。,.,模型：,S.t,假设N需求点的集合，N=1，2，n；M可建设施的候选点集合，M=1，2，m；di第i个需求点的需求量；cj设施节点j的容量；A(j)设施点j能覆盖的需求点i的集合；B(i)可以覆盖需求点i的设施点j的集合；yij需求点i由设施点j提供服务的部分。,.,求解：精确算法：规模较小时可用分枝定界求解法（整数规划中的一个重要解法）求模型的最优解，但运算量很大近似算法：实际中，n和m一般较大（也可能n=m），故需设计近似算法来求解。如启发式方法，所得到的结果不能保证是最优解，但可以保证是可行解。,.,集合覆盖启发式算法步骤：确定A(j),B(i),简化问题。若，则省去A(j),即忽略j,作后选，M=M-j,最后得M*确定合适的组合解。例2乡村医疗诊所选址问题如P38图210，9个村希望在每一个村周边30KM内至少有一个诊所，不考虑诊所服务能力的限制。除第6村外，其他村均可作为候选点。,.,例2乡村医疗诊所选址问题卫生部门考虑到农村地区的医疗条件的落后和匮乏，计划在某一个地区的9个村增加一系列诊所以改善该地区的医疗卫生水平。它希望在每一个村周边30km的范围之内至少有一个诊所，不考虑诊所服务能力的限制。卫生部门需要确定至少需要多少个诊所和它们相应的位置。除了第6个村之外，其他任何一个村都可以作为诊所的候选地点，原因是在第6村缺乏建立诊所的必要条件。图210是各个村之间的相对位置和距离的地图。第一步，找到每一个村可以提供服务的所有村的集合A(j)，即它们距该村距离小于或等于30km的所有村的集合。例如从1村开始，2、3和4村到1村的距离都小于30km，这样它们都可以由1村的诊所提供服务，得到集合A(1)11，2，3，4；然后逐一地进行考虑计算，就可以得到所有的A(J),J1，9，并将所得结果垣入表26中。第二步，找到可以给每一个村提供服务的所有村的集合B(i)。一船说来，这两个集合是一致，但是考虑到其他的一些限制条件，就可能出现差异。例如本例中，6村由于本身条件所限不可能建立诊所，所以也不可能给别人提供相应的医疗服务。考虑7村，B(7)24，7，81。相应地将其他的结果垣入到表26中，得到进行选择评价的基本信息。,.,.,解：求A(j),B(i),.,简化问题若,则省去A(j)，即忽略在j村建，其提供的可能服务范围已含在k村的范围。M*3,4,7,8,确定合适的组合解。可行解：（3，4，7，8）、（3，4，8）、（3，8）最优解：（3，8）（3，4，7，8）中，2唯一A（3），9唯一A（8），且A（3）A（8）覆盖全部需求点。,.,2最大覆盖模型问题：已知需求点的位置和需求量，候选点的位置和所建设施的数量，选择P个设施位置，尽可能地满足各需求点的服务要求。目标：为固定数量的设施选址，尽可能多地满足需求点的服务要求。,.,模型,其中：NN=1，2，n，需求点集；MM=1，2，m，可建设施的候选点集；di需求点i的需求量；Cj设施点j的相应容量；A(j)设施点j能覆盖的需求点i的集合；B(i)可以覆盖需求点i的设施点j的集合；p允许投建的设施数目；yij需求点i中由设施点j提供服务的部分。,.,模型的求解贪婪算法（近似算法）设解为,若,若,否则，转,.,例2建医疗站问题,仍不考虑服务能力的限制，允许投建的设施数为P2。,解：S=,由前得,注：第2个需求点没被覆盖。,.,2P中值模型,问题：已知数量和位置的需求集合，候选设施位置集合，分别为p个设施选址，并指派每一需求点到一个特定的设施，使设施和需求点之间的总运输费用最低。目标：为p个设施选址并确定各设施的服务对象，设总运费最少。,.,建立模型,S.t,其中，N，M，di，P,xj同前Cij-从点i到点j的单位运输费用,和覆盖模型有什么不同？,.,模型的求解,求解P中值模型需解决两方面问题：选择合适设施位置（Xj变量）指派客户到相应的设施中去（yij变量）,求解方法：精确计算法：（只能求解规模较小的P中值问题）启发式算法贪婪取走启发式算法,.,例3某饮料公司的仓库选址问题（P41）解:(1)令K4，A=(a1,a8)=(1,1,1,4,4,2,3,3),(2)k=3时若删1：则（a1,a2,a8）=(4,2,2,4,4,2,3,3)Z=3200,Z=3200-2480=720若删2：（a1,a2,a8）=（1,1,1,4,4,3,3,3）Z=2620Z=140若删3：（a1,a2,a8）=（1,1,1,4,4,2,4,2）Z=3620Z=1140若删4：（a1,a2,a8）=（1,1,1,2,3,2,3,3）Z=3520Z=1040选择删去2,则(a1,a2,a8）=（1,1,1,4,4,3,3,3）Z=2620,.,例3某饮料公司的仓库选址问题某饮料公司在某新地区经过一段时间的宣传广告后，得到了8个超市的定单，由于该新地区离总部较远，该公司拟在该地区新建2个仓库，用最低的运输成本来满足该地区的需求。经过一段时间的实地考查之后，已有4个候选地址。从候选地址到不同的仓库的运输成本、各个超市的需求量都已经确定，如图212所示。这里我们介绍一种启发式求解P一中值模型的算法贪婪取走启发式算法(GKcdyDI叩PE吧HeurzsticAl80rit比)o这种算法的基本步骤如下：第一步，韧始化，令循环参数Am将所有的m个候选位置都选中，然后将每个客户指派给离其距离最近的一个候选位置。第二步，选择并取定一个位置点，满足以下条件：假如将它取走并将它酌客户重新指派后，总费用增加量最小。然后令k,k=k-1,.,.,(3)k=2时若删1：则（a1,a2,a8）=(4,4,4,4,4,3,3,3)Z=4540,Z=4540-2620=1920若删3：（a1,a2,a8）=（1,1,1,4,4,4,4,4）Z=5110Z=2490若删4：（a1,a2,a8）=（1,1,1,1,3,3,3,3）Z=3740Z=1120选择删去4,则(a1,a2,a8）=（1,1,1,1,3,3,3,3）Z=3740k=2=p,故计算结束，应在候选位置1,3投建新的仓库,总运输成本为3740。,.,贪婪取走启发式算法步骤令当前选中设施点数K=m；将各客户指派给（k个设施中）离其最近的设施点，求出总运费Z；令kk1，即从k个候选点中确定一个取走点，该点必须满足条件：若将它取走并将它的客户重新指派后，使总运费增加量最小。若k=p