Presentation is loading. Please wait.

Presentation is loading. Please wait.

第7章 單形法敏感度分析及對偶性 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.

Similar presentations


Presentation on theme: "第7章 單形法敏感度分析及對偶性 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted."— Presentation transcript:

1 第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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Download ppt "第7章 單形法敏感度分析及對偶性 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted."

Similar presentations


Ads by Google