單純形表

單純形表

對於線性規劃問題,使用單純型法進行表上作業所得到的表格。直接用公式進行單純形法疊代計算是很不方便的,其中最複雜的是進行基變換,但施行基變換所用的實際上是消元法。由線性代數知道,用消元法解線性方程組可在增廣矩陣上利用行初等變換進行計算。因此,我們可以將單純形法的全部計算過程在一個類似增廣矩陣的數表上進行,這種表格稱為單純形表

基本介紹

  • 中文名:單純形表
  • 外文名:simplex tebleau
  • 適用範圍:數理科學
簡介,舉例,

簡介

線性規劃的標準型:
min
s.t.
記一個基礎可行解的基為 BA 其餘的列為 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

相關詞條

熱門詞條

聯絡我們