资源描述
新 祥 旭 考 研 官 网 http:/www.xxxedu.net/2020 年 浙 江 师 范 大 学 888 运 筹 学 硕 士 研 究 生 入 学 考 试 初 试科 目考 试 大 纲科 目 代 码 、 名 称 : 运 筹 学适 用 专 业 : 0812z2 智 能 交 通 技 术一 、 考 试 形 式 与 试 卷 结 构（ 一 ） 试 卷 满 分 及 考 试 时 间本 试 卷 满 分 为 150 分 ， 考 试 时 间 为 180 分 钟 。（ 二 ） 答 题 方 式答 题 方 式 为 闭 卷 、 笔 试 。试 卷 由 试 题 和 答 题 纸 组 成 ； 答 案 必 须 写 在 答 题 纸 （ 由 考 点 提 供 ） 相 应 的 位 置 上 。（ 三 ） 试 卷 题 型 结 构单 选 题 ： 10 小 题 ， 每 小 题 2 分 ， 共 20 分填 空 题 ： 7 小 题 ， 每 空 2 分 ， 共 20 分简 答 题 ： 3 小 题 ， 每 小 题 5 分 ， 共 15 分建 模 题 ： 2 小 题 ， 每 小 题 10 分 ， 共 20 分计 算 题 ： 5 小 题 ， 每 小 题 15 分 ， 共 75 分二 、 考 查 目 标 （ 复 习 要 求 ）全 日 制 攻 读 硕 士 学 位 研 究 生 入 学 考 试 运 筹 学 科 目 考 试 内 容 包 括 线 性 规 划 、 整 数 规 划 、 运输 问 题 、 网 络 规 划 、 动 态 规 划 等 内 容 ， 要 求 考 生 系 统 掌 握 相 关 学 科 的 基 本 知 识 、 基 础 理 论 和基 本 方 法 ， 并 能 运 用 相 关 理 论 和 方 法 分 析 、 解 决 生 产 实 践 中 的 实 际 问 题 。三 、 考 查 范 围 或 考 试 内 容 概 要第 一 章 线 性 规 划1 线 性 规 划 问 题 数 学 模 型 的 三 个 要 素 （ 决 策 变 量 、 约 束 条 件 、 目 标 函 数 ）2 线 性 规 划 问 题 的 解 的 几 种 可 能 情 况 （ 无 可 行 解 、 有 无 界 解 、 有 唯 一 最 优 解 、有 无 穷 多 最 优 解 ） 。3 线 性 规 划 问 题 的 建 模 方 法 。4 线 性 规 划 问 题 数 学 模 型 的 一 般 形 式 及 标 准 形 式 。5 线 性 规 划 问 题 的 基 、 基 本 解 、 可 行 解 、 基 本 可 行 解 的 概 念 及 它 们 之 间 的 关系 。6 凸 集 的 概 念 。7 图 解 法 的 步 骤 及 几 何 意 义 。新 祥 旭 考 研 官 网 http:/www.xxxedu.net/8 单 纯 形 法 的 基 本 原 理 及 几 何 意 义 。9 单 纯 形 法 的 思 路 与 图 解 法 的 思 路 的 相 同 之 处 。10 单 纯 形 法 的 计 算 步 骤 及 实 际 运 用 。第 二 章 线 性 规 划 的 对 偶 理 论 与 灵 敏 度 分 析1 线 性 规 划 的 对 偶 问 题 。2 对 偶 问 题 的 性 质 （ 对 偶 性 定 理 、 松 弛 互 补 定 理 ） 。3 对 偶 单 纯 形 算 法 的 计 算 步 骤 及 实 际 应 用 。4 灵 敏 度 分 析 的 概 念 。5 利 用 单 纯 形 表 进 行 常 用 的 几 种 灵 敏 度 分 析 。第 三 章 运 输 问 题1 运 输 问 题 及 其 数 学 模 型 。2 用 表 上 作 业 法 求 解 产 销 平 衡 的 运 输 问 题 （ 西 北 角 法 、 最 小 元 素 法 、 位 势 法 ） 。3 会 将 产 销 不 平 衡 的 运 输 问 题 转 化 成 产 销 平 衡 问 题 并 用 表 上 作 业 法 求 解 。第 五 章 整 数 规 划1 整 数 规 划 的 概 念 、 特 点 和 数 学 模 型 。2 割 平 面 法 、 分 支 定 界 法 的 思 想 。3 会 用 割 平 面 法 求 解 纯 整 数 规 划 问 题 。4. 会 用 分 支 定 界 法 求 解 简 单 的 纯 整 数 规 划 问 题 。5. 会 用 匈 牙 利 算 法 求 解 最 优 分 配 问 题 （ 即 指 派 问 题 ） 。第 六 章 网 络 规 划 （ 图 论 ）1 图 的 基 本 概 念 。2 树 的 定 义 及 几 种 等 价 定 义 。3 会 用 狄 克 斯 特 拉 算 法 求 解 最 短 路 径 问 题 。4. 最 小 生 成 树 的 概 念 及 求 解 最 小 生 成 树 的 方 法 。5. 运 输 网 络 及 其 相 关 概 念 。6. 会 求 运 输 网 络 的 最 大 流 及 最 小 割 。第 八 章 动 态 规 划1 多 阶 段 的 决 策 问 题2 动 态 规 划 的 基 本 概 念 （ 包 括 阶 段 、 状 态 、 决 策 、 允 许 决 策 集 合 、 状 态 转 移方 程 、 递 归 方 程 等 ） 。3 动 态 规 划 的 逆 序 解 法 。4 动 态 规 划 的 应 用 ： 会 使 用 动 态 规 划 求 解 最 优 路 径 问 题 、 投 资 问 题 、 0-1 背包 问 题 等 。新 祥 旭 考 研 官 网 http:/www.xxxedu.net/参 考 教 材 或 主 要 参 考 书 ：1 运 筹 学 方 法 与 模 型 傅 家 良 主 编 复 旦 大 学 出 版 社 ， 2007.022 运 筹 学 教 程 第 三 版 胡 运 权 主 编 清 华 大 学 出 版 社 ， 2008.06四 、 样 卷（ 一 ） 单 项 选 择 题 （ 从 下 列 各 题 四 个 备 选 答 案 中 选 出 一 个 正 确 答 案 ， 答 案选 错 或 未 选 者 ， 该 题 不 得 分 。 每 小 题 2分 ， 共 20分 ）1. 在 线 性 规 划 模 型 中 ， 满 足 约 束 条 件 和 非 负 条 件 的 解 称 为 ( )A 基 本 解 B 基 本 可 行 解 C 可 行 解 D 最 优 解2. 线 性 规 划 可 行 域 的 顶 点 一 定 是 ( )A 基 本 可 行 解 B 最 优 解 C 非 可 行 解 D 非 基 本 解3. X 是 线 性 规 划 的 基 本 可 行 解 则 有 ( )A X 中 的 基 变 量 非 负 ， 非 基 变 量 为 零 B X 是 最 优 解C X 不 一 定 满 足 约 束 条 件 D X 中 的 基 变 量 非 零 ， 非 基 变 量为 零 4. 线 性 规 划 最 优 解 唯 一 是 指 ( )A 可 行 解 集 合 无 界 B 最 优 表 中 存 在 非 基 变 量 的 检 验数 为 零C 可 行 解 集 合 是 空 集 D 最 优 表 中 非 基 变 量 的 检 验 数 全 大于 零 5. 原 问 题 有 4个 变 量 3个 约 束 ， 其 对 偶 问 题 ( )A 有 3个 变 量 4个 约 束 B 有 4个 变 量 3个 约 束C 有 4个 变 量 3个 约 束 D 有 4个 变 量 4个 约 束6. 在 运 输 问 题 中 ， 每 次 迭 代 时 ， 如 果 有 某 非 基 变 量 的 检 验 数 等 于 零 ， 则 该运 输 问 题( )A 无 最 优 解 B 有 唯 一 最 优 解C 有 无 穷 多 个 最 优 解 D 不 确 定7. 对 偶 单 纯 形 法 中 ， 若 满 足 ( )， 则 原 问 题 没 有 可 行 解 。A 基 变 量 的 取 值 出 现 负 值新 祥 旭 考 研 官 网 http:/www.xxxedu.net/B 检 验 数 中 出 现 正 数C 检 验 数 全 部 小 于 零D 存 在 某 个 基 变 量 为 负 数 ， 且 其 所 在 行 的 系 数 全 部 大 于 或 等 于 零8. 若 树 T有 n个 顶 点 ， 那 么 它 的 边 数 一 定 是 ( )A n-1 B n+1 C n D n29. 原 问 题 与 对 偶 问 题 都 有 可 行 解 ， 则 有 ( )A、 原 问 题 有 最 优 解 ， 对 偶 问 题 可 能 没 有 最 优 解B、 原 问 题 与 对 偶 问 题 可 能 都 没 有 最 优 解C、 可 能 一 个 问 题 有 最 优 解 ， 另 一 个 问 题 具 有 无 界 解D、 原 问 题 与 对 偶 问 题 都 具 有 最 优 解10.用 割 平 面 法 求 解 整 数 规 划 时 ， 构 造 的 割 平 面 只 能 切 去 ( )A 整 数 可 行 解 B 整 数 解 最 优 解 C 非 整 数 解 D 无 法 确 定（ 二 ） 填 空 题 （ 每 空 格 2分 ， 共 20 分 ）1. 线 性 规 划 解 的 情 形 有 唯 一 最 优 解 、 、 和 无 可行 解 。2. 如 果 在 线 性 规 划 模 型 中 变 量 xj 的 符 号 不 受 限 制 ， 即 变 量 xj 取 正 值 ， 取 负值 或 取 零 都 可 以 ， 则 称 xj为 。3. 如 果 线 性 规 划 问 题 (LP)的 基 本 解 又 满 足 非 负 条 件 ， 即 有 0ib (i=1, ,m)，则 称 它 为 (LP)的 一 个 。4. 线 性 规 划 问 题 的 标 准 形 式 的 特 点 为 目 标 函 数 求 最 小值 、 、 和 右 端 常 数 项 都 非 负 。5. 树 连 通 ， 但 不 存 在 。6. 如 果 某 一 整 数 规 划 ：Min Z=-7X1-9X2-X1+3X2 67X1+ X2 35X1, X2 0且 均 为 整 数所 对 应 的 线 性 规 划 （ 松 弛 问 题 ） 的 最 优 解 为 X1=9/2， X2=7/2， Min Z=-63，新 祥 旭 考 研 官 网 http:/www.xxxedu.net/我 们 现 在 要 对 X1进 行 分 枝 ， 应 该 分 为 和 。7. 求 解 非 负 赋 权 图 的 最 短 路 径 问 题 的 较 好 算 法 是 。（ 三 ） 简 答 题 （ 共 3小 题 ， 每 题 5 分 ， 共 15分 ）1. 线 性 规 划 只 要 有 可 行 解 一 定 有 基 本 可 行 解 。 那 么 ， 能 否 确 定 一 定 存 在 最 优解 ？2. 已 知 原 问 题 有 最 优 解 ， 那 么 对 偶 问 题 呢 ？ 它 们 的 什 么 是 相 等 的 ？3. 为 什 么 说 任 一 运 输 网 络 中 至 少 存 在 一 个 可 行 流 ？（ 四 ） 建 模 题 （ 共 2小 题 ， 每 题 10 分 ， 共 20分 ）1. 一 个 车 间 要 加 工 3种 零 件 ， 其 需 要 量 分 别 为 4000件 、 5000件 和 3500件 .车 间 内 现 有 4台 机 床 ， 都 可 用 来 加 工 这 3种 零 件 ， 每 台 机 床 可 利 用 的 工 时 分 别 为1600,1250,1800 和 2000. 机 床 i#加 工 零 件 j#所 需 工 时 和 成 本 由 表 1 给 出 ， 问 如何 安 排 生 产 ， 才 能 使 生 产 成 本 最 低 ， 请 列 出 数 学 模 型 ， 不 需 要 求 解 。表 12. 写 出 下 列 线 性 规 划 问 题 的 对 偶 问 题 ：Max f =3x1-2x2-5x3-8x5;s.t. 2x1+3x2-3x3- x4 -5x5 -2,x2-2x3+3x4 +4x5=-5,-x1+2x3 -2x4 -3x5 -5.x1 0, x2无 约 束 , x30, x40, x5无 约 束 .（ 五 ） 计 算 题 （ 共 5小 题 ， 每 题 15 分 ）1. 用 单 纯 形 法 求 解 下 列 线 性 规 划 问 题 ：min f =-5x1-4x2;新 祥 旭 考 研 官 网 http:/www.xxxedu.net/s.t. x1+2x2 6,2x1 -x2 4,5x1+3x2 15,x1 0, x2 0.2. 求 解 表 2所 给 运 输 问 题 ：(1) 用 西 北 角 法 求 初 始 解 ；(2) 用 位 势 法 求 最 优 解 。 表 23. 用 割 平 面 法 求 解 下 列 整 数 规 划 ：min f =-3x1-4x2;s.t. 2x1+5x2+x3 =15,2x1-2x2+x4 =5,xj 0, 整 数 , j=1,2,3,4.已 知 相 应 的 (LP)的 最 优 单 纯 形 表 如 表 3所 示 。表 3XB x1 x2 x3 x4 bx2 0 1 1/7 -1/7 10/7x1 1 0 1/7 5/14 55/14r 0 0 1 1/2 35/24. 求 图 1中 v1至 v10的 最 短 路 径 和 长 度 。新 祥 旭 考 研 官 网 http:/www.xxxedu.net/图 15. 求 运 输 网 络 图 图 2的 最 大 流 及 最 小 割 。图 2
展开阅读全文