运筹学试题及答案.pdf

第 1 页 共 4 页 陕西理工学院考试试卷陕西理工学院考试试卷 A A 卷卷答案答案 2010 2011 学年 第一学期 科目 科目 运筹学与最优化运筹学与最优化 数数学学 系系 数学与应用数学数学与应用数学 专业专业 081081 083083 班班 题号题号 一一 二二 三三 四四 五五 六六 七七 八八 九九 十十 总分总分 得分得分 阅卷人阅卷人 一 判断题 1 若标准形式的线性规划问题有有限的最优值 则一定存在一个基本可行解是最优值 2 目标规划的数学模型与线性规划的数学模型结构形式上有本质区别 3 变量 222333311112 xxxxxx 可以构成闭回路 4 树必连通 但连通图不一定是树 5 一 个 可 行 流 是 最 大 流 当 且 仅 当 不 存 在 关 于 它 的 从 起 点 到 终 点 的 增 广 路 二 填空题 1 若线性规划可行域有界 则目标函数一定在 可行域的顶点 处达到最优 2 对偶单纯形法的核心是保持基的 对偶可行 性 3 目标规划中若要求恰好达到目标值 则目标函数应当为 min ddfz 4 任一个图中 奇点的个数为 偶数 5 图 G 有支撑树的充分必要条件是图 G 是 连通的 三 计算题 1 写出线性规划问题的对偶问题 已知对偶问题的最优解为1 4 2 1 yy 求原问题的 最优解 12 分 0 12222 82 652max 4321 431 4321 i x xxxx xxx xxxxz 解 由原问题可以得到其对偶问题 0 62 5 12 222 128min 21 21 21 2 21 21 yy yy yy y yy yyz 6 分 将最优解1 4 2 1 yy带入 有 10 2 2 1 5 5 6 6 由互补松弛性条件得 34 34 xx8 x2x 12 求解得 34 x4 x4 原问题的最优解为 T X 4 4 0 0 6 分 2 用伏格尔法确定下表中的运输问题的初始基可行解 12 分 销地 甲 乙 丙 丁 产量 1 3 7 6 4 5 2 2 4 3 2 2 3 4 3 8 5 3 销量 3 3 2 2 解 计算各行 各列的最小运费和次小运费的差额 得 3 分 销地 产地 甲 乙 丙 丁 行差额 1 3 7 6 4 1 2 2 4 3 2 0 3 4 3 8 5 1 系名 姓名 学号 考试日期 班级 装 订 线 下 上 装 订 线 第 2 页 共 4 页 2 列差额 1 1 3 2 从 行 列 差 额 中 选 出 最 大 者 3 选 择 它 所 在 的 丙 列 中 最 小 元 素 3 取 2 2 2min 23 x 重新调整产量与销量 在单位运价表里划去第 2 行与丙列 在空格 4 2 2 2 1 2 3 3 3 1 中任选一个填入 0 再计算各行 各列的最小运费和次小运费 的差额 得 3 分 销地 产地 甲 乙 丁 行差额 1 3 7 4 1 3 4 3 5 1 列差额 1 4 1 从行列差额中选出最大者 4 选择它所在的乙列中最小元素 3 取 3 3 3min 32 x 重 新调整产量与销量 在单位运价表里划去第 3 行与乙列 在空格 2 1 4 3 1 3 中任选一 个填入 0 再计算各行 各列的最小运费和次小运费的差额 得 3 分 销地 产地 甲 丁 行差额 1 3 4 1 列差额 3 4 从 行 列 差 额 中 选 出 最 大 者 4 选 择 它 所 在 的 丁 列 中 最 小 元 素 4 取 2 5 2min 14 x 在单位运价表里划去丁列 取 3 3 3min 11 x 划去第一行 第 一列 得初始解为 3 分 销地 产地 甲 乙 丙 丁 产量 1 3 0 2 5 2 2 0 2 3 3 3 销量 3 3 2 2 3 利用割平面法求解 2 12 12 12 max 326 320 0 x xx stxx x x 整数 解 求解其松弛问题 0 P 对应的最优解为 T x 2 3 1 0 最优值为 2 3 z 4 分 由于 0 x不是整数向量 增加割平面条件 2 1 4 1 4 1 43 xx 利用对偶单纯形法求解其对应的 松弛问题 1 P 得其最优解 T x 1 3 2 1 4 分 再增加割平面条件 3 2 3 2 3 2 14 sx 利用对偶单纯形法求解对应的松弛问题 2 P 得最优 解 T x 1 1 2 即为所求整数规划问题的最优解 4 分 4 运用逆推解法求解下列问题 2 123 maxzxxx 123 0 01 2 3 i xxxcc xi 解 按问题的变量个数划分三个阶段 设状态变量 1 s 2 s 3 s 4 s 并记 1 sc 取问题 中的变量 i x 为决策变量 各阶段指标函数按乘积方式结合 令最优值函数 kk fs 表示第k阶 段的初始状态为 k s 从k 阶段到第 3 阶段所得的最大值 设 33 xs 223 sxs 112 csxs 则有 csxsxxs 112233 0 0 3 分 运用逆推法 有 3333 33 33 max sxsxsf sx max max 22 2 2 220 33 2 2 220 22 xsxxfxsf sxsx 运用微分法得 22 3 2 sx 为极 第 3 页 共 4 页 3 3 v 4 v t v 2 v s v 4 7 1 4 9 3 3 3 大值点 故 22 3 222 3 2 27 4 sxssf 27 4 max max 3 111 110 221 110 11 xsxxfxsf sxsx 同样运用微分法得 11 4 1 sx 为 极大值点 故 11 4 111 4 1 64 1 sxssf 由于已知 cs 1 故可得最优解为 cx 4 1 1 ccsx 2 1 4 3 3 2 3 2 22 cccxssx 4 1 2 1 4 3 2233 最优值为 4 1 64 1 maxccfz 9 分 四 解答题 1 某工厂生产 A B 两种产品 A B 产品的价格分别为 2 万元和 5 万元 又知每生产 A B 的所需原料 机器台数和每天的供应量如下表 问如何生产以取得最大产值 当原料 I 的 日供应量变为 8kg 时 又应如何安排生产 14 分 产品 A 产品 B 日供应量 kg 原料 I 1 0 4 原料 II 0 2 12 机器台数 3 2 18 解 设生产 A 产品 1 x件 生产 B 产品 1 x件 根据题目要求建立线性规划模型 0 1823 122 4 52max 21 21 2 1 21 xx xx x x xxz 3 分 化为标准形式 0 1823 122 4 00052max 21 621 52 41 65421 xx xxx xx xx xxxxxz c 2 5 0 0 0 CB xB b X1 X2 X3 X4 X5 0 X3 4 1 0 1 0 0 0 X4 12 0 2 0 1 0 6 0 X5 18 3 2 0 0 1 9 2 5 X3 4 1 0 1 0 0 4 5 X2 6 0 1 0 1 2 0 X5 6 3 0 0 1 1 2 2 0 0 5 2 0 X3 2 0 0 1 1 3 1 3 5 X2 6 0 1 0 1 2 0 2 X1 2 1 0 0 1 3 1 3 0 0 0 11 6 2 3 此时检验数全小于等于 0 故线性规划达到最优解 x1 2 x2 6 目标函数 z 34 5 分 当原料 I 的供应变为 8kg 时 2 6 6 18 12 8 3 13 10 02 10 3 13 11 bBb 单纯形表变为 c 2 5 0 0 0 CB xB b X1 X2 X3 X4 X5 X3 6 0 0 1 1 3 1 3 5 X2 6 0 1 0 1 2 0 2 X1 2 1 0 0 1 3 1 3 0 0 0 11 6 2 3 检验数仍然全部小于等于 0 故此时最优解不变 6 分 2 求下列网络的最大流问题 弧旁的数为 i j c 13 分 第 4 页 共 4 页 4 解 取零流作为初始流 1 分 给 ts vvv 2 标号 找到增广链 s v ts vvv 2 3 1 调整流量有 3 3 22 ts ff 其它仍为零流 给 ts vvv 3 标号 找到增广链