2.10.1 候选点服务范围 村落号
和可覆盖需求点 i 的设
1
1,2,3
1,2,3
2
1,2,4,5
1,2,4,5
3
1,3,41,3,442,3,4,6,7
2,3,4,6,7
5
2,5,6
2,5,6
6
4,5,6
4,5,6
7
4,7
4,7
因为 ={2,3,4,6,7}，| |=5 为最大，故首先 =4。因无容量约束，指派
主要的日常费用是他们员工完成任务过程中的运输费用。因此，用城
市距离进行考虑，要求新的办公室到各个合作伙伴之间运输的运输费
用最小。1）请确定一个新办公室的地址，用笛卡尔坐标来表达相应 结果。2）如果由于该地区的人口稀少，城市还没有达到一定的规模， 可以用欧几米德距离进行计算，新办公室又得在哪里投建?请比较两
2,3,4,6,7 归村落 4 服务。
此时 N={1,5}，M={1,2,3,5,6,7}；则更新候选点服务范围，见表 2.10.2。
2.10.2 更新后的候选点服务范围
精品文档
精品文档
村落号
1
1
1,2,3
2
1,5
3
1
4
5
5
2,5,6
6
5
7 因为 ={1,5}=N，恰好满足条件。则 =2。 综上所述，银行需要 2 台自动取款机，分别至于村落号为 2 和 4 的位置，2 号为 1,5 村落服务，4 号为 2,3,4,6,7 村落服务。
要点： 1. 明确 N，M， ， 含义； 2. 分析正确后， 可参照 直接写出，无需再看网络图； 3. 熟悉最少点覆盖启发式算法的步骤，考虑是否有容量约束。
解：【集合覆盖模型】
区域中需求点集合 N={1,2,3,4,5,6,7}； ATM 取款机设施候选点集合 M={1,2,3,4,5,6,7}； 由网络图确定候选设施点 j 可覆盖的需求点集合 施节点的集合 ，见表 2.10.1。
精品文档
精品文档
费用结果保留三位小数得最优解为 X=5.5767，y=4.010,H=13.456
1 n
n
x j , y0( 0 )
j 1
1 n
n j 1
yj
，即
精品文档
,仓库到各生产地的距离 。
精品文档
直线距离为 =
目标函数运输总费用 H=
，其中
根据下列进行迭代：
=，
，=
直到运费无法减小。
用 MATLAB 进行编码：
运行结果得，迭代 78 次得到最优解。 其中选址坐标为（5.6235,4.9918），最小运费为 H=13.4550。 或由 EXCEL 迭代得，结果如图
12.一台机器工具小制造商要迁址，并确定了两个地区以供选择。 A 地的年固定成本为 800000 元，可变成本为 14000 元/台；B 地的年 固定成本为 920000 元，可变成本为 13000 元/台。产品最后售价为 17000 元/台。
（1） 当产量为多少时，两地的总成本相等？ （2） 当产量处于什么范围时，A 地优于 B 地？当产量处于什么 范围时，B 地优于 A 地？
由
EXCEL
迭代得，结果如图
精品文档
精品文档
费用结果保留四位小数得最优解为 x=7.6257,y=7.6047,此时费用最小为 H=62.1020 （3）比较两次结果可知欧基米德中的费用小于笛卡尔距离，因直线距离是＜直 角距离，因此用欧基米德距离更为精确。直角距离比较适合于城区范围内的选址， 欧基米德距离比较适合于远距离的选址。
|
4
3
3
4
3
3
4
2
5
11
2
5
7
2
7
2
2
7
11
4
11
11
4
11
14
1
12
7
1
12
可得
为偶数，即 均在第六个、第七个点之间。 ，
（2）设初始点为（
）有题意得，阿基米德距离为
=
,
目标函数 H(运输总费用)=
,
利用不动点算法，取一个初始的迭代点（ , ）=(8,7),此时 =62.51
令=
,
,=
=
=62.14
11. —个临时帮助服务中心计划在一个大城市的郊外开设一个新
的办公室。在经过一定的精简之后，该公司有 5 个大的合作伙伴。在
一个以 km 为单位的笛卡尔坐标系中，它们的坐标分别为：(4，4)，
(4，11)，(7 ，2)，(11，11)， (14，7)。它们的服务需求量的权重分
别为：wl=3，w2=2，w3=2，w4=4，w5=1。对于该服务中心来说，
精品文档
第二章 设施选址
10.一家银行准备在某县的农村地区投放一批 ATM 自动取款机， 以方便农村的用户取款。该农村地区的村落座落情况和相对距离如图 2.13 所示。为了能确保任一村的人都可以在 20 分钟之内到达自动取 款机取款，银行需要多少台自动取款机？它们的位置又在哪里?
图 2.13 村落座落情况和相对距离
13．利用表 2.8 所示的因素评分，以最大综合得分为基础，建模 分析应选择地点 A、B、C 中的哪一个?
精品文档
精品文档
表 2.8 因素评分表
解：权重矩阵设为 W，则 三个位置的因素评分作为 3 行构成因素矩阵 S。
可得综合加权矩阵 E=S*W=
。
可知 E(A)> E(B)> E(C)。即选择 A 点。
次结果，分析它们之间的关系。
要点：1. 补充交叉中值模型知识点
精品文档
精品文档
关键句：将 n 点需求的选址问题转化为
精品文档
点需求的选址问题。
精品文档
2.笛卡尔距离即直角距离，欧基米德距离即直线距离； 3.重心法：初始化+迭代公式+Excel/C 编程/matlab 编程迭代+迭代终止条件 解：（1）设新办公室的地址的坐标为(x,y),给题目已知的 5 个点编号 1~5。 由于笛卡尔距离 =| - |+| - |。 则目标函数为时总运输距离 H 最短。
14.一个玩具制造商在全国的五个地区生产玩具，原材料将从一个
新的中心仓库运出，而此仓库的地点还有待确定。运至各地的原材料
数量相同，已建立一个坐标城，各地的坐标位置如表 2.9 所示。请确
定中心仓库的坐标位置。
表 2.9 各地的坐标位置
解：设仓库的坐标为（
为 ,因运至各地的原材料数量相同，故可设
初始解： x0( 0 )
解：答：设 x 为之制造商的年产量 A 地，总成本 C(A)=800000+14000x B 地，总成本 C(B)=920000+13000x
1)若两地成本相等，则 C(A)=C(B) 解得：x=120
2）若 A 地优于 B 地，则 C(A)<C(B),因此得 0<x<120 同理，当 x>120 时，B 地优于 A 地。