试卷序号： 班级： 学号： 姓名：

━ ━ ━ ━ ━ ━ ━ ━ ━ 装 ━ ━ ━ ━ ━ ━ ━ 订 ━ ━ ━ ━ ━ ━ ━ 线 ━ ━ ━ ━ ━ ━ ━ ━ ━ 防灾科技学院

2013 ~ 2014 学年 第一学期期末考试

管理运筹学(48学时) 试卷（A）参考答案与评分标准 答题时间 120分钟

使用班级 1150231/232/411/412/413/511/512/513/521/522/523/524/525

阅卷 题号 一 二 三 四 五 六 总分 教师 得分 一、

阅卷教师 得 分

单选题（本大题共4小题，每题2分，共8 分。）

1、若某线性规划问题存在基可行解，则该问题（ C ）。

A．一定有最优解 B．具有无界解 C．有非空的可行域 D．可能无可行解 2、关于线性规划，（ B ）是错误的。

A．当最优解多于一个时，最优解必有无穷多个 B．当有可行解时必有最优解 C．当有最优解时必能在可行域的某顶点达到 D．当有可行解时必有基可行解 3、互为对偶的两个问题的解存在关系有（ D ）。

A．原问题无可行解，对偶问题一定无可行解 B．原问题有无界解，对偶问题可能有可行解 C．原问题有最优解，对偶问题可能没有最优解 D．原问题无界解，对偶问题一定无可行解

4、用表上作业法求解3个产地4个销地的运输问题，若某步求得空格A3B2的检验数为?2，下列说法中正确的是（ A ）。

A．增加空格A3B2处的运输量将使总成本降低 B．当前方案是最优运输方案

C．由A3至B2的运输量增加1个单位，可使总运费增加2 D．为使总运费更小，应使A3至B2的运输量减少2

二、

阅卷教师 得 分

1、对偶单纯形法求解最大化线性规划问题时，要求初始单纯形表中的检验数都 ?0 。

2、在运输问题中，当总供应量S小于总需求量R时，求解时需虚设一个供应量等于 R?S 的虚拟供应点。

3、某钻井队要从编号为1、2、3、4、5的五个井位中选择若干钻井探油，则“要么选择钻井2，要么选择钻井5” 可用xi的线性表达式表示为 x2?x5?1 ，其中选择第i号钻井时xi=1，否则xi=0，i?1,?,5。 4、来源行x1?填空题（本大题共5小题，每题3分，共15分。）

255515x3?x4?的割平面是 ?x3?x4?0 。

3666635、下图给出某城市部分道路的分布情况，现要沿道路铺埋输水管，为了使铺设的管线最短，要求按道路分布图的最小支撑树来设计管线，则所铺设管线的最小总长度应该是 11 （单位km）。

第 1 页 共 3 页

三、

阅卷教师 得 分

某厂计划生产甲、乙两种产品，需在A、B两种设备上加工，并消耗一定的原料资源，单位产品所需资源等相关数据如下表

产品甲 产品乙 资源限量 设备A 0 5 15 设备B 6 2 24 原料 1 1 5 单位利润（万元） 2 1 计算题（本大题共3小题，每题依次为10、12、4分，共26分。）

1、应如何安排生产使该工厂获利最多？建立该问题的线性规划模型，并写出其对偶问题； 2、用单纯形法确定使总利润最大的生产计划，并求出最高总利润；

3、已知原料的市场价格为0.8万元/单位，该厂是否需要以市场价购进所需原料？为什么？ 解：1、设甲、乙两种产品的产量分别为x1,x2，建立线性规划模型

cj? CB 0 0 0 0 2 0 XB x3 x4 x5 σj x3 x1 x5 σj b 15 24 5 15 4 1 2 x1 0 [6] 1 2? 0 1 0 0 0 1 0 0 1 x2 5 2 1 1 5 1/3 [2/3] 1/3? 0 0 1 0 0 x3 1 0 0 0 1 0 0 0 1 0 0 0 0 x4 0 1 0 0 0 1/6 －－0 x5 0 max z?2x1?x2s..t 5x2?156x1?2x2?24…(5分) (4分)… x1?x2?5x1,x2?0 设对偶变量为y1,y2,y3，则原问题的对偶问题为 (2分) …

?i x3 15/2 0 x1 2 7/2 x2 1 3/2 2、引入变量x3,x4,x5?0，得原问题的标准形式 (2分) … σ j min w?15y1?24y2?5y3s..t 6y2?y3?2…(5分)

5y1?2y2?y3?1y1,y2,y3?01/6 1/3 5/4 1/4 －－1/4 1/4 － 0 4← 1 5 0 0 3 0 12 1 3/2← 0 －15/2 －1/2 3/2 －1/2 用单纯形法求解得

max z?2x1?x2?0x3?0x4?0x5*T检验数?j?0，得最优解X?(7/2,3/2,15/2,0,0)，即最优生产s..t 5x2?x3?15…(2分) A产品3.5个单位，生产B产品1.5个单位 (1分) ，最高6x1?2x2?x4?24计划为生产

*x1?x2?x5?5总利润z?2?3.5?1.5?8.5（万元）(1分)。

x1,x2,x3,x4,x5?03、由单纯形表得对偶变量y3的最优解为0.5，即原料的影子价格是

05，说明该厂按最优生产计划安排生产时，每增加1单位原料可使企业多获利0.5万元(2分)，但是由市场价0.8＞0.5，可知该厂购进原料用于生产无法获利，故不能以市场价购进原料(2分)。

计算题（本大题共1小题，每题15分，共15分。）

四、

阅卷教师 得 分

解：虚拟一个建筑公司A5，由于每栋楼房都建设，为使总费用最低，设 建筑公司 A 1 A 2 A 3 A 4 楼房 其对各楼的预算费用都是“最低”，得标准形式的分派问题(5分)，变换矩 9 4 3 7 B1 阵(3分)进行试分派(4分)得 4 6 5 6 B2

?94373??61040?5 4 7 5 B3 ????46564021207 5 2 3 B4 ???? ?54754???10310? 10 6 7 4 B5 某房地产公司计划在一个住宅小区建设5栋不同类型的楼房??75232???106744?????53010???62300???B1,B2,B3,B4,B5，由四家建筑公司A1,A2,A3,A4进行投标。经过投标得出建筑公司Ai(i?1,?,4)对新楼Bj(j?1,?,5)的预算费用如上表所示。试确定最优分派方案，使房地产公司支付的总费用最少，其中规定每家建筑公司要承建1～2栋楼房。 圈0数目恰等于5，说明试分派成功，最优指派方案为A1→B2；A2→B3；A3→B1和B4；A4→B5，总费用为3+4+4+2+4=17(3分)。 [备注] 1、本题为多重最优解，使总费用最低的其他分配方案同样正确。 2、若解题方法中虚拟建筑公司费用定为“0”，使用匈牙利法求解过程正确即可得到步骤分。其中，所求分派方案使总费用为17，则可得满分；若总费用多于17，第 2 页 共 3 页 五、

阅卷教师 得 分

解答题（本大题共1小题，每题12分，共12分。）

解：设种植玉米x1亩，大豆x2亩，小麦x3亩，建立模型为 ????? min z?Pd?Pd?P(d?d)?Pd112233344友谊农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物。这三种作物每亩所施化肥分别为0.12吨、0.20吨、0.15吨。预计秋后玉米每亩可收获500公斤，售价为0.24元/公斤，大豆每亩可收获200公斤，售价为1.20元/公斤，小麦每亩可收获300公斤，售价为0.70元/公斤。农场年初规划时需要按优先级别考虑

(1分) (1分) (2分) (2分) s..t x1?x2?x3?30000 120x1?240x2?210x3?d1??d1??3500000500x1?200x2?300x3?d2??d2??12500000 P1：年终收益尽可能达到350万元；

(2分) 300x3?d3??d3??5000000P2：希望总产量不低于1250万公斤；

??(2分) P3：由于销量原因，小麦产量以500万公斤为宜； 0.12x1?0.2x2?0.15x3?d4?d4?5000

??P4：农场现能提供5000吨化肥，若不够，可在市场高价购买，(2分) x,x,x?0; d,d?0,i?1,4123ii

但希望高价采购数量愈少愈好。

[备注] 建立模型时单位没有统一的每处扣1分。 试对该农场的种植计划建立线性目标规划模型。

六、

阅卷教师 得 分 解答题（本大题共2小题，每题12分，共24分。）

v3 1、求右图中v1到其它各点的最短路，并给出最短路长。 64 v24v6 解：用Dijkstra算法标号如下 v9v143.53 固定标号 临时标号 4v5235 v1 [0,0] →v2[v1,4] →v4[v1,5] 5v74 v2 [v1,4] →v3[v2,8] →v5[v2,7] →v6[v2,8] 3v8v4 v3 [v2,8] →v9[v3,14]

v4 [v1,5] →v7[v4,9] (4分) v2：v1→v2 4； v3：v1→v2→v3 8； v4：v1→v4 5； v5 [v2,7] →v6[v5,11] v5：v1→v2→v5 7； v6：v1→v2→v6 8； v6 [v2,8] →v7[v6,10] →v9[v6,11.5] (8分) v7：v1→v4→v7 9； v8：v1→v4→v7 →v8 12； v7 [v4,9] →v8[v7,12] →v9[v7,12] v8 [v7, 12] v9：v1→v2→v6 →v9 11.5. v9 [v6, 11.5] [备注] 可采用其他方法求最短路，过程4分，v1到8个点的最短路 反向追踪得v到其他各点的最短路及最短路长，依次为 1和最短路长结果每个1分。

(+vs,1) v2 v5(+v3,1) 2、求右图中所示容量网络中从vs到vt的最大流，并给出最大流流量和最(1,1) (7,6)(4,3)(4,3)(3,2)小割集及容量，其中括号内第一个数字为弧容量cij，第二个数字为流量fij。 (+v,1) s (+v5,1) (△,+∞) (1)为寻找可增广链，标号如下 解：vs (△,+∞)；v2(+vs,1)；v3(+vs,1)；v1(-v3,1)；v4(+v3,1)；v5(+v3,1)；vt(+v5,1) 反向追踪得可增广链vs→v3→v5→vt，调整流量得 (+vs,1) v2vs(3,2)(4,4)(3,2)v3(-v3,1) v1(5,3)(2,2)(8,3)vt(4,2)v4(+v3,1) v5(7,7)(1,1)(4,4),1) 3)(△,+∞) (4,3)(7,6)(+v4,1) (3,2)(+v2(4,(3,3)vtvs(3,2)v3(5,3)(2,2)(3,2)3)(4,4)(+v(8,3,1) (-v3,1) (4,2)v4v1 (3)再次给vs标号(△,+∞)后，其他点已无法标号，图中所给可行流即为网络的最大流，最大流流量为7+4=11. 此时，连接已标号点和未标号点的弧，即最小割集{(vs,v2), (vs,v3), (vs,v1)}，最小割集容量为4+3+4=11. [备注] 求解过程不唯一，答案仅供参考。寻找可增广链过程3分，每个 (2)再次标号如下 vs (△,+∞)；v2(+vs,1)；v3(+v2,1)；v1(-v3,1)；v4(+v3,1)；vt(+v4,1) 反向追踪得可增广链vs→v2→v3→v4→vt，调整流量得 (7,7)(4,4)v(1,1)5(△,+∞) (7,6)(5,4)(4,3)(3,3)(3,2)(4,3)(8,4)vvs(3,2)v3(5,3)(2,2)第 3 t页 共 3 页 (3,2)(8,3)(4,4) (4,4)v(3,23)v(4,2)v