顾客为子树结构的树上半厌恶型2-中位问题  

Semi-obnoxious Weighted 2-median Problem on Tree Graph with Subtree-shaped Customers

作　　者：柏春松[1] 姚云飞[1] 王茂华[1] 

机构地区：[1]阜阳师范学院数学学院,安徽阜阳236037

出　　处：《运筹与管理》2012年第5期119-122,共4页Operations Research and Management Science

基　　金：国家教育部财政部资助国家特色专业(TS11496)

摘　　要：树上半厌恶型加权中位问题是确定一个设施集合,使得目标函数最小的问题。这类问题有两个不同的目标函数:一个是最小化所有顾客到达设施集合的最小加权距离之和,另一个是最小化所有顾客到达设施集合的加权最小距离之和。对于第二个目标函数,本文研究了顾客为子树结构树图上半厌恶型加权2-中位问题,当2-中位限制在顶点上时,我们给出了一个时间复杂度为O(mn3)的多项式时间精确算法,其中n和m分别表示树图的顶点数和边数。The semi-obnoxious weighted median problem is to find a set of facilities such that the value of certain objective function is minimized.In this case we have two different objective functions： minimizing the sum of the minimum weighted distances from the set of facilities to all customers and minimizing the sum of the weighted minimum distances.In this paper we consider the semz-obnoxious weighted 2-median problem for the latter function in a tree with n vertices and m edges.If the 2-median is restricted to vertices then we devise a polynomial time algorithm with complexity of O（mn3）.

关 键 词：运筹学 选址问题 中位问题 半厌恶型 子树结构顾客 

分 类 号：O224[理学—运筹学与控制论]