运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2010年
2期
23-36
,共14页
运筹学%选址问题%中位问题%可带负权%区间图
運籌學%選阯問題%中位問題%可帶負權%區間圖
운주학%선지문제%중위문제%가대부권%구간도
Operation research%location theory%median problem%semi-obnoxious facility%interval graph
本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题(P≥2)可分为两类:即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和,在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O(n2)的多项式时间算法.
本文研究瞭區間圖上可帶負權的2-中位選阯問題.根據目標函數的不同,可帶負權的p-中位選阯問題(P≥2)可分為兩類:即MWD和WMD模型;前者是所有頂點與服務該頂點的設施之間的最小權重距離之和,後者是所有頂點與相應設施之間的權重最小距離之和,在本篇論文中,我們討論瞭區間圖上可帶負權2-中位選阯問題的兩類模型,併分彆設計時間複雜度為O(n2)的多項式時間算法.
본문연구료구간도상가대부권적2-중위선지문제.근거목표함수적불동,가대부권적p-중위선지문제(P≥2)가분위량류:즉MWD화WMD모형;전자시소유정점여복무해정점적설시지간적최소권중거리지화,후자시소유정점여상응설시지간적권중최소거리지화,재본편논문중,아문토론료구간도상가대부권2-중위선지문제적량류모형,병분별설계시간복잡도위O(n2)적다항식시간산법.
This paper deals with the facility location problem on interval graphs with positive and negative interval weights.We consider two difierent objective functions:the sum of the minimum weighted distances (MWD) of the intervals from the facilities and the sum of the weighted minimum distances(WMD).Two O(n2)time algorithms for both models of the 2-median problem have been developed.
