K种产品容量有限设施选址问题

摘要

在k种产品容量有限设施选址问题中，我们事先给出一个用户点的集合，每一个用户的需求已知。我们要从可能建厂的地点中选出一些开设工厂并供应每一个用户，且每一个用户需要用k个不同的工厂来供应k种不同的产品。每一个工厂在每一个位置都有一个事先给定的正的建厂费用，还有两个位置之间的运输费用也是已知的，我们假设地点与地点之间的距离是非负的并且满足三角不等式。问题的目标是找到一个指派满足每一个用户的需求且其运费和建厂费用之和最小。我们从一个单产品容量有限的设施选址问题的近似比为5的算法入手，将其改动并运用到我们的k种产品容量有限的设施选址问题上，这个算法需要用到模型的原问题和对偶问题的最优解并随机选取工厂序列开设，最终我们证明这个算法在k种产品的模型上也可以得到一个近似比为5的结果。

目录

摘要

1．引言

1．1 背景与动机

1．2 问题的提出

1．3 选址问题研究现状

1．4 总体的结构

2 k种产品容量有限选址问题

2．1 k种产品容量有限选址问题模型介绍

2．2 解的改造

2．3 建厂模型的近似算法

2．4 算法的性能比分析

3 对于算法所得解的分析和改进

4 结束语

参考文献

致谢

声明