运筹学课后习题答案--林齐宁版本--北邮出版社.doc

1、运 筹 学 作 业 标 准 答 案 (教 师 用 ) 1No.1 线 性 规 划1、 某 织 带 厂 生 产 A、 B 两 种 纱 线 和 C、 D 两 种 纱 带 ， 纱 带 由 专 门 纱 线 加 工 而成 。 这 四 种 产 品 的 产 值 、 成 本 、 加 工 工 时 等 资 料 列 表 如 下 ：产 品项 目A B C D单 位 产 值 (元 ) 168 140 1050 406单 位 成 本 (元 ) 42 28 350 140单 位 纺 纱 用 时 (h) 3 2 10 4单 位 织 带 用 时 (h) 0 0 2 0.5工 厂 有 供 纺 纱 的 总 工 时 7200h， 织

2、 带 的 总 工 时 1200h。(1) 列 出 线 性 规 划 模 型 ， 以 便 确 定 产 品 的 数 量 使 总 利 润 最 大 ；(2) 如 果 组 织 这 次 生 产 具 有 一 次 性 的 投 入 20 万 元 ， 模 型 有 什 么 变 化 ？ 对 模 型的 解 是 否 有 影 响 ？解 ： (1)设 A 的 产 量 为 x1， B 的 产 量 为 x2， C 的 产 量 为 x3， D 的 产 量 为 x4，则 有 线 性 规 划 模 型 如 下 ：max f(x)=(16842)x1 +(14028)x2 +(1050350)x3 +(406140)x4=126 x1 +1

3、12 x2 +700 x3 +266 x4s.t. 4, ,5. 33ixi(2)如 果 组 织 这 次 生 产 有 一 次 性 的 投 入 20 万 元 ， 由 于 与 产 品 的 生 产 量 无 关 ，故 上 述 模 型 只 需 要 在 目 标 函 数 中 减 去 一 个 常 数 20 万 ， 因 此 可 知 对 模 型 的解 没 有 影 响 。2、 将 下 列 线 性 规 划 化 为 极 大 化 的 标 准 形 式解 ： 将 约 束 条 件 中 的 第 一 行 的 右 端 项 变 为 正 值 ， 并添 加 松 弛 变 量 x4， 在 第 二 行 添 加 人 工 变 量 x5， 将第 三

4、行 约 束 的 绝 对 值 号 打 开 ， 变 为 两 个 不 等 式 ，分 别 添 加 松 弛 变 量 x6, x7， 并 令 ， 则33有maxf(x)= 2 x1 3 x2 5( )+0 x4 M x5+0 x6 +0 x73s.t. 0, 13 5719 6 96764324xx不 限321321 ,0,|579| 66 .)(inxxtsf运 筹 学 作 业 标 准 答 案 (教 师 用 ) 23、 用 单 纯 形 法 解 下 面 的 线 性 规 划 ,0,425.2136 .)(max112xtsxf解 ： 在 约 束 行 1,2,3 分 别 添 加 x4, x5, x6 松 弛

5、变 量 ， 有 初 始 基 础 可 行 解 和 单 纯 形法 迭 代 步 骤 如 下 ：Cj 2 5 3 0 0 0CB XB b x1 x2 x3 x4 x5 x6 bi/aij*0 x4 610 3 2 1 1 0 0 610/20 x5 125 1 (6) 3 0 1 0 125/6*0 x6 420 2 1 1/2 0 0 1 420/1OBJ= 0 zj 0 0 0 0 0 0cj - zj 2 5 3 0 0 0Cj 2 5 3 0 0 0CB XB b x1 x2 x3 x4 x5 x6 bi/aij*0 x4 1705/3 (10/3) 0 2 1 1/3 0 170.55 x

6、2 125/6 1/6 1 1/2 0 1/6 0 0 x6 2395/6 11/6 0 0 0 1/6 1 OBJ= 625/6 zj 5/6 5 5/2 0 5/6 0cj - zj 17/6 0 1/2 0 5/6 0Cj 2 5 3 0 0 0CB XB b x1 x2 x3 x4 x5 x6 bi/aij*2 x1 341/2 1 0 3/5 3/10 1/10 0 5 x5 197/4 0 1 (2/5) 1/20 3/20 0 125.1250 x6 2847/4 0 0 11/10 11/20 7/20 1 OBJ= 2349/4 zj 2 5 4/5 17/20 11/20

7、0cj - zj 0 0 11/5 0 11/20 0Cj 2 5 3 0 0 0CB XB b x1 x2 x3 x4 x5 x6 bi/aij*2 x1 1955/8 1 3/2 0 3/8 1/8 03 x3 985/8 0 5/2 1 1/8 3/8 00 x6 13555/16 0 11/4 0 11/16 1/16 1OBJ= 6865/8 zj 2 21/2 3 9/8 11/8 0cj - zj 0 11/2 0 9/8 11/8 0答 ： 最 优 解 为 x1 =244.375, x2 =0, x3 =123.125, 剩 余 变 量 x6 =847.1875； 最 优解 的

8、 目 标 函 数 值 为 858.125。运 筹 学 作 业 标 准 答 案 (教 师 用 ) 3No.2 两 阶 段 法 和 大 M 法解 ： 将 原 问 题 变 为 第 一 阶 段 的 标 准 型0,75382 .0)(max6413621xtsf第 一 阶 段 单 纯 形 表Cj 0 0 0 0 1 1CB XB b x1 x2 x3 x4 x5 x6 bi/aij*1 x5 80 1 2 1 0 1 0 801 x6 75 (3) 1 0 1 0 1 75/3*OBJ= 155 zj 4 3 1 1 1 1cj - zj 4 3 1 1 0 0Cj 0 0 0 0 1 1CB XB b

9、 x1 x2 x3 x4 x5 x6 bi/aij*1 x5 55 0 (5/3) 1 1/3 1 1/3 553/5*0 x1 25 1 1/3 0 1/3 0 1/3 253OBJ= 55 zj 0 5/3 1 1/3 1 1/3cj - zj 0 5/3 1 1/3 0 4/3Cj 0 0 0 0 1 1CB XB b x1 x2 x3 x4 x5 x6 bi/aij*0 x2 33 0 1 3/5 1/5 3/5 1/50 x1 14 1 0 1/5 2/5 1/5 2/5OBJ= 0 zj 0 0 0 0 0 0cj - zj 0 0 0 0 1 1第 二 阶 段Cj 4 6 0 0

10、CB XB b x1 x2 x3 x4 bi/aij*6 x2 33 0 1 3/5 1/54 x1 14 1 0 1/5 2/5OBJ= 254 zj 4 6 14/5 2/5cj - zj 0 0 14/5 2/5答 ： 最 优 解 为 x1 =14， x2 =33， 目 标 函 数 值 为 254。1、 用 两 阶 段 法 解 下 面 问 题 ：,75380 .64)(min2121xtsf运 筹 学 作 业 标 准 答 案 (教 师 用 ) 42、 用 大 M 法 解 下 面 问 题 ， 并 讨 论 问 题 的 解 ,0,5216593 . 210)(max313xtsxf解 ： 第

11、1、 2 行 约 束 条 件 添 加 x4, x5 松 弛 变 量 ， 第 3 行 添 加 x6 剩 余 变 量 和 x7人 工 变 量 ， 有 如 下 初 始 单 纯 形 表 和 迭 代 步 骤 ：Cj 10 15 12 0 0 0 MCB XB b x1 x2 x3 x4 x5 x6 x70 x4 9 (5) 3 1 1 0 0 00 x5 15 5 6 15 0 1 0 0M x7 5 2 1 1 0 0 1 1OBJ= 5M zj 2M M M 0 0 M Mcj - zj 10+2M 15+M 12+M 0 0 M 0Cj 10 15 12 0 0 0 MCB XB b x1 x2

12、x3 x4 x5 x6 x710 x1 9/5 1 3/5 1/5 1/5 0 0 00 x5 24 0 9 (16) 1 1 0 0M x7 7/5 0 1/5 3/5 2/5 0 1 1OBJ= 187M/5 zj 10 6+M/5 23M/5 2+2M/5 0 M Mcj - zj 0 9M/5 10+3M/5 22M/5 0 M 0Cj 10 15 12 0 0 0 MCB XB b x1 x2 x3 x4 x5 x6 x710 x1 3/2 1 39/80 0 3/10 1/10 0 012 x3 3/2 0 9/16 1 1/20 3/20 0 0M x7 1/2 0 43/80

13、0 11/20 7/20 1 1OBJ= 33M/2 zj 10 93/8+43M/80 12 21/8+7M/16 5/8+3M/80 M Mcj - zj 0 27/843M/80 0 21/87M/16 5/83M/80 M 0答 ： 最 后 单 纯 形 表 中 检 验 数 都 小 于 等 于 0， 已 满 足 最 优 解 判 定 条 件 ， 但 人 工变 量 x7 仍 未 迭 代 出 去 ， 可 知 原 问 题 无 可 行 解 (无 解 )。运 筹 学 作 业 标 准 答 案 (教 师 用 ) 5No.3 线 性 规 划 的 对 偶 问 题解 ： 对 偶 问 题 为不321312,0,

14、 5 . 64)(minyyytsg0,12 8 4 631321xxx不令 改 写 后 约 束 条 件 每 行 对 应 的 对 偶 变 量 为 y1,.,y6， 则 有 对 偶 规 划 如 下 ：0, ,0,8 3 4 . 2126)(max642531 51yytsyyg1、 写 出 下 列 线 性 规 划 问 题 的 对 偶 问 题 ：(1) 不43214321 ,0,6 5 .)(maxxxtsxf(2) 81246.3)(min321xtsxf解 ： 原 问 题 的 约 束 条 件 可 改 写 为 右 式运 筹 学 作 业 标 准 答 案 (教 师 用 ) 62、 写 出 下 问 题

15、 的 对 偶 问 题 ， 解 对 偶 问 题 ， 并 证 明 原 问 题 无 可 行 解解 ： 对 偶 问 题 为 约 束 条 件 标 准 化 为0,324.)(min11ytsg0,3 +24 5431yy有 对 偶 问 题 解 的 单 纯 形 表 如 下 ：Cj 1 1 1 0 0CB YB b y1 y2 y3 y4 y50 y4 4 1 0 1 1 00 y5 3 1 (1) 2 0 1OBJ= 0 zj 0 0 0 0 0zj cj 1 1 1 0 0Cj 1 1 1 0 0CB YB b y1 y2 y3 y y50 y4 4 1 0 (1) 1 01 y2 3 1 1 2 0 1

16、OBJ= 3 zj 1 1 2 0 1zj cj 0 0 1 0 1Cj 1 1 1 0 0CB YB b y1 y2 y3 y4 y51 y3 4 1 0 1 1 01 y2 11 3 1 0 2 1OBJ= 7 zj 2 1 1 1 1zj cj 1 0 0 1 1入 变 量答 ： 迭 代 到 第 三 步 ， x1 为 入 变 量 ， 但 主 列 中 技 术 系 数 全 为 负 值 ， 故 对 偶 问 题 有可 行 解 但 解 无 界 ， 由 弱 对 偶 定 理 推 论 可 知 ， 原 问 题 无 可 行 解 。 ,0,12 .34)(max121xtsxf运 筹 学 作 业 标 准 答

17、案 (教 师 用 ) 73、 用 对 偶 单 纯 形 法 求 下 面 问 题0,75382 .64)(min121xtsf解 ：Cj 4 6 0 0 min( zj - cj)/ai*jCB XB b x1 x2 x3 x4 ai*j00 x3 80 1 (2) 1 0 4,3*0 x4 75 3 1 0 1OBJ= 0 zj 0 0 0 0zj - cj 4 6 0 0Cj 4 6 0 0CB XB b x1 x2 x3 x46 x2 40 1/2 1 1/2 00 x4 35 (5/2) 0 1/2 1 2/5*,6OBJ= 240 zj 3 6 3 0zj - cj 1 0 3 0Cj

18、4 6 0 0CB XB b x1 x2 x3 x46 x2 33 0 1 3/5 1/54 x1 14 1 0 1/5 2/5OBJ= 254 zj 4 6 14/5 2/5zj - cj 0 0 14/5 2/5答 ： 最 优 解 为 x1 =14， x2 =33， 目 标 函 数 值 为 254。No.4 线 性 规 划 的 灵 敏 度 分 析1、 下 表 是 一 线 性 规 划 最 优 解 的 单 纯 形 表Cj 21 9 4 0 0 0CB XB b x1 x2 x3 x4 x5 x621 x1 4 1 0 1/3 2/3 0 1/30 x5 2 0 0 2/3 4/3 1 1/39

19、 x2 23 0 1 1/3 1/3 0 2/3zj 21 9 10 11 0 1cj zj 0 0 6 11 0 1原 问 题 为 max 型 ， x4， x5 为 松 驰 变 量 ， x6 为 剩 余 变 量 ， 回 答 下 列 问 题 ：(1)资 源 1、 2、 3 的 边 际 值 各 是 多 少 ？ (x4， x5 是 资 源 1、 2 的 松 驰 变 量 ， x6 是资 源 3 的 剩 余 变 量 )(2)求 C1, C2 和 C3 的 灵 敏 度 范 围 ；(3)求 b1， b2 的 灵 敏 度 范 围 。解 ： (1) q1 =11, q2 =0, q3 = 1。(2) x1 ,

20、 x2 为 基 变 量 ， 故运 筹 学 作 业 标 准 答 案 (教 师 用 ) 8max/,/max,.61321186533111CCC/in/, .13285052 22 9x3 为 非 基 变 量 ， 故 CC3610(3) 5.6 /1,34min/24a1 bb同 理 有 2No.5 运 输 问 题1、 分 别 用 西 北 角 法 、 最 低 费 用 法 和 运 费 差 额 法 ， 求 下 面 运 输 问 题 (见 表 )的初 始 可 行 解 ， 并 计 算 其 目 标 函 数 。 (可 不 写 步 骤 )2、 以 上 题 中 最 低 费 用 法 所 得 的 解 为 初 始 基

21、础 可 性 解 ， 用 表 上 作 业 法 （ 踏 石 法 ）求 出 最 优 解 。 （ 要 求 列 出 每 一 步 的 运 费 矩 阵 和 基 础 可 行 解 矩 阵 ）销 地产 地B1 B2 B3 B4 B5 产 量A1 6 9 4 8 5 20A2 10 6 12 8 7 30A3 6 5 9 20 9 40A4 2 13 6 14 3 60销 量 25 15 35 45 30(2) 最 低 费 用 法20 x143015 10 1525 5 30OBJ 955 运 费 表 (检 验 数 zij |wij )0 6 0 9 4 (15) 8 1 5 4-7 10 -7 6 -3 12 8

22、 -6 7 35 6 5 9 20 6 9 92 2 13 6 17 14 3 64 4 0 11 3运 费 表 (检 验 数 zij |wij )0 6 0 9 4 8 1 5 40 10 0 6 4 12 8 1 7 4解 ： (1) 西 北 角 法205 15 1025 1530 30OBJ 1415(2) 差 额 法5 153015 2525 5 30OBJ 850迭 代 后 的 分 配 表 xij 5 153015 2525 5 30OBJ 850运 筹 学 作 业 标 准 答 案 (教 师 用 ) 95 6 5 9 13 20 6 9 92 2 13 6 10 14 3 64 4

23、0 4 3答 ： x13=5, x14=15, x24=30, x32=15, x33=25, x41=25, x43=5, x45=30, OBJ=850。No.6 指 派 问 题1、 有 4 个 工 人 。 要 指 派 他 们 分 别 完 成 4 项 工 作 。 每 人 做 各 项 工 作 所 消 耗 的 时间 (h) 如 下 表 ， 问 如 何 分 派 工 作 ， 使 总 的 消 耗 时 间 最 少 ？消 耗 工 作工 人A B C D甲 3 3 5 3乙 3 2 5 2丙 1 5 1 6丁 4 6 4 10解 ： 变 换 效 率 矩 阵 如 下 ：3 3 5 3 逐 (0) 0* 2

24、0* 逐 (0) 0* 2 0*3 2 5 2 行 1 0 3 0 列 1 (0) 3 0*1 5 1 6 标 0* 4 (0) 5 标 0* 4 (0) 54 6 4 10 记 0* 2 0* 6 记 0* 2 0* 6每 行 每 列 都 有 两 个 以 上 的 0 未 找 到 最 优 解4 (0) 0* 2 0* 重 0* (0) 2 0*8 1 (0) 3 0* 新 1 0* 3 (0)5 0* 4 (0) 5 标 0* 4 (0) 51 0* 2 0* 6 记 (0) 2 0* 62 6 3 7划 线 过 程 (发 现 有 4 条 直 线 ) 找 到 最 优 解答 ： 容 易 看 出

25、， 共 有 四 个 最 优 解 ： 甲 B， 乙 D， 丙 A， 丁 C； 甲 D， 乙 B， 丙 A， 丁 C； 甲 B， 乙 D， 丙 C， 丁 A； 甲D， 乙 B， 丙 C， 丁 A； OBJ=10。下 面 是 用 匈 亚 利 算 法 求 解 的 过 程 ： 1.5 2.5 1.5 2.50.5 3 3 5 (3)-0.5 3 (2) 5 2-0.5 (1) 5 1 6* 0.5 4 6 4 10slack 2 3 2 7nbour 4 4 4 4S*=1 1 2 1 2* 0 3 3 5 30 3 (2) 5 20 (1) 5 1 6* 0 4 6 4 10slack 2 1 3 1

26、nbour 1 1 4 1S*=0.5*运 筹 学 作 业 标 准 答 案 (教 师 用 ) 10 2.5 3.5 2.5 3.5-0.5 3 3 5 (3)-1.5 3 (2) 5 2-1.5 1 5 (1) 61.5 (4) 6 4 10slacknbour第 二 个 最 优 解 ： OBJ 102、 学 生 A、 B、 C、 D 的 各 门 成 绩 如 下 表 ， 现 将 此 4 名 学 生 派 去 参 加 各 门 课的 单 项 竞 赛 。 竞 赛 同 时 举 行 ， 每 人 只 能 参 加 一 项 。 若 以 他 们 的 成 绩 为 选 派 依 据 ，应 如 何 指 派 最 有 利 ？

27、得 分 课 程学 生数 学 物 理 化 学 外 语A 89 92 68 81B 87 88 65 78C 95 90 85 72D 75 78 89 96解 ： 变 换 效 率 矩 阵 为 适 用 于 min 化 问 题 ， 用 96 减 去 上 面 矩 阵 中 所 有 元 素 值 ，7 4 28 15 逐 3 0 24 11 逐 3 (0) 17 11 39 8 31 18 行 1 0 23 10 列 1 0* 16 10 11 6 11 24 变 0 5 10 23 变 (0) 5 3 2321 18 7 0 换 21 18 7 0 换 21 18 (0) 0*22 (0) 16 10 5

28、 2 (0) 13 7 答 ： A 物 理(0) 0* 15 9 3 (0) 0* 12 6 B 数 学 OBJ=0* 6 3 23 1 0* 6 (0) 20 C 化 学 36021 19 (0) 0* 24 22 0* (0) D 外 语2 4No.7 动 态 规 划1、 某 公 司 有 9 个 推 销 员 在 全 国 三 个 不 同 市 场 里 推 销 货 物 ， 这 三 个 市 场 里 推 销员 人 数 与 收 益 的 关 系 如 下 表 ， 做 出 各 市 场 推 销 人 员 数 的 分 配 方 案 ， 使 总 收 益 最大 。推 销 员市 场0 1 2 3 4 5 6 7 8 91

29、 20 32 47 57 66 71 82 90 100 1102 40 50 60 71 82 93 104 115 125 1353 50 61 72 84 97 109 120 131 140 150解 ： 令 分 配 到 各 地 区 的 推 销 员 人 数 为 决 策 变 量 xk ， k=1,2,3 代 表 第 1、 2、 3地 区 ； 令 各 地 区 可 供 分 配 的 推 销 员 人 数 为 状 态 变 量 sk 。 最 先 分 配 给 第 1 地 2.5 3.5 2.5 3.5-0.5 3 3 5 (3)-1.5 3 (2) 5 2-1.5 (1) 5 1 61.5 4 6 (4) 10slacknbour第 一 个 最 优 解 ： OBJ 10