规划计算题整理

第二章设施选址10.一家银行准备在某县的农村地区投放一批ATM自动取款机，以方便农村的用户取款。该农村地区的村落座落情况和相对距离如图2.13所示。为了能确保任一村的人都可以在20分钟之内到达自动取款机取款，银行需要多少台自动取款机？它们的位置又在哪里?图2.13村落座落情况和相对距离要点：1.明确N，M，𝐴(𝑗)，𝐵(𝑖)含义；2.𝐴(𝑗)分析正确后，𝐵(𝑖)可参照𝐴(𝑗)直接写出，无需再看网络图；3.熟悉最少点覆盖启发式算法的步骤，考虑是否有容量约束。解：【集合覆盖模型】区域中需求点集合N={1,2,3,4,5,6,7}；ATM取款机设施候选点集合M={1,2,3,4,5,6,7}；由网络图确定候选设施点j可覆盖的需求点集合𝐴(𝑗)和可覆盖需求点i的设施节点的集合𝐵(𝑖)，见表2.10.1。2.10.1候选点服务范围村落号𝑨(𝒋)𝑩(𝒊)11,2,31,2,321,2,4,51,2,4,531,3,41,3,442,3,4,6,72,3,4,6,752,5,62,5,664,5,64,5,674,74,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}；则更新候选点服务范围，见表2.10.2。2.10.2更新后的候选点服务范围村落号𝑨(𝒋)𝑩(𝒊)111,2,321,5314552,5,6657因为𝐴(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最短。𝐻=∑𝑤𝑖5𝑖=1𝑑𝑖=∑𝑤𝑖5𝑖=1|𝑥−𝑥𝑖|+∑𝑤𝑖5𝑖=1|𝑦−𝑦𝑖|xiwi∑wiyiwi∑wi43343342511257272271141111411141127112∑𝑤𝑖=12为偶数，即𝑥,𝑦均在第六个、第七个点之间。可得𝑥=7，𝑦∈[7,11]。H=81。（2）设初始点为（x0，y0）有题意得，阿基米德距离为di(0)=√(x0−xi)2+(y0−yi)2,目标函数H(运输总费用)=∑wi5i=1di,利用不动点算法，取一个初始的迭代点（x0(0),y0(0)）=(8,7),此时H0=62.51令x0(1)=∑wixidi5i=1∑xidi5i=1,y0(1)=∑wiyidi5i=1∑yidi5i=1,di(1)=√(x0(1)−xi)2+(y0(1)−yi)2H1=∑wi5i=1di(1)=62.14由EXCEL迭代得，结果如图费用结果保留四位小数得最优解为x=7.6257,y=7.6047,此时费用最小为H=62.1020（3）比较两次结果可知欧基米德中的费用小于笛卡尔距离，因直线距离是＜直角距离，因此用欧基米德距离更为精确。直角距离比较适合于城区范围内的选址，欧基米德距离比较适合于远距离的选址。12.一台机器工具小制造商要迁址，并确定了两个地区以供选择。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地，则C(A)C(B),因此得0x120同理，当x120时，B地优于A地。13．利用表2.8所示的因素评分，以最大综合得分为基础，建模分析应选择地点A、B、C中的哪一个?表2.8因素评分表解：权重矩阵设为W，则𝑊𝑇=[0,150.200.180.270.100.10]三个位置的因素评分作为3行构成因素矩阵S。𝑆=[807288949896707690869085609290808275]可得综合加权矩阵E=S*W=[87.0282.6280.90]。可知E(A)E(B)E(C)。即选择A点。14.一个玩具制造商在全国的五个地区生产玩具，原材料将从一个新的中心仓库运出，而此仓库的地点还有待确定。运至各地的原材料数量相同，已建立一个坐标城，各地的坐标位置如表2.9所示。请确定中心仓库的坐标位置。表2.9各地的坐标位置解：设仓库的坐标为（x0，y0)，五个生产地为(xi,yi),仓库到各生产地的距离为di,因运至各地的原材料数量相同，故可设wi=1(i=1,2,…5）;初始解：nn()()jjjjxx,yynn00001111，即𝑥0(0)=5，𝑦0(0)=4。直线距离为𝑑𝑖(0)=√(𝑥0−𝑥𝑖)2+(𝑦0−𝑦𝑖)2目标函数运输总费用H=∑wi5i=1di，其中wi=1(i=1,2,…5）𝐻(0)=∑𝑑𝑗5𝑗=1=13.6094根据下列进行迭代：x0(1)=∑xidi5i=1∑1di5i=1，y0(1)=∑yidi5i=1∑1di5i=1，di(1)=√(x0(1)−xi)2+(y0(1)−yi)2直到运费无法减小。用MATLAB进行编码：运行结果得，迭代78次得到最优解。其中选址坐标为（5.6235,4.9918），最小运费为H=13.4550。或由EXCEL迭代得，结果如图费用结果保留三位小数得最优解为X=5.5767，y=4.010,H=13.45615.某物流公司拟建一仓库负责向四个工厂进行物料供应配送，各工厂的具体位置与年物料配送量见表2.10，设拟建物流公司仓库对各工厂的单位运输成本相等。利用重心法计算确定物流公司的仓库坐标位置为多少。表2.10各工厂的具体位置与年物料配送量解：设仓库的坐标为（x0，y0)，4个工厂的坐标为(xi,yi),仓库到各生产地的距离为di=√(x0−xi)2+(y0−yi)2,目标函数运输总费用H=∑αi𝑐𝑖5i=1di=∑wi5i=1di，𝛼𝑖为工厂年配送量，𝑐𝑖为单位运输成本，因单位运输成本相等，故令𝑐𝑖=1，于是有w1=2000,w2=1200,w3=1000,w4=2500初始解x0=1n∑xi=37.5,y0=1n∑yi=42.5di(0)=√(x0−xi)2+(y0−yi)2,此时H0=192249.4令x0(1)=∑wixidi5i=1∑xidi5i=1,y0(1)=∑wiyidi5i=1∑yidi5i=1,di(1)=√(x0(1)−xi)2+(y0(1)−yi)2H1=∑wi5i=1di(1)=190400.4由EXCEL迭代得，结果如图结果保留整数得最优解为（42.22076，33.82437）,H=188709或用MATLAB进行编码（文件见附件）：运行结果得，迭代59次得到最优解。其中选址坐标为（42.2865,33.6732），最小运费为H=188707.914。16.筹建一农副产品流通加工厂，可供选择的候选厂址有D、E、F三处，因地址不同各厂加工成本亦有区别，各厂址每年费用如表2.7所示。此外，为决定厂址还考虑了一些重要的非成本因素，如当地竞争能力、气候变化和周围环境是否适合农副产品流通加工等。对于竞争能力而言，F地最强，D、E两地相平；就气候来说，D比E好，F地最好；至于环境，E地最优，其次为F地、D地。如果各主观因素的重要性指数a、b、c依次为0.6、0.3和0.1，要求用因次分析法评定最佳厂址在何处。表2.11各候选厂址每年加工成本费用要点：P中值法分5个步骤进行。解:（1）计算客观量度值OMi，[OMi=Ci∑1Ci]−1OMD=[523∗(1523+1525+1551)]−1=0.3395同理可得：OME=0.3382,OMF=0.3223。（2）计算主观评比值Sik（有3个不同的主观因素）①竞争能力（FD=E）注：D=E，比较记为0.5两两相比厂址FED比重SiaD00.50.50.167E00.50.50.167F1120.666②气候（FDE）两两相比厂址FED比重SiaD0110.33E000F1120.67③环境（EFD）两两相比厂址FED比重SiaD0000E1120.67F0110.33（3）计算主观量度值SMi，𝑆𝑀𝑖=∑𝐼𝑘𝑆𝑖𝑘3𝑘=1，其中Ik为各主观因素的重要性指数。因素kDEF重要性指数IkSia0.1670.1670.6660.6Sib0.3300.670.3Sic00.670.330.1计算可得SMD=0.167∗0.6+0.33∗0.3+0∗0.1=0.1992SME=0.167∗0.6+0∗0.3+0.67∗0.1=0.1672SMF=0.666∗0.6+0.67∗0.3+0.33∗0.1=0.6336（4）计算位置量度值LMi，LMi=X∗SMi+（1−X）∗OMi由于题中没有给出主观因素与客观因素的相互比重，假设两者相等即同种重要，即主客观比重值X=0.5。LMD=0.5∗0.3395+0.5∗0.1992=0.26935LME=0.5∗0.3382+0.5∗0.1672=0.2527LMF=0.5∗0.3223+0.5∗0.6336=0.47795（5）决策根据各位置量度值LMi的大小，F厂址所得位置量度值在3个候选地址中最高，故选F为建厂厂址。17.在某区域需规划建设若干个农贸市场为将来该区9个主要居民点提供服务，除第6居民点外，其他各点均有建设市场的条件，如图2－6所示。已知市场的最大服务直径为3km，为保护该区域的环境，希望尽可能少地建造农贸市场。问应如何规划？图2－6小区居民点位置图解：N＝{1,2,3,4,5,6,7,8,9}，M＝{1,2,3,4,5,7,8,9}，由图2－6两点间的最短距离，根据最大服务半径为3km的约束及第6居民点不适合建市场的要求，可确定集合A(j)和B(i)。如表2－3所示。因为A(4)={1,3,4,5,6,7}，A(3)={1,2,3,4,5,6},|A(4)|=|A(3)|=6为最大,随机选取j’＝4。由于无容量约束故依次指派5,7,1,6,3,4点归节点4服务。此时，N＝{2,8,9},M表2－3候选点服务范围3＝{1,2,3,5,7,8,9},更新集合A(j)和集合B(i)后如表2－4所示。因为A(8)＝{8,9}，|A(8)|＝|A(9)|=2为最大，故选取j’＝8或j’＝9，并且8，9两点归节点8或9服务。同理，再迭代一次，得j’＝2，居民点2归节点2服务。因