福建工程学院 运筹学 期末考 赵忠华 B卷.pdf

沈阳理工大学试卷参考答案及评分标准 沈阳理工大学试卷参考答案及评分标准 2005 2006 学年第 二 学期 2005 2006 学年第 二 学期 课程名称 运筹学 考试班级 04421 4 04451 3 命题教师 赵忠华 答 案 A 或 B B 考核形式 开 闭 闭 考试类型 课程名称 运筹学 考试班级 04421 4 04451 3 命题教师 赵忠华 答 案 A 或 B B 考核形式 开 闭 闭 考试类型 考查 考试考查 考试 考试 考试 2006 年 5 月 20 日 一 已知线性规划问题 14 分 21 xxMinZ 1 21 xx 25 0 21 xx 0 21 xx 求 1 用图解法求解 6 分 2 写出其对偶问题 4 分 3 直接写出对偶问题的最优解 4 分 解 1 x2 2 Z Z x1 x1 x2 1 0 2 4 0 5x1 x2 2 3 分 由图可知 25 0 21 xx 解之得 4 1 x 0 2 x 0 2 x 2 分 则最优解为 X 4 0 T Max Z 4 0 4 为唯一最优解 1 分 2 该问题的对偶问题为 21 2yyMaxZ 1 分 15 0 21 yy 1分 1 21 yy 1分 0 0 21 yy 1 分 3 由对偶问题性质可知 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 15 0 2 1 yy 解之得 0 1 y 42 2 1 yy 2 2 y 所以 Y 0 2 T Max Z 4 4 分 二 已知下列线性规划问题 22 分 321 336xxxMaxZ 603 321 xxx 20422 321 xxx 60333 321 xxx 0 321 xxx 求 1 用单纯形法求解 并指出问题属于哪一类解 20 分 2 若增加一约束条件30 321 xxx 则最优解如何变化 2 分 解 1 将原问题划为标准形得 654321 000336xxxxxxMaxZ 4321 3xxxx 60 20422 5321 xxxx 60333 6321 xxxx 0 654321 xxxxxx 4 分 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 计算表每步 4 分 j C 6 33 0 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 6 x 0 4 x 603 1 1 1 0 0 0 5 x 20 2 24 0 1 0 0 6 x 603 3 3 0 0 1 j 6 33 0 0 0 j C 6 33 0 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 6 x 0 4 x 300 4 5 1 3 20 6 1 x 101 12 0 1 20 0 6 x 300 6 9 0 3 21 j 0 3 9 0 3 0 j C 6 33 0 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 6 x 0 4 x 100 0 1 1 1 2 2 3 6 1 x 151 0 1 20 1 41 6 3 2 x 50 1 3 20 1 41 6 j 0 0 9 20 9 4 1 2 所以 X 15 5 0 10 0 0 T 为唯一最优解 2 分 Max Z 6 15 3 5 75 2 分 2 将 X 15 5 0 10 0 0 T代入给出的约束条件中可知 最优解满足此约束条件 所以 最优解不变 2 分 三 已知某运输问题如下 单位 百元 吨 12 分 单位运价 销地 产地 B1 B2 B3 供应量 吨 A1 37218 A2 581012 A3 94515 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 需求量 吨 161217 求 1 使总运费最小的调运方案和最小运费 10 分 2 该问题是否有多个最优调运方案 若没有 说明为什么 若有 请再求出一 个最优调运方案来 2 分 解 1 用伏格尔法确定初始调运方案为 B1B2B3供 A11 1718 A212 12 A33 12 15 需161217 12 9 22 0 23 6 33 3 4 分 有 ij 0 所以需要调整为 B1B2B3供 A14 1418 A212 12 A3 123 15 需161217 12 6 22 5 23 6 31 3 4 分 因为 ij 0 所以为最优方案 Min Z 3 4 2 14 12 5 12 4 3 5 163 为唯一最优解 2 分 2 无 因为 ij 0 所以该题仅有唯一最优方案 2 分 四 分配甲 乙 丙 丁 戊五个人去完成 A B C D E 五项工作 每个人完成各项任务 的时间如下表所示 10 分 表中单位 小时 务 人 A B C D E 甲 乙 丙 丁 戊 25 28 31 41 38 40 38 26 26 33 35 27 28 40 32 24 42 37 23 45 30 29 26 20 32 已知甲不可能完成任务 D 丁只可以完成任务 B C 试确定最优分配方案 使完成任务的总 时间为最少 解 252831380362513 40382626331412007 3527284032801135 423737503737 30292620321096012 MM MMMMMM 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 0 36258 1412002 28 0 1130 375 0 3742 1096 0 7 0 16256 141000 0 10 0 3150 373 0 3744 1076 0 5 M k MMM M MMM uuuuu r 初始 4 分 其余每步 1 分 即 甲 A 乙 E 丙 B 丁 C 戊 D 1 分 Min Z 25 33 27 37 20 142 小时 2 分 五 某台机器可连续工作 4 年 也可于每年末卖掉 换一台新的 已知于各年初购置一台新 机器的价格及不同役龄机器年末的处理价如下表所示 又新机器第一年运行及维护费用为 0 3 万元 使用 1 3 年后机器每年的运行及维修费用为 0 8 1 5 2 0 万元 试确定该机器的最优 更新策略 使 4 年内用于更换 购买及运行维修的总费用为最省 12 分 单位 万元 j 第一年第二年第三年第四年 年初购置价 2 5 2 6 2 8 3 1 使用 j 年后的处理价2 0 1 6 1 3 1 1 解 6 0 2 3 2 0 2 1 0 8 0 9 1 1 1 4 0 1 2 3 4 0 0 8 1 7 2 8 4 0 3 9 3 8 由上图可知 画图并标出权重 4 分 计算最短路径 4 分 写出答案 4 分 最佳更新策略为 第一年初购入 年末卖出 第二年年初购入年末卖出 第三年年初购入用 至第四年末 MinZ 4 0 六 求下图的网络最大流 并写出最小割集 12 分 V1 4 V4 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 8 7 6 4 5 Vs 9 V2 3 V5 3 Vt 15 5 2 8 7 V3 7 V6 解 找增广链 ts VVVV 41 4 1 f ts VVVV 52 3 2 f ts VVVV 63 7 3 f 6 分 Vs 4 V1 4 4 V4 8 4 7 6 4 5 4 Vs 9 3 V2 V1 4 3 3 V5 3 3 Vt 15 7 5 2 8 7 7 V3 7 7 V6 Vs 8 3 分 最小割集为 V V3 V6 V2 V5 V1 V4 1 分 C V V 14 1 分 且 V f 14 1 分 七 某厂有一种新产品 其推销策略有 123 S SS三种可供选择 各方案所需的资金 时间不 同 市场情况也有差别 因而获利和亏损情况不同 而市场情况有三种 1 Q 需要量大 2 Q 需要量一般 3 Q 需要量低 其概率为 0 3 0 4 0 3 其损益矩阵如下表 10 分 Qi Si 市场情况 Q1Q2Q3 S1 4510 8 S2 25280 S3 1599 1 分别用最大收益期望值 EMV 决策准则和最小机会损失期望值 EOL 决策准则决定该公 司最佳设计方案 4 分 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 二 五 二 六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 2 如果该公司能确切掌握市场需求信息 求完备信息的收益期望值 EPPI 3 分 3 若有一单位愿帮助该公司调查市场的确切需要量 该公司最多能付出调查费是多少 EVPI 3 分 解 1 最大收益期望矩阵为 Q1Q2Q3EMV EMV S1 4510 815 1 S2 25 28018 7 S3 159 910 8 2 分 最小机会损失矩阵为 Q1Q2Q3EMV EOL S1 0 181712 3 S2 20 0 8 8 7 S3 30190 16 6 2 分 2 EPPI 45 0 3 28 0 4 9 0 3 27 4 3 分 3 EVPI 27 4 18 7 8 7 EOL 3 分 八 A B 两种产品 都需要经过前后两道工序 每一个单位产品 A 需要前道工序 1 小时和后 道工序 2 小时 每单位产品 B 需要前道工序 2 小时和后道工序 3 小时 可供利用的前道工序 有 11 小时 后道工序有 17 小时 每加工一个单位产品 B 的同时 会产生两个单位的副产品 C 且不需要任何费用 产品 C 一部分可出售盈利 其余只能加以销毁 出售 A B C 的利润分别为 3 7 2 元 每单位产品 C 的销毁费用为 1 元 预测表明