运筹学第一章习题完整版.pdf

第一章习题答案 第一章习题答案 1 用 Xj j 1 2 5 分别代表 5 中饲料的采购数 线性规划模型 12345 1234 1234 1234 min0 20 70 40 30 8 326700 0 50 20 530 0 20 8100 1 2 3 4 5 6 0 j zxxxxx stxxxxx xxxxx xxxxx xj 5 5 5 18 2 0 5 2 2 解 设 123456 x x x x x x x 表示在第 i 个时期初开始工作的护士人数 z 表示所需的总 人数 则 123456 16 12 23 34 45 56 min 60 70 60 50 20 30 1 2 3 4 5 6 0 i zxxxxxx stxx xx xx xx xx xx x i 3 解 设用 i 1 2 3 分别表示商品 A B C j 1 2 3 分别代表前 中 后舱 Xij 表示装于 j 舱的 i 种商品的数量 Z 表示总运费收入则 111213212223313233 111213 212223 313233 112131 122232 132333 112131 max1000 700 600 600 1000 800 1057400 10575400 10571500 8652000 zxxxxxxxxx stxxx xxx xxx xxx xxx xxx xxx 122232 132333 112131 122232 132333 122232 112131 132333 8653000 8651500 865 0 15 865 865 0 15 865 865 0 1 865 0 1 2 3 1 2 3 ij xxx xxx xxx xxx xxx xxx xxx xxx xij 4 解 设第 i 周加工 i z 小时 其 1i z 为加工 产品的时间 2i z 为加工 的时间 i x i y 为参加生产 和 的人数 i n 为第 i 周开始接受培训的人数 i i 为第 i 周推迟交货的产品 和 的量 i a i b 表示第 i 周对产品 和 的需求量 minZ 878 111 1250 360 8 120 2240 7 0 50 6 iiii iii Zi n st 7 1 50 i i n 3 50 iii nxy 2 50 3 iiii xynn 2i 111 50 3xyn 222 50 3xyn 1 10 4010 iiii xza 2 6 406 iiii yzb 12 0 iiiiiiiiii x y z zzna b 综上所述得 minz 878 12 111 12 14400 240 7 240 0 50 6 iiiii iii zzin st 7 1 50 i i n 3 50 iii nxy 2 50 3 iiii xynn 2i 111 50 3xyn 222 50 3xyn 1 40010 iiii xza 2 2406 iiii yzb 12 0 iiiiiiiiii x y z zzna b 5 1 Z 4 2 12 12 12 1 2 max 610120 70 510 38 zxx stxx xx x x 解 如图 由图可得 10 6 16 T xZ 即该问题具有唯一最优解 10 6 Tx 3 无可行解 4 12 12 12 12 max56 22 232 0 zxx stxx xx x x 如图 由图知 该问题具有无界解 6 1 1234456 12344 123445 123446 1234456 max3425500 22 2214 32 zxxxxxxx stxxxxx xxxxxx xxxxxx xxxxxxx 2 2 0 2 12334 1233 12334 12334 max22330 4 6 zxxxxx stxxxx xxxxx xxxxx 2 0 7 1 系数矩阵 A 3 6 4 1 20C 123456 1236300 8102 0 p p p p p p 30000 种组合 11231 1236 814540 300 BPPPB 1 可构成基 求B的基本解 B b 0 40 12369100 8110 0116 3 3000001 7 6 y1 0 16 3 7 6 0 0 0 T 同理 y2 0 10 0 7 0 0 T y3 0 3 0 0 7 2 0 T y4 7 4 4 0 0 0 21 4 T y5 0 0 5 2 8 0 0 T y 6 0 0 3 2 0 8 0 T y 7 1 0 1 2 0 0 3 T y8 0 0 0 3 5 0 T y 9 5 4 0 0 2 0 15 4 T y 10 0 3 7 6 0 0 0 T y 11 0 0 5 2 8 0 0 T y 12 0 0 5 2 3 5 0 T y 13 4 3 0 0 0 2 3 4 T y 14 0 10 0 7 0 0 T y 15 0 3 0 0 7 3 0 T y 16 0 0 3 2 0 8 0 T 基可行解 每个 x 值都大于 0 y3 y6 y8 y12 y13 y15 y16 最优解 y3 y6 y15 y16 Zmax 3 p2 p3 p4 p2 p3 p5 p3 p4 p5 p2 p4 p5 为奇异 只有 16 个基 解 2 该线性问题最多有 2 4 6C 个基本解 基本解 Z 基本可行解最优解 1 X1 X2 X3 X4 2 4 11 2 0 0 3 2 5 0 11 5 0 3 1 3 0 0 11 6 4 0 1 2 2 0 5 0 1 2 0 2 6 0 0 1 1 8 基的定义 106 21350 314 B X1 X2 X3所对应的列向量可以构成基 B 由 X1 X2 X3 列向量构成 106 213 314 N 由 非基变量对应的向量构成 35 41 20 B b 10610 2131 314 0 13 5 00 37 5 0013 5 B 对应的基解 13 5 37 5 0 0 3 5 9 解 1 由图知 1 3 2 35 2 T xZ 单纯形法 化为标准形如下 12 123 124 max105 349 528 1 2 3 4 0 i zxx stxxx xxx x i C 10 5 0 0 b CB XB X1 X2 X3 X4 0 X3 3 4 1 0 9 0 X4 5 2 0 1 8 检验数 10 5 0 0 0 0 X3 0 14 51 3 5 21 5 10 X1 1 2 5 0 1 5 8 5 检验数 0 1 0 2 16 5 X2 0 1 5 14 3 14 3 2 10 X1 1 0 1 7 3 7 0 检验数 0 0 5 14 25 14 35 2 所以 1 3 2 35 2 T xZ 其中 0 0 8 5 0 1 3 2 A B C 对应T 对应T 对应T 0 0 9 8 8 5 0 21 5 0 1 3 2 0 0 9 2 A 点最大 Z 8 化为标准形 1234 123 12 max200 3515 224 1 2 3 4 0 i zxxxx stxxx xxx x i 4 6 0 点 0 0 15 24 A 点 4 0 3 0 Zmax 8 10 解 1 要使 A 0 0 成为最优解则需 C 0 且 d 0 2 要使 B 8 5 0 成为最优解则 C 0 且 d 0 或 C 0 且 d0 3 要使 C 1 3 2 成为最优解则 5 2 C d 3 4 且 Cd 0 即 5 2 C d 3 4 且 Cd 0 4 要使 D 0 9 4 成为最优解则 C0 或 C 0 d 0 11 1 化为标准型 123 1234 123 123 max2 360 210 20 1 2 3 4 5 6 0 j zxxx stxxxx xxxx xxxx x i 5 6 C 2 1 0 0 b CB XB X1 X2 X3 X4 0 X3 3 5 1 0 15 0 X4 6 2 0 1 24 检验数 2 1 0 0 0 X3 0 4 1 1 2 3 X1 1 1 3 0 1 6 4 检验数 0 5 3 0 1 3 8 C 2 1 1 0 0 0 b CB XB X1 X2X3 X4 X5 X6 0 X4 3 1 1 1 0 0 60 0 X5 1 1 2 0 1 0 10 0 X6 1 1 1 0 0 1 20 检验数 2 1 1 0 0 0 0 0 X4 0 4 5 1 3 0 30 2 X1 1 1 2 0 1 0 10 0 X6 0 2 3 0 1 1 10 检验数 0 1 3 0 2 0 20 0 X4 0 0 1 1 1 2 10 2 X1 1 0 1 2 0 1 2 1 2 15 1 X2 0 1 3 2 0 1 21 2 5 检验数 0 0 3 2 0 3 2 1 2 25 T xZ 15 5 0 25 2 1234567 1234 123 13 23 max235 22312 228 616 4312 1 2 3 7 0 i zxxxxxxx stxxxx xxxx xxx xxx x i 5 6 7 0000 4 C 2 3 5 0 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 0 X4 2 2 3 1 0 0 0 12 0 X5 1 2 2 0 1 0 0 8 0 X6 4 0 6 0 0 1 0 16 0 X7 0 4 3 0 0 0 1 12 检验数 2 3 5 0 0 0 0 0 0 X4 0 2 0 1 0 1 2 0 4 0 X5 1 3 2 0 0 1 1 3 0 3 8 5 X3 2 3 0 1 0 0 1 6 0 3 8 0 X7 2 4 0 0 0 1 2 1 4 检验数 4 3 3 0 0 0 5 6 0 40 3 0 X4 1 0 0 1 0 1 4 1 22 0 X5 2 3 0 0 0 1 1 12 1 22 3 5 X3 2 3 0 1 0 0 1 6 0 8 3 3 X2 1 2 1 0 0 0 1 8 1 41 检验数 1 6 0 0 0 0 11 24 3 4 49 3 0 X4 0 0 0 1 2 3 1 8 1 41 2 X1 1 0 0 0 2 3 1 8 3 41 5 X3 0 0 1 0 1 1 4 1 22 3 X2 0 1 0 0 3 4 3 16 1 83 2 检验数 0 0 0 0 1 4 7 16 5 8 33 2 1 3 2 33 2 T xZ 1 1 0 0 3 标准型 12 13 2 12 max35 4 212 218 1 2 3 4 5 0 i zxx stxx xx xxx x i 4 5 3 C 3 5 0 0 0 b CB XB X1 X2X3 X4 X5 0 X3 1 0 1 0 0 4 0 X4 0 2 0 1 0 12 0 X5 3 2 0 0 1 18 检验数 3 5 0 0 0 0 X3 1 0 1 0 0 4 X2 0 1 0 1 2 0 6 X5 3 0 0 1 1 6 检验数 3 0 0 5 2 0 30 X3 0 0 1 1 3 1 32 X2 0 1 0 1 2 0 6 X1 1 0 0 1 3 1 3 2 检验数 0 0 0 3 2 1 36 T xZ 2 6 36 4 标准型 12344556678910 144667 123668 1355669 2310 123445 max0 9 34222 2226 4312 zxxxxxxxxxxMxMxx stxxxxxx xxxxxx xxxxxxx xxx xxxxxxx 56678910 xxxxxx 0 C 1 1 1 1 1 1 1 1 1 M M M 0 b CB XB X1 X2 X3 X4 X4 X5 X5 X6 X6 X7 X8 X9 X10 M X7 1 0 0 1 1 0 0 1 1 1 0 0 0 9 M X8 3 1 4 0 0 0 0 2 2 0 1 0 0 2 M X9 1 2 0 0 1 1 2 2 0 0 1 0 6 0 X10 0 4 3 0 0 0 0 0 0 0 0 0 1 12 检验数 5M 1 M 1 1 2M M 11 MM 1 1 M 5M 11 5M0 0 0 0 17M M X7 0 1 3 4 3 1 1 0 0 1 3 1 3 1 1 3 0 0 28 3 1 X1 1 1 3 4 3 0 0 0 0 2 3 2 3 0 1 3 0 0 2 3 M X9 0 1 3 10 3 0 0 1 1 4 3 4 3 0 1 3 1 0 16 3 0 X10 0 4 3 0 0 0 0 0 0 0 0 0 1 12 检验数 0 4 3 2 3M 14 5M 7 3 M 11 MM 1 M 1 5 3M 1 3 5 3M 1 3 0 5 3M 1 3 0 0 41 3M 2 3 M X7 0 1 5 0 1 1 2 5 2 5 1 5 1 5 1 1 5 2 5 0 31 5 1 X1 1 1 5 0 0 0 2 5 2 5 6 5 6 5 0 1 5 2 5 0 14 5 1 X3 0 1 10 1 0 0 3 10 3 10 2 5 2 5 0 1 10 3 10 0 8 5 0 X10 0 43 10 0 0 0 9 10 9 10 6 5 6 5 0 3 10 9 10 1 36 5 检验数 0 1 5M 11 10 0 M 11 M2 5M 17 10 2 5M 17 10 3 5 1 5M 1 5M 3 5 0 6 5M 7 5M0 31M 5 22 5 5 1234 1234 123 123 max62108 564420 32825 2310 1 2 3 4 0 j zxxxx stxxxx xxxx xxxx xj 4 4 5 4 解 标准化 1234 12345 1236 1237 max62108 564420 32825 2310 1 2 3 4 5 6 7 0 j zxxxx stxxxxx xxxxx xxxxx xj 4 4 5 4 C 6 2 10 8 0 0 0 b CB XB X1 X2X3 X4 X5X6 X7 0 X5 5 6 4 4 1 0 0 20 0 X6 3 32 8 0 1 0 25 0 X7 4 21 3 0 0 1 10 检验数 6 2 10 8 0 0 0 0 0 X5 21 20 8 1 1 4 60 0 X6 5 1 0 2 0 0 2 5 10 X3 4 21 3 0 0 1 10 检验数 34 220 22 0 0 10 100 0 X5 11 0 0 12 1 2 0 70 2 X2 5 1 0 2 0 1 2 5 10 X3 6 0 1 7 0 2 3 20 检验数 76 0 0 66 0 2234 210 由表可得 7 0 k p 0 且因此问题的解无界 6 化为 标准形 Z Z 123 146 246 34 max 425 233 265 1 2 3 4 5 6 0 i zxxxx stxxx xxxx xxxx x i 5 56 I C x 1 1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X X1 1 0 0 4 0 2 5 1 X2 0 1 0 2 3 1 3 1 X3 0 0 1 2 5 6 5 检验数 0 0 0 4 4x 8 7 2x5x 8 4401 7207 2 44722 3 xx xx xxx 如图 1 X 7 2 时 检验数 0 最优解 5 3 5 0 0 T 2 1 X 7 2 时 4 4X0 由 I 得 C x 1 1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X X1 1 0 1 3 10 3 5 3 0 20 3 1 X2 0 1 1 6 5 3 13 6 0 13 6 0 X6 0 0 1 6 1 3 5 6 1 5 6 检验数 0 0 X 3 7 6 10X 3 5 3 5X 3 13 60 20X 3 13 6 20 313 6 0 0 0 5 6 20 3 13 6 T xZX 3 X 2X 7 0 C x 1 1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X X1 1 2 0 0 6 0 11 1 X2 0 1 2 0 1 3 2 1 23 2 1 X3 0 1 1 0 2 5 2 检验数 0 2x 20 0 6X 25 11X 2 检验数 0 列系数 0 所以解无界 4 3 2 X4 4X 0 C x 1 1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X X1 1 0 0 10 3 5 3 0 20 3 1 X2 0 1 0 5 3 13 6 0 13 6 1 X6 0 0 1 1 3 5 6 1 5 6 检验数 X 3 7 6 10X 3 5 3 5X 3 13 6 20X 3 13 6 判断检验数的符号 10 35 301 2 5 3 13 6013 10 10 35 35 3 13 62 3 xx xx xxx 1 1 2 X 1 所有检验数 0 20 3 13 6 0 0 0 5 6 20 3 13 6 T xZX 1 2 X 2 1 3 X 1 2 时 表 A C x 1 1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X X1 1 2 0 0 6 0011 0 X4 0 3 5 1 10 1 13 100013 10 0 X6 0 1 5 1 5 0 2 5 112 5 检验数 0 2X 1 1 0 6X 0 11X 对 6X 讨论 令 6X 0 X 0 1 0 X 1 2 时 检验数 0 11 0 0 13 10 0 2 5 11 T xZX 0 X 1 2 2 1 3 X0 又 X5列的系数 0 所以解无界 3 1 5 X0 又 X5的列的系数 0 所以解无界 7 123 123 123 123 123 max64 2213 20 217 123 zxxx stxxx xxx xxx xxx 4 解 化为标准形 123101112 1234 1235 1236 1710 2811 3912 max64 2213 20 217 1 2 3 i zxxxMxMxMx stxxxx xxxx xxxx xxx xxx xxx x 4 0 1 2 3 11 i C 1 6 4 0 0 0 0 0 0 M M M b CB XB X1 X2 X3 X4 X5X6X7 X8X9 X10 X11 X12 0 X4 1 2 2 1 0 0 0 0 0 0 0 0 13 0 X5 4 4 1 0 1 0 0 0 0 0 0 0 20 0 X6 1 2 1 0 0 1 1 0 0 0 0 0 17 M X10 1 0 0 0 0 0 0 0 0 1 0 0 1 M X11 0 1 0 0 0 0 0 1 0 0 1 0 2 M X12 0 0 1 0 0 0 0 0 1 0 0 1 3 检验数 1 M 6 M 4 M 0 0 0 M M M 0 0 0 0 X4 1 0 2 1 0 0 0 2 0 0 2 0 9 0 X5 4 0 1 0 1 0 0 4 0 0 4 0 26 0 X6 1 0 1 0 0 1 0 2 0 0 2 0 13 M X10 1 0 0 0 0 0 1 0 0 1 0 0 1 6 X2 0 1 0 0 0 0 0 1 0 0 1 0 2 M X12 0 0 1 0 0 0 0 0 1 0 0 1 3 检验数 1 M 0 4 M 0 0 0 M 6 M 0 6 M 0 0 X4 1 0 0 1 0 0 0 2 2 0 2 2 3 0 X5 4 0 0 0 1 0 0 4 1 0 4 1 25 0 X6 1 0 0 0 0 1 0 2 1 0 2 1 10 M X10 1 0 0 0 0 0 1 0 0 1 0 0 1 6 X2 0 1 0 0 0 0 0 1 0 0 1 0 2 4 X3 0 0 1 0 0 0 0 0 1 0 0 1 3 检验数 1 M 0 0 0 0 0 M 6 4 10 6 M 4 M 0 X4 0 0 0 1 0 0 1 2 2 1 2 2 4 0 X5 0 0 0 0 1 004 4 1 4 4 1 21 0 X6 0 0 0 0 0 1 1 2 1 1 2 1 9 1 X1 1 0 0 0 0 0 1 0 0 1 0 0 1 6 X2 0 1 0 0 0 0 0 1 0 0 1 0 2 4 X3 0 0 1 0 0 0 0 0 1 0 0 1 3 检验数 0 0 0 0 0 0 1 6 4 0 X8 0 0 0 1 2 0 0 1 21 1 1 2 1 1 2 0 X5 0 0 0 2 1 0 2 0 5 2 0 5 29 0 X6 0 0 0 1 0 1 2 0 1 2 0 1 5 1 X1 1 0 0 0 0 0 1 0 0 1 0 0 1 6 X2 0 1 0 1 2 0 0 1 20 1 1 2 1 2 1 4 4 X3 0 0 1 0 0 0 0 0 1 0 0 1 3 检验数 0 0 0 3 0 0 4 0 2 0 X8 0 0 0 1 4 0 1 40 1 3 4 0 1 3 4 13 4 0 X5 0 0 0 3 1 1 0 0 6 0 0 6 24 0 X7 0 0 0 1 20 1 21 0 1 2 1 0 1 2 5 2 1 X1 1 0 0 1 20 1 20 0 1 20 0 1 2 7 2 6 X2 0 1 0 1 4 0 1 40 0 3 4 0 0 3 4 21 4 4 X3 0 0 1 0 0 0 0 0 1 0 0 1 3 检验数 0 0 0 1 0 2 0 0 0 47 即 T xZ 7 2 21 4 3 47 为最优解 但该问题具有无穷多最优解 8 1233567 356 23 16 367 max33 36 210 0 6 1 2 7 0 j zxxxxxxx stxxx xxx xx xxx x i 4 解 化为标准形 123356711 356 23 16 36711 max33 36 210 0 6 1 2 0 j zxxxxxxxxxxx stxxxx xxxx xxx xxxx x i 910 49 10 MMMM 11 C 1 1 1 3 1 1 3 M M M M b CB XB X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 M X8 0 0 3 0 1 1 0 1 0 0 0 6 M X9 0 1 2 1 0 0 0 0 1 0 0 10 M X10 1 0 0 0 0 1 0 0 0 1 0 0 M X11 0 0 1 0 0 1 1 0 0 0 1 6 检验数 1 M M 1 6M 1 M 31 M 1 3M3 M0 0 0 0 1 X3 0 0 1 1 3 1 3 0 1 3 0 0 0 2 M X9 0 1 0 1 2 3 2 3 0 2 3 1 0 0 6 M X10 1 0 0 0 0 1 0 0 0 1 0 0 M X11 0 0 0 0 1 3 2 3 1 1 3 0 0 1 4 检验数 1 M M 1 0 M 32 3 M M 1 3 M 3 0 0 0 1 X3 0 0 1 0 1 3 1 3 0 1 3 0 0 0 2 1 X2 0 1 0 1 2 3 2 3 0 0 1 0 0 6 M X10 1 0 0 0 0 1 0 2 3 0 1 0 0 M X11 0 0 0 0 1 3 2 3 1 1 3 0 0 1 4 检验数 1 M 0 0 4 5 3M 2M 3 0 0 1 X3 0 0 1 0 1 2 0 1 2 1 2 0 0 1 20 1 X2 0 1 0 1 1 0 1 1 1 0 1 10 M X10 1 0 0 0 1 2 0 3 2 1 2 0 1 1 2 6 1 X6 0 0 0 0 1 2 1 3 2 1 2 0 0 3 2 6 检验数 1 M 0 0 4 1 2M 10 0 1 X3 1 1 1 0 0 0 1 0 0 1 1 0 1 X2 2 0 0 1 0 0 2 0 1 2 2 2 1 X5 2 0 0 0 1 0 3 1 0 2 3 12 1 X6 1 0 0 0 0 1 0 0 1 0 0 检验数 1 0 0 4 0 0 3 0 2 6 0 12 0 0 4 T xZ 12 1 解 标准形 1 123789 12347 138 236 max22 6 2 0 1 2 3 9 0 j zxxxMxMxMx stxxxxx xxxx xxxx x i 5 9 2 C 2 1 2 0 0 0 M M M b CB XB X1 X2 X3 X4 X5 X6 X7 X8 X9 M X7 1 1 1 1 0 0 1 0 0 6 M X8 1 0 1 0 1 0 0 1 0 2 M X9 0 2 1 0 0 1 0 0 1 0 检验数 2 1 3M 2 M M M M 0 0 0 M X7 1 0 3 2 1 0 1 2 1 0 1 2 6 M X8 1 0 1 0 1 0 0 1 0 2 1 X2 0 1 1 2 0 0 1 2 0 0 1 2 0 检验数 2 0 5 2M 3 2 M M 1 2M 1 20 0 M X7 5 2 0 0 1 3 2 1 2 1 3 2 1 2 3 2 X3 1 0 1 0 1 0 0 1 0 2 1 X2 1 1 0 0 1 2 1 2 0 1 2 1 2 1 检验数 5 2M 7 20 0 M 3 2M1 2M 0 2 X1 1 0 0 2 53 5 1 5 2 5 3 5 1 5 6 5 2 X3 0 0 1 2 5 2 5 1 5 2 52 5 1 5 16 5 1 X2 0 1 0 1 5 1 5 2 5 1 51 5 2 5 8 5 检验数 0 0 0 7 5 3 5 6 5 由表可知此题解无界 2得一辅助问题 789 12347 138 236 max 6 2 0 1 2 3 9 0 j wMxMxMx stxxxxx xxxx xxxx x i 5 9 2 C 0 0 0 0 0 0 1 1 1 b CB XB X1 X2 X3 X4 X5 X6 X7 X8 X9 1 X7 1 1 1 1 0 0 1 0 0 6 1 X8 1 0 1 0 1 0 0 1 0 2 1 X9 0 2 1 0 0 1 0 0 1 0 检验数 0 3 1 1 1 1 0 0 0 1 X7 1 0 3 2 1 0 1 21 0 1 26 1 X8 1 0 1 0 1 0 0 1 0 2 0 X2 0 1 1 2 0 0 1 20 0 1 20 检验数 0 0 5 2 1 1 1 20 0 3 2 1 X7 5 2 0 0 1 3 21 21 3 2 1 23 0 X3 1 0 1 0 1 0 0 1 0 2 0 X2 1 1 0 0 1 2 1 20 1 21 21 检验数 5 2 0 0 1 3 2 0 0 X1 1 0 0 2 5 3 51 52 5 3 5 1 56 5 0 X3 0 0 1 2 5 2 51 52 52 5 1 516 5 0 X2 0 1 0 1 5 1 5 2 51 51 52 58 5 检验数 0 0 0 0 0 0 1 1 1 0 5 6 5 8 5 16 5 0 0 6 5 8 5 16 5 0 0 0 T xxxxxxxxw x 1234789 其最优解为 其原问题的初始基本解可行解 C 2 1 2 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 2 X1 1 0 0 2 5 3 5 1 5 1 X3 0 0 1 2 5 2 51 5 2 X2 0 1 0 1 5 1 5 2 5 检验数 0 3 3 4 5 由表知此题属于解无界 2 大 M 法 先化为标准形 Z Z 123 14 12 12 max400 24 3 36 1 2 3 4 5 6 0 i zxxxxMxMx stxxx xxx xxxx x i 456 4 5 36 4 C 4 1 0 0 M Mb CB XB X1 X2 X3 X4 X5X6 0 X4 1 2 0 1 0 0 4 M X5 1 1 0 0 1 0 3 M X6 4 3 1 0 0 1 6 检验数 5M 4 4M 1 M 0 0 0 9M 0 X4 0 5 4 1 4 1 0 5 2 M X5 0 1 4 1 4 0 1 3 2 4 X1 1 3 4 1 4 0 0 3 2 检验数 0 M 4 2 M 4 1 0 0 3M 2 6 1 X2 0 1 1 5 4 5 0 2 M X5 0 0 1 5 1 5 1 1 4 X1 1 0 2 5 3 5 0 0 检验数 0 0 M 5 7 5 M 5 8 50 M 2 1 X2 0 1 0 1 1 0 X3 0 0 1 1 5 4 X1 1 0 0 1 2 0 0 0 3 9 原问题唯一最优解 二阶段法 引入人工变量 X5 X6 得原问题的一个辅助问题 14 12 12 max 24 3 36 1 2 3 4 5 6 0 i wxx stxxx xxx xxxx x i 56 4 5 36 4 C 0 0 0 0 1 1b CB XB X1 X2 X3 X4 X5X6 0 X4 1 2 0 1 0 0 4 M X5 1 1 0 0 1 0 3 M X6 4 3 1 0 0 1 6 检验数 5 4 1 0 0 0 9 0 X4 0 5 4 1 4 1 0 5 2 M X5 0 1 4 1 4 0 1 3 2 4 X1 1 3 4 1 4 0 0 3 2 检验数 0 1 4 1 4 0 0 3 2 1 X2 0 1 1 5 4 5 0 2 M X5 0 0 1 5 1 5 1 1 4 X1 1 0 2 5 3 5 0 0 检验数 0 0 1 5 1 5 0 1 1 X2 0 1 0 1 1 0 X3 0 0 1 1 5 4 X1 1 0 0 1 2 检验数 0 0 0 1 0 5 2 1 5 0 0 2 1 5 0 0 0 T xxxxxxw x 12346 其最优解为 其原问题的初始基本解可行解 C 4 1 0 0 b CB XB X1 X2 X3 X4 1 X2 0 0 1 1 5 0 X3 0 1 0 1 1 4 X1 1 0 0 1 2 检验数 0 0 0 3 9 3 123 123 12 min23 428 26 1 2 3 0 j zxxx stxxx xx xj 3 标准形 12378 12347 1258 min23 428 26 1 2 3 8 0 j zxxxMxMx stxxxxx xxxx xj 3 C 2 3 1 0 0 0 M M b CB XB X1 X2 X3 X4 X5 X6X7 X8 M X7 1 4 2 1 0 0 1 0 8 M X8 3 2 0 0 1 0 0 1 6 检验数 2 4M 6M 3 2M 1 M M 0 0 0 3 X2 1 4 1 1 2 1 4 0 0 1 4 0 2 M X8 5 2 0 1 1 2 1 0 1 21 2 检验数 5 2M 11 40 M 5 21 2M 3 4 M 0 0 3 X2 0 1 3 5 3 10 1 100 3 10 1 10 9 5 2 X1 1 0 2 5 1 5 2 50 1 52 5 4 5 检验数 0 0 18 5 13 10 0 3 X2 5 2 1 0 0 1 20 0 1 2 3 0 X4 5 0 2 1 2 0 1 2 4 检验数 0 1 0 3 2 0 M M 由表知此题解无界 6 两阶段法 78 12347 1258 max 428 26 1 2 3 8 0 j zxx stxxxxx xxxx xj 3 C 0 0 0 0 0 0 1 1 b CB XB X1 X2 X3 X4 X5 X6X7 X8 1 X7 1 4 2 1 0 0 1 0 8 1 X8 3 2 0 0 1 0 0 1 6 检验数 4 6 2 1 1 0 0 0 0 X2 1 4 1 1 2 1 4 0 0 1 4 0 2 1 X8 5 2 0 1 1 2 1 0 1 21 2 检验数 5 2M 11 40 M 5 2 1 2M 3 4 M 0 0 0 X2 0 1 3 5 3 10 1 100 3 10 1 109 5 0 X1 1 0 2 5 1 5 2 50 1 52 5 4 5 检验数 0 0 0 0 0 0 1 1 5 4 5 9 5 0 0 xxx xxxxw 123478 其最优解为 C 2 3 1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 3 X2 0 1 3 5 3 10 1 100 9 5 2 X1 1 0 2 5 1 5 2 50 4 5 检验数 0 0 18 5 13 10 0 3 X2 5 2 1 0 0 1 20 3 0 X4 5 0 2 1 2 0 4 检验数 0 1 0 3 2 0 由表知此题为解无界 4 123 123 123 123 max101512 539 561515 5 1 2 3 0 j zxxx stxxx xxx xxx x i 2 化为标准形 1237 1234 1235 12367 max101512 539 561515 5 1 2 3 7 0 j zxxxMx stxxxx xxxx xxxxx x i 2 C 10 15 12 0 0 0 Mb CB XB X1 X2 X3 X4 X5 X6X7 0 X4 5 3 1 1 0 0 0 9 0 X5 5 6 15 0 1 0 0 15 M X7 2 1 1 0 0 1 1 5 2M 10 M 15 12 M 0 0 M0 10 X1 1 3 5 1 5 1 5 0 0 0 9 5 0 X5 0 9 16 1 1 0 0 24 M X7 0 1 5 3 5 2 5 0 1 1 2 5 0 3 5M 0 0 10 X1 1 39 80 0 15 80 1 800 0 15 10 12 X3 0 9 16 1 1 16 1 160 0 3 2 M X7 0 43 80 0 35 80 3 80 1 1 1 2 0 0 0 13 1 1 00b 2 1 00 0 12 3 0 0 0 0d c c 第二章习题答案 第二章习题答案 1 解 设 123 xxx 分别表示 A B C 各产品的数量 Z 表示总产值则 123 123 123 123 max200300250 4260 240 3320 1 2 3 0 i zxxx stxxx xxx xxx x i 3 2 min604020 2 300 23250 wyyy styyy yyy yyy yyy 原问题的对偶问题为 3200 3 2 0 0 0 经济解释 y1 y2 y3分别表示给别人代工时所得收入 对厂方而言 w 越大越好 但定价 不能太高 要对方容易接受 应考虑使总收入即对方的总支出尽可能少才比较合理 厂方不 会吃亏 对方也容易接受 2 1 min1020 10 1 2 wyy styy yy yy yy 2 0 0 2 max235 32 42 764 0 wyyy styyy yyy yyy yyy 2 3 5 0 0 3 min538 45 576 33 0 wyyy styyy yyy yyy yyy 2 2 自由 0 max3 23 53 37 444 0 wyyy styy yyy yyy yyy yyy 52 2 2 3 3 4 0 0 3 证明 0 0 0 x 是线性问题的可行解 即该问题存在可行解 又 其对偶问题为 min2 21 1 0 0201 wyy styy yy yy yy y yyy 0 0 这与约束条件 不符 该对偶问题无可行解 原问题无最优解 4 证明 该线性问题的对偶问题为 00 min22 21 2 1 0 010 0 1 2 1 2 1 0 max T wyyy styyy yyy yyy yyy Y cxy b z 0 自由 易知 是对偶问题的一个可行解 由对偶问题的对偶定理可得 即最大值不超过1 1 5 证明 对偶问题 min4143 33 24 0 23 wyyy styyy yyy yyy T T 2 0 0 由题易知X 3 0 是原问题的一个可行解 Y 0 1 0 是对偶问题的一个可行解 由对偶问题的推论可得它们都有最优解 即得证 6 证明题没有做 7 1 对偶问题 min512 22 31 43 wyy styy yy yy yy 2 0 无符号限制 2 由题知原问题的最优解为 3 2 0 Tx 由互补松弛定理得 在对偶问题中对应第一 二个约束为紧 第三个约束条件为松 即 12 1 12 2 12 22 4 31 1 243 yy y yy y yy 对偶规划问题的最优解 1 41y 3 影子价格为 y1 4 8 解 先写出其对偶问题 min2020 21 2 33 324 wyy styy yy yy yy yy 2 2 0 0 对偶规划问题的最优解 1 12 12 1 20 2 0 0 yy xx yy Q 代入约束条件 知第1 2约束条件成立严格不等式 由互补松弛定理 原规划最优解中相应变量 又 不为 则在原问题规划中对应的约束条件为紧 得 3 34 34 4 42320 32204 xxx xxx 原对偶规划问题的最优解 0 0 4 4x 9 1 min3622 38 6 3 6 00 wyyyy styyy yy yyy yyy yyyy 4 4 12 234 4 2 0 0 5678 20 01 0 30082 2062 0031 61 2 21020 T Z X xxxx yyyy yyy yyy yyy yyyyy Yw T T 4567 88 2 1 1 2 0 把 1 1 2 0 代入约束条件可得 10 解 1112 2122 1112 2122 1 210 011 6 1 2 1 2 1 201020 1 61 30113 1 21 20 1 21 61 3 xx NB xx xx BB xx a NN b 1 1 1 1 0 1 由表知B 1 3 B令则 B B 1 31 3 22 1 1 0125 25 3115 210 61 20 42 101 61 3 442 Abb C CC C CC 1 B 1 2 1 123 23 123 max 10 1 2 3 0 i zxxx stxx xxx x i 原线性问题为 6210 2 5 3 2 min510 36 2 10 wyy sty yy yy yy 2 0 0 4535 3 5 2 0 5 2 40 00 34 22 4 T xZ xxyy yy yyyy yyy Y 2 4 T 6 即 2 10 4 2 w 40 11 解 1 设 123 xxx 分别表示甲 乙 丙各产品的数量 Z 表示总产值则 123 123 123 max32 2400 2500 1 2 3 0 i zxxx stxxx xxx x i 2 化为标准形 123 1234 1235 max32 2400 2500 1 2 3 4 5 0 i zxxx stxxxx xxxx x i 2 C 3 2 1 0 0 b CB XB X1 X2 X3 X4 X5 0 X4 1 2 1 1 0 400 0 X5 2 1 2 0 1 500 检验数 3 2 1 0 0 0 X4 0 3 2 0 1 1 2150 3 X1 1 1 2 1 0 1 2 250 检验数 0 1 2 2 0 3 2250 2 X2 0 1 0 2 3 1 3100 3 X1 1 0 1 1 3 2 3 200 检验数 0 0 2 1 3 4 3 800 200 100 800 T xZ 2 min400500 23 2 21 wyy styy yy yy yy 原问题的对偶问题为 2 0 0 此时 y1 y2分别表示出租 A B 设备所得利润 由 1 中的最优表得 1 y 1 3 即如出租 A 设备可获得 1000 3 元 而 1000 320 3 最优解将发生变化 100 3 0 2200 3 T xZ 200 3 C 10 6 4 0 0 0 b CB XB X1 X2X3 X4 X5 X6 6 X2 0 1 5 6 5 3 1 60 200 3 10 X1 1 0 1 6 2 3 1 60 100 3 0 X6 0 0 4 4 5 0 1 100 检验数 0 0 8 3 10 3 2 30 6 X2 0 1 0 3 2 1 6 5 24275 6 10 X1 1 0 0 7 10 1 3 1 24175 6 50 6 X3 0 0 1 1 5 0 1 4 25 0 0 0 11 3 2 3 5 12 2350 3 1 1 1 3max44 min 55 6 15 C C C 4 新产品的生产数量为 7 x 777 7 1 8 1 4 3 8 10 3 2 3 0 420 3 5 31 6011 2 31 6040 4 501319 5 T Cp p 则有 C 10 6 4 0 0 0 8 b CB XB X1 X2 X3 X4 X5 X6 X7 6 X2 0 1 5 6 5 3 1 60 1 200 3 10 X1 1 0 1 6 2 3 1 60 0 100 3 0 X6 0 0 4 4 5 0 1 19 5100 检验数 0 0 8 3 10 3 2 30 2 2200 3 6 X2 0 1 25 114 83 57 1 6 5 19 0 2300 57 10 X1 1 0 1 6 2 3 1 60 0 100 3 8 X7 0 0 20 9 4 19 0 5 19 1 500 19 检验数 0 0 544 114 214 57 2 3 10 190 27700 57 100 3 0 0 0 0 500 19 27700 57 T xZ 2300 57 值得安排生产 5 设生产 I 产品 X1件 生产 II 产品 X2件 III 产品 10 X1件 123 123 123 123 max1064 90 45550 26240 1 2 3 0 i zxxx stxxx xxx xxx x i 10 2 123 1234 1235 1236 max1064 90 45550 26240 1 2 34 5 6 0 i zxxx stxxxx xxxx xxxx x i 10 2 C 10 6 4 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 0 X4 1 1 1 1 0 0 90 0 X5 10 4 5 0 1 0 550 0 X6 2 2 6 0 0 1 240 检验数 10 6 4 0 0 0 0 X4 0 3 5 1 2 1 1 100 35 10 X1 1 2 5 1 2 0 1 100 55 0