软容量约束的带惩罚的设施选址博弈-论文.pdf

文档介绍：肉 怔 年．第期
软容 量 约 束 酌 带惩 罚的 设 施 选 址博 弈
◇武警 学院基 础部 姜春艳 段 耀 勇 陈 广雷 高 岩 刘丽 芳 苏国强
本 文主要研 究软容量 约束的带惩 罚的设施选 址博 弈，每 个用户提供服 务。 的线性松弛的对偶为 ：
一 个设施 都是有容量 约柬 ，而且每 一个用 户或者有开放 的设
篇；
施 为其服 务或者 接 受惩 罚。 我们 改进 了传 统 的 费用分 摊 方 ． 一一，，∈
法 ，给出 了一种满足单调 性 、竞争性和一近 似成本补偿 的 费
“∑屈， ，∈，
用 分 摊 方 法 。
， ≤ ，，∈，
，” ，∈，∈．
设施选址 问题是一类具有 重要研究价值的问题 ，对设施选
址 问题的研 究能推动很多领域 的发展 。尽管对 设施选址的研究 令：丢， ’孚，可以化简为：
起源于军事问题 ，但在现代化 的诸 多领域如网络 、信息流 、资 ∑
源配置等方面都有广泛重要的应 用。通常我们的 目的是最小化
．． 一，∈，