江苏大学运筹学样卷3

江苏大学江苏大学 运筹学运筹学 期末考试期末考试 任课老师 张怀胜 考试日期 2012 06 06 班级 工业 09 学号 3090804031 姓名 徐峰 上机 IP 202 195 169 154 上机总得分 71 题目 填空 题 判断 题 选择 题 计算 题 1 计算 题 2 计算 题 3 计算 题 4 计算 题 5 计算 题 6 计算 题 7 计算 题 8 应用 题 总分 题分 510108988888810100 得分 25389848878171 一 填空题 每题 1 分 共 5 分 徐峰得分 2 分 1 已知线性规划 max Z 3x1 4x2 x3 x1 2x2 x3 10 2x1 2x2 x3 16 x1 x2 x3 0 的最优基为约束条件 系数矩阵的第一 第二两列 则最优解 x1 x2 6 2 1 分 2 若一个线性规划为无界解 则其对偶问题一定 无可行解 1 分 3 用 0 1 变量 x1 x2 x3分别表示 A1 A2 A3的选与不选 值为 1 表示选中 否则为不选 则 A1 A2 A3中必须选两个的表达式为 x1 x2 x3 2 参考 答案 x1 x2 x3 2 4 一个可行流为最大流的充要条件是存在一个截集使其截量 大于 网络流的 流量 参考答案 5 报童模型中的损失 h 增加 会使得最优进货量 Q0 减小 参考答案 减 少或不变 二 判断题 每题 1 分 共 10 分 徐峰得分 5 分 1 在基本可行解中非基变量一定为零 正确 1 分 2 若线性规划的原问题有无穷多最优解 则其对偶问题也一定有无穷多最优 解 错误 1 分 3 变量取 0 或 1 的规划是整数规划 正确 1 分 4 运输问题的检验数就是对偶问题的松驰变量的值 错误 5 最大流问题是找一条从发点到收点的路 使得通过这条路的流量最大 正确 6 m n 1 个变量构成基变量组的充要条件是它们不包含闭回路 正确 1 分 7 单位存储费和订购费同时增加 i 则总成本也增加 i 错误 1 分 8 LP 问题的基本可行解对应可行域的顶点 错误 9 定义状态时应保证各个阶段中所做的决策相互独立 错误 10 在其他费用不变的条件下 随着单位缺货费用的增加 最优订货批量将相 应增加 正确 三 单项选择题 每题 1 分 共 10 分 徐峰得分 3 分 1 设 X 是一个线性规划问题的基本可行解 如果其中一个分量 xj 0 则 1 只有解不退化时 xj才是一个基变量 选择 2 只有解退化时 xj才是一个基变量 3 xj是非基变量 正确 4 无论解是否退化 xj一定是一个基变量 2 设一目标为极大化的线性规划有最优解 其对偶解的某一个分量大于零 则该分量对应的原问题的约束条件 1 可能是紧约束 也可能是松约束 正确 2 不可能是松约束 且当右边项增加时 其目标函数值上升 选择 3 只能是紧约束 且当右边项增加时 其目标函数值下降 4 只能是松约束 且当右边项发生变化时目标函数值不会变化 3 对一个求目标函数最大的混合整数规划问题 以下命题中不正确的是 选择 1 任一可行解的目标函数值不可能大于其松弛问题的目标函数最优 值 正确 2 该问题可行解的个数是有限的 3 该问题可行解中可能存在不取整数值的变量 4 其松弛问题的最优解可能是该整数规划问题的最优解 4 求总销量小于总产量的运输问题不需要做的是 1 虚设一个销地 2 令产地到虚设的销地的单位运费为 0 选择正确 3 删去一个产地 1 分 4 取虚设的销地的需求量为恰当值 5 设 P 是图 G 从 vs到 vt的最短路 则有 正确 1 P 的长度等于 P 的每条边的长度之和 2 P 的最短路长等于 vs到 vt的最大流量 选择 3 P 的长度等于 G 的每条边的长度之和 4 P 有 n 个点 n 1 条边 6 下列关于运输问题的说法正确的是 选择 1 运输问题的对偶问题不一定存在最优解 2 平衡运输问题的对偶问题的变量非负 3 若变量组 B 包含有闭回路 则 B 中的变量对应的列向量线性无关 正确 4 第 i 行的位势 Ui是第 i 个对偶变量 7 某商店经销某种饮料 据统计 饮料日需求量 单位 箱 的概率分布为 P 100 0 1 P 120 0 25 P 150 0 35 P 180 0 2 P 200 0 1 每天进货一 次 进价为 6 元 箱 零售价是 9 元 箱 若当天不能售完 则第二天可以 4 元 箱售完 为获得最大利润 商店每天应进饮料 1 120 箱 2 180 箱 选择正确 3 150 箱 1 分 4 200 箱 8 下例错误的说法是 选择 1 标准型的目标函数是求最小值 2 标准型的目标函数是求最大值 3 标准型的变量一定要非负 正确 4 标准型的常数项非正 9 在生产与存储问题中 选择正确 1 状态变量为存储量 决策变量是生产量 1 分 2 状态变量为生产量 决策变量是存储量 3 阶段指标函数是从第 k 阶段到第 n 阶段的总成本 4 过程指标函数是从第 k 阶段到下一阶段的总成本 10 已知某一求极大值的线性规划的最优目标函数值 如果加入一个新约束 则 1 无论加入什么样的约束 最优目标函数值不会下降 选择 2 只有新约束是小于等于约束时 最优目标函数值会下降 正确 3 无论加入什么样的约束 最优目标函数值不会上升 4 只有新约束是大于等于约束时 最优目标函数值会下降 四 计算题 题目 1 用图解法求解下列线性规划问题 题分 8 徐峰得分 8 max z x1 9x2 4x1 3x2 12 3x1 2x2 6 x1 x2 1 x1 x2 0 做题记录 见图 1 可行域见图 1 中灰色区域 目标函数初始线见图 1 中的 A1B1 线 结论 此 LP 有唯一最优解 x1 4 5 x2 9 5 目标函数最优值为 max z 17 图 1 徐峰所作的图 答案 见图 2 可行域见图 2 的灰色区域 图 2 中直线 A1B1 为目标函数等值线 此 LP 有唯一最优解 x1 4 5 x2 9 5 目标函数最优值为 max z 17 1 图 2 答案图 题目 2 用单纯形法求解下列线性规划问题 题分 9 徐峰得分 9 Maxz 9x1 x2 M 5x1 6x2 30 2x1 x2 2 x1 5 做题记录 已通过标准化 列单纯形表计算如下 cj0 91000 M CBXBbx1x2x3x4x5x6 Mx630 56 1001 0 x422 10100 0 x55100010 检验数 30M 5M 96M 1 M000 1x25 5 61 1 6001 6 0 x477 60 1 6101 6 0 x55100010 检验数 5 49 601 600 1 6 M 此 LP 为无界解 参考答案 列单纯形表迭代如下 cj0 91000 M CBXBbx1x2x3x4x5x6 Mx630 56 1001 0 x422 10100 0 x55100010 检验数 5M 96M 1 M000 1x25 5 61 1 6001 6 0 x477 60 1 6101 6 0 x55100010 检验数 49 601 600 M 1 6 此 LP 为无界解 题目 3 用对偶单纯形法求解下列线性规划问题 题分 8 徐峰得分 8 Maxz 6x1 6x2 4x1 5x2 20 x1 x2 1 4x1 x2 4 做题记录 已通过标准化 列单纯形表计算如下 cj0 6 6000 CBXBbx1x2x3x4x5 0 x3 20 45100 0 x4 1 11010 0 x5 4 4 1001 检验数 0 6 6000 6x151 5 4 1 400 0 x440 1 4 1 410 0 x5160 6 101 检验数 300 27 2 3 200 此 LP 的最优解为 X 5 0 0 4 16 min z 30 参考答案 列单纯形表迭代如下 cj0 6 6000 CBXBbx1x2x3x4x5 0 x3 20 45100 0 x4 1 11010 0 x5 4 4 1001 检验数 6 6000 6x151 5 4 1 400 0 x440 1 4 1 410 0 x5160 6 101 检验数 0 27 2 3 200 此 LP 的最优解为 X 5 0 0 4 16 min z 30 题目 4 求解下列运输问题 使总运费最小 题分 8 徐峰得分 4 单位运费与产量销量表 运费 B1B2B3B4 产量 A15714910 A210157645 A315919105 销量 8201616 做题过程 加括号的为检验数 其余为运输量 第 1 次运输方案与检验 表表 1 1 B1B1B2B2B3B3B4B4 产量产量 A1A18 82 2 15 11 1010 A2A2 3 1313161616164545 A3A3 8 5 5 18 10 5 5 销量销量 8 8202016161616 第 2 次运输方案与检验 表表 2 2 B1B1B2B2B3B3B4B4 产量产量 A1A1 7 71010 A2A28 85 5161616164545 A3A35 55 5 销量销量 8 8202016161616 表 2 所示运输方案为最优 最小总运费为 457 总运费计算错误 调整后的运输方案不是基本可行解 答案 第 1 次运输方案与检验 加括号的数字为检验数 其余的数字为运输量或产量和销量 表表 1 1 B1B1B2B2B3B3B4B4 产量产量 A1A18 82 2 15 11 1010 A2A2 3 1313161616164545 A3A3 8 5 5 18 10 5 5 销量销量 8 8202016161616 第 2 次运输方案与检验 表表 2 2 B1B1B2B2B3B3B4B4 产量产量 A4A4 3 1010 15 11 1010 A5A58 85 5161616164545 A6A6 11 5 5 18 10 5 5 销量销量 8 8202016161616 第 2 次检验数无负数 故第 2 次运输方案为最优 最小总运费为 478 题目 5 用匈牙利法求解下列指派问题 题分 8 徐峰得分 8 完成任务所需时间表 人 任务任务 1任务 2任务 3任务 4 第 1 人 810717 第 2 人 111239 第 3 人 771316 第 4 人 7667 做题记录 最优指派方案为 1 1 2 3 3 2 4 4 目标函数最小值为 25 答案 最优指派方案为 1 1 2 3 3 2 4 4 目标函数最小值为 25 题目 7 求下图中 v1至其它各点的最短路 题分 8 徐峰得分 8 做题过程 以 P 表示最短路标号 T 表示一般路程标号 标号过程如下 P vs 0 T v3 5 T v4 6 T v2 13 P v3 5 P v3 来自于点 v1 T v5 10 P v4 6 P v4 来自于点 v1 T v7 14 T v6 21 P v5 10 P v5 来自于点 v3 T v6 20 T v8 13 P v2 13 P v2 来自于点 v1 P v8 13 P v8 来自于点 v5 P v7 14 P v7 来自于点 v4 T v6 18 P v6 18 P v6 来自于点 v7 点 v1到其它各点的最短路见下图 答案 标号过程如下 P v1 0 T v2 13 T v3 5 T v4 6 P v3 5 P v3 来自于点 v1 T v2 13 T v4 6 T v5 10 P v4 6 P v4 来自于点 v1 T v2 13 T v5 10 T v6 21 T v7 14 P v5 10 P v5 来自于点 v3 T v2 13 T v6 20 T v7 14 T v8 13 P v2 13 P v2 来自于点 v1 T v6 20 T v7 14 T v8 13 P v8 13 P v8 来自于点 v5 T v6 20 T v7 14 P v7 14 P v7 来自于点 v4 T v6 18 P v6 18 P v6 来自于点 v7 点 v1到其它各点的最短路见下图 题目 8 求下图所示网络中 v1至 v8的最大流 并找出一个最小截集 题分 8 徐 峰得分 7 做题记录 第 1 次标号 s 0 2 s 3 6 2 1 t 6 1 点 v6标号错误 第 1 次增广链 v1 v2 v6 v8 第 1 次调整后的可行流如下图 第 2 次标号 s 0 2 s 2 6 2 2 7 6 2 t 7 2 第 2 次增广链 v1 v2 v6 v7 v8 第 2 次调整后的可行流如下图 第 3 次标号 s 0 已是最大流 最大流量为 11 最小截集为 v1 v4 v1 v2 v1 v3 答案 第 1 次标号 v1 0 v2 v1 3 v6 v2 3 v7 v6 3 v8 v7 3 第 1 次增广链 v1 v2 v6 v7 v8 第 1 次调整后的可行流如下图 第 2 次标号 v1 0 至此标号中断 收点 v8得不到标号 已无增广链 故调整后的流是最大流 最大流量为 11 最小截集为 v1 v2 v1 v3 v1 v4 题目 9 用动态规划方法求解下列资源分配问题 题分 8 徐峰得分 8 分配的资源数0 1 234 甲创的效益 0 9 11 14 14 乙创的效益 0 47 10 12 丙创的效益 0 11 14 17 17 做题记录 s01234 f3 s 011141717 u3 01234 f2 s 011151821 u2 001 1 2 1 2 3 u101234u1 1 s 40 219 1811 1514 1114 0f1 4 27 最优分配方案为 u 1 1 2 最大总效益为 27 答案 s01234 f3 s 011141717 u3 01234 f2 s 011151821 u2 0011 21 2 3 u101234u1 1 s 40 219 1811 151