运筹学1至6章习题参考答案

运筹学 第 3 版 习题答案1 运筹学运筹学 1 至至 6 章习题参考答案章习题参考答案 第第1章章 线性规划线性规划 1 1 工厂每月生产 A B C 三种产品 单件产品的原材料消耗量 设备台时的消耗量 资 源限量及单件产品利润如表 1 23 所示 表表1 23 产品 资源 ABC资源限量 材料 kg 1 51 242500 设备 台时 31 61 21400 利润 元 件 101412 根据市场需求 预测三种产品最低月需求量分别是 150 260 和 120 最高月需求是 250 310 和 130 试建立该问题的数学模型 使每月利润最大 解解 设 x1 x2 x3分别为产品 A B C 的产量 则数学模型为 123 123 123 1 2 3 123 max101412 1 51 242500 31 61 21400 150250 260310 120130 0 Zxxx xxx xxx x x x x x x 1 2 建筑公司需要用 5m 长的塑钢材料制作 A B 两种型号的窗架 两种窗架所需材料规格 及数量如表 1 24 所示 表表1 24 窗架所需材料规格及数量窗架所需材料规格及数量 型号 A型号 B 长度 m 数量 根 长度 m 数量 根 A1 22B1 2 52 每套窗架需要 材料 A2 1 53B2 23 需要量 套 300400 问怎样下料使得 1 用料最少 2 余料最少 解解 第一步 求下料方案 见下表 方案一二三四五六七八九十需要量 B12 52111000000800 B2201002110001200 A120010010210600 A21 50001002023900 余料 m 00 50 51110100 5 第二步 建立线性规划数学模型 设 xj j 1 2 10 为第 j 种方案使用原材料的根数 则 1 用料最少数学模型为 运筹学 第 3 版 习题答案2 10 1 1234 2567 3689 47910 min 2800 21200 2600 223900 0 1 2 10 j j j Zx xxxx xxxx xxxx xxxx xj 2 余料最少数学模型为 23456810 1234 2567 3689 47910 min0 50 50 5 2800 21200 2600 223900 0 1 2 10 j Zxxxxxxx xxxx xxxx xxxx xxxx xj 1 3 某企业需要制定 1 6 月份产品 A 的生产与销售计划 已知产品 A 每月底交货 市场需 求没有限制 由于仓库容量有限 仓库最多库存产品 A1000 件 1 月初仓库库存 200 件 1 6 月份产品 A 的单件成本与售价如表 1 25 所示 表 1 25 月份1 2 3 4 5 6 产品成本 元 件 销售价格 元 件 300 330 320 360 360 300 350 340 350 420 410 340 1 1 6 月份产品 A 各生产与销售多少总利润最大 建立数学模型 2 当 1 月初库存量为零并且要求 6 月底需要库存 200 件时 模型如何变化 解解 设 xj yj j 1 2 6 分别为 1 6 月份的生产量和销售量 则数学模型为 运筹学 第 3 版 习题答案3 1 1122334 45566 1 112 11223 1122334 112233445 11223344556 max300350330340320350360 420360410300340 800 800 800 800 800 Zxyxyxyx yxyxy x xyx xyxyx xyxyxyx xyxyxyxyx xyxyxyxyxyx 11 1122 112233 11223344 1122334455 112233445566 800 200 200 200 200 200 200 0 1 2 6 jj xy xyxy xyxyxy xyxyxyxy xyxyxyxyxy xyxyxyxyxyxy xyj 2 目标函数不变 前 6 个约束右端常数 800 改为 1000 第 7 11 个约束右端常数 200 改为 0 第 12 个约束 200 改为 200 1 4 某投资人现有下列四种投资机会 三年内每年年初都有 3 万元 不计利息 可供投资 方案一 在三年内投资人应在每年年初投资 一年结算一次 年收益率是 20 下一年可 继续将本息投入获利 方案二 在三年内投资人应在第一年年初投资 两年结算一次 收益率是 50 下一年可 继续将本息投入获利 这种投资最多不超过 2 万元 方案三 在三年内投资人应在第二年年初投资 两年结算一次 收益率是 60 这种投资 最多不超过 1 5 万元 方案四 在三年内投资人应在第三年年初投资 一年结算一次 年收益率是 30 这种投 资最多不超过 1 万元 投资人应采用怎样的投资决策使三年的总收益最大 建立数学模型 解解 是设 xij为第 i 年投入第 j 项目的资金数 变量表如下 项目一项目二项目三项目四 第 1 年 第 2 年 第 3 年 x11 x21 x31 x12 x23 x34 数学模型为 运筹学 第 3 版 习题答案4 112131122334 1112 112123 12213134 12 23 34 max0 20 20 20 50 60 3 30000 1 230000 1 51 230000 20000 15000 10000 0 1 3 1 4 ij Zxxxxxx xx xxx xxxx x x x xij 最优解 X 30000 0 66000 0 0 Z 84720 1 5 炼油厂计划生产三种成品油 不同的成品油由半成品油混合而成 例如高级汽油可以 由中石脑油 重整汽油和裂化汽油混合 辛烷值不低于 94 每桶利润 5 元 见表 1 26 表 1 26 成品油高级汽油一般汽油航空煤油一般煤油 半成品油 中石脑油 重整汽油 裂化汽油 中石脑油 重整汽油 裂化汽油 轻油 裂化 油 重油 残油 轻油 裂化 油 重油 残油按 10 4 3 1 调合 而成 辛烷值 94 84 蒸汽压 公斤 平方厘米 1 利润 元 桶 54 231 5 半成品油的辛烷值 气压 及每天可供应数量见表 1 27 表 1 27 问炼油厂每天生产多少桶成品油利润最大 建立数学模型 解解 设 xij为第 i i 1 2 3 4 种成品油配第 j j 1 2 7 种半成品油的数量 桶 总利润 1112132122233435363744454647 5 4 2 3 1 5 Zxxxxxxxxxxxxxx 高级汽油和一般汽油的辛烷值约束 111213212223 111213212223 8011510580115105 94 8494 xxxxxx xxxxxx 航空煤油蒸气压约束 34353637 34353637 1 50 60 05 1 xxxx xxxx 一般煤油比例约束 半成品油1 中石脑油2 重整汽油3 裂化汽油4 轻油5 裂化油6 重油7 残油 辛烷值80115105 蒸汽压 公斤 平方厘米 1 01 50 60 05 每天供应数量 桶 200010001500120010001000800 运筹学 第 3 版 习题答案5 44454647 10 4 3 1xxxx 即 454644 454647 1043 431 xxx xxx 半成品油供应量约束 1121 1222 1323 3444 3545 3646 3747 2000 1000 1500 1200 1000 1000 800 xx xx xx xx xx xx xx 整理后得到 111213212223 3435363744454647 111213 212223 212223 353637 4445 4546 464 max5554 24 24 2 33331 51 51 51 5 1421110 1421110 431210 0 50 40 950 4100 340 3 Zxxxxxx xxxxxxxx xxx xxx xxx xxx xx xx xx 7 1121 1222 1323 3444 3545 3646 3747 0 2000 1000 1500 1200 1000 1000 800 0 1 2 3 4 1 2 7 ij xx xx xx xx xx xx xx xij 1 6 图解下列线性规划并指出解的形式 1 12 12 1 2 12 max52 28 3 5 0 Zxx xx x x x x 解解 最优解 X 3 2 最优值 Z 19 运筹学 第 3 版 习题答案6 2 12 12 12 12 12 max4 45 32 24 0 Zxx xx xx xx x x 解解 有多重解 最优解 X 1 0 5 4 X 2 3 1 2 最优值 Z 5 运筹学 第 3 版 习题答案7 3 12 12 12 12 12 12 min32 211 410 27 31 0 Zxx xx xx xx xx x x 解解 最优解 X 4 1 最优值 Z 10 有唯一最优解 4 12 12 12 2 12 min46 28 8 3 0 0 Zxx xx xx x xx 解解 最优解 X 2 3 最优值 Z 26 有唯一最优解 运筹学 第 3 版 习题答案8 5 0 6 3 2 2max 21 2 1 21 21 xx x x xx xxZ 解解 无界解 运筹学 第 3 版 习题答案9 6 12 12 12 12 min25 26 2 0 Zxx xx xx x x 解解 无可行解 运筹学 第 3 版 习题答案10 1 7 将下列线性规划化为标准形式 1 123 123 123 123 123 min6 315 57432 10365 0 0 Zxxx xxx xxx xxx xxx 无限制 解解 1 令为松驰变量 则标准形式为 654 3 33 xxxxxx 1233 12334 12335 12336 1233456 max6 3315 574432 103665 0 Zxxxx xxxxx xxxxx xxxxx x x x x x x x 2 123 123 1 12 123 min935 674 20 5 88 0 0 0 Zxxx xxx x xx xxx 解解 2 将绝对值化为两个不等式 则标准形式为 运筹学 第 3 版 习题答案11 123 1234 1235 16 12 123456 max935 67420 67420 5 88 0 Zxxx xxxx xxxx xx xx x x x x x x 3 12 1 12 12 max23 15 1 0 0 Zxx x xx xx 解解 方法1 12 13 14 12 1234 max23 1 5 1 0 Zxx xx xx xx x x x x 方法2 令 11111 1 1 5 14xxxxx 有 12 1 12 12 max2 1 3 4 1 1 0 Zxx x xx x x 则标准型为 12 13 12 123 max223 4 0 0 Zxx xx xx x x x 4 12123 123 123 123 123 maxmin 34 230 4215 965 0 Zxx xxx xxx xxx xxx xxx 无约束 解解 令 线性规划模型变为 12123111 34 yxxyxxx xxx 运筹学 第 3 版 习题答案12 112 1123 1123 1123 1123 1123 max 3 4 230 4 215 9 65 0 Zy yxxx yxxxx xxxx xxxx xxxx x x xx 标准型为 1124 11235 11236 11237 11238 112345678 max 3340 0 230 44215 9965 0 Zy yxxxx yxxxxx xxxxx xxxxx xxxxx x x x x x x x xx 1 8 设线性规划 12 123 124 max52 2240 4260 0 1 4 j Zxx xxx xxx xj 取基分别指出对应的基变量和非基变量 求出基本 12 2120 4021 BB BB 12 和 解 并说明是不是可行基 BB 12 解解 B1 x1 x3为基变量 x2 x4为非基变量 基本解为 X 15 0 10 0 T B1是可 行基 B2 x2 x4是基变量 x1 x3为非基变量 基本解 X 0 20 0 100 T B2是可 行基 1 9 分别用图解法和单纯形法求解下列线性规划 指出单纯形法迭代的每一步的基可行解对 应于图形上的那一个极点 1 12 12 12 12 max3 22 2312 0 Zxx xx xx x x 解解 图解法 运筹学 第 3 版 习题答案13 单纯形法 单纯形法 C j 1300 C i Basis X1X2X3X4 bRatio 0X3 2 1 1022 0X42301124 C j Z j 13000 3X2 21102M 0X4 8 0 3160 75 C j Z j 70 306 3X2010 250 257 2 1X110 0 3750 1253 4 C j Z j 00 0 375 0 87545 4 对应的顶点 基可行解可行域的顶点 X 1 0 0 2 12 X 2 0 2 0 6 X 3 0 0 2 7 4 3 0 0 0 2 2 7 4 3 最优解 4 45 2 7 4 3 ZX 运筹学 第 3 版 习题答案14 2 12 12 12 12 12 min35 26 410 4 0 0 Zxx xx xx xx xx 解解 图解法 单纯形法 C j 3 5000 Basis C i X1X2X3X4X5 bRatio X301210063 X401 4 010102 5 X501100144 C j Z j 3 50000 X30 0 5 01 0 5012 X2 50 25100 2502 510 X500 7500 0 2511 52 C j Z j 1 75001 250 12 5 X1 3102 102M X2 501 0 50 5024 X5000 1 5 0 5 100 C j Z j 003 5 0 50 16 X1 310 1022 X2 50110 12 X4000 3120 C j Z j 00201 16 运筹学 第 3 版 习题答案15 对应的顶点 基可行解可行域的顶点 X 1 0 0 6 10 4 X 2 0 2 5 1 0 1 5 X 3 2 2 0 0 0 X 4 2 2 0 0 0 0 0 0 2 5 2 2 2 2 最优解 X 2 2 0 0 0 最优值 Z 16 该题是退化基本可行解 5 个基本可行解对应 4 个极点 1 10 用单纯形法求解下列线性规划 1 123 123 123 max34 234 223 0 1 2 3 j Zxxx xxx xxx xj 解解 单纯形表 C j 34100 BasisC i X1X2X3X4X5 R H S Ratio X402 3 11044 3 X501220133 2 C j Z j 341000 X24 2 3 11 31 30 4 32 X50 1 304 3 2 311 3M C j Z j 1 30 1 3 4 30 16 3 X1313 21 21 202 X5001 23 2 1 211 C j Z j 0 1 2 1 2 3 20 6 最优解 X 2 0 0 0 1 最优值 Z 6 2 1234 1234 1234 1234 max235 53730 310 26420 0 1 4 j Zxxxx xxxx xxxx xxxx xj 解解 单纯形表 C j 21 35000 BasisC i X1X2X3X4X5X6X7 R H S Ratio X50153 710030M X603 1 1 10101010 X702 6 1 4 001205 运筹学 第 3 版 习题答案16 C j Z j 21 35000 X509 2 11 25 40107 465M X605 2 1 2 5 4001 1 4510 X451 2 3 2 1 41001 45M C j Z j 1 217 2 7 4000 5 4 X50320150111 1120M X21515 2002 1 21010 X45807 2103 1 220M C j Z j 430 2300 173 因为因为 7 3 0 并且并且 ai70 原问题无可行解 两阶段法两阶段法 第一阶段 数学模型为 6 123 124 1256 min 539 5615 25 0 1 2 6 j Zx xxx xxx xxxx xj C j 000001R H S Ratio BasisC i X1X2X3X4X5X6 X30 5 3100091 8 X40 56010015M X612100 1152 5 C j Z j 2 10010514 X1013 51 50009 5 X4009110024 运筹学 第 3 版 习题答案21 X610 1 5 2 50 117 5 C j Z j 01 52 5010 因为 X6 0 原问题无可行解 图解法如下 4 123 123 123 123 max425 6410 3358 220 0 1 2 3 j Zxxx xxx xxx xxx xj 解解 大 M 法 X7 是人工变量 数学模型为 123 1234 1235 12 7 736 max425M 6410 3358 2220 0 1 2 7 j Zxxx xxxx xxxx xxxx x x xj Cj425000 MR H S Ratio CBXBX1X2X3X4X5X6X7 0X46 14110 0X53 3 518 MX71 2 1 112010 C j Z j 425 Big MM2MM 1 运筹学 第 3 版 习题答案22 0X413 2 9 2 1 1 21 220 0X59 2 7 21 3 23 238 2X21 211 2 1 21 210 C j Z j 341 1 Big M 1 5X313 912 9 1 91 940 9 0X586 97 91 17 917 9482 9 2X2 2 91 1 9 4 94 970 9 C j Z j 25 9 8 913 9 13 9 Big M 1 无界解 两阶段法 第一阶段 1234 1235 12673 7 min 6410 3358 220 0 1 2 7 j Z xxxx xxxx xxxx xj x x Cj0001R H S Ratio CBXBX1X2X3X4X5X6X7 0X46 14110 0X53 3 518 1X71 2 1 112010 C j Z j 1 2 11 0X413 2 9 2 1 1 21 220 0X59 2 7 21 3 23 238 2X21 211 2 1 21 210 C j Z j 1 第二阶段 Cj425000R H S Ratio CBXBX1X2X3X4X5X6 0X413 2 9 2 1 1 220 0X59 2 7 21 3 238 1X21 211 2 1 210 C j Z j 7 29 21 2 0X313 912 9 1 940 9 0X586 97 91 17 9482 9 2X2 2 91 1 9 4 970 9 C j Z j 3 11 原问题无界解 运筹学 第 3 版 习题答案23 1 12 在第 1 9 题中 对于基求所有变量的检验数 并判断 B 是B 21 40 jj 14 不是最优基 解解 1 1 0 4 4 1 1 2 BB 1 1 0 2210 4 5 2 0 0 5 0 14201 1 2 5595 5 2 0 0 5 0 0 0 2424 B CC B A B 不是最优基 可以证明 B 是可行基 95 0 0 24 1 13 已知线性规划 1234 1234 1234 max5874 233220 354230 0 1 4 j zxxxx xxxx xxxx xj 的最优基为 试用矩阵公式求 1 最优解 2 单纯形乘子 3 4 B 23 25 NN 13 及 13 和 解解 则 1 42 53 44 4 8 11 22 B BCc c 1 1 42 55 5 0 5 0 50 22 TTT B Xx xB bXZ 最优解 2 1 1 1 BCB 3 运筹学 第 3 版 习题答案24 1 1 1 1 3 3 531 2 444 1131 222 533 3 444 1141 222 NB P NB P 4 1 11 3 33 1 4 5 4 8 550 1 2 3 4 7 4 8 770 1 2 B B cC N cC N 注 该题有多重解 X 1 0 5 0 5 2 X 2 0 10 3 10 3 0 X 3 10 0 0 0 x2是基变量 是基变量 X 3 是退化基本可行解是退化基本可行解 Z 50 1 14 已知某线性规划的单纯形表 1 28 求价值系数向量 C 及目标函数值 Z 表表 1 28 Cjc1c2c3c4c5c6c7 CBXBx1x2x3x4x5x6x7 b 3x40121 3024 4x110 1020 10 0 x60 140 4123 2 j 0 1 1010 2 解解 由有 jjiij i cc a jjiij i cc a c2 1 3 1 4 0 0 1 2 c3 1 3 2 4 1 0 4 1 c5 1 3 3 4 2 0 4 0 c7 2 3 2 4 1 0 2 0 则 C 4 2 1 3 0 0 0 Z CBXB 12 1 15 已知线性规划 332211 maxxcxcxcZ 运筹学 第 3 版 习题答案25 0 321 2323222121 1313212111 xxx bxaxaxa bxaxaxa 的最优单纯形表如表 1 29 所示 求原线性规划矩阵 C A 及 b 最优基 B 及 B 1 表表1 29 Cjc1c2c3c4c5 CBXBx1x2x3x4x5 b c1x11041 61 156 c2x201 301 52 j00 1 2 3 解解 由c4 c5 0 111 11 62 615 105 0 5 BBB 得到 由公式得 jjiij i cc a 41211 1 6 2 2 6012 0 cc ccc 522 1 15 3 12 011 1 5 ccc 3 4 1 12 11 14 3 c 由 1 AB A 得 621046230 050130515 ABA 由 1 bB b 得 62632 05210 bBb 1 16 思考与简答 1 在例 1 2 中 如果设 xj j 1 2 7 为工作了 5 天后星期一到星期日开始休息的营 业员 该模型如何变化 2 在例 1 3 中 能否将约束条件改为等式 如果要求余料最少 数学模型如何变化 简 述板材下料的思路 3 在例 1 4 中 若允许含有少量杂质 但杂质含量不超过 1 模型如何变化 4 在例 1 6 中 假定同种设备的加工时间均匀分配到各台设备上 要求一种设备每台每 天的加工时间不超过另一种设备任一台加工时间 1 小时 模型如何变化 5 在单纯形法中 为什么说当时线性规划具有无界解 00 1 2 kik aim 并且 6 选择出基变量为什么要遵循最小比值规则 如果不遵循最小比值规则会是什么结果 7 简述大 M 法计算的基本思路 说明在什么情形下线性规划无可行解 8 设 X 1 X 2 X 3 是线性规划的 3 个最优解 试说明 1 2 3 123123123 01 XXXX 其中并且 也是线性规划的最优解 运筹学 第 3 版 习题答案26 9 什么是基本解 可行解 基本可行解 基本最优解 这四个解之间有何关系 10 简述线性规划问题检验数的定义及其经济含义 返回顶部 运筹学 第 3 版 习题答案27 第第2章章 线性规划的对偶理论线性规划的对偶理论 2 1 某人根据医嘱 每天需补充 A B C 三种营养 A 不少于 80 单位 B 不少于 150 单位 C 不少于 180 单位 此人准备每天从六种食物中摄取这三种营养成分 已知六种食物每百 克的营养成分含量及食物价格如表 2 22 所示 1 试建立此人在满足健康需要的基础上花 费最少的数学模型 2 假定有一个厂商计划生产一中药丸 售给此人服用 药丸中包含 有 A B C 三种营养成分 试为厂商制定一个药丸的合理价格 既使此人愿意购买 又使 厂商能获得最大利益 建立数学模型 表表2 22 含量 食物 营养成分 一二三四五六需要量 80 B24930251215 150 C1872134100 180 食物单价 元 100g 0 50 40 80 90 30 2 解解 1 设 xj为每天第 j 种食物的用量 数学模型为 0 180103421718 15015122530924 8011840142513 2 03 09 08 04 05 0min 654321 54321 654321 654321 654321 xxxxxx xxxxx xxxxxx xxxxxx xxxxxxZ 2 设 yi为第 i 种单位营养的价格 则数学模型为 123 123 123 123 123 123 12 123 max80150180 1324180 5 25970 4 1430210 8 4025340 9 812100 3 11150 2 0 wyyy yyy yyy yyy yyy yyy yy y yy 2 2 写出下列线性规划的对偶问题 1 解解 123 123 123 123 min32 3510 24 0 xxx xxx xxx x x x 12 12 12 12 12 max104 21 33 52 0 wyy yy yy yy y y 运筹学 第 3 版 习题答案28 2 解解 123 123 123 123 max2 2415 310 0 Zxxx xxx xxx x xx 无约束 12 12 12 12 12 min1510 2 231 41 0 wyy yy yy yy yy 无约束 3 解解 1234 1234 1234 1234 1234 max243 10414 762520 486 0 0 Zxxxx xxxx xxxx xxxx x xxx 9 无约束 123 123 123 123 123 123 min14209 10742 681 264 453 0 wyyy yyy yyy yyy yyy yyy 0 无约束 4 解解 1234 1234 134 1234 1 1234 max267 32612 656 222 820 0 Zxxxx xxxx xxx xxxx x xx x x 无约束 1234 1234 134 1234 1 1 1234 max267 32612 656 222 8 20 0 Zxxxx xxxx xxx xxxx x x xx x x 无约束 对偶问题为 12345 12345 13 123 123 12345 min1262 820 362 221 56 627 0 000 wyyyyy yyyyy yy yyy yyy yyyyy 0 2 3 考虑线性规划 0 732 25 44 2012min 21 21 21 21 21 xx xx xx xx xxZ 1 说明原问题与对偶问题都有最优解 2 通过解对偶问题由最优表中观察出原问题的最优解 3 利用公式 CBB 1求原问题的最优解 4 利用互补松弛条件求原问题的最优解 解解 1 原问题的对偶问题为 运筹学 第 3 版 习题答案29 123 123 123 max427 212 45320 0 1 2 3 j wyyy yyy yyy yj 容易看出原问题和对偶问题都有可行解 如 X 2 1 Y 1 0 1 由定理 2 4 知都有 最优解 2 对偶问题最优单纯形表为 C j 42700 BasisC i y1y2y3y4y5 R H S y370 1 514 5 1 528 5 y1417 50 3 52 54 5 C j Z j 0 11 50 16 5 1 5w 42 4 对偶问题的最优解 Y 4 5 0 28 5 由定理 2 6 原问题的最优解为 X 16 5 1 5 Z 42 4 3 CB 7 4 1 41 55 32 55 B 41 55 7 4 16 5 1 5 32 55 X 4 由 y1 y3不等于零知原问题第一 三个约束是紧的 解等式 12 12 44 237 xx xx 得到原问题的最优解为 X 16 5 1 5 2 4 证明下列线性规划问题无最优解 无约束 321 321 321 321 0 232 322 22min xxx xxx xxx xxxZ 证明 证明 首先看到该问题存在可行解 例如 x 2 1 1 而上述问题的对偶问题为 12 12 12 12 21 max32 21 22 232 0 wyy yy yy yy yy 无约束 由约束条件 知 y1 0 由约束条件 当 y2 0 知 y1 1 对偶问题无可行解 因此原问 题也无最优解 无界解 2 5 已知线性规划 运筹学 第 3 版 习题答案30 123 123 123 123 123 max15205 55 566 3107 0 0 Zxxx xxx xxx xxx xxx 无约束 的最优解 求对偶问题的最优解 119 0 44 T X 解解 其对偶问题是 123 123 123 123 123 min567 5315 561020 5 0 wyyy yyy yyy yyy y yy 由原问题的最优解知 原问题约束 的松弛变量不等于零 x1 x3不等于零 3 0 s x 则对偶问题的约束 约束 为等式 又由于知 y3 0 解方程 3 0 s x 12 12 515 5 yy yy 得到对偶问题的最优解 Y 5 2 5 2 0 w 55 2 27 5 2 6 用对偶单纯形法求解下列线性规划 123 123 123 123 1min346 2310 2212 0 Zxxx xxx xxx x x x 解解 将模型化为 123 1234 1235 min346 2310 2212 0 1 2 3 4 5 j Zxxx xxxx xxxx xj 对偶单纯形表 cj34600 CBXBX1X2X3X4X5 b 0 0 X4 X5 1 2 2 2 3 1 1 0 0 1 10 12 C j Z j 346000 0 3 X4 X1 0 1 1 1 5 2 1 2 1 0 1 2 1 2 4 6 运筹学 第 3 版 习题答案31 C j Z j 019 203 2 18 5 3 X2 X1 0 1 1 0 5 2 2 1 1 1 2 1 4 2 C j Z j 00211 22 b 列全为非负 最优解为 x 2 4 0 Z 22 12 12 12 12 2min54 6 22 0 0 Zxx xx xx xx 解解 将模型化为 12 123 124 min54 6 22 0 1 2 3 4 j Zxx xxx xxx xj 5400 XB CB X1 X2 X3 X4 b X30 1 110 6 X4021012 Cj Zj3400 X1311 106 X400 1 21 10 Cj Zj0130 X131011 4 X2401 2 110 Cj Zj0051 出基行系数全部非负 最小比值失效 原问题无可行解 12 12 12 12 12 3 min24 2324 210 318 0 Zxx xx xx xx x x 解解 将模型化为 12 123 124 125 min24 2324 210 318 0 1 2 3 4 5 j Zxx xxx xxx xxx xj cj24000 b 运筹学 第 3 版 习题答案32 XBCB X1 X2 X3 X4 X5 X302310024 X40 1 2010 10 X50 1 3 001 18 Cj Zj24000 X30101016 X40 1 3001 2 32 X241 3100 1 36 Cj Zj2 30004 3 最优解 X 0 6 Z 24 1234 1234 1234 4min2356 232 233 0 1 4 j Zxxxx xxxx xxxx xj 解解 将模型化为 1234 12345 12346 min2356 232 233 0 1 6 j Zxxxx xxxxx xxxxx xj Cj235600 XB CB X1 X2 X3 X4 X5 X6 b X50 1 2 3 410 2 X60 21 1301 3 Cj Zj235600 X231 213 22 1 201 X60 5 20 5 2 11 21 4 Cj Zj1 201 203 20 X23 1 1013 5 1 53 5 7 5 X35101 2 5 1 5 2 58 5 Cj Zj0001 58 51 5 X121 10 13 51 5 3 57 5 X350 1 111 5 2 51 51 5 Cj Zj0001 58 51 5 X12101 2 5 1 5 2 58 5 X2301111 5 2 51 51 5 Cj Zj0001 58 51 5 原问题有多重解 X 1 7 5 0 1 5 最优解 X 2 8 5 1 5 0 Z 19 5 如果第一张表 X6出基 则有 Cj235600 XB CB X1 X2 X3 X4 X5 X6 b 运筹学 第 3 版 习题答案33 X50 1 2 3 410 2 X60 2 1 1301 3 Cj Zj235600 X500 5 2 5 2 11 21 1 2 1 2 X121 1 21 2 3 20 1 23 2 Cj Zj044901 X2301111 5 2 51 51 5 X12101 7 5 1 5 2 58 5 Cj Zj0001 58 51 5 2 7 某工厂利用原材料甲 乙 丙生产产品 A B C 有关资料见表 2 23 表表2 23 产品 材料消耗 原材料 ABC 每月可供原材料 Kg 211200 123500 甲 乙 丙 221600 每件产品利润413 1 怎样安排生产 使利润最大 2 若增加 1kg 原材料甲 总利润增加多少 3 设原材料乙的市场价格为 1 2 元 Kg 若要转卖原材料乙 工厂应至少叫价多少 为 什么 4 单位产品利润分别在什么范围内变化时 原生产计划不变 5 原材料分别单独在什么范围内波动时 仍只生产 A 和 C 两种产品 6 由于市场的变化 产品 B C 的单件利润变为 3 元和 2 元 这时应如何调整生产计 划 7 工厂计划生产新产品 D 每件产品 D 消耗原材料甲 乙 丙分别为 2kg 2kg 及 1kg 每件产品 D 应获利多少时才有利于投产 解解 1 设 x1 x2 x3分别为产品 A B C 的月生产量 数学模型为 123 123 123 123 123 max43 21200 23500 2600 0 0 0 Zxxx xxx xxx xxx xxx 最优单纯形表 C j 413000 XB CBX1X2X3X4X5X6 R H S Ratio X1411 503 5 1 5020 X3303 51 1 52 50160 X60000 101400 C j Z j 0 8 50 9 5 2 50Z 560 最优解 X 20 0 160 Z 560 工厂应生产产品 A20 件 产品 C160 种 总利润为 560 元 运筹学 第 3 版 习题答案34 2 由最优表可知 影子价格为 故增加利润 1 8 元 123 92 0 55 yyy 3 因为 y2 0 4 所以叫价应不少于 1 6 元 4 依据最优表计算得 123 123 8 32 19 5 13 1 6 2 12 5 ccc ccc 5 依据最优表计算得 123 123 100 400 400100 400 3 500 600 100 600 200 3 bbb bbb 6 变化后的检验数为 2 1 4 2 5 0 故 x2进基 x1出基 得到最最优解 X 0 200 0 即 只生产产品 B 200 件 总利润为 600 元 C j 432000 XB CBX1X2X3X4X5X6 R H S Ratio X141 1 5 03 5 1 5020100 X3203 51 1 52 50160800 3 X60000 101400M C j Z j 010 200560 X225103 10100M X33 301 2 1 0100100 X60000 101400M C j Z j 500 510 X22211100200 X40 301 210100 X60000 101400 C j Z j 20 1 300 7 设产品 D 的产量为 x7 单件产品利润为 c7 只有当时才有利于投 1 777 0 B cC B P 产 1 777 2 9 222 02 5 55 1 B cC B PYP 则当单位产品 D 的利润超过 4 4 元时才有利于投产 2 8 对下列线性规划作参数分析 运筹学 第 3 版 习题答案35 1 0 1823 6 4 5 23 max 21 21 2 1 21 xx xx x x xxZ 解 0 时最优解 X 4 3 0 最优表 C j 35000 BasisC i X1X2X3X4X5 R H S X13101004 X250100 503 X5000 3 110 C j Z j 00 3 2 5027 将参数引入到上表 C j 3 2 5 000 BasisC i X1X2X3X4X5 R H S X13 2 101004 X25 0100 503 X5000 3 110 C j Z j 00 3 2 2 5 0 5 027 当 3 2 0 及 2 5 0 5 0 时最优基不变 有 1 5 5 当 5 时 X4 进基 X2 出基 用单纯形法计算 参数变化与目标值变化的关系如下 表所示 FromToFromTo LeavingEntering Range Vector Vector OBJ Value OBJ ValueSlopeVariableVariable 10527525X2X4 25M52M8 30 1 52719 55X1X3 4 1 5 M19 5M 3 目标值变化如下图所示 运筹学 第 3 版 习题答案36 2 0 21823 6 4 53max 21 21 2 1 21 xx xx x x xxZ 解 0 时最优解 X 4 3 0 Z 27 最优表 C j 35000 BasisC i X1X2X3X4X5 R H S X13101004 X250100 503 X5000 3 110 C j Z j 00 3 2 5027 41 60 182 bbb 111 41001 300 500 03112 41 30 05 bBbbB bB b 0 Z 27 5 Z 52 1 5 Z 19 5 0 运筹学 第 3 版 习题答案37 替换最优表的右端常数 得到下表 C j 35000 BasisC i X1X2X3X4X5 R H S X13101004 X250100 503 X5000 3 11 5 C j Z j 00 3 2 50 4 时问题不可行 4 0 时 X5 出基 X3 进基得到下表 C j 35000 BasisC i X1X2X3X4X5 R H S X13100 1 31 3 4 2 3 X250101 203 X300011 3 1 3 5 3 C j Z j 000 3 2 1 0 6 时为最优解 6 时 Z 15 6 时 X1 出基 X4 进基得到下表 C j 35000 BasisC i X1X2X3X4X5 R H S X40 3001 1 12 2 X253 21001 2 9 X3010100 4 C j Z j 9 时最优解 X 0 0 13 6 0 Z 0 9 时无可行解 综合分析如下表所示 FromToFromTo LeavingEntering Range Vector Vector OBJ ValueOBJ Value SlopeVariableVariable 10027273X5X3 2062715 2X1X2 369150 5X2 49InfinityInfeasible 50 427153X1 6 4 InfinityInfeasible 目标值变化如下图所示 运筹学 第 3 版 习题答案38 2 9 有三个决策单元的输入输出矩阵有三个决策单元的输入输出矩阵 9510 628 364 535 439 XY 1 建立 C2R 模型并求解 判断各决策单元的 DEA 有效性 2 建立 BC2模型并求解 判断各决策单元的 DEA 有效性 3 指出哪些决策单元是技术有效又规模有效 是技术有效非规模有效 既不是技术有效 又非规模有效 4 分别求三个决策单元的整体效率 技术效率 规模效率及规模报酬 解解 1 12312 3 3 2 TT mns 对第一决策单元有 11 9 3 4 6 5 TT XY 112 12312 12312 12312 123 12312 max65 934650 563230 1049850 9341 0 P Z 最优解 Z1P 1 0 0894 0 0 0488 0 1667 0 TT 对偶问题的最优解 Z1D 1 123 1 0 0 1 DEA 有效 运筹学 第 3 版 习题答案39 对第二决策单元有 212 12312 12312 12312 123 12312 max23 934650 563230 1049850 5631 0 P Z 最优解 Z2P 0 7967 0 0820 0 0 1475 0 0 2656 TT 对偶问题的最优解 Z2D 0 7967 123 0 4426 0 0 1574 0 7967 非 DEA 有效 对第三决策单元有 312 12312 12312 12312 123 12312 max85 934650 563230 1049490 10491 0 P Z 最优解 Z3P 0 7465 0 0253 0 0 0829 0 0933 0 TT 对偶问题的最优解 Z3D 0 7465 123 0 8295 0 0 3779 0 7465 非 DEA 有效 2 第一决策单元 BC2模型 max 0 1 2 1 0 0 T kPkk TT jjk T k Wc cjn Y X Y X 9510 628 364 535 439 XY 1121 123121 123121 123121 123 12312 max65 934650 563230 1049850 9341 0 P Wc c c c 最优解 W1P 1 1 0 0894 0 0 0488 0 1667 0 0 T