运筹学期末考试试卷1.pdf

运 筹 学 期 考 试 试 卷 学 院 班 级 姓 名 学 号 运 筹 学(I)课 程 试 卷 A(本 卷 考 试 时 间 1 2 0分 钟)题 号 一 二 三 四 五 去 七 八 九 十 总 得 分 题 分 15 13 10 12 10 10 10 10 10 100得 分 一、辨 析 题(注：请 详 细 说 明 理 由)。(每 小 题 3 分，本 题 共 1 5分)1.一 个 极 小 化 线 性 规 划 的 某 轮 表 格 中 有 r=(-1,-2,0,0,0),请 问 是 否 可 以 选 择 西 作 为 进 基 变 量？为 什 么？2.线 性 规 划 原 问 题 向 n C X|A X 2 4?0 和 对 偶 问 题 m axb7u A U a5、分 别 为 何 值 时：(本 题 共 1 3分)XB x?七%当 bX3-3 0 1 0-1 2x231 1 0 0 2a4X4a20 0 1 4ra50 0 0a6(1)(1)表 中 给 出 线 性 规 划 是 唯 一 解;(2)表 中 给 出 线 性 规 划 有 无 穷 多 解;表 中 给 出 线 性 规 划 的 可 行 解 无 界;(4)表 中 给 出 线 性 规 划 为 换 入 变 量，/为 换 出 变 量;三、给 出 线 性 规 划：(本 题 共 10分)max f=6 2 2X2+3x3s,t 2项-冗？+2*3 2$+4x3 0 x20 0四、已 知 线 性 规 划：(本 题 共 12分)(1)写 出 对 偶 问 题；(2)已 知 X|=4,%=6,%3=(),是 上 述 线 性 规 划 的 最 优 解，用 互 补 松 弛 定 理 求 对 偶 问 题 的 最 优 解。max/=7xj+1 2X2+10 x3S.t X+*2+*3 V 22X j+2X2+/0 x2 0 x3 0标 准 化 后 的 初 始 表 和 最 优 表 如 下（/=一/）CjCB XB-7-1 2-1 0 0 0Xi x2 x3 x4 x5b0 X40 X51 1 1 1 02 2 1 0 12030r-7-1 2-1 0 0 0-1 0 x3-1 2 X20 0 1 2-11 1 0-1 11010r 5 0 0 8 2(1)求 对 偶 问，(2)若 该 L P:题 的 最 优 解。可 题 原 目 标 函 数 中 X i 的 系 数 由 7 变 为 9,问 最 优 解 有 什 么 变 化?叩 的(40、(3)若 右 端 常 数 由 130)变 为(30),问 最 优 解 有 什 么 变 化?五、若 发 点 A,4 及 收 点 用，层，纭 的 有 关 数 据 如 下 表 所 示。假 定 4,4 处 允 许 物 资 存 储，问 怎 样 调 配 以 使 总 的 支 付 费 用 最 少？试 建 立 运 输 模 型 再 进 行 求 解。(本 题 共 10分)4 4 4供 应 量 存 储 费44 6 86 2 4200200需 求 量 50 100 100六、用 分 支 定 界 法 求 解 整 数 规 划 问 题：（本 题 共 10分）max z=3%+2x2st 211+2X2 7%)2x2 2龙：0,不 为 整 数，i=l,2七、已 知 4 个 人 做 4 件 事 情 的 收 益 如 下 表，问 如 何 分 配 任 务 使 得 收 益 最 大 化。A-X164I41 1八、用 Dijkstra法 求 w到 各 顶 点 的 最 短 路。（本 题 共 1 0分）65V6匕 1 5 3九、下 图 中 弧 旁 的 数 字（目，4）（4 表 示 容 量，力 表 示 流 量）：（本 题 共 io分）（2）求 网 络 的 最 大 流；（3）证 明（2）中 求 出 的 流 是 最 大 流。海，彩 枝 4 人 孝（勤 奋、求 是、创 新、奉 献）2 0 0 5 2 0 0 6学 年 第 二 学 期 考 试 试 卷 主 考 教 师：_学 院 班 级 姓 名 学 号 运 筹 学（I）课 程 试 卷 A 参 考 答 案（本 卷 考 试 时 间 120分 钟）题 号 一 二 三 四 五 六 七 八 九 十 总 得 分 题 分 15 13 10 12 10 10 10 10 10 100得 分 一、辨 析 题（本 题 共 5 小 题，每 小 题 3 分，共 15分）1.答：可 以。（1分）因 为 王 所 对 应 的 检 验 数 为“-1”，把 玉 作 为 进 基 变 量，仍 然 可 以 改 进 目 标 函 数 值。（2 分）2.答：对。（1分）因 为 原 问 题 和 对 偶 问 题 都 有 可 行 解，则 两 问 题 必 有 最 优 解，则 依 照 对 偶 问 题 的 性 质 可 知，原 问 题 的 目 标 函 数 值 一 定 大 于 等 于 对 偶 问 题 的 目 标 函 数 值。（2 分）3.答：不 可 以。（1分）因 为 该 线 性 规 划 只 有 4 个 独 立 约 束，则 相 应 基 变 量 只 有 4 个，则 X 的 解 中 最 多 只 有 4 个 是 非 零。（2 分）4.答：独 立 约 束 条 件 有 m+n-1个。（1分）因 为，该 运 输 问 题 数 学 模 型 中 虽 然 有 m+n个 约 束 条 件，但 其 中 一 个 是 沉 余 项，约 束 条 件 中 实 际 只 有 m+n-1个 条 件 是 独 立 的。（2 分）5.答：不 是 唯 一。（1分）因 为 赋 权 图 中 边 的 所 赋 权 可 能 是 相 同 的，在 这 种 情 况 下 得 到 的 最 小 生 成 树 就 不 唯 的。（2 分）二、解：（1）。4,。50,4。（3 分）（2）%W 0、“2 W 0。4,%=0,4 0。（3 分）（3）%20,a5 0,a 0,a20（3 分）!（4）”42,%0,%0,且 出 卬 或 4 4 2 0,%0,4 忘 0,%0。（4 分）三、解：（1）其 对 偶 问 题 如 下:min Z=2%+4%S T2M,+M2 6_%-22ut+4a2 2 3%0,%。（3 分）（2）使 用 互 补 松 弛 定 理，得 到 如 下 结 果：（其 中，为 U 取 最 优 解 时 约 束 条 件 不 等 号 左 右 两 边 的 差 值，i=1，2,3.）min Z=2%+也 s.t 2U+U26u-22u+4%3Wj 0 u2 0由 此 得 到：|=0,A2=0O X 玉（=4）=0A2 X X2（=6）=0 3 X（=0）=0（2 分）（2 分）所 以：2%+w2=6 uj=2 V-M,=-2 得 到：%=2（2 分）则 对 偶 问 题 的 最 优 解 为 U=（2,2），（1分）四、解：（1）根 据 对 偶 问 题 最 优 解 与 原 问 题 最 优 表 的 联 系，可 以 直 接 得 到 对 偶 问 题 的 最 优 解 为：八（8,2），（3 分）（2）由 题 意 可 知：A Ci=2,6=5 2=3,因 此 可 知：该 最 优 表 中 的 最 优 基 不 变，所 以：最 优 解 不 发 生 变 化。（3 分）（3）由 最 优 表 中 的 信 息 可 得：（T 分）则 5=B-h=2-1丫 40、1 人 30,5 0、（2 分）50将 1代 替 最 优 表 中 的,采 用 对 偶 单 纯 形 法 继 续 求 角 碎 得 到 最 终 最 优 表 为 CB XBX,x2 x3 x4 x5b-10 X30 X42 2 1 0 1-1-1 0 1-13010r 13 8 0 0 10（2 分）由 此 可 知：最 优 解 产 生 了 变 化，且 最 优 解 为 X*=（0,0,30,10,0）；（1分）五、解：该 运 输 问 题 为 产 销 的 问 题，虚 拟 销 地 8，形 成 新 的 问 题：耳 供 应 量 24 6 8 5 2006 2 4 4 200需 求 里 50 100 100 150设 4 一 约 的 运 输 量 为 看,由 就 的 塔 轮 问 蹲 注 以 得 劄：.min F=4玉+6xI2+8x13+5x14+ox21+2x22+4x23+4x244xu+6玉 2+8斗 3+5X14=2006XZ 91 I+2XZ 9Z 7+4x）4=200乙 3 244 卬+6X2 1=506X1 2+2.2=1008XI3+4X23=1005XI4+4X94=150X户 0,i=l,2.J=l,2,3,4.（2 分）使 用 最 小 元 素 法 得 到 初 始 解：修 生 可 出 供 应 量 250 100 50100 100200200需 求 里 50 100 100 150（2 分）使 用 位 势 法，得 到 检 验 数 为:用 斗 鸟 丛%欠 V.0 3 0 03 0-3 00-1J 4 3 8 5增 加 A2 f 4 的 运 输 量，得 到 新 的 解 为:纥 鸟 层 1供 应 量 工 501000100150 20020050 100 100 150（2 分）使 用 位 势 法，得 到 检 验 数 为:4 B2 鸟 乩%XV.0 0 0 06 0 0 30-4J 4 6 8 5因 此 可 知:为 该 运 输 问 题 的 最 优 解。（2分）耳 层 可 1供 应 量 2501000100150 200200而 况 里 50 100 100 150六、解：采 用 分 支 定 界 法 进 行 求 解，其 求 解 枚 举 树 图 如 下:（%）9（/）8（2）17/2由 分 支 定 界 法 求 解 过 程 可 知，最 优 解 为 X=（2/），其 对 应 的 最 优 值 为：/*=8。（2分）七、解：注 意 到 本 题 要 求 求 解 收 益 最 大 化，因 此 按 照 极 大 化 问 题 转 化 为 极 小 化 问 题 的 原 则，并 按 照 匈 牙 利 方 法 计 算 如 下：-11-6-14-7-8-7-12-5-9-8-10-8-12、-10-7-6-12-1(1-14-8140101 24 132:(2 分)6)IQ0)13,1 0),、-1-1o 2),(2分)4，9 3,（2 分）43232从 而 得 到 本 题 的 最 优 分 配 方 案 I：A2-B4,4 当,一 冬.，最 优 分 配 方 案 11：4-四,4 f 与，4-4,4 f 鸟。最 大 收 益 为 4。（2 分）八、%0 6 95 7（10 分）匕 九、用 标 号 法 求 最 大 t,并 给 与 证 明。（本 题 共 X 分）解：对 于 任 何 一 个 边 上.的 流 量“都 满.-4 d 且 在 该 运 输 网 络 中 间 顶 点 都 满 足 流 量 守 恒 条 件,所 以，该 图 中 的 流 为 可 行 流。(3分)(6,1)3)在 该 运 输 网 络 中 找 到 不 他 和 心.(1,0)调 整 量 为。=1,得 到 新 的 流:匕 V%匕 V（2 分）再 找 到 不 饱 利 链:(6.1)调 整 量 为 6=3,得 到 新 的 流:岭 上 图 即 为 最 大 流。（3 分）（3）由 上 图 中 的/中 不 存 在/的 增 流 链，因 此 上 图 中 的 流/即 为 最 大 流。（2 分）S=VS,V1,V2 S*=V3,V4,VtC（S,S*）=Valf=6