第二章设施选址10.—家银行准备在某县的农村地区投放一批ATM自动取款机, 以方便农村的用户取款。

该农村地区的村落座落情况和相对距离如图所示。

为了能确保任一村的人都可以在20分钟之内到达自动取款机取款，银行需要多少台自动取款机它们的位置又在哪里图村落座落情况和相对距离要点：1.明确N, M, "I ,丨「含义;2. j.:.分析正确后，• i可参照“直接写出，无需再看网络图；3. 熟悉最少点覆盖启发式算法的步骤，考虑是否有容量约束。

解：【集合覆盖模型】区域中需求点集合N={1,2,3,4,5,6,7};ATM取款机设施候选点集合M={1,2,3,4,5,6,7};由网络图确定候选设施点j可覆盖的需求点集合」和可覆盖需求点i的设施节点的集合；，见表。

候选点服务范围因为.i | ={2,3,4,6,7},|「，|=5为最大，故首先’=4。

因无容量约束，指派2,3,4,6,7归村落4服务。

此时N={1,5}, M={1,2,3,5,6,7};则更新候选点服务范围，见表。

更新后的候选点服务范围因为A(2)={1,5}=N,恰好满足条件。

则亍=2。

综上所述，银行需要2台自动取款机，分别至于村落号为2和4的位置，2号为I, 5村落服务，4号为2,3,4,6,7村落服务。

II.—个临时帮助服务中心计划在一个大城市的郊外开设一个新的办公室。

在经过一定的精简之后，该公司有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•补充交叉中值模型知识点”对卜卜即|+卜卅卜亦卜咄 0-D如酗斥 已超爍宸將醐吋|狗«］翻財,蹣卜砧卜讣0F 卜檢 卜计+卜”卜卜朋巍眦就軽种.甥我0MSM 竝駆犯肿肝宜詞腔8謹枣H IM#|ii-i 2|+|ft-J工述原理可以推r 到多个需求u H ■的情形.洽定啼沪的坐标佝 小)訂七』2)、…“(鬲丿并八 确定设褲的坐标仗」)，便该点至所有给定点的怠折线鹿咼握耳吕标画数为*门工力-二片-站工卩」川3)r-l?-1求箏左法対下.将丑.习、■■"-亏进行排序.找出中间值.当“为奇数甘，则最忧的卫就等 于该中间值-岂”为儒拔时\记两个中冋直为可和无由’则最兄的X 为可艺兀二却+L ・洌如.迳定 竹，3). (14,5). (A 9)三个肖“悟X 燮标排序后為乩7. 14t 则最代的工坐标为丁・如果造定 (23? 4X (6? 2). (lb ilh (4, 25)也个点，将K 坐标排亭后为仏6、1K 23,则阮施最优盯 斗坐标^6<X<11*对于最优的y 坐标的确毘-与上述方法充全一样'*君恚条蘇査師物淀量葩不同，假设空求点汀勺物拭虽为吧，则目标函数为屮“乳刃网* -xj I 丫％仪-丹|3〕i-li-1如果粤为整数，则可以认为超标点(可・旳)处有嗎址需求，将H 縣磁的选址问題转换礒 三：們蕊迷的进址问愛然肆用前面的方法菠得设施的最优的坐标宜.如果嗎为小数，可耳 睚其处冬为整数形式*例如假段珥等于03我们可以取嗎=3,然后将目标函数编小1/10,这 样就可以延毎前而的方法求聚"|关键句：将n 点需求的选址问题转化为点需求的选址问题。

3.重心法：初始化+迭代公式+Excel/C编程/matlab编程迭代+迭代终止条件解：（1）设新办公室的地址的坐标为（x,y）,给题目已知的5个点编号1~5。

由于笛卡尔距离d；i=l兀-岸］1+1 v^yi l。

则目标函数为时总运输距离H最短。

H- S-^jWidj = *xi I + i|y-yi|Xi Wi Sws yi Wj Swi|433434251125727227 11411114M1 141127112工冋il：为偶数，即石均在第六个、第七个点之间可得x = 7, ” 丘|7J11C U -8U（2）设初始点为（•.■）有题意得，阿基米德距离为目标函数H（运输总费用）=r ,利用不动点算法，取一个初始的迭代点（曲|感'）=（8,7），此时H0 =令曲卜卩命（対-d + （网-yi）2匸，丄由EXCEL迭代得，结果如图ABC费用结果保留四位小数得最优解为x=,y=,此时费用最小为H=(3)比较两次结果可知欧基米德中的费用小于笛卡尔距离，因直线距离是v直角距离，因此用欧基米德距离更为精确。

直角距离比较适合于城区范围内的选址，欧基米德距离比较适合于远距离的选址。

12345673910113 ?.S51255 7.535267. 582447.592226 ?,S025627. 6109857, 6173947. 622157. 62565y7?.368S957.46S0757. 5344877. 5600377. 5750537. 5670337, 5948597. 6005257. 604652dl54.9680135.0006845. 0325415. 0574655. 0760825. 0897935. 0998585.1072255.112617d25. 6568545.1494255. 020133d35.099025. 40S255. 517205d454. 9395334. 399005d5 H6 62. 511756. 359449 62,136986. 43313 62.109034. 9843414・9736744. 9700974. 968664.967954. 9675344. 9672665. 565055. 5914885. S085165. S203425, 6288215. 634^765. 6394654. 367186L 8421354. 3234844. 3097554, 7996884. 7923174. 7869225.4397796.4322016. 4233216. 4159236, 4102666.40606氐40296362.1049362.1034662-10273S2.1023462,1021362.1020262-1019612•—台机器工具小制造商要迁址，并确定了两个地区以供选择。

A地的年固定成本为800000元，可变成本为14000元/台；B地的年固定成本为920000元，可变成本为13000元/台。

产品最后售价为17000 元/台。

(1)当产量为多少时，两地的总成本相等(2)当产量处于什么范围时，A地优于B地当产量处于什么范围时，B 地优于A地解：答：设x为之制造商的年产量A 地，总成本C(A)=800000+14000xB 地，总成本C(B)=920000+13000x1)若两地成本相等，则C(A)=C(B)解得：x=1202)若A地优于B地，贝U C(A)<C(B),因此得0<x<120同理，当x>120时，B地优于A地。

13.利用表所示的因素评分，以最大综合得分为基础，建模分析应选择地点A、B、C中的哪一个解：权重矩阵设为W，则W r= [0,15 070 0.18 0,27 0-10 0,101三个位置的因素评分作为3行构成因素矩阵S。

rgo 72 54(4 94 9S 961S= 7C 76 90 86 90 83.60 92 90 80 82 75j87.021可得综合加权矩阵E=S*W=X?S。

180.90J可知E(A)> E(B)> E(C)即选择A点。

14.一个玩具制造商在全国的五个地区生产玩具，原材料将从一个新的中心仓库运出，而此仓库的地点还有待确定。

运至各地的原材料数量相同，已建立一个坐标城，各地的坐标位置如表所示。

请确定中心仓库的坐标位置。

表各地的坐标位置料数量相同，故可设.■.1n1n初始解：x00)- X j,y00)- y j，即n j i n j -直线距离为h'-.<!i= iv 乩;；；靳「上『目标函数运输总费用H== 「‘T，其中|號- I - ■-5= = 13 6094根据下列进行迭代：曲"节斗，丫审=、〔斗，卅- Xi)2 + (y^ - Vi)2直到运费无法减小。

用MATLAB进行编码：cl«ai .clc a ，])=5 打⑴二46 4 4 91.y=(7 2 6 1 >1 . i*l. fQ L J« 1 B -tiudHH)=d [1)■*■(1(2^+d(3)+dKi^dtS 3 , t=E(i).r ¥hi：c H-L'Oll |H^i)=E(l)A-0 B —0 P C =0, foi j-i ；eC=CMi>/d(J}; end^Hfi];»A/B：b(U=C/B ：for j=]:5fb(il-yG)>"2)"0. E:H(i -d(l i+d ⑵+d ⑶七⑷彌箱]: tnd运行结果得，迭代78次得到最优解 其中选址坐标为(，)，最小运费为 或由EXCEL迭代得，结果如图AB C D E F G H1 X y dl d2 d3 d4 d5且 2 5 4 3. 605551 3. 605551 2. 236068 3.162278 1 13. 60945 3 5. 22169 4・ 3. 656192 玉 4S0405 比 262042 3. 323546 0. 784237 13. 51142 4 5. 328709 4. 083713 3.. 728067 3.. 390946 2.327765 3. 362382 CL 677127 13.48629 5 5.396846 4. 065729 3. 788775 3. 323198 2. 385913 3. 368957 0. 606725 13,47357 6 5.446264 047031 3. S3461 3. 272904 2. 430179 3. 372844 0. 555729 13.46627 7 5. 4S3617 4. 034095 3. 363455 3. 23569b 2. 462905 3. 377403 0. 517503 13.46197 8 5・ 5123 4・3. 893604 £ 207915 2. 487221 3. 382282 0. 488359 13.4593S 9 5. 5345544. 019364 3. 912564 3.186888 2. 505549 3.386948 0. 465849 13. 4578 10_5.551977 4. 015149 3. 927075 3.. 170748 2. 519576 3. 391129 0. 443279 13.45661 11 5.565728 4. 012107 3. 933333 3.. 158204 2. 530459 3. 394745 0. 434441 13. 4561812 5. 5766594. 00986 3. 947165 玉143352 2. 53B99B 3. 39781 0. 423455 13.45578费用结果保留三位小数得最优解为 X=，y=,H=15. 某物流公司拟建一仓库负责向四个工厂进行物料供应配送，各工 厂的具体位置与年物料配送量见表，设拟建物流公司仓库对各工厂的 单位运输成本相等。