多设施选址问题第6节.pdf

第6章多设施选址问题 1 华中科技大学管理学院 主要内容 • 一、概论 • 二、折线距离多设施MINISUM选址问题 • 三、最小费用流方法 • 四、平方欧几里得距离多设施MINISUM选 址问题 • 五、欧几里得距离多设施MINISUM选址问 题 • 六、选址-分配问题 2 华中科技大学管理学院 一、概论 3 华中科技大学管理学院 一、概论 4 华中科技大学管理学院 一、概论 • 例6.1 设 p =(5,25),p =(25,15),p =(10,0),p =(0,10). 1 2 3 4 新设施1和已有设施1、3、4有运输关系， 新设施2和已有设施2、3有运输关系，欧几 里得距离多设施MINISUM选址问题的最优 解是多少？折线距离问题的最优解是多 少？ 5 华中科技大学管理学院 一、概论 • 答：欧几里得距离 • X*1=(8.8388,5.7922) • X*2=(9.1645,5.6370) • f(X* , X* )=59.7402 1 2 • 折线距离： • X* =X* =(10,10) 1 2 • f(X* , X* )=70 1 2 6 华中科技大学管理学院 一、概论 • 设P≥1,一般距离（欧几里得距离、折线距 离、Tchebychev距离）为： • Tchebychev距离是： 7 华中科技大学管理学院 8 华中科技大学管理学院 用表格表示多设施选址问题的数据 9 华中科技大学管理学院 10 华中科技大学管理学院 图论的相关概念 • 顶点邻接：两个顶点有一条边连接 • 道路： • 连通图：若图的两顶点之间存在一条道 路，则称此两顶点是连通的。若图的任意 两顶点连通，则称图G是连通的；否则是非 连通的。非连通图可分解为若干连通子图。 11 华中科技大学管理学院 根据图论分解原问题 • 构建G(V,W)图，看其是否为连图，若为非