運籌學(xué)基礎(chǔ)(第2版)何堅勇第四章習(xí)題答案.ppt

第四章習(xí)題 4 2 已知線性規(guī)劃問題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 如果愿問題與對偶問題都有可行解 則二者都有最優(yōu)解 由原題可見 下列解是原問題與對偶問題的可行解 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無約束最優(yōu)解 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無約束最優(yōu)解 X 0 5 0 1 T maxz 2x1 x2 2x3s t x1 x2 x3 4 x1 x2 Kx3 6X1 0 X2 0 X3無約束最優(yōu)解 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無約束最優(yōu)解 X 0 5 0 1 T 寫出目標等式和互補松緊條件 根據(jù)定理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無約束 續(xù) W 1 1 2 0W 2 0 2 0由互補松弛條件可得 x1 2x2 2x3 3x4 20 4 4 1 2x1 x2 3x3 2x4 20 續(xù) 將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原問題最優(yōu)解 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最優(yōu)解 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最優(yōu)解 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最優(yōu)解 X 0 1 1 2 0 T 互補松弛條件 最優(yōu)解 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對偶問題最優(yōu)解 w 2 2 1 0 T 4 7 已知線性規(guī)劃問題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 目標函數(shù)中的價值系數(shù)c1 c2分別在什么范圍內(nèi)變動時 上述最優(yōu)解不變 當C由C C C時新檢驗數(shù) C C CB CB B 1A4 5 2目標涵數(shù)Z CB CB B 1b4 5 3若 0時 最優(yōu)解仍為最優(yōu)解 目標值發(fā)生了變化 否則 重新迭代 解 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 矩陣乘法的性質(zhì) AB C A BC A B C AC BCC A B CA CBK AB KA B A KB 2 約束右端項b1 約束右端項b1 b2當一個不變時 另一個在什么范圍變化時 原問題的最優(yōu)解保持不變 解 當右端列向量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因為 沒有變則最優(yōu)基不變 最優(yōu)解為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發(fā)生變化后最優(yōu)單純表變?yōu)槿缦?要保持最優(yōu)解不變 所有檢驗數(shù)應(yīng) 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 由于目標函數(shù)中其它參數(shù)不變 b1變化不影響檢驗數(shù) 如果變化后XB 0那么最優(yōu)基也不變 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 目標函數(shù) 目標函數(shù)變?yōu)閙axz 12x1 4x2時 最優(yōu)解如何變化 根本是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 最優(yōu)解 X 8 5 0 21 5 0 T 4 右端項 約束右端項由變?yōu)樽顑?yōu)解為多少 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 最優(yōu)解 X 11 3 0 0 2 3 T 4 6題 其中X2變?yōu)閄2 500 即某一個約束的右端項變化為350