基本介紹
- 中文名：單純形表
- 外文名：simplex tebleau
- 適用範圍：數理科學
簡介,舉例,
簡介
對線性規劃的標準型：
min
s.t.
記一個基礎可行解的基為 B ，A 其餘的列為 N ，
相應地，記
。有
這是一個很重要的式子，說明了對一個非基變數，僅當量
為負時，才有可能變成新的基變數。這些係數在下面的單純形表中稱為判別數或檢驗數。
當
全部大於等於零時，已經是最優基。對基 B ，以下的表稱為單純形表：
 | 0 （基變數判別數） |  (非基變數判別數） |
 (基礎可行解基變數值） |  （基變數對於的單位矩陣） |  （非基變數對應的約束矩陣） |
舉例
設有線性規劃問題如下：
min 
s.t. 
其對應的單純形表為：
max | 0 | 0 | 0 | 0 | 0 | -1 | -1 | RHS |
x1 | x2 | x3 | x4 | x5 | x6 | x7 | ||
x6 | 1 | 2 | 1 | -1 | 0 | 1 | 0 | 3 |
x7 | 2 | -1 | 3 | 0 | -1 | 0 | 1 | 4 |
檢驗數σ𝚓 | 3 | 1 | 4 | -1 | -1 | 0 | 0 | |
x6 | 1/3 | 7/3 | 0 | -1 | 1/3 | 1 | -1/3 | 5/3 |
x3 | 2/3 | -1/3 | 1 | 0 | -1/3 | 0 | 1/3 | 4/3 |
檢驗數σ𝚓 | 1/3 | 7/3 | 0 | -1 | 1/3 | 0 | -4/3 | |
x2 | 1/7 | 1 | 0 | -3/7 | 1/7 | 3/7 | -1/7 | 5/7 |
x3 | 5/7 | 0 | 1 | -1/7 | -2/7 | 1/7 | 2/7 | 11/7 |
檢驗數σ𝚓 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | |
x2 | 1/7 | 1 | 0 | -3/7 | 1/7 | 3/7 | -1/7 | 5/7 |
x3 | 5/7 | 0 | 1 | -1/7 | -2/7 | 1/7 | 2/7 | 11/7 |
檢驗數σ𝚓 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
