第6章多设施选址问题.ppt

第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.1645,5.6370) f(X*1, X*2)=59.7402 折线距离： X*1=X*2=(10,10) f(X*1, X*2)=70 一、概论 设P≥1,一般距离（欧几里得距离、折线距离、 Tchebychev距离）为： Tchebychev距离是： 图论的相关概念 顶点邻接：两个顶点有一条边连接 道路： 连通图：若图的两顶点之间存在一条道路，则称此两顶点是连通的。若图的任意两顶点连通，则称图G是连通的；否则是非连通的。非连通图可分解为若干连通子图。 根据图论分解原问题 构建G(V,W)图，看其是否为连图，若为非连通图，则原问题可分解为几个单一设施选址问题。 在G(V,W)图中去掉所有的已有设施点和与之相关的连线，构建G(V)图，看其是否为连图，若为非连通图，则原问题可分解为几个单一设施选址问题。 一、概论 例6.2 已有设施： 混凝土（10，20） 钢材加工场（7，6） 发货场（13，0） 待定位设施： 电杆浇铸场(X1) 安装储存场(X2) 生产定额为每天40根。 输入数据 每天计划销售40根电线杆 需要的原材料：10立方码混凝土，8400磅钢材 已有设施的坐标： 混凝土（10，20） 钢材加工场（7，6） 发货场（13，0） 二、折线距离多设施MINISUM选址问题 二、折线距离多设施MINISUM选址问题 用变量替换解此问题。设rji为xj在ai右边的位移量，sji为xj在ai左边的位移量，则有： 二、折线距离多设施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。 二、折线距离多设施MINISUM选址问题 NF和EF点重合时，可选附近点。如令： X1=(19,15),X2=(21,15),得f(X1, X2)=222. 二、折线距离多设施MINISUM选址问题 Intersection point property: 过所有已定位点画水平线和垂直线得一些交点，则有：至少存在一个最优解其中每一个新设施都落在某一交点上。 二、折线距离多设施MINISUM选址问题 坐标下降法: 省略︱x1－x2︱项，运用两次中值条件，得(x1,x2)的解。 固定X2，变化X1，运用中值条件得X1的解 固定X1，变化X2，运用中值条件得X2的解 再到第2步，往复循环，直到得到两个相同的(x1,x2)的解，且X1，X2不相同。 如果X1，X2相同，则不能判断(x1,x2)是否为最优解，用列举法判断交点中哪个为最优 二、折线距离多设施MINISUM选址问题 下面用例说明坐标下降法。 例6.4 设p1=(0,2),p2=(4,0),p3=(6,8),p4=(10,4)。数据见表6.3. 二、折线距离多设施MINISUM选址问题 省略6︱x1－x2︱项，运用两次中值条件，得(x1,x2)=(0,6),f1(0,6)=66.开始点就是(0,6)，固定X2＝6，X1为变量，最小化： 得x1 =4， f1(4,6)=50，固定X1＝4，X2为变量，最小化： 得x2 =6， f1(4,6)=50。因为第二次得到同一点(4,6)，算法停止。 二、折线距离多设施MINISUM选址问题 因为4≠6，我们已最小化f1。再最小化f2,开始点为(2,8)， f2 (2,8) =66，固定Y2＝8，变化Y1，最小化： 得y1=2, f2 (2,8) =66。固定Y1＝2，变化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。 二、折线距离多设施MI