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