單純形法的求解步驟

由凸集的定理知，線性規劃的最優解一定是基可行解，基可行解一定是凸集頂點上，而線性規劃問題的可行域就是凸集，可行域就是可行解的集合。所以，為了求得最優解，就要找基可行解。

這就是為什麼線性規劃的步驟為：找基 - 求基解 - 驗證是否為基可行解 - 驗證是否是最優解 - 若不是最優解，迭代（基變換）。

首先，將線性規劃問題轉化為標準數學模型
其次，先找處一個初始基，並驗證它是可行基
- 找基：找一個係數矩陣的最大滿秩子方陣（ $m \times m$ 階）
- 求基解：令非基變量為 0，則約束方程組成為一個 $m \times m$ 階線性方程組，必有唯一解。求解現在的約束方程，所得為基解。
- 驗證是否為基可行解：如果基解中所有基變量均滿足非負約束，則該基解為基可行解。
檢驗是否為最優解：
- 所有 $σ_j ≤ 0$ ，則為當前即為最優解
- 所有 $σ_j ≤ 0$ ，但存在一個 $σ_j = 0$ ，則有無窮多最優解
- 存在 $σ_j > 0$ ，且對應非基變量 $x_j$ 的所有係數 $a_{ij} <0$ ，則無最優解
- 存在 $σ_j > 0$ ，且對應非基變量 $x_j$ 的係數中，存在 $a_{ij} >0$ ，則可以繼續迭代
若可繼續迭代，則進行基變換
- 確定換入變量：選擇取得最大正數 $σ_j$ 的非基變量 $x_j$ ，作為換入變量
- 確定換出變量：選擇取得最小正數 $θ_j=\frac{b_i}{a_{ij}}$ 的 $i$ 對應的基變量 $x_i$ ，作為換出變量
- 基變換：令 $x_j=θ，x_i=0$ ，並將新基變量的係數矩陣 $B$ 化為單位矩陣，得到新的基
- 重新驗證：對新基重新 “求基解 - 驗證是否為基可行解 - 驗證是否為最優解...”，直到無法繼續迭代為止

$σ_j$ 是基變換後目標函數的變動量。（所有 $σ_j≤ 0$ 意味著沒有比現在更好的選擇）
$θ$ 是非基變量的最小的正數取值。