资源描述
第 1 页 共 11 页 运 筹 学 试 题 参 考 答 案 一 、 填 空 题 每 空 2 分 共 1 0 分 1 、 在 线 性 规 划 问 题 中 称 满 足 所 有 约 束 条 件 方 程 和 非 负 限 制 的 解 为 可 行 解 。 2 、 在 线 性 规 划 问 题 中 图 解 法 适 合 用 于 处 理 变 量 为 两 个 的 线 性 规 划 问 题 。 3 、 求 解 不 平 衡 的 运 输 问 题 的 基 本 思 想 是 设 立 虚 供 地 或 虚 需 求 点 化 为 供 求 平 衡 的 标 准 形 式 。 4 、 在 图 论 中 称 无 圈 的 连 通 图 为 树 。 5 、 运 输 问 题 中 求 初 始 基 本 可 行 解 的 方 法 通 常 有 最 小 费 用 法 、 西 北 角 法 两 种 方 法 。 二 、 每 小 题 5 分 共 1 0 分 用 图 解 法 求 解 下 列 线 性 规 划 问 题 1 m a x z = 6 x 1 + 4 x 2 0 7 8 1 02 21 2 21 21 xx x xx xx 解 此 题 在 “ 运 筹 学 复 习 参 考 资 料. doc ” 中 已 有 不 再 重 复 。 2 m i n z = 3 x 1 + 2 x 2 0, 13 72 1 04 2 242 21 21 21 21 21 xx xx xx xx xx 解 、 、 第 2 页 共 11 页 可 行 解 域 为 a b c d a 最 优 解 为 b 点 。 由 方 程 组 02 242 221 xxx 解 出 x 1 = 1 1 x 2 = 0 X * = 21xx = 1 1 0 T m i n z = 3 1 1 + 2 0 = 3 3 三 、 1 5 分 某 厂 生 产 甲 、 乙 两 种 产 品 这 两 种 产 品 均 需 要 A 、 B 、 C 三 种 资 源 每 种 产 品 的 资 源 消 耗 量 及 单 位 产 品 销 售 后 所 能 获 得 的 利 润 值 以 及 这 三 种 资 源 的 储 备 如 下 表 所 示 A B C 甲 9 4 3 70 乙 4 6 10 120 360 200 300 1 建 立 使 得 该 厂 能 获 得 最 大 利 润 的 生 产 计 划 的 线 性 规 划 模 型 5 分 第 3 页 共 11 页 2 用 单 纯 形 法 求 该 问 题 的 最 优 解 。 1 0 分 解 1 建 立 线 性 规 划 数 学 模 型 设 甲 、 乙 产 品 的 生 产 数 量 应 为 x 1 、 x 2 则 x 1 、 x 2 0 设 z 是 产 品 售 后 的 总 利 润 则 m a x z = 7 0 x 1 + 1 2 0 x 2 s . t . 0 3 0 01 03 2 0 064 3 6 049 21 21 21 21 xx xx xx xx 2 用 单 纯 形 法 求 最 优 解 加 入 松 弛 变 量 x 3 x 4 x 5 得 到 等 效 的 标 准 模 型 m a x z = 7 0 x 1 + 1 2 0 x 2 + 0 x 3 + 0 x 4 + 0 x 5 s . t . 5, . . . ,2,1,0 3 0 01 03 2 0 064 3 6 049 521 421 321 jx xxx xxx xxx j 列 表 计 算 如 下 第 4 页 共 11 页 C B X B b 7 0 1 2 0 0 0 0 L x 1 x 2 x 3 x 4 x 5 0 x 3 3 6 0 9 4 1 0 0 9 0 0 x 4 2 0 0 4 6 0 1 0 1 0 0 / 3 0 x 5 3 0 0 3 1 0 0 0 1 3 0 0 0 0 0 0 7 0 1 2 0 0 0 0 0 x 3 2 4 0 3 9 / 5 0 1 0 - 2 / 5 4 0 0 / 1 3 0 x 4 2 0 1 1 / 5 0 0 1 - 3 / 5 1 0 0 / 1 1 1 2 0 x 2 3 0 3 / 1 0 1 0 0 1 / 1 0 1 0 0 3 6 1 2 0 0 0 1 2 3 4 0 0 0 1 2 0 x 3 1 8 6 0 / 1 1 0 0 1 3 9 / 1 1 1 9 / 1 1 7 0 x 1 1 0 0 / 1 1 1 0 0 5 / 1 1 - 3 / 1 1 1 2 0 x 2 3 0 0 / 1 1 0 1 0 - 3 / 2 2 2 / 1 1 1 14 3 0 0 0 7 0 1 2 0 0 1 7 0 / 1 1 3 0 / 1 1 0 0 0 - 1 7 0 / 1 1 3 0 / 1 1 X * = 1 11 0 0 1 13 0 0 1 11 8 6 0 0 0 T m a x z = 7 0 1 11 0 0 + 1 2 0 1 13 0 0 = 1 14 3 0 0 0 四 、 1 0 分 用 大 M 法 或 对 偶 单 纯 形 法 求 解 如 下 线 性 规 划 模 型 m i n z = 5 x 1 2 x 2 4 x 3 0, 1 0536 423 321 321 321 xxx xxx xxx 第 5 页 共 11 页 解 用 大 M 法 先 化 为 等 效 的 标 准 模 型 m a x z / = 5 x 1 2 x 2 4 x 3 s . t . 5, . . . ,2,1,0 1 0536 423 5321 4321 jy xxxx xxxx j 增 加 人 工 变 量 x 6 、 x 7 得 到 m a x z / = 5 x 1 2 x 2 4 x 3 M x 6 M x 7 s . t 7, . . . ,2,1,0 1 0536 423 75321 64321 jx xxxxx xxxxx j 大 M 法 单 纯 形 表 求 解 过 程 如 下 第 6 页 共 11 页 C B X B b 5 2 4 0 0 M M L x 1 x 2 x 3 x 4 x 5 x 6 x 7 M x 6 4 3 1 2 1 0 1 0 4 / 3 M x 7 1 0 6 3 5 0 1 0 1 5 / 3 9 M 4 M 7 M M M M M 9 M 5 4 M 2 7 M 4 M M 0 0 5 x 1 4 / 3 1 1 / 3 2 / 3 1 / 3 0 1 / 3 0 M x 7 2 0 1 1 2 1 2 1 1 5 - M 5/3 - M 10/3 -2 M+5/3 M 2 M 5/3 - M 0 M 1/3 M 2/3 2 M 5/3 M 3 M+5/3 0 5 x 1 5 / 3 1 1 / 2 5 / 6 0 1 / 6 0 1 / 6 1 0 / 3 0 x 4 1 0 1 / 2 1 / 2 1 1 / 2 1 1 / 2 2 5 5 / 2 2 5 / 6 0 5 / 6 0 5 / 6 0 1 / 2 1 / 6 0 5 / 6 M M+ 5 / 6 5 2 x 1 2 / 3 1 0 1 / 3 1 1 / 3 1 1 / 3 x 2 2 0 1 1 2 1 2 1 32 2 5 2 1 1 / 3 1 1 / 3 1 1 / 3 0 0 1 / 3 1 1 / 3 M+ 1 M+ 1 / 3 x * = 32 2 0 0 0 T 最 优 目 标 函 数 值 m i n z = m a x z / = 32 2 = 32 2 五 、 1 5 分 给 定 下 列 运 输 问 题 表 中 数 据 为 产 地 A i 到 销 地 B j 的 单 位 运 费 第 7 页 共 11 页 B1 B2 B3 B4 s i A1 A2 A3 1 2 3 4 8 7 6 5 9 1 0 1 1 9 1 0 8 0 1 5 d j 8 2 2 1 2 1 8 1 用 最 小 费 用 法 求 初 始 运 输 方 案 并 写 出 相 应 的 总 运 费 5 分 2 用 1 得 到 的 基 本 可 行 解 继 续 迭 代 求 该 问 题 的 最 优 解 。 1 0 分 解 用 “ 表 上 作 业 法 ” 求 解 。 1 先 用 最 小 费 用 法 最 小 元 素 法 求 此 问 题 的 初 始 基 本 可 行 解 B 1 B 2 B 3 B 4 S i A 1 1 2 3 4 10 8 2 A 2 8 7 6 5 20 2 18 A 3 9 10 11 9 30 20 10 d j 8 22 12 18 6 0 6 0 初 始 方 案 Z = 1 8 + 2 2 + 6 2 + 5 1 8 + 1 0 2 0 + 1 1 1 0 = 4 2 4 2 1 8 B 3 B 4 A 2 2 0 1 0 B 2 B 3 A 3 销 地 费 用 产 地 8 2 B 1 B 2 A 1 第 8 页 共 11 页 2 用 闭 回 路 法 求 检 验 数 B 1 B 2 B 3 B 4 S i A 1 1 2 3 0 4 2 10 8 2 A 2 8 4 7 2 6 5 20 2 18 A 3 9 0 10 11 9 1 30 20 10 d j 8 22 12 18 6 0 6 0 34 = 1 0 其 余 j 0 选 34x 作 为 入 基 变 量 迭 代 调 整 。 用 表 上 闭 回 路 法 进 行 迭 代 调 整 B 1 B 2 B 3 B 4 S i A 1 1 2 3 1 4 3 10 8 2 A 2 8 3 7 1 6 5 20 1 2 8 A 3 9 0 10 11 1 9 30 20 1 0 d j 8 22 12 18 6 0 6 0 调 整 后 从 上 表 可 看 出 所 有 检 验 数 j 0 已 得 最 优 解 。 最 优 方 案 为 销 地 费 用 产 地 销 地 费 用 产 地 第 9 页 共 11 页 最 小 运 费 Z = 1 8 + 2 2 + 6 1 2 + 5 8 + 1 0 2 0 + 9 1 0 = 4 1 4 六 、8 分 有 甲 、 乙 、 丙 、 丁 四 个 人 要 分 别 指 派 他 们 完 成 A 、B 、C 、D 四 项 不 同 的 工 作 每 人 做 各 项 工 作 所 消 耗 的 时 间 如 下 表 所 示 A B C D 甲 2 1 0 9 7 乙 1 5 4 1 4 8 丙 1 3 1 4 1 6 1 1 丁 4 1 5 1 3 9 问 应 该 如 何 指 派 才 能 使 总 的 消 耗 时 间 为 最 少 解 用 “ 匈 牙 利 法 ” 求 解 。 效 率 矩 阵 表 示 为 913154 11161413 814415 79102 591 10 0532 41 001 1 5780 541 20 0)0(32 45)0(1 1 528)0( * * 541 20 0)0(32 45)0(1 1 528)0( * * 行约简 1 2 8 B 3 B 4 A 2 2 0 1 0 B 2 B 4 A 3 8 2 B 1 B 2 A 1 标号 列约简 第 10 页 共 11 页 321 0)0( )0(034 45)0(1 3 3)0(60 * * 至 此 已 得 最 优 解 0001 1000 0010 0100 使 总 消 耗 时 间 为 最 少 的 分 配 任 务 方 案 为 甲 C 乙 B 丙 D 丁 A 此 时 总 消 耗 时 间 W = 9 + 4 + 1 1 + 4 = 2 8 七 、 6 分 计 算 下 图 所 示 的 网 络 从 A 点 到 F 点 的 最 短 路 线 及 其 长 度 。 此 题 在 “ 运 筹 学 参 考 综 合 习 题 我 站 搜 集 信 息 自 编 . doc ” 中 已 有 。 解 此 为 动 态 规 划 之 “ 最 短 路 问 题 ” 可 用 逆 向 追 踪 “ 图 上 标 号 法 ” 解 决 如 下 4 3 7 3 5 1 9 1 2 5 7 9 6 2 4 2 4 4 6 8 5 1 5 4 5 4 A B1 B2 B3 C1 C2 C3 D1 D2 D3 E 1 E 2 F 第 11 页 共 11 页 最 佳 策 略 为 A B 2 C 1 D 1 E 2 F 此 时 的 最 短 距 离 为 5 + 4 + 1 + 2 + 2 = 1 4 1 7 3 4 3 2 0 1 2 5 7 9 6 2 4 2 4 4 6 8 5 1 5 4 5 4 A B1 B2 B3 C1 C2 C3 D1 D2 D3 E 1 E 2 F 5 9 1 4 7 7 11 8 5 9 1 2 1 4 1 4
展开阅读全文