线性规划解的各种情形.ppt
第第 四四 節節 線性規劃線性規劃解的各種情形的各種情形 在第二章第三節圖解法時介紹線性規劃的解有多種情況，本節要探討如何由單形表中辨認之。例 5：(多重最佳解，第二章例 2)Max z=x1+2x2 s.t.x1+2x2 10 x1+x2 1 x2 4 x10，x20 將問題寫成標準形並加入人工變數 Max z=x1+2x2+0s1+0s2MA2+0s3 s.t.x1+2x2+s1 =10 x1+x2 -s2+A2=1 x2 +s3=4 xj 0，j=1,2.si 0，i=1,2,3.A20 cj 1 2 0 0 -M 0 cB xB x1 x2 s1 s2 A2 s3 bi bi/aij 0 s1 -1 0 1 2 -2 0 8 4 2 x2 1 1 0 -1 1 0 1 負數不考慮 0 s3 -1 0 0 1 -1 1 3 3 zj 2 2 0 -2 2 0 2 cj-zj -1 0 0 2 -2-M 0 0 s1 1 2 1 0 0 0 10 5-M A2 1 1 0 -1 1 0 1 1 0 s3 0 1 0 0 0 1 4 4 zj -M -M 0 M -M 0 -M cj-zj 1+M 2+M 0 -M 0 0 cj 1 2 0 0 -M 0 cB xB x1 x2 s1 s2 A2 s3 bi bi/aij 1 x1 1 0 1 0 0 -2 2 負數不考慮 2 x2 0 1 0 0 0 1 4 4 0 s2 0 0 1 1 -1 -1 5 負數不考慮 zj 1 2 1 0 0 0 10 cj-zj 0 0 -1 0 -M 0 0 (已最佳解)0 s1 1 0 1 0 0 -2 2 2 2 x2 0 1 0 0 0 1 4 0 s2 -1 0 0 1 -1 1 3 負數不考慮 zj 0 2 0 0 0 2 8 cj-zj 1 0 0 0 -M -2 cj 1 2 0 0 -M 0 cB xB x1 x2 s1 s2 A2 s3 bi bi/aij1 x1 1 0 1 0 0 -2 2 負數不考慮 2 x2 0 1 0 0 0 1 4 40 s2 0 0 1 1 -1 -1 5 負數不考慮 zj 1 2 1 0 0 0 10 cj-zj 0 0 -1 0 -M 0 0 (最佳解)第四表第五表1 x1 1 2 1 0 0 0 10 2 0 s3 0 1 0 0 0 1 4 0 s2 0 1 1 1 -1 0 9 負數不考慮 zj 1 2 1 0 0 0 10 cj-zj 0 0 -1 0 -M 0 0 (最佳解)由第四表可以發現所有的 cj-zj 0 最佳解已得到，其解為 (x1，x2，s1，s2，A2，s3)=(2，4，0，5，0，0)Max z=10。第五表亦是最佳解，其解為 (x1，x2，s1，s2，A2，s3)=(10，0，0，9，0，4)Max z=10。雖然xj值並完全不相同，但目標函數值 z=10 是一樣的，由第五表中亦可引進 s1，其 z值也為10，因此本例題有多重解。那麼如何辨認是否為多重最佳解呢？我們是由 cj zj 所在的列來判斷，先前曾 提及基礎變數所對應的 cj-zj 為0，在第四表中，x1,x2和s3是基礎變數，其對應的 c1-z1=c2-z2=c4-z4=0，我們也發現到 s3 的 c6-z6=0 引進為基礎變數的話，對目標函數值的邊際貢獻為 0，也就是對目標函數沒有影響，所以將 s3 引進成基礎變數，其目 標函數值亦為 z=10，將第四表、第五表與第二章 圖 2-5 對照，完全一樣。第四表(x1,x2)=(2,4)第二章圖2-5,D(2,4)第五表(x1,x2)=(10,0)第二章圖2-5,E(10,0)多重最佳解如何辨認呢？簡言之，從 cj-zj 所在列來判斷，如果基礎變數有 K 個，cj-zj 所在列的 0 超過 K 個，則表示此題就有多重最佳解。如本例題有 3 個基礎變數，而在第四表中，cj-zj 所在列有 4 個 0；而在第五表中，cj-zj 所在列有 4個 0，故本題為多重解。例 6：(無限值解，第二章例 3)Max z=3x1+4x2 s.t.x1+x2 4 x1-2x2 5 x10，x20 將問題寫成標準型並引進人工變數 Max z=3x1+4x2+0s1-MA1+0s2 s.t.x1+x2-s1+A1=4 x1-2x2 +s2=5 x1，x2，s1，s2，A10 cj 3 4 0 -M 0cB xB x1 x2 s1 A2 s2 bi bi/aij-M A1 1 1 -1 1 0 4 4 0 s2 1 -2 0 0 1 5 負數不考慮 zj -M -M M -M 0 -4M cj-zj 3+M 4+M -M 0 0 4 x2 1 1 -1 1 0 4 0 s2 3 0 -2 2 1 13 zj 4 4 -4 4 0 16 cj-zj -1 0 4 -4-M 0 0 代入變數 在第二表中，現行解並非最佳解，因為所有的cjzj 0，又 s1 的 c3-z3=4 0，必須進入基礎變數，然而s1所在的行為()皆為負數，找不到代出變數，因而也找不到樞元素，無法做轉換，此時為無限值解。因為-1 和-2 表示生產產品不僅沒有把資源用掉，反而資源愈用愈多，資源愈用愈多，獲取的利潤呈現無限大，亦既先前曾提及為何 bi/aij負數不允考慮的原因。簡言之，若代入變數所在行之係數皆為負數，則產生無限值解。-1-2例 7：(無可行解，第二章例 4)Min z=3x1+5x2 s.t.x1 -x2 2 x1+x2 5 -x1+2x2 4 x10，x20 將問題改寫成標準型並引進人工變數 Min z=3x1+5x2+0s1+MA1+0s2+0s3+MA3 s.t.x1-x2-s1+A1 =2 x1+x2 +s2 =5 -x1+2x2 -s3+A3=4 x1,x2,s1,s2,s3,A1,A30 cj 3 5 0 M 0 0 McB xB x1 x2 s1 A1 s2 s3 A3 bi bi/aijM A1 1 -1 -1 1 0 0 0 2 負數不考慮 0 s2 1 1 0 0 1 0 0 5 5M A3 -1 2 0 0 0 -1 1 4 2 zj 0 M -M M 0 -M M 6M cj-zj 3 5-M M 0 0 M 0M A1 1/2 0 -1 1 0 -1/2 1/2 4 80 s2 3/2 0 0 0 1 1/2 -1/2 3 25 x2 -1/2 1 0 0 0 -1/2 1/2 2 負數不考慮 zj -2.5+0.5M 5 -M M 0 -2.5-0.5M 2.5+0.5M 10+4M cj-zj 5.5-0.5M 0 M 0 0 2.5+0.5M -2.5+0.5M cj 3 5 0 M 0 0 McB xB x1 x2 s1 A1 s2 s3 A3 bi bi/aijM A1 0 0 -1 1 -1/3 -2/3 2/3 3 3 x1 1 0 0 0 2/3 1/3 1/3 2 5 x2 0 1 0 0 1/3 -1/3 1/3 3 zj 3 5 -M M (11-M)/3 -2(1+M)/3 2(1+M)/3 21+3M cj-zj 0 0 M 0 (-11+M)/3 2(1+M)/3 (-2+M)/3 0 第三表 由第三表中可看出 cj-zj 所在列皆大於等於 0，目標函數是求極小化，cj-zj 0 表示目標函數不能在減少，可見以達成最佳化，其解為 A1=3，x1=2，x2=3，先前亦曾提及，人工變數最後要為 0，如果不為 0 會破壞未引進人工變數時等式關係。本題因 A1 為人工變數而 A1=30，所以本題為無可行解。故在最佳解的情況下，若人工變數在基礎變數中且不為零，則為無可行解。例 8：(退化解)Max z=6x1+10 x2 s.t.x1 5 x2 6 3x1+2x2 12 x10，x20 將問題寫成標準型模式 Max z=6x1+10 x2 s.t.x1+s1 =5 x2+s2 =6 3x1+2x2+s3=12 xj0，j=1,2.si0，i=1,2,3.cj 6 10 0 0 0 cB xB x1 x2 s1 s2 s3 bi bi/aij 0 s1 1 0 1 0 0 5 0 s2 0 1 0 1 0 6 6 0 s3 3 2 0 0 1 12 6 zj 0 0 0 0 0 0 cj-zj 6 10 0 0 0 0 s1 1 0 1 0 0 5 510 x2 0 1 0 -1 0 6 0 s3 3 0 0 -2 1 0 0 zj 0 10 0 10 0 60 cj-zj 6 0 0 -10 0 cj 6 10 0 0 0 cB xB x1 x2 s1 s2 s3 bi bi/aij 0 s1 1 0 1 0 0 5 510 x2 0 1 0 -1 0 6 0 s3 3 0 0 -2 1 0 0 zj 0 10 0 10 0 60 cj-zj 6 0 0 -10 0 0 第二表第三表 0 s1 0 0 1 2/3 -1/3 510 x2 0 1 0 1 0 6 6 x1 1 0 0 -2/3 1/3 0 zj 6 10 0 6 2 60 cj-zj 0 0 0 -6 -2 0 由第二表中得到的可行解基礎變數為 s1=5，x2=6 ，s3=0，因為 s3 是基礎變數且等於 0，此解即稱為退化解。又第二表中x1 的 c1-z1=60，未得到最佳解，將x1引進基礎變數中，得到第三表獲得最佳解s1=5，x2=6，x1=0也是退化解。第二表的退化解目標函數值 z=60，第三表的退化解目標函數值 z=60，沒有增加；依照前面解釋，代入變數 x1之c1-z1=6 0，對目標函數的邊際貢獻為正值，理應 z 值會增加，為何沒有增加？我們可以這樣解釋，在第二表中因為第三種資源已經全部用完且其 bi/aij 又是最小，既然第三種資源用盡且生產單位 x1 需第三種資源 3 單位，當然無法生產出 x1 的產品數量，故 x1=0，自然對目標函數沒有任何貢獻。
