第四章 線性規劃:敏感度分析與電腦報表解讀 電腦解-Lindo 敏感度分析簡介 改變一個參數 同時改變 4-1
線性規劃問題的電腦解 (1/5) 重新檢視第三章力新問題: Max 9X + 10Y 總利潤 Subject to (s.t.) 4-2
4-3
4-4
線性規劃問題的電腦解(2/5) 在最佳解右方的欄位為決策變數的「削減成本」,表示決策變數的目標函數係數要「改善」多少,才能使決策變數出現正值。 此題共有四條<=限制式,從圖可知前兩個限制式為束縛限制式,其「寬裕值」均為0(亦即資源全部用完);後兩個限制式其寬裕值分別為:組裝1270小時、檢裝720小時的未用人力。 4-5
線性規劃問題的電腦解(3/5) 「對偶價」(Dual prices):其意義為該限制式不等式「右側值」每增加一單位,目標值「改善」量。 OBJ COEFFICIENT RANGES:其意義為只要目標函數中決策變數的係數在此範圍內變動,則最佳解(decision variables)不變,此範圍稱之為「最佳化範圍」 RIGHTHAND SIDE RANGES:其意義為只要右側值在此範圍內變動,則限制式之對偶價不變;此範圍又稱之為可行性範圍 4-6
線性規劃問題的電腦解(4/5) C2目前係數 = 10.000000 可允許增量 2.28 可允許減量 = 3.57 最佳化範圍上限 = 10.00 + 5.75 = 15.75 最佳化範圍下限 = 10.00 – 2.28 = 7.72 C2最佳化範圍為:7.72 C2 15.75 4-7
線性規劃問題的電腦解(5/5) 以第一條限制式(切染部門)的對偶價U1為例: 目前右側值 = 4220.000000 可允許增量 = 1041.666748 1041.66 可允許減量 = 1200.000000 可行性範圍上限 = 4220.00 + 1041.66 = 5261.66 可行性範圍下限 = 4220.00 – 1200.00 = 3020.00 U1可行性範圍為:3020.00 RHS1 5261.66 4-8
敏感度分析簡介 「敏感度分析」(Sensitivity Analysis) 是探討線性規劃問題中參數係數的改變,如何影響最佳解。 由於此項分析是在已經求得最佳解的情況下,探討參數係數改變對於最佳解的影響,故又稱之為「後最佳化分析」 兩大類: 與 第一類:求最佳範圍(電腦報表及圖形分析) 例如: (7.72 C2 15.75) 4-9
重要對偶性質 <=限制式 ←→ DP >=0 束縛限制式 ←→ DP ≠ 0 >=限制式 ←→ DP <=0 4-10
一次改變一個參數(1/5) 題目請見課本p92 範例4.1(Y-型球袋單位利潤10元有誤,應為12元 ) 【解】 變數Y之係數C2最佳化範圍:7.72 C2 15.75 因新單位利潤12元仍在範圍內,故最佳解不變,仍為X*=250,Y*=460 新目標函數 = 9X* + 12Y* = 9(250) + 12(460) = 7770(元)所以,目標函數已經從6,850元增加920(=2460)元至7,770元。 4-11
一次改變一個參數(2/5) 題目請見課本p92 範例4.2(Y-型球袋單位利潤改為7元 ) 【解】 因Y-型球袋單位利潤7元超出最佳化範圍:7.72 C2 15.75 故最佳解可能已改變,必須重解線性規劃模型。如圖4.2示,最佳解為X=538(個),Y=124(個),目標函數值為5,710元。 4-12
4-13
一次改變一個參數(3/5) 第二類:對偶價及可行性範圍(課本p93 範例4.3) 人事部門可多提供9人工小時, 如何安排? 【解】 當限制式右側值改變時,對偶值愈大,則目標函數的改善愈大。 發現第二條限制式的對偶值0.92元為最大,可知四個部門當中,以增加縫合部門每單位(分鐘)人力,可增加0.92元的獲利為最高,其次為切染部門的0.64元,另外兩個部門皆為0元。 4-14
一次改變一個參數(4/5) 第二條限制式U2的可行性範圍為:3617.15 RHS2 5110.00 縫合部門增援後可用人力為4510 + 540 = 5050(分鐘),仍然在可行性範圍內,故知其對偶值0.92(元/分鐘)不變,則所增加的最大利潤為:5400.92 = 496.8(元),增加人力後的總利潤:6850 + 496.8 = 7346.8(元)。 4-15
一次改變一個參數(5/5) 【解】 題目請見課本p94 範例4.4(若縫合部門增加20小時的人力) 縫合部門增援後總人力 = 4510 + 1200 = 5710(分) 因5,710分超出範圍:3617.15 U2 5110.00,須重新求解。 最佳解X*=418(個),Y*=364(個),目標值為7,402元。 增援20小時力的貢獻:7402 – 6850 = 552(元)。每分鐘的貢獻利潤為:552/1200 = 0.46(元/分鐘) 4-16
一次可同時改變多個參數(1/10) 在實務上,管理者作敏感度分析時,可能必須考慮一次同時改變多個參數,其可能的情況有以下三種: 同時改變多個目標函數係數 同時改變多個限制式右側值 同時改變多個目標函數係數以及限制式右側值 先介紹會用到的兩項法則: 目標函數係數改變的100%法則 限制式右側值改變的100%法則 4-17
一次可同時改變多個參數(2/10) 題目請見課本p95 範例4.5 (X-型與Y-型球袋單位利潤分別改為8元與12元 ) 【解】由圖4.1可算出: X之係數C1最佳化範圍為:5.72 C1 11.66 Y之係數C2最佳化範圍為:7.72 C2 15.75 8元與12元分別在C1與C2的最佳化範圍內,同時改變兩個係數必須計算其總係數改變率是否超過100%。 4-18
一次可同時改變多個參數(3/10) C1從9減為8,減量為1,可允許減量為3.285714則X係數改變率 = 1/3.2857 0.3043 = 30.43% C2增量為2,可允許增量為5.750000則Y係數改變率 = 2/5.7500 0.3478 = 34.78% 總係數改變率 30.43% + 34.78% = 65.21% < 100% 故最佳解不變,仍X*=250,Y*=460。新目標函數 = 8X + 12Y = 8(250) + 12(460) = 7520(元) 目標函數從6,850元增加670元至7,520元。 4-19
一次可同時改變多個參數(4/10) 題目請見課本p96 範例4.6 (X-型與Y-型球袋單位利潤分別改為11元與9元 ) 【解】 11元與9元分別在C1與C2的最佳化範圍內,由於同時改變兩個係數,必須計算其總係數改變率是否超過100%。 C1增量為2元,可允許增量2.666667,則變數 X係數改變率 = 2/2.6667 0.7500 = 75.00% 4-20
一次可同時改變多個參數(5/10) C2減量為1元,可允許減量2.285714,則變數Y的係數改變率 = 1/2.2857 0.4375 = 43.75% 總係數改變率 75.00% + 43.75% = 118.75% > 100% 故最佳解可能已經改變,必須重解線性規劃模型,以求得新的最佳解。 最佳解為X*=538(個),Y*=124(個),目標函數值為7,034元。 4-21
4-22
一次可同時改變多個參數(6/10) 題目請見課本p97 範例4.7(支援切染與縫合兩部門分別可多提供7與5人工小時) 【解】 420分鐘與300分鐘在U1與U2的可行性範圍內,同時改變兩個右側值,必須計算其總右側值改變率是否超過100% RHS1增加420(分),可允許增量為1041.6667,則RHS1改變率 = 420/1041.6667 0.4032 = 40.32% 4-23
一次可同時改變多個參數(7/10) 因RHS2增加300(分鐘),可允許增量為600.0000,則RHS改變率 = 300/600.0000 0.5000 = 50.00% 總右側值改變率 40.32% + 50.00% = 90.32% < 100% 故知所有對偶價不變。則約可替公司增加利潤 = 420(0.64) + 300(0.92) = 544.8。 4-24
一次可同時改變多個參數(8/10) 題目請見課本p98 範例4.8(人事部門考慮將切染部門的人力調撥8人工小時至縫合部門 ) 【解】 單位換算:8小時 = 480分 480分都在U1與U2的可行性範圍內,同時改變兩個右側值,必須計算其總右側值改變率是否超過100%。 RHS1減少480(分),可允許減量為1200.0000,則RHS1右側值改變率 = 480/1200.0000 0.4000 = 40.00% 4-25
一次可同時改變多個參數(9/10) 因RHS2增加480(分),可允許增量為600.0000,則RHS2右側值改變率 = 480/600.0000 0.8000 = 80.00% 總右側值改變率 40.00% + 80.00% = 120.00% > 100% 原對偶價可能已經改變,故必須重新求解。 如圖4.5所示,最佳解為X*=466(個),Y*=268(個),目標函數值為6,874元。此人力調度,確實可為公司增加獲利。 4-26
4-27
一次可同時改變多個參數(10/10) 題目請見課本p99 範例4.9 (Y-型球袋單位利潤為12元,切染與縫合兩部門分別增加7與5小時之人力 ) 【解】 如圖4.6所示,最佳解為X*=233(個),Y*=529(個),目標函數值為8,454元。切染與縫合兩限制式的對偶價皆已改變,分別為1.2(元/分鐘)與0.6(元/分鐘)。 4-28
4-29
HW All (self-practice) 第一次交作業- 題目-Ch03: 4, 9; ch04:1, 2, 3 Due date: 10/26-27 4-30