第二章设施选址自动取款机,10.ATM一家银行准备在某县的农村地区投放一批该农村地区的村落座落情况和相对距离如图以方便农村的用户取款。分钟之内到达自动取款机所示。为了能确保任一村的人都可以在20取款,银行需要多少台自动取款机它们的位置又在哪里
村落座落情况和相对距离图
,,含义;明确N,M要点: 1.
分析正确后,无需再看网络图;可参照直接写出,2.
熟悉最少点覆盖启发式算法的步骤,考虑是否有容量约束。 3.
解:【集合覆盖模型】N={1,2,3,4,5,6,7};区域中需求点集合
M={1,2,3,4,5,6,7};ATM取款机设施候选点集合
ij的设由网络图确定候选设施点和可覆盖需求点可覆盖的需求点集合
施节点的集合,见表。候选点服务范围
村落号
11,2,31,2,31,2,4,521,2,4,51,3,41,3,43
2,3,4,6,72,3,4,6,742,5,62,5,65
64,5,64,5,674,74,7
。因无容量约束,,因为={2,3,4,6,7}|为最大,故首先|=5=4指派2,3,4,6,7归
村落4服务。
此时N={1,5},M={1,2,3,5,6,7};则更新候选点服务范围,见表。
更新后的候选点服务范围
村落号
111,2,3
21,5
13.
42,5,65556
7
。,恰好满足条件。则=2={1,5}=N因为综上所述,银行需要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点需求的选址问题转化为点需求的选址问题。
2.笛卡尔距离即直角距离,欧基米德距离即直线距离;
3.重心法:初始化+迭代公式+Excel/C编程/matlab编程迭代+迭代终止条件
x,y),给题目已知的5个点编号1~5。(1解:()设新办公室的地址的坐标为
。|-|+|-=|由于笛卡尔距离
H最短。则目标函数为时总运输距离
|
4 3 3 4 33 24 5
5 2 11 27 72 2 7 11 1111 4 411
1212 11 14 7
均在第六个、第七个点之间。为偶数,即
可得,
(2)设初始点为()有题意得,阿基米德距离为
=,
目标函数H(运输总费用 ,)=
利用不动点算法,取一个初始的迭代点(,=此时)=(8,7),
令=,,=
==由EXCEL迭代得,结果如图
费用结果保留四位小数得最优解为
x=,y=,此时费用最小为H=
(3)比较两次结果可知欧基米德中的费用小于笛卡尔距离,因直线距离是<直角距离,因此用欧基米德距离更为精确。直角距离比较适合于城区范围内的选址,欧基米德距离比较适合于远距离的选址。
12.一台机器工具小制造商要迁址,并确定了两个地区以供选择。A
地的年固定成本为800000元,可变成本为14000元/台;B地的年台。产品最后售价为/元13000元,可变成本为920000固定成本为17000元/台。1)当产量为多少时,两地的总成本相等(地当产
量处于什么范A地优于B(2)当产量处于什么范围时,地优于A
地围时,B x为之制造商的年产量答:设解:地,总成本C(A)=800000+14000x
A地,总成本C(B)=920000+13000x B若两地成本相等,则C(A)=C(B)1)x=120解得:0 时,同理,当x>120.利用表所示的因素评分,以最大综合得分为基础,建模分析13 CB、中的哪一个应选择地点A、因素评分表表 ,则权重矩阵设为W解:S。三个位置的因素评分作为3行构成因素矩阵 可得综合加权矩阵E=S*W=。 可知E(A)> E(B)> E(C)。即选择A点。 14.一个玩具制造商在全国的五个地区生产玩具,原材料将从一个新的中心仓库运出,而此仓库的地点还有待确定。运至各地的原材料数量相同,已建立一个坐标城,各地的坐标位置如表所示。请确定中心仓库的坐标位置。 各地的坐标位置表. 仓库到各生产地,解:设仓库的坐标为 ( 的距离为,因运至各地的原材料数量相同,故可设nn11 ??)()(00yxy??x,,即。初始解:j0j0nn j1?1j?直线距离为 = ,其中H= 目标函数运输总费用 根据下列进行迭代: =,,=直到运费无法减小。 用MATLAB 进行编码: 运行结果得,迭代78次得到最优解。 其中选址坐标为(,),最小运费为H=。 或由EXCEL迭代得,结果如图 费用结果保留三位小数得最优解为X=,y=,H= 5.某物流公司拟建一仓库负责向四个工厂进行物料供应配送,1各工厂的具体位置与年物料配送量见表,设拟建物流公司仓库对各工厂的单位运输成本相等。利用重心法计算确定物流公司的仓库坐标位置为多少。 表各工厂的具体位置与年物料配送量 解:设仓库的坐标为(,仓库到各生产 用费总输运数函标目,为离距的 地. 为单位运输成本,因单H=为工厂年配送量,, 有是相令等=1,,故于位运输成本 初始解=,=