多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
例 3-6
第二步
➢取走候选点2，使得ΔZ=140为最
小
➢所以，第一个被取走的是候选点2
➢候选位置：k=4-1=3
➢指派结果：(1,1,1,4,4,3,3,3)
➢总费用1 ：Z=2620
4 600 5
400
8 24 12 6 22 100
多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
例 3-6
第二步 ➢分别对取走候选点1,2,3,4进行分析 ，并计算各自的费用增量：
✓取走候选点4，结果(1,1,1,2,3,2,3,3)， Z=3520，费用增量ΔZ=1040
1 2 100
1
400
4
4
5
7 120
1 4 12 20 6 100
2 2 10 25 10 50
3 3 4 16 14 120
i
4 6 5 9 2 80 5 18 12 7 3 200
6 14 2 4 9 70
7 20 30 2 11 60
8 24 12 6 22 100
多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
例 3-6
第一步
多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
P-中值模型
贪婪取走算法
第一步
• 令当前选中设 施点数k=m， 即所有m个候 选位置都选中
第二步
• 将每个需求点 指派给k个设施 点中离其距离 最近的一个设 施点。
• 求出总运输费 用Z
第三步
• 若k=p，得到k 个设施点及各 需求点的指派 结果，停止
➢初始化，令k=m=4；
➢将每个客户指派给运输成本最低
的一个候选位置，指派结果为：
A=(a1, a2, … a8)=(1,1,1,4,4,2,3,3)；
8
➢总费用 Z ciai di 2480
1
i1
4 600 5
2 100
400
160 4
7 120
1
3
600
360
2 140 6
3
8
c ij
1
j 23
4 di
1 4 12 20 6 100
2 2 10 25 10 50
3 3 4 16 14 120
i
4 6 9 70
7 20 30 2 11 60
8 24 12 6 22 100
多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
例 3-6
单，由于该地区离总部较远，公司拟在该地区新建2个仓库，用最低的配
送成本来满足该地区的需求。经过一段时间的实地考察之后，已有4个候
选地址，如下图所示。从候选地址到各个超市运输成本cij、各超市的需求
量di都已经确定，如下表所示。试选择其中的两个候选点作为仓库地址，
使总运输成本最小。
c ij
1
j
23
4 di
公式 3-23
多设施选址模型
集合覆盖模型 最大覆盖模型 P-中值模型
P-中值模型
模型求解
求解一个P-中值模型需要解决两方面问题： ✓选择合适的设施位置（x变量） ✓指派需求点到相应的设施中去（y变量）
与覆盖模型相似，求解P-中值模型主要有两大 类方法，即精确计算法和启发式算法。常用的求解 P-中值模型的启发式算法被称为：贪婪取走启发式 算法。
多设施选址模型
集合覆盖模型 最大覆盖模型 P-中值模型
P-中值模型
问题描述
在一个给定数量和位置的需求集合和一个候 选设施位置的集合下，确定p个设施的位置，并指 派每个需求点到一个特定的设施，使之达到设施 和需求点之间的运输费用最低。
多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
P-中值模型
模型建立
✓取走候选点2，结果(1,1,1,4,4,3,3,3)， Z=2620，费用增量ΔZ=140
1 2 100
1
3
360
400
4 600 5
160
7
4
120
3
600
280
2
6
8
c ij
1
j 23
4 di
1 4 12 20 6 100
2 2 10 25 10 50
3 3 4 16 14 120
i
4 6 5 9 2 80 5 18 12 7 3 200
2 2 10 25 10 50
3 3 4 16 14 120
i
4 6 5 9 2 80 5 18 12 7 3 200
6 14 2 4 9 70
7 20 30 2 11 60
8 24 12 6 22 100
多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
例 3-6
第二步 ➢分别对取走候选点1,2,3,4进行分析 ，并计算各自的费用增量：
6 14 2 4 9 70
7 20 30 2 11 60
8 24 12 6 22 100
多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
例 3-6
第二步 ➢分别对取走候选点1,2,3,4进行分析 ，并计算各自的费用增量：
✓取走候选点3，结果(1,1,1,4,4,2,4,2)， Z=3620，费用增量ΔZ=1140
3
600 1400
400
360
2 140 6
3
8
c ij
1
j 23
4 di
1 4 12 20 6 100
2 2 10 25 10 50
3 3 4 16 14 120
i
4 6 5 9 2 80 5 18 12 7 3 200
6 14 2 4 9 70
7 20 30 2 11 60
8 24 12 6 22 100
第二步 ➢分别对取走候选点1,2,3,4进行分析 ，并计算各自的费用增量：
✓取走候选点1，结果(4,2,2,4,4,2,3,3)， Z=3200，费用增量ΔZ=720
1
600
4 600 5
160
7
2
4
120
5100
3
600
3 480 2 140 6
8
c ij
1
j 23
4 di
1 4 12 20 6 100
1 2 100
1
400
4
160
600
5 660
7
4
3
360
2 140 61200
3
8
c ij
1
j 23
4 di
1 4 12 20 6 100
2 2 10 25 10 50
3 3 4 16 14 120
i
4 6 5 9 2 80 5 18 12 7 3 200
6 14 2 4 9 70
7 20 30 2 11 60
• 否则，转第四 步
第四步
• 从k个候选点中 确定一个取走点 ，满足：若将它 取走并将它的需 求点指派给其它 最近设施后，总 费用增加量最小
• 从候选集合中删 去取走点，令 k=k-1，转第二步
多设施选址模型
集合覆盖模型
最大覆盖模型
P-中值模型
例 3-6
P-中值模型
某公司在一新地区经过一段时间的宣传广告后，得到了8个超市的订