第7章 單形法敏感度分析及對偶性 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

第7章 單形法敏感度分析及對偶性 7.1 以單形表進行敏感度分析　 7.2 對偶性　 第7章 單形法敏感度分析及對偶性 第287頁

前言 本章討論如何由最終單形表得到有關敏感度分析的資料，例如，目標函數係數的範圍、對偶價格及右側值的範圍。 第7章 單形法敏感度分析及對偶性 第288頁

7.1 以單形表進行敏感度分析─目標函數係數 目標函數係數之敏感度分析，在找出目標函數值的範圍，我們稱這個範圍為最佳區間(range of optimality)。 在計算目標函數係數的最佳區間時，我們假設這個問題的所有其他係數仍為原來的值。換句話說，每次只允許改變一個係數。 第7章 單形法敏感度分析及對偶性 第288頁

目標函數係數 第 6 章海德公司的問題為例，其線性規劃模式如下： 第7章 單形法敏感度分析及對偶性 第288頁

目標函數係數 海德問題最終單形表如下： 第7章 單形法敏感度分析及對偶性 第288-289頁

目標函數係數 當淨評估列的所有(cj - zj) 都 ≤ 0，目前的解即為最佳解。 第7章 單形法敏感度分析及對偶性 第289頁

目標函數係數 計算每台桌上型產品的利潤 c1 的最佳區間以說明上述的定義。我們以 c1（而非 50）作為 x1 變數的目標函數係數，得到最終單形表如下： 第7章 單形法敏感度分析及對偶性 第289頁

目標函數係數 由s1行，我們得到： 由s3行，我們得到： 利用第1個不等式，得到： 利用第2個不等式，得到： 因為c1必須滿足(7.2)式及(7.3)式，所以c1的最佳區間是 第7章 單形法敏感度分析及對偶性 第289-290頁

目標函數係數 假設桌上型產品的利潤因為物料成本上漲而減少為 30 美元。最佳區間指出，目前的解（x1 = 30，x2 = 12，s1 = 0，s2 = 8，s3 = 0）仍為最佳解。 第7章 單形法敏感度分析及對偶性 第290頁

目標函數係數 因為所有變數的 cj - zj ≤ 0，所以，x1 = 30、x2 = 12、s1 = 0、s2 = 8、s3 = 0 仍為最佳解。 如果桌上型的單位利潤再降低，譬如 20 美元，將最終單形表的 c1 換成 20。 目前的解不再是最佳解。 第7章 單形法敏感度分析及對偶性 第290-291頁

目標函數係數 計算 c1 最佳區間的方法可適用於任何基本變數。 計算非基本變數最佳區間的方法更簡單 海德公司問題的最終單形表中，將 s1 的目標函數係數由 0 改 cs1： 第7章 單形法敏感度分析及對偶性 第291頁

目標函數係數 只要 s1 的目標函數係數小於等於14/5，目前的解仍是最佳解。因為係數沒有下限，所以 cs1 的最佳區間為： 極大化問題的最佳區間沒有下限，上限則是 zj。所以，任何非基本變數目標函數係數的最佳區間為： 第7章 單形法敏感度分析及對偶性 第291-292頁

目標函數係數 計算最佳區間的步驟 利用最佳區間以找出目標函數係數的改變是否大到足以改變最佳解，經常可以避免重新去建立模式及求解修改後的問題。 步驟1. 最終單形表中的 xk 的所有目標函數係數從數值改成 ck。 步驟2. 重新計算每個非基本變數的 cj - zj（如果 xk 是非基本變數只須計算ck - zk）。 步驟3. 在 cj - zj ≤ 0 的條件下，解每個不等式，找出 ck 的上界或下界。如果 ck有兩個以上的上界，其中最小的就是最佳區間的上限；如果有兩個以上的下界，其中最大的就是最佳區間的下限。 步驟4. 如果原來的問題是極小化問題，為使用單形法求解而將其轉變成極大化問題。將步驟3 的不等式乘以–1，並改變不等號的方向，以找出原來極小化問題的最佳區間。 利用最佳區間以找出目標函數係數的改變是否大到足以改變最佳解，經常可以避免重新去建立模式及求解修改後的問題。 第7章 單形法敏感度分析及對偶性 第292頁

右側值 許多線性規劃問題的右側值(bi)可解釋為可用的資源。 對偶價格提供關於額外資源的價值的資訊；對偶價格有效的範圍，就是右側值的範圍。 對最佳解的改善量稱為對偶價格(dual price)。用單形法來解線性規劃問題時，對偶價格就是最後單形表中的zj列。 第7章 單形法敏感度分析及對偶性 第292頁

右側值 在最佳解中s2=8，表示有8台攜帶型顯示器未使用。 如果寬鬆變數是最佳解的基本變數，其zj值即此限制式的對偶價格將為零。 第7章 單形法敏感度分析及對偶性 第293頁

右側值 對大於等於限制式，其對偶價格將小於等於零。對極大化問題而言，當大於等於限制式的右側值增加時，可以預期最佳值反而會減少。對偶價格代表預期改善程度，它是負值，因為我們預期最佳值將會減少。大於等於限制式的對偶價格，為其於最佳單形表的剩餘變數zj的負值。 使用單形法解線性規劃問題時，限制式的對偶價格已包含在最終單形表。 第7章 單形法敏感度分析及對偶性 第293-294頁

右側值 第7章 單形法敏感度分析及對偶性 第294頁

右側值 M&D化學公司的極小化問題的目標函數乘以-1變成極大化問題。x1及x2代表產品A及B的製造量。 第7章 單形法敏感度分析及對偶性 第294頁

右側值 第7章 單形法敏感度分析及對偶性 第294-295頁

右側值 在不使任何目前的基本解變成不可行解的前提下，bi可以改變的範圍，稱為可行區間(range of feasibility)。 第7章 單形法敏感度分析及對偶性 第295頁

右側值 將海德公司問題的可用組裝時間從150小時改為160小時。可以預期目標函數值將增加10(2.80)=28。以下是最終單形表。 第7章 單形法敏感度分析及對偶性 第295頁

右側值 不必重新解此問題以找出新的解。只有單形表的最後一行改變。由s1行的四個元素乘以10後，與舊的單形表的最後一行相加而得： b1的 改變量 舊的解 s1行 新的解 第7章 單形法敏感度分析及對偶性 第295-296頁

右側值 b1 有多大的改變，會使目前的基底變得不可行？ 當b1的改變量為b1時，海德公司問題基本變數的新值為： 只要每個基本變數的新值維持非負，則目前的基底仍可行，且為最佳解。 第7章 單形法敏感度分析及對偶性 第296頁

右側值 要滿足三個不等式，因此b1必須滿足： 將150+b1換成b1，我們將得到b1的可行區間為： 只要可用組裝時間維持在112.5及175小時之間，目前的最佳解仍然可行。 第7章 單形法敏感度分析及對偶性 第297頁

右側值 第一步是對限制式i計算bi值的範圍，以滿足以下不等式。 目前的解 （最終單形表對 最終單形表中對應限 應的最後一行） 第7章 單形法敏感度分析及對偶性 第297-298頁

右側值 找出大於等於限制式右側值的可行區間的方法。對大於等於限制式i，先找出滿足以下不等式(7.13) 的bi範圍。 目前的解 （最終單形表對 應的最後一行） 最終單形表中對應限 制式 i 的剩餘變數行 第7章 單形法敏感度分析及對偶性 第298頁

右側值 計算等式限制式右側值的可行區間。將最終單形表中與限制式i的人工變數對應的行，應用到(7.12)式中。 計算等式限制式的可行區間，需要許多額外的計算工作。詳細過程請參考進階的教科書。 第7章 單形法敏感度分析及對偶性 第298頁

7.2 對偶性 每個線性規劃都有一個伴隨的線性規劃問題，稱為對偶題(dual problem)，而原來的線性規劃問題則稱為原題(primal problem)。 在原題及對偶題計算困難度不同的情形，我們可以選擇求解比較簡單的問題。 第7章 單形法敏感度分析及對偶性 第299頁

7.2 對偶性 海德公司的原題為： 第7章 單形法敏感度分析及對偶性 第299頁

7.2 對偶性 一個極大化問題，如果所有限制式均為小於等於限制式及變數均為非負，則稱為正規型(canonical form)。 一個正規型極大化問題，很容易轉換成對偶線性規劃。海德公司對偶問題如下： 第7章 單形法敏感度分析及對偶性 第299頁

7.2 對偶性 極小化的正規型問題(canonical form for a minimization problem)，所有限制式均為大於等於限制式，且變數均為非負的極小化問題。 正規型極大化問題的對偶題就是正規型的極小化問題。這些變數u1、u2及u3稱為對偶變數(dual variables)。 第7章 單形法敏感度分析及對偶性 第299頁

7.2 對偶性 正規型極大化問題的對偶題的一般性描述如下： 其對偶是一個正規型極小化問題。 當原題有n 個決策變數時（海德問題的 n = 2），對偶題就有 n 個限制式。對偶題的第 1 個限制式對應原題的 x1 變數，對偶題的第 2 個限制式對應原題的x2 變數，其餘類推。 原題有 m 個限制式時（海德問題的 m = 3），對偶題就有 m 個決策變數，對偶變數 u1 對應原題的第 1 個限制式，對偶變數 u2 對應原題的第 2 個限制式，其餘類推。 原題限制式的右側值變成對偶題的目標函數係數。 原題目標函數係數變成對偶題的限制式右側值。 第i 個原始變數在限制式中的係數，變成對偶題中第 i 個限制式的係數。 第7章 單形法敏感度分析及對偶性 第299-300頁

7.2 對偶性 運用單形法。減去剩餘變數s1及s2得到標準型，加上人工變數a1及a2得到表格型後，我們將目標函數乘以-1，將對偶題轉成對等的極大化問題，得到以下的初始單形表。 第7章 單形法敏感度分析及對偶性 第300頁

7.2 對偶性 第一次迭代以後，u3進入基底而a1移出。 第2次迭代後，u1進入基底而a2移出。單形表結果如下。 最佳解，u1=14/5、u2=0、u3=26/5、s1=0、s2=0。 第7章 單形法敏感度分析及對偶性 第300頁

7.2 對偶性 對所有線性規劃問題的原題與對偶題均成立 特性1： 如果對偶題有最佳解，則原題亦有最佳解，反之亦然。此外，原題與對偶題最佳解的目標函數值相等。 第7章 單形法敏感度分析及對偶性 第301頁

對偶變數之經濟涵義 建立對偶題時，每個對偶變數都對應原題的一個限制式。 當原題是產品組合問題時，可得到以下原題與對偶題的結論。 原題：已知每個產品的價值，找出各種產品的生產量，以使總產值最大。限制式要求每種資源的使用量小於等於最大可用量。 對偶題：已知每種資源的可用量，找出每單位資源的價值，以使所使用的資源總價值最小。限制式要求每單位資源的價值大於等於每個產品的價值。 第7章 單形法敏感度分析及對偶性 第301-302頁

用對偶題找出原題的解 對偶題的最終單形表提供對偶變數的最佳解數值，所以原始變數的值應該可由最佳對偶表的zj列找到。 特性2： 已知最佳對偶解的單形表，原始決策變數的最佳解值為剩餘變數的 zj 項。此外，原始寬鬆變數的最佳值，則是 uj 變數的 cj - zj 項之負值。 第7章 單形法敏感度分析及對偶性 第302-303頁

用對偶題找出原題的解 x1和x2的最佳值，以及所有原始寬鬆變數的最佳值，位在對偶題最終單形表的zj及cj- zj列。再次列示如下： 第7章 單形法敏感度分析及對偶性 第303頁

找出任意原題的對偶題 先將任何原題變成對等的正規型問題，再依已經建立的規則找出正規型問題的對偶題會更容易。 以找出下列極小化問題的對偶題為例，說明對任何線性規劃問題找出其對偶題的方法： 第7章 單形法敏感度分析及對偶性 第304頁

找出任意原題的對偶題 先將所有限制式轉變成大於等於型，變成正規型： 步驟1. 將限制式1兩邊乘以-1，變成大於等於型式，我們得到： 步驟1.　將限制式1兩邊乘以-1，變成大於等於型式，我們得到： 步驟2　 對一個等式限制式，我們創造出兩個不等式，一個是型；另一個則是型。於是得到： 將限制式乘以-1變成兩個限制式： 第7章 單形法敏感度分析及對偶性 第304頁

找出任意原題的對偶題 原來問題已經被改成以下的相等形式： 第7章 單形法敏感度分析及對偶性 第304-305頁

找出任意原題的對偶題 原題對偶關係找到對偶題如下： 第7章 單形法敏感度分析及對偶性 第305頁