规划计算题整理

1、规划计算题整理 . . 第二章 设 施 选 址 10. 一家 银 行准 备 在某 县 的 农 村地 区批 投放一批 m atm 自 动 取款机，以方便 农 村的用 户。 取款。 该农 村地 区 的村落座落情 况 和相 对 距离如 图3 2.13 所示。 为 了能确保任一村的人都可以在 0 20 分 钟 之到 达 自 动 取款机取款， 银 行需要多少台自 动 取款机？它 们 的位置又在哪里? ? 图 2.13 村落座落情况和相对距离 要点：1.明确 n，m， ， 含义； 2. 分析正确后， 可参照 直接写出，无需再看网络图； 3.熟悉最少点覆盖启发式算法的步骤，考虑是否有容量约束。 ： 解：【集

2、合覆盖模型】 区域中需求点集合 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 候选点服务围 村落号 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 因为 =2,3,4,6,7，|=5 为最大，故首先 =4。因无容量约束，指派2,3,4,6,7 归村落

3、 4 服务。 此时 n=1,5，m=1,2,3,5,6,7；则更新候选点服务围，见表 2.10.2。 2.10.2 更新后的候选点服务围 村落号 1 1 1 1,2,3 2 1,5 3 1 1 4 5 5 5 2,5,6 6 5 5 7 因为 =1,5=n，恰好满足条件。则 =2。 综上所述，银行需要 2 台自动取款机，分别至于村落号为 2 和 4 的位置，2号为 1,5 村落服务，4 号为 2,3,4,6,7 村落服务。 . . 11. 个临时帮 助服 务 中心 计 划在一 个 大城市的郊外 开设 一 个 新的 办 公室。在 经过 一定的精 简 之后， 该 公司有 5 5 个 大的合作伙伴。

4、在一 个以 以 m km 为单 位的笛卡 尔 坐 标 系中，它 们 的坐 标 分 别为 ： (4 ， 4) ，(4 ， 11) ， (7 ， 2) ， (11 ， 11) ， (14 ， 7) 。它 们 的服 务 需求量的 权 重分 别为 ： wl=3 ， w2=2 ， w3=2 ， w4=4 ， w5=1 。 对 于 该 服 务 中心 来说 ，主要的日常 费 用是他 们员 工完成任 务过 程中的 运输费 用。因此，用城市距离 进 行考 虑 ，要求新的 办 公室到各 个 合作伙伴之 间运输 的 运输费 用最小。1 1 ） 请 确定一 个 新 办 公室的地址，用笛卡 尔 坐 标来 表 达 相 应

5、结果。2 2 ）如果由于 该 地 区 的人口稀少，城市 还没 有 达 到一定的 规 模，可以用 欧 几米德距离 进 行 计 算，新 办 公室又得在哪里投建? ? 请 比 较两次 结 果，分析它 们 之 间 的 关 系。 要点：1. 补充交叉中值模型知识点 . . 关键句：将 n 点需求的选址问题转化为 点需求的选址问题。 2.笛卡尔距离即直角距离，欧基米德距离即直线距离； 3.重心法：初始化+迭代公式+excel/c 编程/matlab 编程迭代+迭代终止条件 ： 解：（1）设新办公室的地址的坐标为( x,y ),给题目已知的 5 个点编号 15。 由于笛卡尔距离 =| - |+| - |。

6、则目标函数为时总运输距离 h 最短。 | . . 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 由 excel 迭 代 得 ， 结 果 如 图 费用结果保留四位小数得最优解为 x=7.6257,y=7.6047,此时费用最小为 h=62.1020 （

7、3）比较两次结果可知欧基米德中的费用小于笛卡尔距离，因直线距离是直角距离，因此用欧基米德距离更为精确。直角距离比较适合于城区围的选址，欧基米德距离比较适合于远距离的选址。 12. 一台机器工具小制造商要 迁 址，并确定了 两个 地 区 以供 选择 。a a 地的年固定成本为 为 0 800000 元，可 变 成本为 为 0 14000 元/ / 台；b b 地的年固定成本为 为 0 920210 元，可 变 成本为 为 0 13000 元/ / 台。 产 品最后售价 为0 17000 元/ / 台。 （1 1 ） 当产 量 为 多少 时 ， 两 地的 总 成本相等？ （2 2） ） 当产 量

8、处 于什么 围时， ，a a 地优于 b b 地？ 当产 量 处 于什么 围时 ，b b 地优于 a a 地？ . . 解：答：设 x 为之制造商的年产量 a 地，总成本 c(a)=800000+14000x b 地，总成本 c(b)=920210+13000x 1)若两地成本相等，则 c(a)=c(b) 解得：x=120 2）若 a 地优于 b 地，则 c(a)c(b),因此得 0x120 同理，当 x120 时，b 地优于 a 地。 13 利用表 8 2.8 所示的因素 评 分，以最大 综 合得分 为 基 础 ，建模分析 应选择 地点 点 a a 、b b 、c c 中的哪一 个 ? 表

9、2.8 因素评分表 解：权重矩阵设为 w，则 三个位置的因素评分作为 3 行构成因素矩阵 s。 可得综合加权矩阵 e=s*w= 。 可知 e(a) e(b) e(c)。即选择 a 点。 14. 一 个 玩具制造商在全 国 的五 个 地 区 生 产 玩具，原材料 将从 一 . . 个 新的中心 仓库运 出，而此 仓库 的地 点还 有待确定。 运 至各地的原材料 数 量相同，已建立一 个 坐 标 城，各地的坐 标 位置如表 9 2.9 所示。 请确定中心 仓库 的坐 标 位置。 表 2.9 各地的坐标位置 解：设仓库的坐标为（,仓库到各生产地的距离为 ,因运至各地的原材料数量相同，故可设 初始解：

10、n n( ) ( )j jj jx x ,y yn n= = =å å0 00 01 11 1，即。 直线距离为 = 目标函数运输总费用 h= ，其中 根据下列进行迭代： = ， ， . . = 直到运费无法减小。 用 matlab 进行编码： 运行结果得，迭代 78 次得到最优解。 其中选址坐标为（5.6235,4.9918），最小运费为 h=13.4550。 或由 excel 迭代得，结果如图 . . 费用结果保留三位小数得最优解为 x=5.5767，y=4.010,h=13.456 1 1 5. 某物流公司 拟 建一 仓库负责 向四 个 工厂 进 行物料供 应 配送，

11、各工厂的具体位置与年物料配送量 见表 表 2.10 ， 设拟 建物流公司 仓库对各工厂的 单 位 运输 成本相等。利用重心法 计 算确定物流公司的 仓库 坐标 位置 为 多少。 表 2.10 各工厂的具体位置与年物料配送量 解 ： 设 仓 库 的 坐 标 为 （ , 仓 库 到 各 生 产 地 的 距 离 为,目 标 函 数 运 输 总 费 用h= ， 为工厂年配送量， 为单位运输成本，因单位运输成本相等，故令 =1，于是有 . . 初始解 =37.5, =42.5 = , 此时 =192249.4 令=, , = = =190400.4 由 excel 迭代得，结果如图 结果保留整数得最优解

12、为（42.22076，33.82437）,h=188709 或用 matlab 进行编码（文件见附件）： . . 运行结果得，迭代 59 次得到最优解。 其中选址坐标为（42.2865, 33.6732），最小运费为 h= 188707.914。 16. 筹 建一 农 副 产 品流通加工厂，可供 选择 的候 选 厂址有 d d 、 e e 、 f f三 处 ，因地址不同各厂加工成本亦有 区别 ，各厂址每年 费 用如表 2.7所示。此外， 为决 定厂址 还 考 虑 了一些重要的非成本因素，如 当 地 竞争 能力、气候 变 化和周 围环 境是否适合 农 副 产 品流通加工等。 对 于 竞争 能力而

13、言，f f 地最 强 ， d d 、 e e 两 地相帄；就气候 来说 ， d d 比 e e 好， f f地最好；至于 环 境， e e 地最优，其次 为 f f 地、 d d 地。如果各主 观 因素的重要性指 数 a a 、 b b 、 c c 依次为 为 0.6 、3 0.3 和 和 0.1 ，要求用因次分析法评 定最佳厂址在何 处 。 表 2.11 各候选厂址每年加工成本费用 . . 要点：p 中值法分 5 个步骤进行。 解 : （1）计算客观量度值 ， 同理可得： （2）计算主观评比值 （有 3 个不同的主观因素） 竞争能力（fd=e）注：d=e，比较记为 0.5 两两相比 厂址 f

14、 e d 比重 d 0 0.5 0.5 0.167 e 0 0.5 0.5 0.167 f 1 1 2 0.666 气候（fde） 两两相比 . . 厂址 f e d 比重 d 0 1 1 0.33 e 0 0 0 f 1 1 2 0.67 环境（efd） 两两相比 厂址 f e d 比重 d 0 0 0 0 e 1 1 2 0.67 f 0 1 1 0.33 （3）计算主观量度值 ， ，其中 为各主观因素的重要性指数。 因素 k d e f 重要性指数 0.167 0.167 0.666 0.6 0.33 0 0.67 0.3 0 0.67 0.33 0.1 计算可得 . . （4）计算位置

15、量度值 ， 由于题中没有给出主观因素与客观因素的相互比重，假设两者相等即同种重要，即主客观比重值 。 （5）决策 根据各位置量度值 的大小，f 厂址所得位置量度值在 3 个候选地址中最高，故选 f 为建厂厂址。 17. 在某 区 域需 规 划建 设 若干 个农贸 市区 场为将来该区 9 9 个 主要居民 点 提供服 务 ，除第 6 6 居民 点 外，其他各 点 均有建 设 市 场 的 条 件，如图 图 2 2 6 6 所示。已知市 场 的最大服 务 直 径为 3km ， 为 保 护该区 域的 环境，希望 尽 可能少地建造 农贸 市 场 。 问应 如何 规 划？ 图 26 小区居民点位置图 3

16、. . 解：n1,2,3,4,5,6,7,8,9，m1,2,3,4,5,7,8,9，由图 26 两点间的最短距离，根据最大服务半径为 3km 的约束及第 6 居民点不适合建市场的要求，可确定集合 a(j)和 b(i)。如表 23 所示。 因为 a(4)=1,3,4,5,6,7，a(3)=1,2,3,4,5,6,|a(4)|= |a(3)|=6 为最大,随机选取 j4。由于无容量约束故依次指派 5,7,1,6,3,4 点归节点 4 服务。此时，n2,8,9,m1,2,3,5,7,8,9,更新集合 a(j)和集合 b(i)后如表 24所示。 表 24 候选点服务范围 表 23 候选点服务范围 .

17、. 因为 a(8)8,9，|a(8)|a(9)|=2 为最大，故选取 j8 或 j9，并且8，9 两点归节点 8 或 9 服务。同理，再迭代一次，得 j2，居民点 2 归节点2 服务。 因此，计算结果为（4,8,2）或（4,9,2）。 若选择 j3，故依次指派 1,2,3,4,5,6 点归节点 3 服务。此时，n7,8,9,m1,2,4,5,7,8,9,更新集合 a(j)和集合 b(i)后如表 25 所示。 由于|a(8)|3 最大，选择 j8。因此计算结果为（3,8）。 第三章 设 施 规 划 11. 某生 产线 共有 8 8 项 作 业 ，其工作周期为 为 8 8 分 钟 。已知各 项 作

18、业 的 装 配 顺 序和 时间 如表 0 3.30 所示。 请 根据周期 时间 和作 业顺 序限制，确定最少工作站 数 和各 项 作 业 的安排，并算出此安排下生 产线 的效率。 表 3.30 周期时间和作业顺序表 表 25 候选点服务范围 . . 解：由题意得网络活动图（job on nodes）： 由题意各作业所需时间之和=5+3+4+3+6+1+4+2=28 最小工作数=28/8=3.5,因此需要 4 个工作台 根据作业的相关情况进行安排，结果如下表 工作站序号 作业单元 工作时间 空闲时间 1 h,g,f 7 1 2 e 6 2 3 d，c 7 1 4 b，a 8 0 生 产 线 效

19、率 = 完 成 作 业 所 需 时 间 总 和 /( 实 际 工 作 站 总 数 * 时 间 周期)= 12. 某流水 线 有 7 17 项 作 业 需要帄衡，其中最 长 的作 业为 4 2.4 分 钟 ，a b c d e f g h . . 所有作 业 的 总时间为 8 18 分 钟 。 该 流水 线 每天工作 0 450 分 钟 。 试 求： （1 1 ）最大和最小的周期 时间 各是多少？ （2 2 ） 该 流水 线 理 论 上可能 达 到的每日 产 能是多少？ （3 3 ）按最大 产 能 来 算，最少需要几 个 工作站？ （4 4 ）若每天 产 能为 为 1 15 25 分 钟 ， 则

20、 周期 时间应为 多 长 ？ （5 5 ）若周期 时间 分 别是 是 9 9 分 钟和 和 5 15 分 钟 ， 则产 能分 别 是多少？ ： 解：（1）当 17 项作业只能串行依次进行时，可得最大周期为 18min。 当 17 项作业均并行进行时，可得最小周期为 2.4min。 （2）产能为单位时间生产的产品数量。 以最大周期计算，得最小产能为 1/18min=0.056/min； 以最小周期计算，得最大产能为 1/2.4min=0.417/min； 综上所述，每日可能产能为25,187.5。 （3）依题意有需要 18/2.4=7.5 ，所以最少需要 8 个工作站。 （4）周期时间为 450

21、/125=3.6min。 （5）当周期时间为 9min 时，产能为 450/9=50/天； 当周期时间为 15min，产能为 450/15=30/天。 13. 某 学 院注 册 有四道手 续 ： 领 取表格、咨 询 、 领 取班 级 卡和确认 交 费 ，分 别 安排在 a a 、b b 、c c 、d d 四 个连续 相 邻 的同 样 大小的房 间 ，因 为 同 时 有新老 学 生，如果 0 450 名新 学 生 领 表后去咨 询 ，0 550 名老 学生 领 表后直接去 领 班 级 卡，而 毕业 班 学 生已 经 注 册过 ， 领 表后直接去缴费 ， 详细学 生流向如表 1 3.31 所示。

22、 试问 已有布置是否可以改 进 ，若能， 该 如何改 进 ？ . . 表 3.31 学生流向表 要点：1.解题思路：单向物流从至表 双向物流从至表 作业对按双向物流从至表中强度值排序，划分物流等级确定物流路线比例 参考相关图得接近程度排序表 按接近程度得作业单位位置相关图 按接近程度排序得作业单位面积相关图 2.参考相关图： 物流强度等级 a e i o u x 物流路线比例 10% 20% 30% 40% 0 0 承担的物流量比例 40% 30% 20% 10% 0 0 接近程度 4 3 2 1 0 0 3.路线比例设计=线路条数/总线路条数 解：由学生流向表得到双向物流表如下： 双向物流表

23、 领表（a） 咨询(b) 领班级卡(c) 缴费(d) 领表（a） 700（2） 550（3） 50（5） 咨询(b) 200（4） 领班级卡(c) 750（1） . . 缴费(d) 根据学生流量划分物流等级确定物流路线比例如下： 序号 作业单位对 强度值 路线比例设计 路线条数 物流强度比例 强度等级 1 c-d 750 20% 1 33.3% e 2 a-b 700 20% 1 31.1% e 3 a-c 550 20% 1 24.4% e 4 b-c 200 40% 2 11.1% o 5 a-d 50 o 合计 2250 由以上关系图得接近程度排序表 领表 a 咨询 b 领班级卡 c 缴

24、费 d 领表 a 3/e 3/e 1/o 咨询 b 3/e 1/o 0/u 领班级卡 c 3/e 1/o 3/e 缴费 d 1/o 0/u 3/e 合计 7 4 7 4 排序 2 4 1 3 作业单位位置相关图和作业单位面积相关图 领班级卡 缴费 领表 咨询 领表 缴费 领班级 咨询 . . 现四道手续：领取表格、咨询、领取班级卡和确认交费，分别安排在 a、b、c、d 四个连续相邻的同样大小的房间，即位置为下图关系 该布置可得到改进，改进方案为 14. 根据作 业 相 关图 ， 绘 制作 业单 位位置相 关图 。 a ab bc cd de ea ai ii i u uu uu uu ue e

25、e eo o 图 3.28 习题 14 作业相关图 解：由该作业相关图可得接近程度排序表如下： a b c d e a 4/a 2/i 0/u 0/u b 4/a 2/i 3/e 3/e c 2/i 2/i 0/u 0/u d 0/u 3/e 0/u 1/o e 0/u 3/e 0/u 1/o 合计 6 12 4 4 4 排序 2 1 5 3 4 领班级卡 缴费 领表 咨询 领班级卡 缴费 领表 咨询 . . 可得作业单位位置相关图如下： 15. 某有 工厂有 e abcde 五 个车间 ，布置 图 如下，其中 为 各 车间 距。 心。 该 厂生 产 四种 产 品，各 产 品的工 艺 路 线 和每月 产 量如表 4 3.4 所示，而且每种 产 品的生 产 批量 为 0 50 件。 （1 1 ） 试 以直角距离 计 算 两两车间 的距离 从 至表； （2 2 ） 计 算物流搬 运 量 从 至表 f f ； （3 3 ） 计 算搬 运 工作量，并以之作 为 物流 强 度表示 从 至表。假 设每批次搬 运 移动 动 1 1 米的成本是 2 2 元/ /， 米批， 试将 上述物流 强 度 从 至表转 化 为 物流成本 从 至表。 + +a b cde1227 15 62430156396123315 解：（1）车间直角距离从至表 a b