【正文】 2/ 5 1/ 52 X111/51 0 7/ 5 1/ 5 2/ 5σj0 0 9/ 5 8/ 5 1/ 5線性規(guī)劃問題的進一步研究（ ） 51 靈敏度分析 ? 進一步理解最優(yōu)單純形表中各元素的含義 考慮問題 Max z = c1 x1 + c2 x2 + … + c n xn . a11 x1 + a12 x2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn ≤ b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ bm x1 ， x2 ， … ， xn ≥ 0 引入 m 個松弛變量后，通過計算得到最優(yōu)單純形表。應 1 1 能夠找到最優(yōu)基 B的逆矩陣 B ，以及 B N，檢驗數(shù)等。 線性規(guī)劃問題的進一步研究（ ） 52 線性規(guī)劃問題的進一步研究（ ） c1 ?cn0 ? 0CBXB x1 ?xnxn + 1 ?xn + mθi0 xn + 1b1a11 ?a1n1 ? 0 θ10 xn + 2b2a21 ?a2n0 ? 0 θ2┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇0 xn + mbmam1 ?amn0 ? 1 θmz f c1? cn0 ? 0c1 ?cncn + 1 ?cn + mCBXB x1 ?xnxn + 1 ?xn + mθici 1xi 1b1a11 ?a1na1 n + 1 ?a1 n + m θ 1ci 2xi 2b2a21 ?a2na2 n + 1 ?a2 n + m θ 2┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇Ci mxi mbmam1 ?amnam n + 1 ?am n + m θ mz f σ1? σnσn + 1? σn + m 最優(yōu)單純形表 B1 (BT)1cB I O 53 ? 價值系數(shù) C發(fā)生變化： m 考慮檢驗數(shù) ?j = cj ∑ cri arij j = 1,2,……,n i = 1 若 ck 是非基變量的系數(shù)： 設 ck 變化為 ck + ?ck ?k’= ck + ?ck ∑ cri arik = ?k+ ?ck 只要 ?k’≤ 0 ，即 ?ck ≤ ?k ， 則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù) ?k 用 ?k’取代，繼續(xù)單純形法的表格計算 。 例 : Max Z = 2x1 3x2 4x3 . x1 2x2 x3 + x4 = 3 2x1 + x2 3x3 + x5 = 4 x1 , x2 , x3 , x4 , x5 ≥ 0 線性規(guī)劃問題的進一步研究（ ） 54 例：最優(yōu)單純形表 從表中看到 σ 3 = C3 +Δ C3 （ C2 * a13 + C1* a23 ） 可得到 Δ C3 ≤ 9/5 時，原最優(yōu)解不變。 線性規(guī)劃問題的進一步研究（ ） C I 2 3 4 0 0C B X B b X 1 X 2 X 3 X 4 X 53 X 2 2/ 5 0 1 1 / 5 2 / 5 1/ 52 X 1 11/ 5 1 0 7/ 5 1 / 5 2 / 5σ j 0 0 9 / 5 8 / 5 1 / 5C I 2 3 4 + Δ c30 0C B X B b X 1 X 2 X 3 X 4 X 53 X 2 2/ 5 0 1 1/ 5 2/ 5 1/ 52 X 1 11 / 5 1 0 7/ 5 1/ 5 2/ 5σ j 0 0 9/ 5 + Δ c 3 8/ 5 1/ 555 若 cs 是基變量的系數(shù)： 設 cs 變化為 cs + ?cs ，那么 ?j’= cj ∑ cri arij ( cs + ?cs ) asj = ?j ?cs asj ，對所有非基變量 i ≠ s 只要對所有非基變量 ?j’≤ 0 ，即 ?j ≤ ?cs asj ， 則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù) ?j 用 ?j’取代，繼續(xù)單純形法的表格計算 。 Max{?j / asj ? asj 0 } ≤ ?cs ≤ Min{?j / asj ? asj 0 } 例 : Max Z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 . x1 + 2x2+ x3 = 8 4x1 + x4 =16 4x2 +x5 = 12 x1 , x2 , x3 , x4 , x5 ≥ 0 線性規(guī)劃問題的進一步研究（ ） 56 例、下表為最優(yōu)單純形表，考慮基變量系數(shù) c2 發(fā)生變化 從表中看到 σ j = Cj （ C1 * a1j + C5 * a5j + （ C2 +Δ C2 ） * a2j ） j = 4 可得到 3 ≤ Δ C2 ≤ 1 時，原最優(yōu)解不變。 C i2 3 0 0 0CBXBB X1X2X3X4X52 X14 1 0 0 1/ 4 00 X54 0 0 2 1/ 2 13 X22 0 1 1/ 2 1 / 8 0σj 0 0 1 / 8 0Ci2 3+ Δ C 2 0 0 0CBXBB X1X2X3X4X52 X14 1 0 0 1/ 4 00 X54 0 0 2 1/ 2 13+ Δ C2 X 2 2 0 1 1/ 2 1 / 8 0σj 0 0 1 . 5 Δ C 2 /2 1 / 8 + Δ C 2 /8 0線性規(guī)劃問題的進一步研究（ ） 57 ? 右端項 b 發(fā)生變化 設分量 br 變化為 br + ?br ，根據(jù)第 1章的討論，最優(yōu)解的基變量 xB = B1b，那么只要保持 B1(b + ?b) ≥ 0 ，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對偶單純形法繼續(xù)計算。 對于問題 (LP) Max z = cT x . Ax ≤ b x ≥ 0 最優(yōu)單純形表中含有 B1 = （ aij ） i = 1, … , m 。 j = n+1, … , n+m 那么，新的 xi = (B1b)i + ?br air i = 1, … , m 。由此可得，最優(yōu)基不變的條件是 Max{bi / air ? air 0 } ≤ ?br ≤ Min{bi / air ? air 0 } 線性規(guī)劃問題的進一步研究（ ） 58 例、上例最優(yōu)單純形表如下 ? 0 0 ? 這里 B1 = ? 2 1 ? 各列分別對應 b b b3 的單一 ? 0 ? 變化。因此，設 b1 增加 4，則 x1 , x5 , x2 分別變?yōu)椋? 4 + 0*4 = 4， 4 + (2)*4 = 4 0， 2 + *4 = 4 用對偶單純形法進一步求解，可得： x* = ( 4, 3, 2, 0, 0 )T f* = 17 線性規(guī)劃問題的進一步研究（ ） C i2 3 0 0 0CBXBB X1X2X3X4X52 X14 1 0 0 1/ 4 00 X54 0 0 2 1/ 2 13 X22 0 1 1/ 2 1 / 8 0σj 0 0 1 / 8 059 ? 增加一個變量 增加變量 xn+1 則有相應的 pn+1 ， +1 。那么，計算出 B1pn+1 ?n+1 = +1 ∑ cri ari n+1 填入最優(yōu)單純形表，若 ?n+1 ≤ 0 則最優(yōu)解不變；否則，進一步用單純形法求解。 例、前例增加 x6， p6 = ( 2, 6, 3 )T ， c6 = 5 。計算得到 線性規(guī)劃問題的進一步研究（ ） Ci2 3 0 0 0 5CBXBb X1X2X3X4X5X62 X14 1 0 0 1/ 4 0 1. 50 X54 0 0 2 1/ 2 1 [ 2]3 X22 0 1 1/ 2 1/ 8 0 0. 25σj0 0 1. 5 1/ 8 0 1. 25用單純形法進一步求解，可得： x* = ( 1,0,0,0,2 )T f* = 60 ? 增加一個約束 增加約束一個之后，應把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個新的非負變量（原約束若是小于等于形式可引入非負松弛變量，否則引入非負人工變量），并通過矩陣行變換把對應基變量的元素變?yōu)?0，進一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻? 例、前例增加 3x1+ 2x2≤15，原最優(yōu)解不滿足這個約束。于是 線性規(guī)劃問題的進一步研究（ ） Ci2 3 0 0 0 5CBXBb X1X2X3X4X5X62 X14 1 0 0 1/ 4 0 00 X54 0 0 2 1/ 2 1 03 X22 0 1 1/ 2 1/ 8 0 00 X61 0 0 1 1/ 2 0 1σj0 0 1. 5 1/ 8 0 061 ? A中元素發(fā)生變化 （只討論 N 中某一列變化情況） 與增加變量 xn+1 的情況類似，假設 pj 變化 。那么，