运筹学(胡运权)第五版课后答案-运筹作业

47 页 1 1b 1 2 3 4 4 3 2 1 X1 2x1 x2 2 3x1 4x2 12 0 X2 用图解法找不到满足所有约束条件的公共范围 所以该问题无可行解 47 页 1 1d 1 2 3 4 5 4 3 2 1 1 2 6 5 4 3 2 1 X2 X1 2x1 x2 2 2x1 3x2 2 无界解 1 2 b 约束方程的系数矩阵 A 1 2 3 4 2 1 1 2 P1 P2 P3 P4 基解基解 基基 X1 X2 X3 X4 是否可行解是否可行解目标函数值目标函数值 P1 P2 4 11 2 0 0否 P1 P32 5 0 11 5 0是43 5 P1 P4 1 3 0 0 11 6否 P2 P30 1 2 2 0是5 P2 P40 1 2 0 2否 P3 P40 0 1 1是5 最优解 A 0 1 2 2 0 T 和 0 0 1 1 T 49 页 13 题 设 Xij 为第 i 月租 j 个月的面积 minz 2800 x11 2800 x21 2800 x31 2800 x41 4500 x12 4500 x22 4500 x32 6000 x13 6000 x23 7300 x14 s t x11 x12 x13 x14 15 x12 x13 x14 x21 x22 x23 10 x13 x14 x22 x23 x31 x32 20 x14 x23 x32 x41 12 Xij 0 用 excel 求解为 用 LINDO 求解 LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1 118400 0 VARIABLE VALUE REDUCED COST Z 0 000000 1 000000 X11 3 000000 0 000000 X21 0 000000 2800 000000 X31 8 000000 0 000000 X41 0 000000 1100 000000 X12 0 000000 1700 000000 X22 0 000000 1700 000000 X32 0 000000 0 000000 X13 0 000000 400 000000 X23 0 000000 1500 000000 X14 12 000000 0 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 2800 000000 3 2 000000 0 000000 4 0 000000 2800 000000 5 0 000000 1700 000000 NO ITERATIONS 3 答 若使所费租借费用最小 需第一个月租一个月租期 300 平方米 租四个月租 期 1200 平方米 第三个月租一个月租期 800 平方米 50 页 14 题 设 a1 a2 a3 a4 a5 分别为在 A1 A2 B1 B2 B3 加工的 产品数量 b1 b2 b3 分别为在 A1 A2 B1 加工的 产品数量 c1 为在 A2 B2 上加工的 产品数量 则目标函数为 maxz 1 25 0 25 a1 a2 a3 2 0 35 b3 2 8 0 5 c1 0 05 a1 b1 0 03 a2 b2 c1 0 06 a3 b3 0 11 a4 c1 0 05a5 0 95a1 0 97a2 0 94a3 1 5b3 2 1c1 0 05b1 0 11a4 0 05a5 s t 5a1 10b1 6000 7a2 b2 12c1 10000 6a3 8a3 4000 4a4 11c1 7000 7a5 4000 a1 a2 a3 a4 a5 0 b1 b2 b3 0 a1 a2 a3 a4 a5 b1 b2 b3 c1 0 用 lindo 求解得 LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION VALUE 1 16342 29 VARIABLE VALUE REDUCED COST A1 1200 000000 0 000000 A2 0 000000 9 640000 A3 285 714294 0 000000 B3 10000 000000 0 000000 C1 0 000000 15 900000 B1 0 000000 0 230000 A4 342 857147 0 000000 A5 571 428589 0 000000 B2 10000 000000 0 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 0 168000 3 0 000000 1 500000 4 0 000000 0 075000 5 5628 571289 0 000000 6 0 000000 0 008571 7 0 000000 0 110000 8 0 000000 1 500000 NO ITERATIONS 6 计算 lindo 截屏 2 1a 2 1a 对偶问题为 maxz 2y1 3y2 5y3 s t y1 2y2 y3 2 3y3 y2 4y3 2 4y1 3y2 3y3 4 y1 0 y 2 0 y3 无约束 因为原问题的对偶问题的对偶问题仍是原问题 因此本问题的对偶问题的对偶 问题为 minz 2x1 2x2 4x3 s t x1 3x2 4x3 2 2x1 x2 3x3 3 x1 4x2 3x3 5 x1 x2 0 x3 无约束 81 页页 2 12 a 设 x1 x2 x3 分别为 A B C 产品数量 maxz 3x1 x2 4x3 s t 6x1 3x2 5x3 45 3x1 4x2 5x3 30 x1 x2 x3 0 用 lomdo 求解为 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1 27 00000 VARIABLE VALUE REDUCED COST X1 5 000000 0 000000 X2 0 000000 2 000000 X3 3 000000 0 000000 X1 X2 X3 0 000000 0 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 0 200000 3 0 000000 0 600000 4 0 000000 0 000000 NO ITERATIONS 2 最大生产计划为 A 生产 5 个单位 C 生产 3 个单位 b LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1 27 00000 VARIABLE VALUE REDUCED COST X1 5 000000 0 000000 X2 0 000000 2 000000 X3 3 000000 0 000000 X1 X2 X3 0 000000 0 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 0 200000 3 0 000000 0 600000 4 0 000000 0 000000 NO ITERATIONS 2 RANGES IN WHICH THE BASIS IS UNCHANGED OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 3 000000 1 800000 0 600000 X2 1 000000 2 000000 INFINITY X3 4 000000 1 000000 1 500000 X1 X2 X3 0 000000 0 000000 INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 45 000000 15 000000 15 000000 3 30 000000 15 000000 7 500000 4 0 000000 0 000000 INFINITY 可知 A 产品的利润变化范围 6 8 2 4 上述计划不变 c 设设 x4 为产品为产品 D 的数量的数量 maxz 3x1 x2 4x3 3x4 s t 6x1 3x2 5x3 8x4 45 3x1 4x2 5x3 2x4 30 x1 x2 x3 x4 0 用 lomdo 求解为 LP OPTIMUM FOUND AT STEP 0 OBJECTIVE FUNCTION VALUE 1 27 50000 VARIABLE VALUE REDUCED COST X1 0 000000 0 100000 X2 0 000000 1 966667 X3 5 000000 0 000000 X4 2 500000 0 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 0 233333 3 0 000000 0 566667 NO ITERATIONS 0 安排生产安排生产 D 有利 新最有生产计划为有利 新最有生产计划为 x1 x2 0 x3 5 x4 2 5 利润为 利润为 27 5 d maxz 3x1 x2 4x3 0 4y s t 6x1 3x2 5x3 45 3x1 4x2 5x3 y 30 x1 x2 x3 y 0 用 lomdo 求解为 LP OPTIMUM FOUND AT STEP 0 OBJECTIVE FUNCTION VALUE 1 30 00000 VARIABLE VALUE REDUCED COST X1 0 000000 0 600000 X2 0 000000 1 800000 X3 9 000000 0 000000 Y 15 000000 0 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 0 400000 3 0 000000 0 400000 NO ITERATIONS 0 可知购进原材料 15 个单位为宜 4 1 a 设 yi 1 第 i 组条件起作用 0 第 i 组条件不起作用 x1 x2 2 1 y1 M M 充分大正数 2x1 3x2 5 1 y2 M y1 y2 1 y1 y2 0 或 1 b 设 yi 1 第 i 组条件起作用 0 第 i 组条件不起作用 x 0y1 x 3y2 x 5y2 x 7y4 y1 y2 y3 y4 1 y1 y2 y3 y4 0 或 1 c 设 yi 1 为假定取值 50 0 为假定取值 x 0 x 0y1 x 50 1 y2 M y1 y2 1 y1 y2 0 或 1 d 设 yi 1 第 i 组条件起作用 0 第 i 组条件不起作用 i 1 2 则 x1 2 1 y1 M x2 1 1 y1 M x2 4 1 y2 M y1 y2 1 y1 y2 0 或 1 e 设 yi 1 第 i 组条件起作用 0 第 i 组条件不起作用 i 1 2 则 x1 x2 5 1 y1 M x1 2 1 y2 M x3 2 1 y3 M x3 x4 6 1 y4 M y1 y2 y3 y4 2 y1 y2 y3 y4 1 或 0 4 2 minz 10 1 5 10 1 x1 x8 1 x7 x8 1 s t x3 x5 1 x4 x5 1 x5 x6 x7 x8 2 xj 1 选择钻探第 sj 井位 0 否 4 5 设 xij 为第 i 种泳姿用第名运动员 minz 4 1 5 1 s t x11 x12 x13 x14 x15 1 x21 x22 x23 x24 x25 1 x31 x32 x33 x34 x35 1 x41 x42 x43 x44 x45 1 x11 x21 x22 x23 1 x12 x22 x32 x42 1 x13 x23 x33 x43 1 x14 x24 x34 x44 1 x15 x25 x35 x45 1 xij 1 或 0 i 1 2 3 4 j 1 2 3 4 5 由 excel 计算得出 张游仰泳 王游蛙泳 赵游自由泳 预期总成绩为 126 2s 5 3c 因为使 mind1 故在 x1 x2 40 的右侧 若使 mind4 则在 x1 x2 50 的左侧 即 阴影区域 因为在阴影部分无法使 2d2 d3 最小 故比较 E 20 30 F 24 26 E 点 d2 4 d3 0 min2d2 d3 8 F 点 d2 0 d3 4 min2d2 d3 4 故 选 F 点 10 20 30 40 50 50 40 30 20 10 d2 d3 d3 d2 d4 d4 d1 d1 E F 程序法 6 4a 破圈法 避圈法 2 1 6 6 2 7 7 1 4 3 4 5 3 2 34 2 1 6 6 2 7 7 1 4 3 4 5 3 2 34 8 8 最小部分树 16 6 4b 1 5 2 6 10 1012 4 2 6 6 7 3 2 82 1 8 10 4 5 8 1 5 2 6 10 1012 4 2 6 6 7 3 2 82 1 8 10 4 5 8 最小部分树 32 172 页 6 11 v0v1 88 v2v3v4 0 8 1 7 2 8 4 2 0 9 1 1 1 4 1 8 2 2 9 00 8 1 7 2 6 红色曲线为使用一年卖出 蓝色曲线为使用两年卖出 绿色曲线为使用三年卖出 紫色曲线为使用四年卖出 最短路程为 3 7 万元 路径为 v0 v1 v4 或 v0 v2 v4 或 v0 v1 v2 v4 三种方案分别为 第一年年初买新车 年末卖掉再买新车 一直用到第四年年末卖掉 第一年出买新车 用两年后于第二年末卖掉再买新车 用两年于第四年末卖掉 第一年出买新车 年末卖掉后再买新车 第二年末卖掉再买新车 再用两年于第四年年末 卖掉 3 7 v0v1 88 v2v3v4 0 8 1 7 2 8 0 9 1 1 1 4 1 8 2 2 9 00 8 1 7 2 63 7 由图可知 若摩托车最多使用三年 答案仍然不变 6 14b vs v2 vs 1 v3 vs 1 v5 v4 1 vt v5 1 v4 v3 1 v1 v2 1 根据题意 先给发点 vs 标号 由弧 vs v2 得对 v2 进行标号 vs 1 弧 v2 v1 对 v1 标号 v2 1 弧 vs v3 得对 v3 进行标号 vs 1 弧 v3 v4 对 v4 标号 v3 1 弧 v3 v4 对 v4 标号 v3 1 弧 v4 v5 对 v5 标号 v4 1 弧 v5 vt 对 vt 标号 v5 1 反向追踪找出增广链 最大流为 14 最小割集为 v1 v3 v2 v3 v2 vt v1 vt 6 14c vs v2 v3 1 v1 vs 2 v3 v5 1 v4 v2 1 v5 v1 1 vt v4 1 最大流 13 无最小割集 193 页页 7 2 表表 7 9 12 3 5 4 78 6 9 10 A B C F D K J G L I H E M 194 页页 7 3b 假定最初事件在时刻零出现 则有 tES 1 2 tES 1 3 tES 1 4 0 tEF 1 2 tES 1 2 t 1 2 2 tEF 1 3 4 tEF 1 4 8 tES 2 5 2 tEF 2 5 5 tES 5 8 8 tEF 5 8 15 tES 8 9 15 tEF 8 9 20 tES 5 7 5 tEF 5 7 7 tES 4 7 8 tEF 4 7 11 tES 4 6 8 tEF 4 6 10 tES 3 6 4 tEF 3 6 12 tES 6 7 12 tEF 6 7 13 tES 7 9 13 tEF 7 9 15 tES 6 9 12 tEF 6 9 19 最短周期为 20 tLF 6 9 tLF 8 9 tLF 7 9 20 tLS 8 9 15 tLS 7 9 16 tLS 6 9 13 tLF 5 8 15 tLS 5 8 8 tLF 5 7 16 tLS 5 7 14 tLS 4 7 10 tLF 4 7 13 tLS 6 7 15 tLF 6 7 16 tLS 4 6 10 tLF 4 6 13 tLS 3 6 5 tLF 3 6 13 tLS 1 3 1 tLF 1 3 5 tLS 1 4 0 tLF 1 4 8 tLF 2 5 8 tLS 2 5 5 tLF 1 2 5 tLS 1 2 3 作业 ij t i j tES i j tEF i j tLS i j tLF i j R i j F i j 12345678 1 2 2023530 1 3 4041510 1 4 8080800 5 3255830 3 6 841251310 4 5 0888800 4 6 2810101332 4 7 3811101322 5 7 757141696 5 8 781581500 6 7 11213151630 6 9 71219132011 7 9 41315162055 8 9 51520152000 关键路线为 1 4 4 5 5 8 8 9 课堂作业课堂作业 1 柴油机生产计划柴油机生产计划 设 x1 x2 x3 x4 分别为一二三四季度计划 minz 11 4x1 11 55x2 11 3x3 11 45x4 s t x1 25 x2 35 x3 30 x4 10 x1 x2 x3 x4 70 LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1 796 2500 VARIABLE VALUE REDUCED COST X1 25 00000