- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1
400
2 100
1
480
4
360
2
3
600 1400
4
5
7
120
3
280
6
8
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
1 2 100
1
3
360
400
4 600 5
160
7
4
120
3
600
280
2
6
8
1 2 100
1
400
4 600 5
160
7
4
120
3
600
360
2 140 6
3
c ij
j 123
1 4 12 20
2 2 10 25
3 3 4 16
i
46 5 9 5 18 12 7
6 14 2 4
7 20 30 2
多设施选址模型
集合覆盖模型 最大覆盖模型
P-中值模型
P-中值模型
p问题描述
n 在一个给定数量和位置的需求集合和一个候选设施 位置的集合下，确定p个设施的位置，并指派每个需求 点到一个特定的设施，使之达到设施和需求点之间的运 输费用最低。
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
P-中值模型
1
4
5
c ij
1
j
23
4 di
1 4 12 20 6 100
2
4
1
7
3
i
2 2 10 25 10 50 3 3 4 16 14 120 4 6 5 9 2 80 5 18 12 7 3 200
2
6
3
8
6 14 2 7 20 30
4 9 70 2 11 60
8 24 12 6 22 100
集合覆盖模型
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
例 3-6
n第二步 Ø分别对取走候选点1,2,3,4进行分析， 并计算各自的费用增量：
ü取走候选点3，结果(1,1,1,4,4,2,4,2)， Z=3620，费用增量ΔZ=1140
1 2 100
1
400
4
160
600
5 660
7
4
3
360
2 140 61200
2 80 3 200 9 70 11 60 22 100
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
例 3-6
n第二步 Ø取走候选点2，使得ΔZ=140为最小 Ø所以，第一个被取走的是候选点2 Ø候选位置：k=4-1=3 Ø指派结果：(1,1,1,4,4,3,3,3) Ø总费用：Z=2620
多设施选址模型
最大覆盖模型
P-中值模型
例 3-6
n第一步 Ø初始化，令k=m=4； Ø将每个客户指派给运输成本最低的一 个候选位置，指派结果为：
A=(a1, a2, … a8)=(1,1,1,4,4,2,3,3)；
Ø总费用
1
2 100
1
400
8
Z ciaidi 2480 i1 4 600 5 160 4
n模型建立
min
d i c ij y ij
i N j M
公式 3-23
s .t . y ij 1， i N j M
y ij
x
，
j
i
N
,
j
M
x j p j M
x j { 0 ,1}， j M
y ij { 0 ,1}， i N ， j M
6 14 2 4 9 70
7 20 30 2 11 60
8 24 12 6 22 100
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
例 3-6
n第三步 Ø分别对取走候选点1,3,4进行分析，并 计算各自的费用增量：
ü取走候选点3，结果(1,1,1,4,4,4,4,4)， Z=5110，费用增量ΔZ=2490
3
8
1 2 100
1
400
4 600 5
160
7
4
120
3
600
360
2 140 6
3
c ij
j 123
1 4 12 20
2 2 10 25
3 3 4 16
i
46 5 9 5 18 12 7
6 14 2 4
7 20 30 2
8 24 12 6
8
4 di
6 100 10 50 14 120
2 80 3 200 9 70 11 60 22 100
8
1 2 100
1
400
4 600 5
160
7
4
120
3
600
360
2 140 6
3
c ij
j 123
1 4 12 20
2 2 10 25
3 3 4 16
i
46 5 9 5 18 12 7
6 14 2 4
7 20 30 2
8 24 12 6
8
4 di
6 100 10 50 14 120
2 80 3 200 9 70 11 60 22 100
6 14 2 4 9 70
7 20 30 2 11 60
8 24 12 6 22 100
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
例 3-6
n第四步 Ø∵k=2=p Ø∴计算结束，得到2个设施点及各客户 的指派结果：
ü 在候选位置1,3建设新仓库 ü 指派结果：(1,1,1,1,3,3,3,3) ü 总运输费用：Z=3740
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
P-中值模型
p贪婪取走算法
第一步
• 令当前选中设 施点数k=m， 即所有m个候 选位置都选中
第二步
• 将每个需求点 指派给k个设施 点中离其距离 最近的一个设 施点。
• 求出总运输费 用Z
第三步
• 若k=p，得到k 个设施点及各 需求点的指派 结果，停止
8 24 12 6
8
4 di
6 100 10 50 14 120
2 80 3 200 9 70 11 60 22 100
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
例 3-6
n第三步 Ø分别பைடு நூலகம்取走候选点1,3,4进行分析，并 计算各自的费用增量：
ü取走候选点1，结果(4,4,4,4,4,3,3,3)， Z=4540，费用增量ΔZ=1920
2
6
8
1 2 100
1
400
4 600 5
160
7
4
120
3
600
360
2 140 6
3
c ij
j 123
1 4 12 20
2 2 10 25
3 3 4 16
i
46 5 9 5 18 12 7
6 14 2 4
7 20 30 2
8 24 12 6
8
4 di
6 100 10 50 14 120
2 80 3 200 9 70 11 60 22 100
1
600
4 600 5
500
160
7
2
4
120
1
3
1680
2
3
600
280
6
8
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
6 14 2 4 9 70
7 20 30 2 11 60
8 24 12 6 22 100
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
练习 3-3
P-中值模型
n 某公司在某地区有6个主要客户A1,A2,A3,A4,A5和A6，该公司拟在该地区新 建两个仓库，用最低的运输成本来满足该地区主要客户需求。经过一段时间的实 地考察之后，公司确定三个候选地址D1、D2和D3，如下图所示。从候选地址到 各客户运输成本、各客户的需求量都已经确定，如下表所示。试确定仓库位置。
6 14 2 4 9 70
7 20 30 2 11 60
8 24 12 6 22 100
集合覆盖模型
多设施选址模型
最大覆盖模型
P-中值模型
例 3-6
n第三步 Ø取走候选点4，使ΔZ=1120为最小 Ø所以，第二个被取走的是候选点4 Ø候选位置：k=3-1=2 Ø指派结果：(1,1,1,1,3,3,3,3) Ø总费用：Z=3740
