第6章多设施选址问题

1、第第6章章 多设施选址问题多设施选址问题主要内容 一、概论 二、折线距离多设施MINISUM选址问题 三、最小费用流方法 四、平方欧几里得距离多设施MINISUM选址问题 五、欧几里得距离多设施MINISUM选址问题 六、选址-分配问题一、概论一、概论一、概论 例6.1 设p1=(5,25),p2=(25,15),p3=(10,0),p4=(0,10).新设施1和已有设施1、3、4有运输关系，新设施2和已有设施2、3有运输关系，欧几里得距离多设施MINISUM选址问题的最优解是多少？折线距离问题的最优解是多少？一、概论 答：欧几里得距离 X*1=(8.8388,5.7922) X*2=(9.1

2、645,5.6370) f(X*1, X*2)=59.7402 折线距离： X*1=X*2=(10,10) f(X*1, X*2)=70一、概论 设P1,一般距离（欧几里得距离、折线距离、 Tchebychev距离）为： Tchebychev距离是：用表格表示多设施选址问题的数据图论的相关概念 顶点邻接：两个顶点有一条边连接 道路： 连通图：若图的两顶点之间存在一条道路，则称此两顶点是连通的。若图的任意两顶点连通，则称图G是连通的；否则是非连通的。非连通图可分解为若干连通子图。根据图论分解原问题 构建G(V,W)图，看其是否为连图，若为非连通图，则原问题可分解为几个单一设施选址问题。 在G(V

3、,W)图中去掉所有的已有设施点和与之相关的连线，构建G(V)图，看其是否为连图，若为非连通图，则原问题可分解为几个单一设施选址问题。一、概论 例6.2 已有设施： 混凝土（10，20） 钢材加工场（7，6） 发货场（13，0） 待定位设施： 电杆浇铸场(X1) 安装储存场(X2) 生产定额为每天40根。输入数据 每天计划销售40根电线杆 需要的原材料：10立方码混凝土，8400磅钢材 已有设施的坐标： 混凝土（10，20） 钢材加工场（7，6） 发货场（13，0）阴影部分表示待定位设施不能放入该区域用表格表示该选址问题的数据二、折线距离多设施MINISUM选址问题二、折线距离多设施MINISU

4、M选址问题 用变量替换解此问题。设rji为xj在ai右边的位移量，sji为xj在ai左边的位移量，则有：引入变量：pjk,表示xj位于xk左边的偏移量， pjk,表示xj位于xk左边的偏移量，（6.10)被替换为一个线性规划问题：二、折线距离多设施MINISUM选址问题 例6.3 设n=2,m=3, p1=(10,15), p2=(20,25), p3=(40,5), 数据见表6.2。建立线性规划模型，求解：二、折线距离多设施MINISUM选址问题 最优解为(x*,15),10 x*20,即X1和X2重合，且为10到20之间的任意值。 最优值为160+60=220。二、折线距离多设施MINIS

5、UM选址问题 NF和EF点重合时，可选附近点。如令： X1=(19,15),X2=(21,15),得f(X1, X2)=222.二、折线距离多设施MINISUM选址问题 Intersection point property: 过所有已定位点画水平线和垂直线得一些交点，则有：至少存在一个最优解其中每一个新设施都落在某一交点上。二、折线距离多设施MINISUM选址问题坐标下降法:省略x1x2项，运用两次中值条件，得(x1,x2)的解。固定X2，变化X1，运用中值条件得X1的解固定X1，变化X2，运用中值条件得X2的解再到第2步，往复循环，直到得到两个相同的(x1,x2)的解，且X1，X2不相同。

6、如果X1，X2相同，则不能判断(x1,x2)是否为最优解，用列举法判断交点中哪个为最优二、折线距离多设施MINISUM选址问题 下面用例说明坐标下降法。 例6.4 设p1=(0,2),p2=(4,0),p3=(6,8),p4=(10,4)。数据见表6.3.二、折线距离多设施MINISUM选址问题 省略6x1x2项，运用两次中值条件，得(x1,x2)=(0,6),f1(0,6)=66.开始点就是(0,6)，固定X26，X1为变量，最小化： 得x1 =4， f1(4,6)=50，固定X14，X2为变量，最小化： 得x2 =6， f1(4,6)=50。因为第二次得到同一点(4,6)，算法停止。二、折

7、线距离多设施MINISUM选址问题 因为46，我们已最小化f1。再最小化f2,开始点为(2,8)， f2 (2,8) =66，固定Y28，变化Y1，最小化： 得y1=2, f2 (2,8) =66。固定Y12，变化Y2，最小化： 得y2 =4， f2 (2,4) =54。最小化：二、折线距离多设施MINISUM选址问题 得y1=2，再一次得f2 (2,4) =54，停止。 我们得到最优解：X*1=(4,2)，X*2=(6,4)， 最优值是50+54=104。二、折线距离多设施MINISUM选址问题 例6.5 设m=2, p1=(0,0),p2=(4,4),数据见表6.4。 我们有：二、折线距离

8、多设施MINISUM选址问题 开始点为(4,0)， f1(4,0)=88，最小化： 得x1=0,结果为（0，0），接下来最小化： 得x2=0, 结果为（0，0），f1(0,0)=24. 停止。但0=0，不能确定是否得到最优解。 通过枚举各交点的横坐标组合，函数值f1(0,0)=24， f1(4,0)=88， f1(0,4)=52， f1(4,4)=36，得(0,0)是最优解。二、折线距离多设施MINISUM选址问题 再最小化f2,开始点为(4,4)， f2 (4,4) =36，最小化： 得y1=4，最小化： 得y2=4，停止。但4=4，不能确定是否得到最优解。 通过枚举各交点函数值f2(0,0

9、)=24， f2(4,0)=88， f2(0,4)=52， f2(4,4)=36，得(0,0)是最优解。二、折线距离多设施MINISUM选址问题练习：练习：工厂内部有五台机器，位置分别为：P1=(8,20), P2=(10,10), P3=(16,30), P4=(30,10), P5=(40,20).有两台新的机器待安装。工厂内部走折线距离。根据估计，两台新机器之间每天会有4趟往返的物料搬运。新机器和已有机器之间每天的往返物料搬运次数如下：求新机器的最优放置位置。86543W23467三、最小费用网络流方法 在x方向移动的总成本是： 采用变量替换得线性规划：minimize三、最小费用流方法

10、 构造此线性规划的对偶问题得一最小费用流问题。该问题构造方法如下：三、最小费用流方法5.n+1等于矩阵W中所有值的和。定义节点Nn+1为终点，需求为n+1,用有向弧连接节点Ei和Nn+1，容量为无穷大，费用为ai. 容易验证：设n=2,m=3, p1=(10,15), p2=(20,25), p3=(40,5), 数据见表6.2。三、最小费用流方法三、最小费用流方法 设z*为最小费用流的最优值，f1*为x方向的移动最小值，则有：三、最小费用流方法 采用对偶算法,设j为节点Nj的势,计算： 则xj*为新设施j的最优地址的x坐标。 要计算y坐标只需将上面的a替换成b,x换成y，f1换成f2。设z(

11、Nj,Nk)为(Nj,Nk)弧上的最优流， z(Nj,Ei)为(Nj,Ei)弧上的最优流，则互补松弛条件如下：现重新计算例6.3。设n=2,m=3, p1=(10,15), p2=(20,25), p3=(40,5), 数据见表6.2。三、最小费用流方法三、最小费用流方法 这里 a=106+201+405=280。网络构造见图6.4。容易验证：z*=1012=120,而a=280，所以： f1*=280-120=160,此为在x方向移动的最小费用。 上述算法可采用表格形式。三、最小费用流方法 由互补松弛条件知x1*=x2*=x*,所以 由中值条件知10 x*20. 第二种方法: 由互补松弛条件

12、得10 x1*=x2*20,同样可得10 x*20。可直接计算得到f1(x1*,x2*)=160. 第三种方法：用最小费用流算出各节点N1、N2、N3的标号分别为0,0,-10,由(6.13)式得：x1*=0-(-10)=10, x2*= 0-(-10)=10.三、最小费用流方法 下面计算y值。 考虑y方向，如何作出网络图？三、最小费用流方法 由图6.4可得最小费用为50+30=80。如何得出？ 所以，在y方向移动的总费用为140-80=60。140是什么的值？三、最小费用流方法 由互补松弛条件得： y1*=b1=15.，y1*=y2*. 检验计算得：f2(15,15)=60. 结果正确。 还

13、可用最小费用流算出各节点N1、N2、N3的标号分别为0,0,-15,由(6.13)式得：y1*=0-(-15)=15, y2*= 0-(-15)=10.四、平方欧几里得距离多设施MINISUM选址问题 把 (6.6)式各项分别用下面项代替： 得平方欧几里得距离多设施MINISUM选址问题f2(X1, ,Xn).它是严格凸函数，令各项偏导数为零得最优解。关于NF t的项为：由于由于Vtj=Vjt,进而得到：进而得到：求偏导：令偏导等于零： 定义矩阵A，它的第t行的各项(除了第t项,即对角线上的元素)为-1乘以V的第t行，第t项等于V的第t行的和加上W的第t行的和。则对所有t都有： 所以，偏导数等

14、于零等同于下面的线性方程： 用此式解例6.1数据问题如下：用表格表示多设施选址问题的数据525100a得到：得到：把把A, Wa, Wb放在一起得到（放在一起得到（A|Wa|Wb），然后），然后进行矩阵变换得到：进行矩阵变换得到：得到：得到：五、欧几里得距离多设施MINISUM选址问题 把 (6.6)式各项分别用下面项代替： 得欧几里得距离多设施MINISUM选址问题HAP。定义下面的式子：则：则：迭代过程：迭代过程：Weiszfeld算法： 求得初始解的坐标 作为候选点坐标 求下一组候选点的坐标 比较前后两个候选点横坐标，若折线距离在允许的精度范围内，则结束计算。否则，转到上一步。(0)(0

15、)(0)12(,.,)nXXX(1)(1)(1)12(,.,)nXXX六、选址-分配问题 如果各新设施的类型都相同，同样，所有已定位设施类型都相同，且每一新设施都可服务任一已定位设施，则权重和新设施的地址一样是决策变量。这类问题称为选址-分配问题。六、选址-分配问题例6.7 设新设施1至7的坐标分别为(0,5),(8,5),(5,4),(2,2,),(3,2),(0,0),和(7,0)，要求每个已定位设施由离它最近的新设施提供服务，使各设施间折线距离最小化。该问题有两方面要求：一是新设施选址；二是分配新设施给已定位设施。用启发式算法解此问题。过程见图6.7。六、选址-分配问题用启发式算法解此问

16、题：给定新设施的坐标把已有设施分配给最近的新设施。对2步确定的分配，变动新设施坐标(把新设施坐标作为自变量)，使新设施和分配给该设施的已有设施之间的距离最小。如果得到的新设施坐标变化，则回到步骤2，否则回到步骤1。重复步骤1至4直到没有总的新设施到已有设施距离的减少为止。过程见图6.7。给定新设施坐标：X1(0,5); X2=(2,2). 分配结果为：A1(P1,P2); A2=(P3,P4,P5,P6,P7)距离为：T18；T217保持分配结果不变：A1(P1,P2); A2=(P3,P4,P5,P6,P7)变动新设施坐标：X1(0,5); X2=(3,2). 距离为：T18；T216变动后

17、新设施坐标：X1(0,5); X2=(3,2). 变动前新设施坐标：X1(0,5); X2=(2,2). 因为X1坐标没变，所以重新给X1赋值(3,5)分配结果为：A1(P1,P2,P3); A2=(P4,P5,P6,P7)距离为：T111；T212保持分配结果不变：A1(P1,P2,P3); A2=(P4,P5,P6,P7)变动新设施坐标：X1(5,5); X2=(3,2). 距离为：T19；T212六、选址-分配问题 实际上，初始点的选取对最终结果影响很大。如果令X1=(2,2),X2=(7,4),A1=P1,P4,P5,P6, A2=P2,P3,P7,则T1=9,T2=8,T=17。 所

18、以要尝试多个不同的初始点。六、选址-分配问题 浅海钻井平台问题：平台平台油井油井油井油井油井油井六、选址-分配问题 浅海钻井平台问题： 钻探和完成成本与钻探角度和钻探长度有关 平台成本：25万至1000万美元。与平台所在地的水深和分配到该平台的井的数目有关 目的是确定平台的数目，大小和井到平台的分配，以最小化总成本。六、选址-分配问题 浅海钻井平台问题：目标函数:最小化平台的建设成本，和钻探成本约束1：每个油井只分配到一个平台上约束2：每个平台分配的油井数目一定六、选址-分配问题 其中：平台与油井之间的水平距离：六、选址-分配问题用alternative-location-allocation(ALA)启发式算法解此问题：给定新设施的坐标把已有设施分配给最近的新设施。对1步确定的分配，变动新设施坐标，使新设施和分配给该设施的已有设施之间的距离最小。如果得