【正文】 優(yōu)解有無變化，但這樣做既麻煩又沒有必要。 把 個別參數(shù)的變化 直接在獲得最優(yōu)解的 最終單純形表 上反映出來。這樣就不需要從頭計算，而只需對獲得最優(yōu)解的單純形表進(jìn)行審查，看一些數(shù)字變化后是否仍滿足最優(yōu)解的條件 ,如果不滿足的話 ,再從這個表開始進(jìn)行迭代計算，求得最優(yōu)解即可。 這也就是靈敏度分析。 對偶線性規(guī)劃 60 ? 靈敏度分析的步驟如下： 參數(shù)的改變 計算反映到最終單純形表上來 △ b*=B1 △ b 具體計算方法是，按下列公式計算出由參數(shù) aij、 bi、 cj的變化而引起的最終單純形表上有關(guān)數(shù)字的變化： △ Pi*=B1 △ Pi △ ?*= △ c ；即 右端常數(shù)是否大于 0 ；即 檢驗(yàn)數(shù)是否小于 0 。 常數(shù)項(xiàng) bi的改變量 系數(shù) aij的改變量 目標(biāo)函數(shù)系數(shù) cj的改變量 對偶線性規(guī)劃 此公式是單純形法利用公式求解的推導(dǎo)結(jié)果 ! 61 解的情況判定表 原問題 對偶問題 結(jié)論或繼續(xù)計算的步驟可行解 可行解 仍為問題最優(yōu)解可行解 非可行解 用單純法繼續(xù)迭代求最優(yōu)解非可行解 可行解 用對偶單純法繼續(xù)迭代求最優(yōu)解非可行解 非可行解 引進(jìn)人工變量，編制新的單純形表重新計算對偶線性規(guī)劃 62 一、分析 cj變化的影響 目標(biāo)函數(shù)中的系數(shù) cj的變化僅僅影響到檢驗(yàn)數(shù) (cjzi)的變化。所以將 cj 的變化直接反映到最終單純形表中，只可能出現(xiàn)表中的前兩種情況。 【 例 】 已知線性規(guī)劃問題： maxZ=2x1 +x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 用單純形法求得最終單純形表如下 對偶線性規(guī)劃 63 最終單純形表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 試確定 ： (a)當(dāng)目標(biāo)函數(shù)變?yōu)?max Z=5x1 +，最優(yōu)解會出現(xiàn)什么變化； (b) 目標(biāo)函數(shù)變?yōu)?max Z=(2+l) x1+x2時， l在什么范圍變化，最優(yōu)解不變； maxZ=2x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 maxZ=5x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 對偶線性規(guī)劃 64 【 解 】 (a)將目標(biāo)函數(shù)系數(shù)的變化直接反映到最終單純形表中 變量 x5的檢驗(yàn)數(shù)為正，繼續(xù)迭代； maxZ=5x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 檢驗(yàn)數(shù) ?jbX BC B比值Cj檢驗(yàn)數(shù)比值x5x4x3x2x100012 1 5 / 25 /41001 5 /2 1 /21 /40017 /23 /2 1 /40103 /2x2x1x3120 1 /2 1 /4000 1 7 / 25 0 0 0 0 5 17/2 52 0 1/4 1/2 17/2 3 1/4 1/2 79/4 0 0 0 7/8 1/4 對偶線性規(guī)劃 65 繼續(xù)迭代得下表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 5 0 0 0 15 0 5 1 0 0 4 1 1/3 0 1/6 0 1 0 2/3 0 1/6 1 x3 x1 x5 0 5 0 20 0 1/6 0 5/6 0 即得新最優(yōu)解 x1=4， x2=0， x3=15， x4=0 ， x5=1 此時 MaxZ=20 對偶線性規(guī)劃 66 (b)將目標(biāo)函數(shù)系數(shù)的變化直接反映到最終單純形表中 為使表中解為最優(yōu)，應(yīng)該有 1/41/4l≤?， 1/2+1/2l≤? 即得 ： 1≤ l≤? 檢驗(yàn)數(shù) ?jbX BC B比值Cj檢驗(yàn)數(shù)比值x5x4x3x2x100012 1 5 / 25 /41001 5 /2 1 /21 /40017 /23 /2 1 /40103 /2x2x1x312+ l0 1 /2 1 /4000 1 7 /22+l 1 0 0 0 0 2+l 1 17/2 l 0 0 1/4 1/2 17/27/2l 0 0 0 1/41/4l 1/2+1/2l 即： 1≤ l≤?時，最優(yōu)解不變； 對偶線性規(guī)劃 二、分析 bi變化的影響 bi的變化 在實(shí)際問題中表明可用資源的數(shù)量發(fā)生變化，其變化 △ b反映到最終單純形表上 只引起基變量列數(shù)字變化 △ b*。因此靈敏度分析的步驟為： △ b*=B1△ b算出 △ b*， 將其加到最終表基變量列的數(shù)字上； （ 檢驗(yàn)行沒變 ） ， 故只需檢查原問題是否仍為可行解 ， 再按相應(yīng)步驟進(jìn)行 。 注 :此公式是單純形法利用公式求解的推導(dǎo)結(jié)果 ! 問題： B與 B1分別是什么 ？ 對偶線性規(guī)劃 ? 以此題為例討論 B1的求法 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j y1 y2 y3 y4 y5 15 24 5 0 0 2 0 6 1 1 0 1 5 2 1 0 1 y4 Y5 0 0 0 15 24 5 0 0 檢驗(yàn)數(shù) ?j 1/4 5/4 1 0 1/4 1/4 1/2 15/2 0 1 1/2 3/2 Y2 y3 24 5 17/2 15/2 0 0 7/2 3/2 初始單純形表 最終單純形表 B B1 原理是： (B|I)經(jīng)過初等變換可化為 (I|B1)，其中 I是單位陣 I I 對偶線性規(guī)劃 【 另例 】 求 B1 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15 0 5 1 0 0 24 6 2 0 1 0 5 1 1 0 0 1 x3 x4 x5 0 0 0 0 2 1 0 0 0 初始單純形表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j= cjzj x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 B* B1 ???????????110260501BI* I對偶線性規(guī)劃 【 另例 】 求 B1 ??????????????????????0,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxxxxZM a x?初始單純形表 對偶線性規(guī)劃 最終單純形表 0 M 0 1 1 3 1 1 0 1 0 2 3 0 0 2 1 4 11 0 1 1 2 1 0 0 1 0 M 0 1 0 2 M+23 1/3 0 0 0 9 7/3 2/3 1 0 0 1 2 0 0 1 0 4 5/3 1/3 0 0 1 1/3 4/3 1 2/3 1/3M 4/3 1 2/3 ???????????3734322103532311B71 【 例 】 分析 bi變化的影響 最終單純形表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 (a)若第 2個約束條件右端項(xiàng)由 24增大到 32，分析最優(yōu)解變化； (b)若第 2個約束條件變?yōu)? 6x1+2x2≤24+l，分析 l在什么范圍內(nèi)變化，最優(yōu)不變； maxZ=2x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 maxZ=2x1 + x2 5x2 ≤15 6x1 + 2x2 ≤ 32 x1 + x2 ≤ 5 x1 , x2 ≥0 對偶線性規(guī)劃 72 【 解 】 (a)第 2個約束條件右端項(xiàng)由 24增大到 32 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 因 因表中原問題為非可行解，故用對偶單純形法繼續(xù)計算 將其加到最終單純形表的基變量 b這一列上得下表 ???????????????????????080024320b?????????????????????????????????????222100802/14/102/34/102/14/102/154/51*b注： B1擴(kuò)充了檢驗(yàn)行，反映目標(biāo)值的變化 △ b*=B1△ b 15/2+10 7/2+2 3/22 17/22 35/2 11/2 1/2 21/2 B1 對偶線性規(guī)劃 73 繼續(xù)迭代得下表 Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15 0 5 1 0 0 5 1 1 0 0 1 2 0 4 0 1 6 x3 x1 x4 0 2 0 10 0 1 0 0 2 最優(yōu)值 maxz*=10 即得新最優(yōu)解 x1=5， x2=0， x3=15， x4=2 ， x5=0 對偶線性規(guī)劃 74 【 解 】 (b)若第 2個約束條件變?yōu)? 6x1+2x2≤24+l Cj 比 值 CB XB b 檢驗(yàn)數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 因 將其加到最終單純形表的基變量 b這一數(shù)列上得下表 ????????????00lb????????