运筹学基础(第2版)何坚勇第四章习题答案.ppt

第四章习题 4 2 已知线性规划问题maxz 3x1 2x2s t x1 2x2 43x1 2x2 14x1 x2 3x1 x2 0 minf 4w1 14w2 3w2s t w1 3w2 3w2 32w1 2w2 w2 2w1 w2 w2 0 2 如果愿问题与对偶问题都有可行解 则二者都有最优解 由原题可见 下列解是原问题与对偶问题的可行解 X 0 0 0 TW 0 0 1 0 T 4 3 minz 2x1 x2 2x3s t x1 x2 x3 4 x1 x2 Kx3 6X1 0 X2 0 X3无约束最优解 X 0 5 0 1 T 先变成变量大于0 写出符合4 18 4 11 4 06条件的标准型 minz 2x1 x2 2x3s t x1 x2 x3 4 x1 x2 Kx3 6X1 0 X2 0 X3无约束最优解 X 0 5 0 1 T maxz 2x1 x2 2x3s t x1 x2 x3 4 x1 x2 Kx3 6X1 0 X2 0 X3无约束最优解 X 0 5 0 1 T 写出对偶问题 minf 4w1 6w2s tw1 w2 2w1 w2 1w1 kw2 2w1无约束 w2 0 令X 1 X1maxz 2x 1 x2 2x3s tx 1 x2 x3 4x 1 x2 Kx3 6X 1 0 X2 0 X3无约束最优解 X 0 5 0 1 T 写出目标等式和互补松紧条件 根据定理4 2 5 X 0 5 0 1 TZ 2x 1 x2 2x3 2 5 0 2 1 12 f Z 4w1 6w2 124 2 7 w1 0w2 2 4 2 7w1 w2 2 求解 代入w1 kw2 1A求得K 1 4 4对偶问题 minf 20w1 20w2s tw1 2w2 12w1 w2 22w1 3w2 33w1 2w2 4w1 0 w2 0 maxz x1 2x2 3x3 4x3s tx1 2x2 2x3 3x4 202x1 x2 3x3 2x4 20X1 X2 X3 0无约束 续 W 1 1 2 0W 2 0 2 0由互补松弛条件可得 x1 2x2 2x3 3x4 20 4 4 1 2x1 x2 3x3 2x4 20 续 将W 1 1 2 W 2 0 2代入对偶问题的约束条件 w1 2w2 1 2 2 0 2 1 6 12w1 w2 2 1 2 0 2 2 6 22w1 3w2 2 1 2 3 0 2 33w1 2w2 3 1 2 2 0 2 4 由互补松弛条件定理可知 X 1 0 X 2 0代入 4 4 1 得x1 2x2 2x3 3x4 20 4 4 1 2x1 x2 3x3 2x4 20解得 x 3 4x 4 4原问题最优解 X 0 0 4 4 T 4 5 minz 8x1 6x2 3x3 6x4s tx1 2x2 x4 33x1 x2 x3 x4 6x3 x4 23x1 x3 2Xj 0 j 1 2 3 4最优解 X 0 1 1 2 0 T 化标准型 maxz 8x1 6x2 3x3 6x4s t x1 2x2 x4 3 3x1 x2 x3 x4 6 4 5 1 x3 x4 2 3x1 x3 2Xj 0 j 1 2 3 4最优解 X 0 1 1 2 0 T 写对偶问题 minf 3w1 6w2 2w3 2w4s t w1 3w2 w4 8 2w1 w2 6 w1 w3 w4 3 4 5 2 w1 w2 w3 4wi 0I 1 2 3 4 maxz 8x1 6x2 3x3 6x4s t x1 2x2 x4 3 3x1 x2 x3 x4 64 5 1 x3 x4 2 3x1 x3 2Xj 0 j 1 2 3 4最优解 X 0 1 1 2 0 T 互补松弛条件 最优解 X 0 1 1 2 0 T即Xj 0 j 1 2 3s t w1 3w2 w4 8 2w1 w2 6 4 5 3 w1 w3 w4 3 代原问题约束条件左端 X 0 1 1 2 0 T x1 2x2 x4 1 2 0 33x1 x2 x3 x4 3 1 2 0 6x3 x4 2 0 23x1 x3 1 2 2互补松弛定理w4 0 w4 0代入对偶问题约束条件 s t w1 3w2 w4 8 2w1 w2 6 4 5 3 w1 w3 w4 3w4 0解得 w1 2w2 2w3 1对偶问题最优解 w 2 2 1 0 T 4 7 已知线性规划问题maxz 10 x1 5x2s t3x1 4x2 95x1 2x2 8x1 x2 0 化成标准型maxz 10 x1 5x2s t3x1 4x2 x3 95x1 2x2 x4 8x1 x2 0 A 表4 7 B 1 1 C C C 1 目标函数中的价值系数c1 c2分别在什么范围内变动时 上述最优解不变 当C由C C C时新检验数 C C CB CB B 1A4 5 2目标涵数Z CB CB B 1b4 5 3若 0时 最优解仍为最优解 目标值发生了变化 否则 重新迭代 解 c1C 1 变量 C CB CB B 1A变 C C BB 1A C 1 5 0 0 5 C 1 B 1 P1 P2 P3 P4 B E E B 1 B 1 5 14 3 14 1 72 7 B C 5 C 1 B B 5 C 1 4325 B B 4 5 3 2 14 B11B21B12B22 B 4325 B21 1 1 2 3 5 3 24 5 14 3 14 1 72 7 B 1 5 C 1 P P1 P2 P3 P4 34105201 A HV 代入 C 1 5 0 0 5 C 1 B 1 P1 P2 P3 P4 C 1 5 0 0 5 C 1 5 14 3 14 1 72 7 34105201 C 1 5 0 0 C 1 5 25 2C 1 14 4C 1 25 14 每个分量小于0 0 0 25 2C 1 14 4C 1 15 14 25 2C 1 14 0C 1 25 2 4C 1 15 14 0C 1 15 4 15 4 C 1 25 2 B B C 1 C 2 3452 B B 4 5 3 2 14 B11B21B12B22 B 3452 B21 1 1 2 4 2 4 53 1 72 75 14 3 14 B 1 代入 C 1 5 0 0 C 1 5 B 1 P1 P2 P3 P4 C 1 5 0 0 C 1 5 1 72 75 14 3 14 34105201 C 1 5 0 0 C 1 5 25 2C 1 14 4C 1 25 14 矩阵乘法的性质 AB C A BC A B C AC BCC A B CA CBK AB KA B A KB 2 约束右端项b1 约束右端项b1 b2当一个不变时 另一个在什么范围变化时 原问题的最优解保持不变 解 当右端列向量bb b改变第三列XB B 1bX B B 1 b b Z CBB 1b Z CBB 1 b b A 若X B B 1 b b 0因为 没有变则最优基不变 最优解为X B和Z 不大于0 B 若X B B 1 b b 0因为 0没有变 X B B 1 b b X N 0 X BX N B 1 b b 0 正则解 b2不变 X B B 1 b b 5 14 3 14 1 72 7 b 18 0 5b 1 24 14 16 b 1 7 求解不等式 5b 1 24 14 0 16 b 1 7 0 24 5 b 1 16 解法2 1 解 1 当其它值不变 C1发生变化后最优单纯表变为如下 要保持最优解不变 所有检验数应 0故 25 2C 1 14 0 C 1 25 2 4C 1 15 14 0 C 1 15 4所以15 4 C 1 25 2 2 b10 3 21 5 14 1 7 00 2 由于目标函数中其它参数不变 b1变化不影响检验数 如果变化后XB 0那么最优基也不变 B 1b B 1 b1 b1 21 5 b1 7 b1 b1 24 5 b1 b1 16 b1的范围是 21 5 7 即b1的范围是 24 5 16 3 目标函数 目标函数变为maxz 12x1 4x2时 最优解如何变化 根本是c1 c2同时变化 解 基变量 C CB CB B 1A变 C C BB 1A C 1 C 2 0 0 C 2 C 1 B 1 P1 P2 P3 P4 B E E B 1 B 1 5 14 3 14 1 72 7 P P1 P2 P3 P4 34105201 代入 C 1 C 2 0 0 C 2 C 1 B 1 P1 P2 P3 P4 C 1 C 2 0 0 C 2 C 1 5 14 3 14 1 72 7 34105201 C 1 C 2 0 0 C 1 C 2 5C 2 2C 1 14 4C 1 3C 2 14 每个分量 0 0 5C 2 2C 1 14 4C 1 3C 2 14 0 0 2 7 18 7 表4 7 1 表4 7 2 表4 7 2 最优解 X 8 5 0 21 5 0 T 4 右端项 约束右端项由变为最优解为多少 98 1119 X B X B B 1 b b 5 14 3 14 1 72 7 1119 1 727 7 B 1 5 14 3 14 1 72 7 B 1 表4 7 41 表4 7 42 表4 7 43 表4 7 43 最优解 X 11 3 0 0 2 3 T 4 6题 其中X2变为X2 500 即某一个约束的右端项变化为350