管理运筹学作业答案(韩大卫)MBA.pdf

运筹学作业答案 1 第 1 章 线性规划基本性质 P47P47P47P47 1 1 1 1 1 1 1 1 2 2 2 2 解 设每天从i煤矿 2 1 i运往j城市 3 2 1 j的煤为 ij x吨 该问题的 LP 模型为 3 2 1 2 10 200 150 100 250 200 85 681079min 2313 2212 2111 232221 131211 232221131211 2 1 3 1 jix xx xx xx xxx xxx ts xxxxxxxc ij ij ijij P48P48P48P48 1 1 1 1 2 2 2 2 2 2 2 2 0 2 33 1 0 max 21 21 21 21 xx xx xx ts xxz 3 1 x 1 0 1 2 1 R 2 R 2 x 解 21 RR 则该 LP 问题无可行解 P48P48P48P48 1 1 1 1 2 2 2 2 3 3 3 3 运筹学作业答案 2 0 2 55 1 0 102min 21 21 21 21 xx xx xx ts xxz 1 1 x 50 1 2 2 x Q Z 0 Z 10 1 P 解 目标函数等值线与函数约束 2 的边界线平行 由图可知则该 LP 问题为多重解 无 穷多最优解 4 5 4 5 55 0 2 1 21 21 x x xx xx 则10 4 5 4 5 1 zX T 射线 QP 上所有点均为最优点 P48P48P48P48 1 1 1 1 2 2 2 2 4 4 4 4 0 3 22 2 825 1 1043 1110min 21 21 21 21 21 xx xx xx xx ts xxz 运筹学作业答案 3 1 x 2 x 1 2 3 Z 0 11 z Q 解 由图可知 Q 点为最优点 7 13 7 6 825 1043 2 1 21 21 x x xx xx 则29 7 13 7 6 zX T P48P48P48P48 1 1 1 1 3 3 3 3 2 2 2 2 0 1 4 664 73 243min 21 4321 321 321 4321 xx xxxx xxx xxx ts xxxxz 0 1 4 6664 73 2243max 1 765 4 4 3 321 71 4 4 3 321 6 3 321 5 3 321 4 4 3 321 4 44 3 33 1 xxxxxxxxx xx xxxxxx xxxxx xxxxx ts xxxxxxz xxxxxx x 令自由变量 看作一函数约束解 把 P49P49P49P49 1 1 1 1 5 5 5 5 运筹学作业答案 4 解 可行域的极点与基本可行解是一一对应的 解 可行域的极点与基本可行解是一一对应的 解 可行域的极点与基本可行解是一一对应的 解 可行域的极点与基本可行解是一一对应的 1 1 1 1 对于 对于 对于 对于 TX8 0 0 7 9 2 不满足约束条件 不满足约束条件 不满足约束条件 不满足约束条件85274 54321 xxxxx 即 即 即 即 TX8 0 0 7 9 2 不是可行解 也就不是基本可行解 故不是该可行域的极点 不是可行解 也就不是基本可行解 故不是该可行域的极点 不是可行解 也就不是基本可行解 故不是该可行域的极点 不是可行解 也就不是基本可行解 故不是该可行域的极点 2 2 2 2 对于对于对于对于 TX 0 20 0 15 5 1 是可行解是可行解是可行解是可行解 此时基变量为此时基变量为此时基变量为此时基变量为 421 xxx 由此得到的基矩阵为由此得到的基矩阵为由此得到的基矩阵为由此得到的基矩阵为 0 274 131 012 所以 所以 所以 所以 T X 0 20 0 15 5 1 不是基本解 也就不是基本可行解 故不是该不是基本解 也就不是基本可行解 故不是该不是基本解 也就不是基本可行解 故不是该不是基本解 也就不是基本可行解 故不是该 可行域的极点 可行域的极点 可行域的极点 可行域的极点 3 3 3 3 对于对于对于对于 TX0 0 10 5 15 3 是可行解是可行解是可行解是可行解 此时基变量为此时基变量为此时基变量为此时基变量为 321 xxx 由此得到的基矩阵为由此得到的基矩阵为由此得到的基矩阵为由此得到的基矩阵为 0 174 031 112 所以所以所以所以 TX0 0 10 5 15 3 不是基本解不是基本解不是基本解不是基本解 也就不是基本可行解也就不是基本可行解也就不是基本可行解也就不是基本可行解 故不是该可故不是该可故不是该可故不是该可 行域的极点 行域的极点 行域的极点 行域的极点 P50P50P50P50 1 1 1 1 8 8 8 8 1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8 A 2 9 A 2 9 A 2 9 A 2 9 1 1 1 11 1 1 11 1 1 12 2 2 20 0 0 00 0 0 00 0 0 00 0 0 0100100100100 B 2 1 B 2 1 B 2 1 B 2 1 1 1 1 12 2 2 20 0 0 00 0 0 01 1 1 10 0 0 02 2 2 23 3 3 3100100100100 C 1 2 C 1 2 C 1 2 C 1 2 2 2 2 20 0 0 03 3 3 31 1 1 14 4 4 46 6 6 62 2 2 20 0 0 0100100100100 余料余料余料余料0 0 0 00 30 30 30 30 90 90 90 90 40 40 40 40 50 50 50 50 20 20 20 20 80 80 80 81 11 11 11 1 解 设按第解 设按第解 设按第解 设按第j种截法下料种截法下料种截法下料种截法下料 8 2 1 jxj根 该问题的根 该问题的根 该问题的根 该问题的 LPLPLPLP 模型为 模型为 模型为 模型为 8 2 10 10026432 100322 1002 min 765431 87521 4321 87654321 jx xxxxxx xxxxx xxxx ts xxxxxxxx j 运筹学作业答案 5 第 2 章 单纯形法 P70P70P70P70 2 2 2 2 1 1 1 1 2 2 2 2 解 标准化为 0 5 2426 155 2max 54321 521 421 32 21 xxxxx xxx xxx xx ts xxz 容易得 0 5 24 15 0 0 00 zX T 第一次迭代 1 21 2max 则 1 x为进基变量 此时 2 x仍为非基变量 5 246 15 51 41 3 xx xx x 05 0624 015 15 14 3 xx xx x 1 5 6 24 1 1 x x 则 4 x为进基变量 6 为主元 1 6 1 3 2 4 6 1 3 1 155 542 421 32 xxx xxx xx 此时 8 1 0 15 0 4 3 1 3 1 8 6 1 3 1 422 11 4224221 zX xxxxxxxz T 第二次迭代 0 3 1 2 则 2 x为进基变量 0 3 2 1 0 3 1 4 0515 25 21 23 xx xx xx 3 2 1 3 1 4 5 15 2 2 2 x x x 则 5 x为进基变量 3 2 为主元 2 3 2 3 4 1 4 6 1 3 1 155 542 421 32 xxx xxx xx 2 3 2 3 4 1 2 7 2 1 4 1 2 15 2 15 4 5 542 541 543 xxx xxx xxx 运筹学作业答案 6 此时 2 17 0 0 2 15 2 3 2 7 2 1 4 1 2 17 3 1 2 3 4 1 2 3 3 1 8 3 1 3 1 8 22 5445442 zX xxxxxxxz T 此时0 j 则 2 17 2 3 2 7 zX T 图解法略 注意由方程组形式求的每个基本可行解与图解法求得的可行域的极点之间的一一对应关系 P70P70P70P70 2 2 2 2 2 2 2 2 1 1 1 1 解 化标准形为 0 25 0 1 22max 4321 421 321 21 xxxx xxx xxx ts xxz j c 2200 i B C B Xb 1 x 2 x 3 x 4 x 0 3 x1 1 110 0 4 x25 0 101 j 2 2 2 2200 02 1 而它所对应的系数列向量 T T 0 05 0 1 1 则该 LP 问题无最优解 无界解 运筹学作业答案 7 补充作业 补充作业 补充作业 补充作业 求解下列 LP 问题 0 60333 20422 603 336max 321 321 321 321 321 xxx xxx xxx xxx ts xxxz 解 标准化后求解过程如下 j c 63 3000 i B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 0 4 x6031110020 0 5 x10 1 1 1 1 1 201010 0 6 x2011 1 00120 j 63 3000 0 4 x30045 13 030 4 6 1 x1011 2010 0 6 x100 2 2 2 2 3 0 1 15 j 039 06 0 0 4 x1000111 2 6 1 x15101 201 21 2 3 2 x501 3 20 1 21 2 j 00 9 20 9 2 3 2 0 j 则最优解为 75 0 5 15 zX T 运筹学作业答案 8 P70P70P70P70 2 2 2 2 2 2 2 2 4 4 4 4 解 建立该 LP 问题的大 M 法辅助问题如下 0 223 824 32max 7654321 7521 64321 76321 xxxxxxx xxxx xxxxx ts MxMxxxxz j c 2 3 1 0 0 0 00 0 0 0M M i B C B X b b b b 1 x 2 x 3 x 4 x 5 x 6 x 7 x M 6 x8 8 8 81 1 1 1 4 4 4 4 2 2 2 2 1 0 0 0 01 1 1 10 0 0 02 2 2 2 M 7 x6 6 6 63 3 3 32 2 2 20 0 0 00 0 0 0 1 0 0 0 01 1 1 13 3 3 3 j 24 m 36 m12 m m m 0 0 0 00 0 0 0 3 2 x2 2 2 21 41 41 41 41 1 1 11 21 21 21 24 1 0 0 0 01 41 41 41 40 0 0 08 8 8 8 M 7 x2 2 2 2 5 25 25 25 2 0 0 0 0 1 1 2 1 21 21 21 2 1 1 1 1 1 4 4 4 4 5 5 5 5 j 4 5 2 5 m 0 0 0 0m 2 1 4 3 2 m m 4 3 2 3 m 0 0 0 0 3 2 x 5 9 0 0 0 01 1 1 1 3 53 53 53 5 10 3 1 101 101 101 103 103 103 103 10 10 1 2 1 x 5 4 1 1 1 10 0 0 05 2 1 51 51 51 5 5 2 5 1 2 52 52 52 5 j 0 0 0 00 0 0 00 0 0 02 1 1 2 2 2 2 1 3 x3 3 3 30 0 0 05 35 35 35 31 1 1 12 1 1 61 61 61 61 21 21 21 2 1 6 6 6 6 2 1 x2 2 2 21 1 1 12 32 32 32 30 0 0 00 0 0 01 3 3 3 30 0 0 01 31 31 31 3 j 0 0 0 00 0 0 00 0 0 01 2 2 2 21 2 2 2 2 由于出现非基变量的检验数为 0 故该 LP 问题有多重解 T T XX3 0 2 0 5 9 5 4 2 1 运筹学作业答案 9 则最优解为 T T XXX3 0 21 0 5 9 5 4 1 2 1 33 5 9 5 6 2 10 7 运筹学作业答案 10 P71P71P71P71 2 2 2 2 2 2 2 2 5 5 5 5 解 目标函数化标准形为 4321 2maxxxxxz 函数约束添加人工变量 765 xxx 拟采用两阶段法求解 第一阶段 两阶段法辅助问题目标函数为 765 maxxxxz j c 0 0 0 00 0 0 00 0 0 00 0 0 01 1 1 i B C B Xb b b b 1 x 2 x 3 x 4 x 5 x 6 x 7 x 1 5 x2 2 2 2 1 1 1 1 1 2 2 2 21 1 1 1 10 0 0 00 0 0 02 2 2 2 1 6 x6 6 6 62 2 2 21 1 1 13 1 1 1 10 0 0 01 1 1 10 0 0 03 3 3 3 1 7 x711110017 j 4101000 0 0 0 0 1 x2 2 2 21 1 1 11 2 2 2 21 1 1 1 10 0 0 00 0 0 0 1 6 x2 2 2 20 0 0 0 3 3 3 3 7 3 3 3 3 2 1 1 1 10 0 0 02 3 2 32 32 3 1 7 x502 1 21 015 2 j 058 53 00 0 0 0 0 1 x8 38 38 38 31 1 1 10 0 0 0 1 3 1 3 1 3 1 30 0 0 01 31 31 31 31 31 31 31 30 0 0 0 0 0 0 0 2 x2 32 32 32 30 0 0 01 1 1 1 7 3 7 3 7 3 7 31 1 1 1 2 3 2 3 2 3 2 31 31 31 31 30 0 0 0 1 7 x11 300 11 3 01 3 2 311 j 0011 30 0 0 0 2 3 5 30 0 0 0 0 1 x3 3 3 31 1 1 10 0 0 00 0 0 00 0 0 04 114 114 114 113 113 113 113 111 111 111 111 11 0 0 0 0 2 x3 3 3 30 0 0 01 1 1 10 0 0 01 1 1 1 5 11 5 11 5 11 5 11 1 11 1 11 1 11 1 117 117 117 117 11 0 0 0 0 3 x100101 11 2 113 11 j 0000 0 0 01 1 1 运筹学作业答案 11 由第一阶段最终单纯形表可得0 z 故原 LP 问题存在可行基 转入第二阶段继续求解 第二阶段 求解原 LP 问题 j c 2 1 1 1 1 11 1 1 1 i B C B Xb b b b 1 x 2 x 3 x 4 x 2 1 x3 3 3 31 1 1 10 0 0 00 0 0 00 0 0 0 1 2 x3 3 3 30 0 0 01 1 1 10 0 0 0 1 1 1 1 3 3 3 3 1 3 x1 1 1 10 0 0 00 0 0 01 1 1 10 0 0 0 j 0 0 0 00 0 0 00 0 0 02 2 2 2 2 1 x3 3 3 31 1 1 10 0 0 00 0 0 00 0 0 0 1 4 x3 3 3 30 0 0 01 1 1 10 0 0 01 1 1 1 1 3 x1 1 1 10 0 0 00 0 0 01 1 1 10 0 0 0 j 0 0 0 02 0 0 0 00 0 0 0 此时 0 j 故原 LP 问题的最优解为 2 3 1 0 3 T X 补充作业 补充作业 补充作业 补充作业 求解下列 LP 问题 0 16284 2042 4224 2max 321 321 21 321 321 xxx xxx xx xxx ts xxxz 解 建立大M法的辅助问题如下 0 16284 2042 4224 2max 7654321 6321 521 74321 7321 xxxxxxx xxxx xxx xxxxx ts Mxxxxz 运筹学作业答案 12 j c 211000M i B C B Xb b b b 1 x 2 x 3 x 4 x 5 x 6 x 7 x M 7 x4 4 4 4 4 22 1 0011 0 5 x20240010010 0 6 x1648200104 j 24 m12 m 12 m m 000 2 1 x111 21 2 1 4001 4 0 5 x1803 1 1 210 1 236 0 6 x12060 1 1 1 1 01 1 12 j 00 0 0 00 0 0 01 200 2 1 m 2 1 x412 1 21 21 21 2 001 408 0 5 x1200 1 01 1 20 0 4 x120601011 j 03 0 0 0 000 1 2m 1 3 x8241001 20 0 5 x202400100 0 4 x120601011 j 0 0 0 03 000 1 2 m 该 LP 问题有多重解 T T XX8 0 0 0 0 4 2 1 最优解为 88 0 4 8 0 010 0 41 2 1 TT XXX 10 运筹学作业答案 13 8 z 第 3 章 对偶原理 P92P92P92P92 3 3 3 3 1 1 1 1 1 1 1 1 2 2 2 2 4 4 4 4 1 1 1 1 0 40322 603 634max 321 321 321 321 xxx xxx xxx ts xxxz 0 63 32 423 4060min 21 21 21 21 21 yy yy yy yy ts yy 2 2 2 2 0 12 1 23 201060min 321 321 321 321 321 xxx xxx xxx xxx ts xxx 0 20 102 603 2max 321 321 321 321 321 yyy yyy yyy yyy ts yyyz 4 4 4 4 0 15352 1042 23max 321 321 321 321 xxx xxx xxx ts xxxz 为自由变量 21 21 21 21 21 234 352 12 1510min yy yy yy yy ts yy P92P92P92P92 3 3 3 3 2 2 2 2 6 6 6 6 6 6 6 6 0 0 0 4352 188372 217443 632max 421 4321 4321 4321 4321 xxx xxxx xxxx xxxx ts xxxxz 0 0 1387 6534 3274 223 41821min 32 321 321 321 321 321 yy yyy yyy yyy yyy ts yyy 运筹学作业答案 14 P93P93P93P93 3 3 3 3 6 6 6 6 1 1 1 1 用对偶单纯形法求解 用对偶单纯形法求解 用对偶单纯形法求解 用对偶单纯形法求解 LPLPLPLP 问题问题问题问题 解 0 63 5 42 2max 54321 521 41 321 21 xxxxx xxx xx xxx ts xxz j c 1 2 000 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 3 x 4 1 2 100 0 4 x510010 0 5 x6 3 1 001 1 2 000 1 32 0 3 x 2 0 3 5 10 3 1 0 4 x30 3 1 011 3 1 1 x211 300 3 1 0 3 5 00 3 1 11 2 2 x6 501 5 3 0 1 5 0 4 x17 500 5 1 12 5 1 1 x8 5101 50 5 2 001 00 0 0 0 0 5 x6053 01 0 4 x101 110 1 1 x4121 00 运筹学作业答案 15 00 0 0 01 00 该 LP 问题有多重解 T T XX0 4 5 6 5 8 2 1 最优解为 5 6 5 12 4 0 41 5 6 5 8 1 2 1 T T XXX 10 4 z 运筹学作业答案 16 P93P93P93P93 3 3 3 3 7 7 7 7 解 1 设甲 乙 丙三种产品每月的产量分别为 321 xxx件 建立 LP 模型为 0 50022 4002 23max 321 321 321 321 xxx xxx xxx ts xxxz j c 32100 i B C B Xb 1 x 2 x 3 x 4 x 5 x 0 4 x40012110400 0 5 x500 2 2 2 2 1201250 j 32100 0 4 x1500 3 23 23 23 2 012 1 100 3 1 x25011 2101 2500 j 01 22 02 3 2 2 x1000102 33 1 3 1 x2001013 1 2 3 j 002 3 1 3 4 0 j 则最优解为 T X 0 100 200 即 每月生产甲产品 200 件 乙产品 100 件 最大总产值为 800 千元 2 对偶问题为 0 12 22 32 500400min 21 21 21 21 21 yy yy yy yy ts yy 运筹学作业答案 17 由对偶性质可得 3 4 3 1 Y 即 A 设备的影子价格为 1 3 千元 即 3 1000 元 350 元 故外租外厂 A 设备不划算 补充作业 补充作业 1 已知线性规划问题 0 20232 20322 432max 4321 4321 4321 4321 xxxx xxxx xxxx ts xxxxz 其对偶问题的最优解为 2 0 2 1 Y 28 试用对偶性质求出原问题的最优解 解 该问题的对偶问题为 0 4 423 3 332 2 22 1 12 2020min 21 21 21 21 21 21 yy yy yy yy yy ts yy 将对偶问题的最优解 2 0 2 1 Y代入到对偶问题的所有函数约束中去 发现 1 2 为严格不等式 由互补松弛性定理 或松紧定理 知0 2 1 xx 又因02 0 02 1 21 yy 由互补松弛性定理 或松紧定理 知原问题的两个约束条 件应该取严格等式 综上可得 2023 2032 4 3 4 3 xx xx 解得 4 4 4 3 x x 故原问题的最优解为 TX4 4 0 0 28 z 运筹学作业答案 18 第 5 章 运输模型 P144P144P144P144 5 5 5 5 1 1 1 1 解 1234产量 i u 1527 513 10 4 5 2 120 26 528 10 45 0 6 7 171 5 34 10 75 0 515 5 1 111 销量1010101040 j v 36 534 5 05 0 3223 则该方案为非最优方案 又7 4 3223 cc 则 23 x为进基变量 调整量7 t 24 x为离基变量 新方案为 1234产量 i u 1527 50 53 3 4 5 9 120 26 52 58 10 4 7 6171 34 10 71 515 5 1 111 销量1010101040 j v 3734 5 01 32 则该方案仍不是最优方案 32 x为进基变量 调整量1 t 34 x为离基变 量 调 拨 站 工 厂 调 拨 站 工 厂 运筹学作业答案 19 新方案为 1234产量 i u 1517 50 53 2 4 5 10 120 26 51 58 9 4 8 60 5171 34 10 7 1 525 51110 销量1010101040 j v 4734 5 此时 0 ij 此方案为最优方案 100202 z 元 调 拨 站 工 厂 运筹学作业答案 20 第 6 章 整数规划 P171P171P171P171 6 6 6 6 2 2 2 2 2 2 2 2 解 先用图解法求出松弛问题的最优解为 T X 3 10 2 3 3 10 2 3 21 xx 3 1 2 1 21 xx 9 5 2 2 21 xx 2 1 2 1 x x 无可行解 2 14 5 2 2 1 x x 3 2 x 无可行解 2 2 2 1 x x 1 3 2 1 x x 2 2 x2 2 x 3 2 x3 2 x 1 1 x 2 1 x 2 1 x 3 1 x 由上可知 该 IP 问题的最优解为 T T X1 32 2 或 4 z 运筹学作业答案 21 P171P171P171P171 6 6 6 6 2 2 2 2 4 4 4 4 解 将原问题转化为求 为整数 21 1 21 21 21 0 133 455 2max xx x xx xx ts xxz 其松弛问题的最优解为 T X 3 1 0 3 1 0 21 xx 0 2 x1 2 x 无可行解 无可行解 0 3 1 5 4 2 1 x x 1 3 4 5 9 2 1 x x 与0 1 x相矛盾 则原 IP 问题无可行解 运筹学作业答案 22 P172P172P172P172 6 6 6 6 5 5 5 5 解 此题满足标准指派问题的三个条件 直接用匈牙利法求解如下 ijij bc 00341 02531 01312 31042 11700 02344 04534 03315 33045 13703 13455 26756 36648 77489 24814 00341 02531 01312 31042 11700 00341 01420 00201 41042 21700 即解矩阵为 01000 00001 10000 00100 00010 指派方案为 机床 1 加工零件 2 机床 2 加工零件 3 机床 3 加工零件 5 机床 4 加工零件 1 机床 5 加工零件 4 总加工费用为 1736341 z 元 运筹学作业答案 23 P173P173P173P173 6 6 6 6 7 7 7 7 解 1 该指派问题要求目标函数最大化 根据匈牙利法适用的标准指派问题三必要条件应 先化为最小化问题 记 ijijij cMbcM 1000 14640 30205 04510 30042 31240 24750 40315 14620 40152 41350 24750 51426 25731 40152 52461 14640 30205 04510 30042 31240 03530 30206 04510 30043 20130 即解矩阵为 00001 00010 10000 00100 01000 指派方案为 甲翻译德文 乙翻译日文 丙翻译法文 丁翻译俄文 戊翻译英文 总翻译效率为 43001000800800900800 z 印刷符号 小时 2 由于甲不能胜任翻译德文 乙不能胜任翻译日文 效益矩阵变化为 24750 51426 25731 4052 5461 M M 24750 40315 14620 4052 4350 M M 14440 30005 04310 3042 3040 M M 即解矩阵为 00001 00010 10000 01000 00100 运筹学作业答案 24 指派方案为 甲翻译日文 乙翻译德文 丙翻译法文 丁翻译俄文 戊翻译英文 总翻译效率为 420010008008001000600 z 印刷符号 小时 第 8 章 网络分析 P232P232P232P232 8 8 8 8 1 1 1 1 解 1 1 G 3 G 2 G 4 G 不连通图 2 真子图EEVV 432 GGG是 1 G的真子图 支撑子图EEVV 42 G G是 1 G的支撑子图 3 65345211 vvvvvvv 开链 简单链 6452312 vvvvvv 开链 简单链 初等链 3256433 vvvvvv 闭链 简单链 圈 246524 vvvvv 闭链 简单链 圈 245241325 vvvvvvvv 闭链 简单链 圈 运筹学作业答案 25 65245216 vvvvvvv 开链 P233P233P233P233 8 8 8 8 5 5 5 5 a a a a b b b b c c c c 解 a 1 2 467 35 14 T b 13 47 86 52 16 T 运筹学作业答案