【正文】 ﹣ x1 ﹣ 2x2 ﹣ x3+ x4 =﹣ 3 ﹣ 2 x1+x2 ﹣ 3x3 +x5=﹣ 4 max z=﹣ 2 x1 ﹣ 3x2 ﹣ 4x3 x1,x2 ,x3 x4 ,x5 ≥0 解： cj ﹣ 2 ﹣ 3 ﹣ 4 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 ﹣ 3 ﹣ 4 ﹣ 1 [﹣ 2] ﹣ 2 1 ﹣ 1 ﹣ 3 1 0 0 1 δj ﹣ 2 ﹣ 3 ﹣ 4 0 0 θ 1 － 4/3 其中 x4,x5為松弛變量 37 運籌學基礎(chǔ) cj ﹣ 2 ﹣ 3 ﹣ 4 0 0 CB XB b x1 x2 x3 x4 x5 0 ﹣ 2 x4 x1 ﹣ 1 2 0 1 [﹣ 5/2] ﹣ 1/2 1/2 3/2 1 0 ﹣ 1/2 ﹣ 1/2 δj 0 ﹣ 4 ﹣ 1 0 ﹣ 1 θ ﹣ 8/5 ﹣ ﹣ 2 cj ﹣ 2 ﹣ 3 ﹣ 4 0 0 CB XB b x1 x2 x3 x4 x5 ﹣ 3 ﹣ 2 x2 x1 2/5 11/5 0 1 1 0 ﹣ 1/5 7/5 ﹣ 2/5 ﹣ 1/5 1/5 ﹣ 2/5 δj 0 0 ﹣ 9/5 ﹣ 8/5 ﹣ 1/5 原最優(yōu) X*=(11/5,2/5,0,0,0)T，對偶最優(yōu) Y*=(8/5,1/5) 運籌學基礎(chǔ) 38 第二章 線性規(guī)劃 ? 對偶問題的提出 ? 原問題與對偶問題的關(guān)系 ? 對偶問題的基本性質(zhì) ? 對偶單純形法 ? 靈敏度分析 39 靈敏度分析 運籌學基礎(chǔ) 在前面討論線性規(guī)劃問題時，假定 aij,bi,cj都是常數(shù) .但實際上這些參數(shù)往往是估計值和預測值 .所謂靈敏度分析 ,就是要研究初始單純形表上的系數(shù)變化對最優(yōu)解的影響 ,研究這些系數(shù)在什么范圍內(nèi)變化時 ,原最優(yōu)基仍是最優(yōu)；若原最優(yōu)基不再是最優(yōu)的，如何用最簡便的方法找到新的最優(yōu)解。 設(shè)資源 br發(fā)生變化，即 br′ =br +Δ br。并假定其它系數(shù)不變。則解變化為 XB′=B1(b+Δ b)，其中 Δb=(0, …, Δ b r， …,0 ） T。由于 br變化不影響檢驗數(shù)，所以只要 XB′≥0，最優(yōu)基不變 , XB′是最優(yōu)解。 下面分析 Δ br保持 XB′≥0的取值范圍： B1(b+Δ b)= B1b+B1 Δ b= B1b+B1 0 Δ br 0 40 運籌學基礎(chǔ) 下面分析 Δ br保持 XB′≥0的取值范圍： B1(b+Δ b)= B1b+B1 Δ b= B1b+B1 0 Δ br 0 B1 0 Δ br 0 = a1r ′Δ br air ′Δ br amr ′Δ br = Δ br a1r ′ air ′ amr ′ 要使 XB′≥0，只有 bi ′+air ′Δ br ≥0 ,i=1,2, …,m 所以 air ′Δ br ≥ ﹣ bi ′ ,i=1,2, …,m ① 當 air ′ 0時， Δ br ≥ ﹣ bi ′/ air ′ ② 當 air ′ 0時， Δ br ≤ ﹣ bi ′/ air ′ 于是得到 max{ ﹣ bi ′/ air ′| air ′0} ≤Δ br ≤ min{ ﹣ bi ′/ air ′| air ′0} 當 Δ br（ r=1,2, …,m) 取上述范圍之內(nèi)的值， XB′為最優(yōu)。 41 運籌學基礎(chǔ) 如果 Δ br取值在上述范圍之外時，由于檢驗數(shù)不變，所以此時基解是對偶可行的基解。就可以用對偶單純形法求最優(yōu)解。 cj的變化分析 設(shè)價值系數(shù) cj的改變 Δ cj。分非基變量和基變量討論。 ⑴ 設(shè) cj是非基變量 xj系數(shù)，則其檢驗數(shù) δj= cj－ CBB1pj 當 cj改變 Δ cj后， δj′= cj+ Δ cj － CBB1pj 要使原最優(yōu)解，只有δj′≤0，所以有 Δ cj ≤CBB1pj－ cj 。 ⑵ 設(shè) cr是基變量 xr系數(shù)。因 cr ∈ CB，所以當 cr變化 Δ cr時，就引起 CB變化， (CB+ Δ CB) B1A= CB B1A+(0, …, Δ c r , …, 0) B 1A = CB B1A+ Δ cr (ar1′, ar2′, …, a rn′) 。當 cr變化 Δ cr 后，檢驗數(shù)為： δj′= cj － CBB1A － Δ cr arj′ j=1,2, …,n 42 運籌學基礎(chǔ) ⑵ 設(shè) cr是基變量 xr系數(shù)。因 cr ∈ CB，所以當 cr變化 Δ cr時，就引起 CB變化， (CB+ Δ CB) B1A= CB B1A+(0, …, Δ c r , …, 0) B 1A = CB B1A+ Δ cr (ar1′, ar2′, …, a rn′) 。當 cr變化 Δ cr 后，檢驗數(shù)為： δj′= cj － CBB1A － Δ cr arj′ j=1,2, …,n 若要使原最優(yōu)解不變，必須 δj′≤0。 于是得到 ① 當 arj ′ 0時， Δ cr ≥ δ j / arj ′ ② 當 arj ′ 0時， Δ cr ≤ δ j / arj ′ j=1,2, …,n max{δ j / arj ′ | arj ′0} ≤Δ cr ≤ min{δ j / arj ′ | arj ′0} aij的變化 ① 非基向量 Pj變?yōu)?Pj′。 這一改變直接影響第 j數(shù)據(jù)和第 j個檢驗數(shù) δj′= cj － CBB1 Pj′。 43 靈敏度分析 運籌學基礎(chǔ) aij的變化 ① 非基向量 Pj變?yōu)?Pj′。 這一改變直接影響第 j數(shù)據(jù)和第 j個檢驗數(shù) δj′= cj － CBB1 Pj′。 若 δj′≤0， 則原最優(yōu)解仍是新問題的最優(yōu)解。 若 δj′0， 則原最優(yōu)基不再是最優(yōu)基，此時在原問題的最終表的基礎(chǔ)上，換上改變后的第 j列數(shù)據(jù) B1 Pj′和 δj′ ，把 xj作為換入變量，用單純形法繼續(xù)迭代。 ② 基向量 Pj變?yōu)?Pj′。 此時原最優(yōu)解的可行性和最優(yōu)性都遭到破壞 ， 一般不修改原來的最終表 ， 而是重新計算 。