单形法敏感度分析及对偶特性.DOC

第六章 單形法敏感度分析及對偶特性 本章內容： 6.1 以單形表做敏感度分析 6.2 對偶特性 6.1 以單形表做敏感度分析 目標函數係數 目標函數與最適區間之意義： 1.若目標函數之係數範圍能使目前的最適解仍維持最適，則此範圍稱為目標函數之最適區間。 2.最適區間可能使目標函數值改變。 3.目標函數係數的最適區間，由Cj－Zj≦0淨評估值而定。 （1）目標函數基本變數之敏感度分析（只改變一個基本變數係數）。 例：Max 50X1＋40X2 s.t. 3X1＋5X12≦150 裝配可用工時 1X2≦20 P型顯示器 8X1＋5X2≦300 倉儲空間 X1，X2≧0 其中 X1＝D型產品件數 X2＝P型產品件數 最後單形表如下： X1 X2 S1 S2 S3 基底 CB 50 40 0 0 0 X2 S2 X1 40 0 50 0 0 1 1 0 0 8/25 -8/25 -5/25 0 1 0 -3/25 3/25 5/25 12 8 30 Zj Cj－Zj 50 0 40 0 14/5 -14/5 0 0 26/5 -26/5 1980 解：X1＝30，X2＝12，， X1 X2 S1 S2 S3 基底 CB C1 40 0 0 0 X2 S2 X1 40 0 C1 0 0 1 1 0 0 8/25 -8/25 -5/25 0 1 0 -3/25 3/25 5/25 12 8 30 Zj Cj－Zj C1 0 40 0 (64-C1)/5 (C1-64)/5 0 0 (C1-24)/5 (24-C1)/5 480+30C1 ∵最適區間應使Cj－Zj≦0即需(C1-64/5≦0)及(24-C1/5≦0) 所以的最適區間為24≦C1≦64。 註：基本變數（X1，X2，S2）之最適區間係計算非基本變數（S1，S3）之Cj－Zj，使其≦0。 驗証：Ｄ型產品利潤由原來50元減少為30元之最適解為何？ 若將C1改為30元之最後單形表如下： X1 X2 S1 S2 S3 基底 CB 30 40 0 0 0 X2 S2 X1 40 0 30 0 0 1 1 0 0 8/25 -8/25 -5/25 0 1 0 -3/25 3/25 5/25 12 8 30 Zj Cj－Zj 30 0 40 0 34/5 -34/5 0 0 6/5 -6/5 1380 解：X1＝30，X2＝12，，1380元。 （30X1＋40X2＝30＊＊50元減少為20元之最適解為何？ 若將C1改為20元，最後單形表如下： X1 X2 S1 S2 S3 基底 CB 20 40 0 0 0 X2 S2 X1 40 0 20 0 0 1 1 0 0 8/25 -8/25 -5/25 0 1 0 -3/25 3/25 5/25 12 8 30 Zj Cj－Zj 20 0 40 0 44/5 -44/5 0 0 4/5 4/5 1080 解：X1＝30，X2＝12，， X1 X2 S1 S2 S3 基底 CB 50 40 0 0 0 X2 S2 X1 40 0 50 0 0 1 1 0 0 8/25 -8/25 -5/25 0 1 0 -3/25 3/25 5/25 12 8 30 Zj Cj－Zj 50 0 40 0 14/5 -14/5 0 0 26/5 -26/5 1980 解：X1＝30，X2＝12，， X1 X2 S1 S2 S3 基底 CB 50 40 CS1 0 0 X2 S2 X1 40 0 50 0 0 1 1 0 0 8/25 -8/25 -5/25 0 1 0 -3/25 3/25 5/25 12 8 30 Zj Cj－Zj 50 0 40 0 14/5 CS1-(14/5) 0 0 26/5 -26/5 1980 ∵最適區間應使Cj－Zj≦0，因此需CS1-(14/5)≦0，所以CS1的最適區間為CS1≦14/5。 註：在一個極大化的問題，非基本變數沒有下限﹑2.重新計算每個非基本變數之Cj－Zj (如果Xk是非基本變數只須計算Cj－Zj)。 3.在Cj－Zj≦0的條件下，解每個不等式找出Ck的任何上界或下界。如果Ck有兩個或多個上界，其小者就是最適區間的上限。如果有兩個以上的下界，其大者就是最適區間的下限。 4.如果原來問題是極小化問題應將其轉變成極大化問題，以便用單形法求解。將第3步的不等式乘以－1，並改變不等號的方向，以找出原來求極小化問題的最適區間。 右手邊值： 在許多線性規劃問題中，我們將”右手邊值”解釋為”可用的資源”，例如”可用的裝配時