摘要
本文主要考虑如下实际问题:假设选址决策者需要建设p个设施,但是由于资金等等的影响,实际建设时会被要求先建设q个设施,其次再建设p-q个设施(设p>q),同时要求,在建设p-q个设施的时候,已经建设好的q个设施不被删除。本文建立了一个两阶段优化问题,问题的输出是两个待修建的设施的集合Fq,Fp,|Fp|=p,|Fq|=q,且Fq是Fp的子集,问题的目标是最小化这两个设施集合的费用同对应的最优费用的比值的最大值。本文给出一个近似比为9的近似算法,并对一些特殊的情况进行了讨论。所得结论对实际的选址决策具有理论意义,同时也完善已有相关研究结果。
This paper mainly focuses on the following practical problem, assuming one wants to construct p facilities, but for the limited money or other reasons, the practical constructing process firstly establishes q facilities, then establishes p-q facilities （let p〉q）. At the same time, the constructed q facilities can not be removed when the new p-q facilities are established. This paper constructs a two-period optimization problem, whose output is two facilities sets Fq, Fp, such that ｜Fp｜=P, ｜Fq｜=q and Fq is a subset of Fp. The object of the problem is to minimize the maximum ratio between the facility cost and its respectively optimal cost. It presents an approximation algorithm, whose approximation ratio is 9, and also analyses some special cases for this problem. The obtained results not only have a theoretical meaning for the practical facility location, but also improve the existing results.
出处
《运筹与管理》
CSCD
2007年第6期47-50,共4页
Operations Research and Management Science
基金
国家自然科学基金资助项目(10371094
70471035)
国家杰出青年基金资助项目(70525004)
关键词
运筹学
选址
中心
算法
近似比
operational research
facility location
median
algorithm
approximation ratio
