运筹学E2017秋试卷A答案.pdf

第 1 页 共 10 页 学院系专业班级姓名学号 (密封线外不要写姓名、学号、班级、密封线内不准答题，违者按零分计) 密封线 考试方式：闭卷闭卷 太太原原理理工工大大学学运运筹筹学学 E E试试卷卷（A） 适用专业：采矿工程 考试日期： 2018 年 1 月 3 日时间： 120 分钟共10 页 题号一二三四五六总 分 得分 一、规划模型建立题(只建立模型，不求解。每小题 5 分，共 20 分) （1）某矿炸药厂生产两种矿用炸药：2号岩石铵梯炸药和3号露天铵梯炸药。若下 月可提供给该厂的原料数量为：硝酸铵400吨，梯恩梯44吨，木粉36吨。两种炸药所用 的原料和配比如下表所示。这两种炸药的出厂价格分别为1200元/吨和800元/吨。问如何 安排生产才能使该厂下月的产值最高？ 2号岩石铵梯炸药3号露天铵梯炸药 硝酸铵0.850.88 梯恩梯0.110.03 木粉0.040.09 解：设下月2号岩石铵梯炸药和3号露天铵梯炸药的生产量分别为x1吨和x2吨，该厂 下月的产值为Z元。根据已知条件可列以下数学模型： 12 12 12 12 12 =1200800 0.850.88400 0.110.0344 0.040.0936 0,0 Zxx xx xx xx xx 炸药 配 比 原料 第 2 页 共 10 页 （2）将下列线性规划问题模型化为标准型。 123 min23Zxxx 123 123 123 123 29 3+24 323=6 0 ,0 , xxx xxx xxx xxx 取 值 无 约 束 解：令 33311 ,ZZxxxxx ，按上述规则将问题转化为标准型为： 23345 12334 12335 1233 123345 max23300 29 3224 32336 ,0 Zxxxxxx xxxxx xxxxx xxxx x x x x x x （3）建立下列问题的0-1型整数规划模型。 某公司拟在城市的东、西、南三区建立门市部，拟议中有7个位置(1,2,.,7) i A i 可 供选择。规定：在东区，由 123 AAA， ，三个点中至多选两个；在西区，由 45 AA，两个点 中至少选一个；在南区，由 67 AA，两个点中至少选一个。如选用 i A点，设备投资估计为 i b元，每年可获利润估计为 i c，但投资总额不能超过B元，问应该选择哪几个点可使年 利润为最大？ 解：令 1 1, 2,.,7 0 i i i A xi A 当被 选 用 当未 被 选 用 模型为： 7 1 7 1 123 45 67 max 2 1 1 10 ii i ii i i zc x b xB xxx xx xx x 或 第 3 页 共 10 页 学院系专业班级姓名学号 (密封线外不要写姓名、学号、班级、密封线内不准答题，违者按零分计) 密封线 （4）某矿井3个采区，根据生产技术条件，第一采区工人总数不能超过120人，二 采区工人数不能超过200人，矿井采区工人总数不能超过500人。由于各采区瓦斯涌出 量不同， 根据通风要求， 各采区中每个工人所需风量各为8m3/min， 6m3/min和10m3/min， 供给3个采区的总风量不超过1200 m3/min。3个采区的工人劳动生产率各为5t/工，4t/ 工和3t/工。如何安排3个采区的工人数，才能使全矿井的日产量最高？ 解：设一、二、三采区的工人数分别为?，?，?，根据条件可列出模型为： Max Z = 5? ? ? ? ? ? 5? ? ? ? ? ? ? ? ? ? ? ? 二、直写题（共计 10 分） 1、某矿采用立井开拓方式，主副井及安装工程均已完成，紧接着要开始完成主副 井贯通工程。分配甲、乙、丙、丁四个掘进队去完成 A、B、C、D 四段贯通任务。每 个队完成各项任务周数如下表所示。试确定总花费时间为最少的指派方案。 （4 分） 任务/队ABCD 甲25293142 乙39382620 丙34272840 丁26422325 解：找出效率矩阵每行列的最小元素，并分别从每行中减去后得到每行每列中至 少都有一个零元素，则只要将零元素位置变为 1，其余的变为 0 则得到问题的最优解。 甲 A 乙 D 丙 B 丁 C。 25 29 31 42 0 4 6 171 0 0 0 39 38 26 2019 18 6 00 0 0 1 34 27 28 40 7 0 1 130 1 0 0 26 42 23 25 3 19 0 20 0 1 0 第 4 页 共 10 页 2、用破圈法和避圈法求图中最小生成树（简要写出步骤）。（6 分） v1 v2 v3v5 v4 v6 5 10 7 412 7 9 8 6 解： （1）破圈法 A、任选一个圈（?），去掉权最 大的边（?）； B、在余下的图中选取圈（?5?），去 掉权最大的边（?5）； C、重复上述步骤，直到无圈时停止。 D、最小树为： （2）避圈法 v2 v3 4v1 v2 v3 5 4 v1 v2 v3v5 5 4 9 v1 v2 v3v5 v4 5 4 9 6 v1 v2 v3v5 v4 v6 5 7 4 9 6 v1 v2 v3v5 v4 v6 5 7 4 9 6 第 5 页 共 10 页 学院系专业班级姓名学号 (密封线外不要写姓名、学号、班级、密封线内不准答题，违者按零分计) 密封线 三、用大 M 法求解下面的实际问题(30 分) 某矿近期计划安排 4 对新建矿井投产，产量不低于 90 万吨，4 对已设计完成的片 盘斜井基本情况如下表所示： 斜井生产能力（万 t）吨煤投资（元/t）吨煤成本（元/t） 1276010 236779 327818 4365511 共有投资 7300 万元，问各片盘斜井产量安排多少时，总生产成本最少？ 要求： （1）先写出该问题的标准形式(5 分)； （2）完成单纯形表（22 分） ； （3）问 题的最优解和最优值（3 分） 。 解：设?，?，?，?为各片盘的产量，单位万 t。根据题意可列如下数学模型： Min Z = ? ? ? ? ? tt? ? 55? t? ? ? ? ? ? ? ?t ? ? ? ?t ? ? ? ? ? 该问题的标准型为： Max ?= ? ? ? ? t? ? tt? ? 55? ?5= t? ? ? ? ? ? ?= ? ? ?t? ?t ? ? ? ? ? ?t ? ? ? ? ? ? 列单纯形表如下： 由此可见，最优解为 X=（27，36，27，0，721，0，0，0，0，36，0） T 第 6 页 共 10 页 -10-9-8-11000000-M cB基bx1x2x3x4x5x6x7x8x9x10x11 0x5730060778155100000090.1 -Mx119011110-10000190 0x72710000010000- 0x83601000001000- 0x9270010000010027 0x103600010000010- j M-10M-9M-8M-110-M00000 0x5511360770551000-810066.4 -Mx116311010-100-10163 0x72710000010000- 0x8360100000100036 -8x32700100000100- 0x103600010000010- j M-10M-90M-110-M008-M00 0x52341600055100-77-810039 -Mx112710010-10-1-10127 0x7271000001000027 -9x23601000001000- -8x32700100000100- 0x103600010000010- j M-1000M-110-M09-M8-M00 0x5721000-51600-17-210-60 -10x12710010-10-1-101 0x70000-1011110-1 -9x23601000001000- -8x32700100000100- 0x103600010000010- j 000-10-100-1-2010-M 第 7 页 共 10 页 学院系专业班级姓名学号 (密封线外不要写姓名、学号、班级、密封线内不准答题，违者按零分计) 密封线 四、用 Dijkstra 法求解下面的问题(要求写出步骤，10 分) 原煤从某集团公司运到某地可途径的运输线路如下图所示， ?为起点， ?为终点， 弧旁的数据为该段线路的长度。求从?到?的最短路。 v1 v7 v2v3 v8 v5 v4 v6 v10 v9 3 76 5 4 4 587 62 89 6 6 解： （1）P（?）=0，T（?）=? ，? = ? （2）T ?= min T ? P ? ?=3，T ?5= min T ?5? P ? ?5=5，T ?t= min T ?t? P ? ?t=2，所以P（?t）=2 （3）T ?5= min T ?5? P ?t? ?t5=5， T ?= min T ? P ?t? ?t?=10， 所以P （?） =3 （4）T ?= min T ? P ? ?= ?， T ?5= min T ?5? P ? ?5?= 5， 故P （?5） =5 （5）T ?= min T ? P ?5? ?5?= ?，T ?= min T ? P ?5? ?5?= ?，故P （?）=10，P（?）=10 （6）T ?= min T ? P ? ?= ?，T ?= min T ? P ? ?= ?，故P （?）=11 （7）T ?= min T ? P ? ?= ?t，故P（?）=13 （8）T ?= min T ? P ? ?= ?，故P（?）=17 ?到?的最短路是17，? ?5? ? ? 第 8 页 共 10 页 五、用图解法求解下面的目标规划问题。 （15 分） 某矿开采 2 个煤层，上层的粉煤采出率为 20%，下层煤的粉煤采出率为 30%，上层 煤主要生产环节能力 50 万 t/a，下层为 20 万 t/a。由于开采顺序等条件的限制，下层煤 的产量不能超过上层煤的产量。按照粉煤的供销要求，矿井粉煤的年产量不应超过 12 万 t/a。上层煤开采成本为 20 元/t，开采下层煤的成本为 10 元/t，根据当前市场情况和 开采条件及生产经营情况，第一目标是这 2 层煤年产量希望不低于 50 万 t，第二目标总 成本希望不超过 700 万元。试确定这 2 层煤的合理年产量。 （1）列出数学模型5 分 （2）做出图 8 分 （3）确定结果2分 解：设?，?分别为上、下两层煤的年产量，根据题意列数学模型为： Min Z = ? ? ? ? ? ? ? ? ? = 5? ? ? ? ? ? = t? ?艠? ?艠? ? ? 5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 作图如下： 0102030405060708090 10 20 30 40 50 60 70 80 x1 x2 d2+ d2- x1 x2 0.2x1+0.3x2=12 x1=50 x2=20 x2=x1 d1- d1+ 0102030405060708090 10 20 30 40 50 60 70 80 满意解为：X=（30，20）T 第 9 页 共 10 页 学院系专业班级姓名学号 (密封线外不要写姓名、学号、班级、密封线内不准答题，违者按零分计) 密封线 六、用标号算法求以下网络图的最大流量。 （15 分） 图中弧旁数值为：容量 ij c，流量 ij f s 1 2 3 4 t (3,3) (4,3) (2,2) (1,1) (1,1) (3,0) (5,3) (2,1) (5,1) （一）标号 （1）先给 sv 标上0, （2）检查 sv ， 在弧 ,2sv v 上， 2 2 3 s s f c ， 不满足标号条件。 弧 ,1sv v 上， 1 1 s f， 1 5 s f， 1 1 s f sc ，则 1v 的标号为 1 , s l v v ，其中， 1 1 1 min,min,5 14 s s s ll cf vv ,4sv （3）检查 1v ，在弧 13 , v v 上， 13 2f，不满足标号条件，在弧 21 , v v 上， 21 10f ， 则给 2v 记下标号 1 2 ,l v v ，其中 22 21 min,min 4,11ll f vv 1,1v （4）检查 2v ， 在弧 24 , v v 上， 24 3f， 24 4f， 24 24 f c ， 则给 4v 记下标号 2 4 ,l v v ， 其中 24 42 24 min,min 1,431ll cf vv ， 在弧 32 , v v 上， 32 10f ，则给 4v 记下标号 2 3 ,l v v ，其中 32 32 min,min 1,11ll f vv 2,1v （5）在 3v ， 4v 中任选一个进行检查，如果在弧 3,tv v 上， 3 1 t f， 3 2 t f， 3 3 t t f c ， 则给 tv 记下标号 3, t l v v ，其中 3 3 3 min,min 1,2 11 t t t ll cf vv ， 因 tv 有了标号，所以从 sv 到 tv 有增广链，故转入调整过程。 3,1v 第 10 页 共 10 页 （二）调整 按点的第一个标号找到一条增广链，如图示 s 1 2 3 4 t (3,3) (4,3) (2,2) (1,1) (1,1) (3,0) (5,3) (2,1) (5,1) (0,+) ( ,4) ( ,1) s 1 ( ,1) 2 ( ,1) 2 ( ,1)