第4章单一设施选址问题.ppt

1、第4章 单一设施选址问题,主要内容,一、概论 二、单一设施MINISUM选址问题 三、多目标选址问题 四、单一设施MINIMAX选址问题 五、结论,一、概论,1、设施选址模型的特点 2、单一设施选址模型实例 3、单一设施选址模型,1设施选址模型的特点,“quick and dirty” Quick:容易使用，求解迅速。 Dirty:近似值,2单一设施选址模型实例,在制造车间放置一台新的机器 这台机器从已有的机器接受加工工件，且为已有的机器提供加工工件 从此机器到已有的机器有物料搬运成本，由该机器的放置位置决定 决定如何放置这台机器，使总的物料搬运成本最小。,2单一设施选址模型实例,X新的待定位

2、设施物体 Pi已存在且位置固定的物体 ti单位时间物料搬运的数量 vi搬运速度 ci单位时间单位距离搬运成本,两台机器间单位时间的物料搬运成本 (citi/vi)d(X,Pi),权重,代布置的机器和已有机器之间的物料搬运成本,3单一设施选址模型定理,权重为给定的正常数 多数定理：当某一已定位设施的权重占全体权重的多数时，该设施的坐标即为待定位新设施的最优解。 该定理对所有距离lp都成立。,钉板示例： 孔：已有的设施 结：新设施 板面上的绳：新设施到已有设施之间的距离 板面下的重物：每个已有设施的权重 假如把节点拉起，然后释放，等整个系统达到平衡时，节点的位置就是新设施的最优位置。 如果各重物的

3、重量相等，那么该例等同于最小化新设施和已有设施之间总的运输距离的问题。,凸函数的最优取值区间 （convex hull),3单一设施选址模型定理,欧几里得距离的局限 欧几里得距离的作用 人们最熟悉的距离 对实际距离的一种合理近似表示 两点之间直线最短，是实际距离的下界,二、单一设施MINISUM选址问题,1折线距离MINISUM选址问题 2 .欧几里得距离MINISUM选址问题 （简介） 3.欧几里得距离MINISUM选址问题（理论）,1折线距离MINISUM选址问题,折线距离（直角距离。矩形距离，曼哈顿距离）：,1折线距离MINISUM选址问题,折线距离的“圆”是以定点为中心的菱形。,1折线

4、距离MINISUM选址问题,设新设施位置表示为：X=(x,y),已有设施位置表示为Pi=(ai,bi)，我们得到以下方程： 定义f1(x)和f2(x): 则：,1折线距离MINISUM选址问题,原最优问题分解成完全独立的问题，即分别对x坐标和y坐标求解。 f1(x)和f2(x)形式完全一样。只需对x坐标求解。即原问题转化为直线上的选址问题。,1折线距离MINISUM选址问题,我们用案例说明直线上的选址问题的求解方法-中值选址方法 例 4.1 设某仓库要建一条开始点坐标为（0，5），终点坐标设为（x，5）平行于x轴的传送线。货物在传送线终点通过分拣分别运送四个站台p1=(7,10),p2=(15

5、,7),p3=(15,3),p4=(12,0),传送线单位长成本为￥180，传送线终点到四个站台的运送成本分别为￥160，￥40，￥60，￥140，求x使总成本最小。,1折线距离MINISUM选址问题,1折线距离MINISUM选址问题,已定位点有5个，m=5，权重分别为160，40，60，140，180。 在y方向成本为常数：,在坐标图上表示该函数,1折线距离MINISUM选址问题,对 7x12,1折线距离MINISUM选址问题,每个区间x的系数等于x 左边所有已定位点的权重之和减去x 右边所有已定位点的权重之和。,除第一个以外，每个区间线段的斜率等于前一区间的斜率加上两倍两区间公共点的权重的

6、和。,图中看出，当斜率由负变正时，函数取得最优值。至少有一最优解的x坐标值等于某一已定位设施的x坐标值。,1折线距离MINISUM选址问题,设所有已定位点的权重之和为W。另一求最优点的方法是从左到右计算各点权重的部分和。当在某一点权重部分和第一次达到或超过W/2时，该点即是最优点。此方法称为中值选址方法。 W=180+160+140+100=580 第一段：权重为180 W/2, 最优值在第二段开始取得,1折线距离MINISUM选址问题,F1(x)是凸函数，所以斜率由负变正时的局部极值点就是函数的全局最优解。,1折线距离MINISUM选址问题,例 4.2 设m=4,p1=(4,2),p2=(8

7、,5),p3=(11,8),p4=(13,2),权重分别为1，2，2，1，“规范化” 后，权重分别为1/6，1/3，1/3，1/6。（见表4. 2) 最优点x=(8,5). X=(11,5)也是最优点，这两点间线段上的所有点都是最优点。,1折线距离MINISUM选址问题,等值线（水平线）：该线上每一点的函数值都相等。 等值集（水平集）：边界是一条等值线，所有点函数值都不大于等值线上的函数值。 为什么需要等值线？因为有些最优点不可用，如已有别的设施，那么邻近的地点也可以,1折线距离MINISUM选址问题,等值线的构造方法：,分解后的函数：,考虑一个封闭的区域：4x8, 2y5 用x表示 y 因此

8、在此区域内，等值线的斜率为2,1折线距离MINISUM选址问题,等值线在每个框B的斜率等于底边缘x的系数与左边缘y的系数的负比值。 如果y系数等于0,x系数不等于零，等值线是一条垂直线。 如果x y系数都等于零,则框内每一点都是最优点，没有任何等值线通过此框。,等值线作法,1. 通过已有设施点的坐标，作横纵竖线,等值线作法,2. 对每条横纵竖线上的点的权重求和，且把该权重和写在该线的下方,等值线作法,3. 纵线把x轴分成几段，计算每一段的系数，并写在每一段的下方 横线把y轴分成几段，计算每一段的系数,并写在每一段的左方 系数等于每一段左边竖线的权重和减去每一段右边竖线的权重和,等值线作法,3.

9、系数等于每一段左边竖线的权重和减去每一段右边竖线的权重和,等值线作法,4. 计算每一封闭区域内的等值线斜率，负的底部系数/左边系数,等值线作法,5. 通过某一候选点，作等值线,等值线作法,6. 找出最优点（应用中值定理）,技巧： 横纵线相交，生成一系列交叉点 最优点为某一交叉点,2 .欧几里得距离MINISUM选址问题,例4.3 在例4. 1中，设传送线终点x=(x,y)为一“发散”点，开始点p1=(0,5),两个站台p2=(15,7),p3=(15,2).传送线单位长成本为￥30，传送线终点到两个站台的运送成本为￥20，求x使总成本最小。,1折线距离MINISUM选址问题,2 .欧几里得距离

10、MINISUM选址问题,这里,要求最小值，就要对x,y分别求偏导数，然后令其等于零,2 .欧几里得距离MINISUM选址问题,设 则可定义变换WF为： 令偏导数等于零，得到 (x, y)=WF(x, y),2 .欧几里得距离MINISUM选址问题,Weiszfeld算法： 1）任选一点（x,y)； 2）计算i(x,y), i=1, ,m. 3）计算(x,y). 4）计算i(x,y), i=1, ,m. 5）用(ai,bi)乘以4)项的积的和即得变换WF(x,y). 实例见表4. 6,Weiszfeld算法： 求得初始解的坐标(x,y)，作为候选点坐标 求下一个候选点的坐标(x,y) = WF(

11、x,y). 比较前后两个候选点坐标，若距离在允许的精度范围内，则结束计算。否则，转到上一步。,3.欧几里得距离MINISUM选址问题（理论）,对于此函数来说，,因为下列函数为凸函数,所以 为凸函数,所以可令 的偏导数等于零,定义偏导数向量：,则：,可用偏导数向量表示,令偏导数向量等于零,令,X*为已有点的质心,因此对 来说，其解就为已有点组成的平面的质心。,假如有一个点 Y 当YPi,可用(4.2)式检验Y是否为最优解；如果（4.2)式成立，则为最优解 若Y等于某一Pk,则定义k为该点到以下向量的欧几里得距离： 若Y=Pk是最优解， 则k应小于该点的权重,3.欧几里得距离MINISUM选址问题

12、（理论）,Weiszfeld算法迭代到第k步得Xk,可计算f(X*) 的下界：,3.欧几里得距离MINISUM选址问题（理论）,三、多目标选址问题,1.欧几里得距离多目标选址问题 2.折线距离多目标选址问题,1.欧几里得距离多目标选址问题,例 两座城市又高速公路相连，现要建一机场两城市共用。要使两城市使用都方便，机场应建在那里？,1.欧几里得距离多目标选址问题,这个问题首先应该确定那些地点不在考虑之列。 不靠近高速公路的那些地点是受控点。 非受控点称为有效点。,1.欧几里得距离多目标选址问题,定义：设a=(a1, ,am)T,b=(b1, ,bm)T是m维向量。 若ai=bi(I=1, ,m)

13、, 则称向量a等于b，记作a=b. 若aibi(I=1, ,m), 并且其中至少有一个是严格不等式，则称向量a小于b，记作ab.,1.欧几里得距离多目标选址问题,设平面上有已定位点P1, ,Pm,D(X)为m维向量，其中分量I为待定位点x和Pi的欧几里得距离，则由P1, ,Pm构成的凸包是有效点集，凸包外的所有点都是受控点。,2.折线距离多目标选址问题,把欧几里得距离替换成折线距离上节问题就是折线距离多目标选址问题。有效解的定义同上。 折线距离MINISUM选址问题的最优解一定是其有效解。 本节问题的有效解通过调整权重可以得到某个折线距离MINISUM选址问题的最优解。 不管权重如何分布，有效

14、解集合E包含折线距离MINISUM选址问题的所有最优解。,2.折线距离多目标选址问题,零框：四个方向 均被占用 一框：只有一个方向没有被占用 二框：有两个方向没有被占用,2.折线距离多目标选址问题,求解有效解集合E的指针（arrow)算法: 设P1, ,Pm不在一条直线上，如图定义零框、1框和2框（null box,1-box and 2-box). 找出一个1框，画出指针，沿着指针所指的方向，找到leading edge. 删掉非leading edge. 找出下一个1框，同上操作，直到没有1框为止。 E最终由零框、2框和连接零框和2框的连接线构成,四 、单一设施MINIMAX选址问题,1.

15、单一设施MINIMAX选址问题概论 2.圆覆盖问题 3.折线距离单一设施MINIMAX选址问题 4.Tchebychev距离单一设施MINIMAX选址问题,1.单一设施MINIMAX选址问题概论,单一设施MINIMAX选址问题和圆覆盖问题 菱形覆盖问题 覆盖问题的意义,圆覆盖问题的定义： 等价形式：,2.圆覆盖问题,圆覆盖问题的算法： 圆覆盖问题的算法基于“两点plus”算法和 “四点”算法。 该算法每次由两个或三个已定位点确定一个圆，算法严格保证新圆的半径比前一个圆的大，而m 点中选两个或三个点的组合数是有限的，必定某一步得到的圆包括所有的点。该圆既是最优解。,2.圆覆盖问题,2.圆覆盖问题

16、,例 9个已定位点p1至p9,坐标分别是 (0.0,1.75),(5.75,3.5),(6.75,8.00),(8.50,1.50),(8.00,0.75),(3.50,9.75),(9.50,8.50),(9.00,0.50），和（5.25，1.00）。,2.圆覆盖问题,新设施到已定位点的欧几里得距离为： (XPi)T(XPi) 圆覆盖问题为： minimize u s.t (XPi)T(XPi) u, I=1, ,m 因为(XPi)T(XPi)XTX2PiTXPiTPi 令,2.圆覆盖问题,这是一个二次规划问题，可以已有的二次规划算法求解,问题是极小函数： 其中，hi是常量，根据实际问题，

17、可有不同解释。如(x,y)表示救护车的车站，需要走hi才能到达医院。,3.折线距离单一设施MINIMAX选址问题,上式要求所有点(ai,bi)都在以点(x,y)为中心(zhi) wi为半径的菱形内。 如所有wi1, hi0则问题记为UP. 如hi不全为零，wi为权重则问题记为 WPA.,3.折线距离单一设施MINIMAX选址问题,例 用几何作图法解菱形覆盖UP问题。图4.19中，已知点是（9，13），（9，18），（10，7），（14，15），（15，15），（16，6）。 所求菱形是以线段（10.5，10）和(13.5,13)上的点 为中心9.5为半径的所有菱形。,3.折线距离单一设施MIN

18、IMAX选址问题,UPA问题解法： 上式等价于下面四个不等式： xaiybiri xaiybiri xaiybiri xaiybiri,3.折线距离单一设施MINIMAX选址问题,菱形的中心坐标范围：,菱形的半径：C5/2,对于给定的几个点，求中心点，使其到各点的最大折线距离不大于Z 问题转化为：任意给定的菱形半径Z，在坐标图上作出其形状 即作出该问题的等值线,因为： 检验不等式是否成立： 若不成立，重新选择z的值。 若成立，计算菱形中心点的坐标范围,计算菱形四个顶点的坐标：,由菱形四个顶点的坐标，可容易的求得中心点的坐标,4.Tchebychev距离单一设施MINIMAX选址问题,Tcheb

19、ychev距离t(X,Y)的定义：,Tchebychev距离的等值集合:t(X,0)1,x,y,比较折线距离和Tchebychev距离的等值集合,x,y,x,y,比较折线距离的等值集合,Tchebychev距离的等值集合,为研究Tchebychev距离和折线距离的关系，定义线性变换Q(x,y): 定义逆变换Q-1(u,v):,4.Tchebychev距离单一设施MINIMAX选址问题,4.Tchebychev距离单一设施MINIMAX选址问题,平面上有点X,Y,设X=Q(X),Y=Q(Y), 原平面两点间的折线距离等于变换后两点间的Tchebychev距离，反之亦然。,现解图4.19所示的菱形

20、覆盖问题，经过变换Q，原平面上的已定位点(9,13),(9,18),(10,7),(14,15),(15,15),(16,6)分别变换成(22,4),(27,9),(17,-3),(29,1),(30,0),(22,-10),见图4.21。,4.Tchebychev距离单一设施MINIMAX选址问题,折线距离选址问题WPA：,(x, y)经过坐标变换Q后得(u, v), (a, b)经过坐标变换Q后得(,),定义：,所以，极小化二元函数g(x,y)变成分别极小化两个一元函数： 1.minimize g1(u),得最优解u*; 2.minimize g2(v),得最优解v*; 3.对(u*,v*)进行逆变换,得(x*,y*) ,为g(x,y)最优解； 4. g(x,y)的最小值就是max g1(u*) , g2(v*) ,4.Tchebychev距离单一设施MINIMAX选址问题,如果pqhr,则u*=r, g1(u*)=hr;否则，选择p和q之间的u*满足：,求解以上一元函数的一般步骤,计算： 计算： 计算：,1=ij=m,例 设已定位点1至3的坐标分别为（5，0），（5，10）和（10，10）；加数分别为0，12和0；权重分别为2，1和2。 应用变换Q得点(5,-5),(15.5)和(20,0)，则有：,4.Tchebychev距离单一设施MINIM