運籌學/單純形法

我們可以使用上一節中概述的圖形方法輕鬆地求解兩個變數$(x_{2},s_{2})$ 線性規劃模型，但對於三變數問題，例如，當我們的公司生產三種產品時，我們必須做出決策，我們該怎麼做？四變數或五變數問題又該如何？這就是單純形法發揮作用的地方。它是一種迭代方法，透過反覆使用，可以為任何 n 變數線性規劃模型提供解決方案。

線性規劃模型的標準形式

讓我們定義一個線性規劃模型，如果它滿足以下兩個條件，則為標準形式

• 除非負約束外，所有約束都是具有非負右邊的方程。

• 所有變數都非負。

例如，

最大化 $z=5x_{1}+4x_{2}$

受制於，

$6x_{1}+4x_{2}+s_{1}=24$,

$x_{1}+2x_{2}+s_{2}=6$,

$x_{2}-x_{1}+s_{3}=1$,

$x_{2}+s_{4}=2$,

$x_{1},x_{2},s_{1},s_{2},s_{3},s_{4}\geq 0$

是一個標準形式的線性規劃模型。請注意，通常的 $\leq$ 符號已等效地用 $s_{n}$ 變數（s 代表 slack）和 $=$ 符號替換。

我們如何將給定模型轉換為標準模型，同時保留其含義？這可以透過以下方式完成

• 如果存在型別為$6x_{1}+4x_{2}\leq 24$ 的約束，則等式右側通常表示資源的某種限制（例如，可用原材料的數量），等式左側表示該資源的使用量（即，實際使用的原材料數量），因此它們的差表示資源的鬆弛或未使用的數量。因此，為了轉換為等式，我們必須在等式左側新增一個表示鬆弛量的變數。該變數被稱為鬆弛變數，顯然也是非負的。如果用$s_{1}$ 表示它，則約束將轉換為等式$6x_{1}+4x_{2}+s_{1}=24$。在型別為$6x_{1}+4x_{2}\geq 24$ 的約束的情況下，也做類似的事情。這裡等式左側比等式右側存在剩餘或額外數量，因此必須減去一個非負的剩餘變數，比如$s_{2}$，才能得到等式$6x_{1}+4x_{2}-s_{2}=24$。

• 如果給定變數 $x_{i}$ 是非正的，那麼它的負數 $y_{i}=-x_{i}$ 顯然是非負的，可以代入問題中。真正的困難在於當變數可以取任何符號時。這種情況被稱為無限制變數。解決這個問題的方法是使用替換 $x_{i}=x_{i}^{-}-x_{i}^{+}$，其中 $x_{i}^{-},x_{i}^{+}$ 都是非負的。直觀地說，如果變數 $x_{i}$ 是正的，那麼 $x_{i}^{-}$ 是正的，而 $x_{i}^{+}$ 是零；如果變數 $x_{i}$ 是負的，那麼 $x_{i}^{-}$ 是零，而 $x_{i}^{+}$ 是正的。如果 $x_{i}$ 是零，那麼顯然 $x_{i}^{-},x_{i}^{+}$ 都為零。

需要注意的是，原始線性規劃模型和標準模型的目標函式是相同的。

線性規劃的代數解法

現在讓我們嘗試用代數方法分析線性規劃模型。標準線性規劃模型的解將是原始模型的解（因為鬆弛變數和剩餘變數一旦移除，就會使方程恢復到原來的不平衡），並且出於類似的推理，原始模型的解也將對應於標準模型的解。由於目標函式對兩個模型都是相同的，因此標準模型的最優解也將是原始模型的最優解。因此，我們只需要關注標準模型。

那麼哪些解是最佳解的候選者呢？它們是等式約束的解。我們只需要找出這些解，然後檢查哪一個解在代入目標函式時能得到最優值。現在通常在線性規劃模型中，約束的數量，比如 m，少於變數的數量，比如 n，因此約束方程組有無限多個解。我們不可能檢查所有無限個解。但是，由於一個數學結果，我們的工作簡化了。這個結果是，如果在 n 個變數中，將 n-m 個變數設為零，然後如果可以解出約束方程組，那麼這個解將對應於 n 維空間中的一個角點。這樣的解被稱為基本解（初始解）。如果它除了是基本解之外，還恰好滿足原始問題的可行性，那麼它被稱為基本可行解（通常縮寫為 BFS）。由於最優解是在角點上得到的（正如我們在圖形上觀察到的），因此我們只需要檢查所有基本可行解（其數量最多為 ${n \choose m}$，反映了從總共 n 個變數中選擇 n-m 個變數為零的方式數量），然後決定哪一個解能使目標函式的值最大化。

讓我們考慮一個例子

考慮以下線性規劃模型

最大化 z = $2x_{1}+3x_{2}$

受制於，

$2x_{1}+x_{2}\leq 4$,

$x_{1}+2x_{2}\leq 5$,

$x_{1},x_{2}\geq 0$.

我們首先將其轉換為標準形式

最大化 z = $2x_{1}+3x_{2}$

受制於，

$2x_{1}+x_{2}+s_{1}=4$,

$x_{1}+2x_{2}+s_{2}=5$,

$x_{1},x_{2},s_{1},s_{2}\geq 0$.

約束系統有 m=2 個約束和 n=4 個變數。因此我們需要將 4-2=2 個變數設定為零以獲得基本解。例如，將 $x_{1}=0$ 和 $x_{2}=0$ 我們得到一個解 $s_{1}=4$ 和 $s_{2}=5$。這顯然是可行的，因此是基本可行解。設定為零的變數，即 $x_{1},x_{2}$ 被稱為非基變數，而 $s_{1},s_{2}$ 被稱為基變數。這些解（基解和非基解）在目標函式中代入後得到的目標值（即在目標函式中代入解後得到的值）為零。

下表總結了該問題的所有基本解

非基變數	基變數	基本解	可行	目標值
$(x_{1},x_{2})$	$(s_{1},s_{2})$	(4,5)	是	0
$(x_{1},s_{1})$	$(x_{2},s_{2})$	(4,-3)	否	-
$(x_{1},s_{2})$	$(x_{2},s_{1})$	(2.5,1.5)	是	7.5
$(x_{2},s_{1})$	$(x_{1},s_{2})$	(2,3)	是	4
$(x_{2},s_{2})$	$(x_{1},s_{1})$	(5,-6)	否	-
$(s_{1},s_{2})$	$(x_{1},x_{2})$	(1,2)	是	8

請注意，我們沒有費心計算不可行解的目標值。最優解是目標值最高的解，即 $x_{1}=1,x_{2}=2$。因此，我們已經透過代數方法解決了線性規劃模型。

這種解決線性規劃模型的方法適用於任何數量的變數，但在約束和變數數量較多時，實施起來非常困難。例如，對於 m = 10 和 n = 20，需要解決 ${20 \choose 10}=184756$ 組方程，這顯然是一項艱鉅的任務。使用單純形法，你只需要求解其中幾組方程，專注於那些能提高目標值的方程。

單純形法

簡單來說，該方法是這樣工作的。你從標準形式線性規劃的基本可行解開始（通常是所有鬆弛變數都等於相應的右手邊，而其他所有變數都為零），然後用當前非基本變數替換一個基本變數，以獲得新的基本可行解（因為 n-m 個變數仍然為零）。這樣做是為了確保新的基本可行解是可行的，並且其目標值至少與先前的基本可行解相同。重複此過程，直到很明顯當前基本可行解無法再獲得更好的目標值。透過這種方式，可以找到最優解。

很明顯，有一個因素對該方法至關重要：哪個變數應該替換哪個。被替換的變數稱為“離開變數”，而替換它的變數稱為“進入變數”。單純形法的設計就是為了在選擇這兩個變數的過程中實現兩件事。首先，新的目標值是改進（或至少等於）當前目標值的；其次，新的解是可行的。

現在讓我們透過一個例子來解釋該方法。考慮我們之前提到的化工廠問題，其標準形式如下：

最大化 z = $5x_{1}+4x_{2}$

受制於，

$6x_{1}+4x_{2}+s_{1}=24$,

$x_{1}+2x_{2}+s_{2}=6$,

$x_{2}-x_{1}+s_{3}=1$,

$x_{2}+s_{4}=2$,

$x_{1},x_{2},s_{1},s_{2},s_{3},s_{4}\geq 0$.

現在，透過將所有 $x_{i}$ 設定為零，可以立即獲得一個基本可行解。（很明顯，這樣得到的解對於原始問題來說是可行的，因為右手邊都是非負數，這正是我們的解。）如果考慮我們的目標函式 z = $5x_{1}+4x_{2}$，那麼很明顯，增加 $x_{1}$ 或 $x_{2}$ 將會提高我們的目標值。（請注意，目前這兩個變數都是零，是不可行的）。$x_{1}$ 增加一個單位將使目標值增加 5 倍，而 $x_{2}$ 增加一個單位將使目標值增加 4 倍。很明顯，我們應該選擇在下次迭代中將 $x_{1}$ 作為進入變數。

在單純形法的表格形式中，目標函式通常表示為 $z-5x_{1}-4x_{2}=0$。此外，該表格還包含約束系統以及獲得的基本可行解。通常只寫係數，正如處理線性系統時通常的做法那樣。

基本變數	z	$x_{1}$	$x_{2}$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	BFS
z	1	-5	-4	0	0	0	0	0
$s_{1}$	0	6	4	1	0	0	0	24
$s_{2}$	0	1	2	0	1	0	0	6
$s_{3}$	0	-1	1	0	0	1	0	1
$s_{4}$	0	0	1	0	0	0	1	2

現在進入下一輪迭代，我們需要確定進入變數和離開變數。進入變數是 $x_{1}$，正如我們所討論的。事實上，由於我們對目標函式的重新排列，單純形表中 z 行中最小的負值將始終是下一輪迭代的進入變數。這被稱為 *最優性條件*。離開變數呢？我們必須考慮下一基本解是可行的。因此，選擇離開變數時必須考慮到這一點。

為了確定離開變數，我們應用有時被稱為 *可行性條件* 的方法。即：我們計算解座標（分別為 24、6、1 和 2）與進入變數 $x_{1}$ （分別為 6、1、-1 和 0）的約束係數的商。得到以下比率：24/6 = 4，6/1 = 6，1/-1 = -1 和 2/0 = 未定義。忽略負比率和未定義比率，我們現在繼續選擇其他兩個比率中最小的一個，即 4，它是透過將 24（$s_{1}$ 的值）除以 6 得出的。由於最小值涉及除以 $s_{1}$ 的當前值，我們取離開變數為 $s_{1}$。

這個過程背後的理由是什麼？是這樣的。最小比率實際上代表了約束在 $x_{1}$ 軸上的截距。要了解這一點，請檢視以下圖形

由於目前所有 $x_{i}$ 都為 0，我們正在考慮與原點相對應的 BFS。現在，在下一輪迭代中，根據單純形法，我們應該獲得一個新的 BFS，即移動到圖形上的一個新的角點。我們可以透過使一個變數成為進入變數來一次誘導一個變數值的增加，並且由於 $x_{1}$ 是我們的進入變數，我們的計劃是增加 $x_{1}$ 的值。從圖中我們可以看到，$x_{1}$ 的值必須增加到點 (4,0) 的 4，這是與 $x_{1}$ 軸的最小非負截距。超出該點的增加是不可行的。此外，在 (4,0) 處，鬆弛變數 $s_{1}$ 取值為零，因為第一個約束在該點滿足為等式，因此 $s_{1}$ 成為離開變數。

現在的問題是確定新的解決方案。儘管在這個階段可以應用任何求解線性方程組的方法，但通常應用 *高斯-約旦消元法*。它基於線性代數中的一個結果，即對系統 [A|b] 進行初等行變換到 [H|c] 不會改變系統的解。根據它，表中對應於基本變數的列被賦予單位矩陣的形狀。（熟悉線性代數的讀者會認識到這意味著由基本變數列組成的矩陣被轉換為行最簡階梯形。）然後可以從最右邊的解列中直接讀出解（因為 n-m 個變數被置為零，而其餘變數，包括 z，在每個約束中都有係數 1）。由於 z 也是一個變數，所以它的行被視為線性方程組中包含的約束之一。

進入變數列稱為 *主元列*，離開變數行稱為 *主元行*。主元列和離開變數列的交點稱為 *主元元素*。在我們的示例中，第二行（$s_{1}$）是主元行，第二列（$x_{1}$）是主元列。

生成新的基本解所需的計算如下

• 用進入變數替換“基本”列中的離開變數。
• 新的主元行 = 當前主元行 ÷ 主元元素

對於其他行，包括 z 行

• 新行 = 當前行 - （它的主元列係數）×（新的主元行）

在我們的例子中，計算如下進行

• 用 $x_{1}$ 替換“基本”列中的 $s_{1}$
• 新的主元 $x_{1}$ 行 = 當前 $s_{1}$ 行 ÷ 6 = ${\begin{pmatrix}0&1&{\frac {2}{3}}&{\frac {1}{6}}&0&0&0&4\end{pmatrix}}$
• 新的 z 行 = 當前 z 行 - (-5)×新的 $x_{1}$ 行 = ${\begin{pmatrix}1&0&{\frac {-2}{3}}&{\frac {5}{6}}&0&0&0&20\end{pmatrix}}$
• 新的 $s_{2}$ 行 = 當前 $s_{2}$ 行 - (1)×新的 $x_{1}$ 行 = ${\begin{pmatrix}0&0&{\frac {4}{3}}&{\frac {-1}{6}}&1&0&0&2\end{pmatrix}}$
• 新 $s_{3}$ 行 = 當前 $s_{3}$ 行 - (-1)×新 $x_{1}$ 行 = ${\begin{pmatrix}0&0&{\frac {5}{3}}&{\frac {1}{6}}&0&1&0&5\end{pmatrix}}$
• 新 $s_{4}$ 行 = 當前 $s_{4}$ 行 - (0)×新 $x_{1}$ 行 = ${\begin{pmatrix}0&0&1&0&0&0&1&2\end{pmatrix}}$

因此，我們的新表是

基本變數	z	$x_{1}$	$x_{2}$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	BFS
z	1	0	${\frac {-2}{3}}$	${\frac {5}{6}}$	0	0	0	20
$x_{1}$	0	1	${\frac {2}{3}}$	${\frac {1}{6}}$	0	0	0	4
$s_{2}$	0	0	${\frac {4}{3}}$	${\frac {-1}{6}}$	1	0	0	2
$s_{3}$	0	0	${\frac {5}{3}}$	${\frac {1}{6}}$	0	1	0	5
$s_{4}$	0	0	1	0	0	0	1	2

現在，最優性條件表明 $x_{2}$ 是進入變數。可行性條件得出比率：4/(2/3) = 6, 2/(4/3) = 1.5, 5/(5/3) = 3 和 2/1 = 2，其中最小值為 1.5，它是透過將 $s_{2}$ 行（即基本變數 $s_{2}$ 係數為 1 的行）的係數相除得到的。所以 $s_{2}$ 成為離開變數。再次應用高斯-約旦消元法得到以下表格

基本變數	z	$x_{1}$	$x_{2}$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	BFS
z	1	0	0	${\frac {3}{4}}$	${\frac {1}{2}}$	0	0	21
$x_{1}$	0	1	0	${\frac {1}{4}}$	${\frac {-1}{2}}$	0	0	3
$x_{2}$	0	0	1	${\frac {-1}{8}}$	${\frac {3}{4}}$	0	0	${\frac {3}{2}}$
$s_{3}$	0	0	0	${\frac {3}{8}}$	${\frac {-5}{4}}$	1	0	${\frac {5}{2}}$
$s_{4}$	0	0	0	${\frac {1}{8}}$	${\frac {-3}{4}}$	0	1	${\frac {1}{2}}$

根據最優性條件，與非基變數相關的 z 行係數 $s_{1}$ 和 $s_{2}$ 均為負數。因此，最後一個表是最優的。最優解可以讀為 $x_{1}=3,x_{2}={\frac {3}{2}},s_{3}={\frac {5}{2}}$ 以及 $s_{4}={\frac {1}{2}}$，最優值為 z = 21。顯然，變數 $s_{1}$ 和 $s_{2}$ 為零。我們最初只涉及 $x_{1}$ 和 $x_{2}$ 的問題，顯然也有相同的解（只需忽略鬆弛變數）。

我們已經處理了最大化問題。如果是最小化情況，因為 min z = max (-z)（如果 z 是線性函式，它就是），所以我們可以將問題轉換為最大化問題或顛倒最優性條件。我們可以選擇 z 行中係數最正的變數作為進入變數，而不是選擇係數最負的變數。其餘步驟相同。

使用單純形法線上解決問題的工具

練習問題

1. 一家從事印表機組裝和分發的公司關注兩種型別——雷射印表機和噴墨印表機。每臺雷射印表機的組裝需要 2 小時，而每臺噴墨印表機的組裝需要 1 小時，員工每天可以提供 40 人小時的組裝時間。此外，倉庫空間必須可用於印表機的組裝和分發，每臺雷射印表機 1 平方米，每臺噴墨印表機 3 平方米；該公司每天有 45 平方米的倉庫空間可用於組裝好的印表機。雷射印表機的每臺利潤為 30 歐元，噴墨印表機的每臺利潤為 25 歐元，但公司運營的市場每天最多能吸收 12 臺雷射印表機。（噴墨印表機市場沒有這種限制）。將此問題表述為線性規劃問題，並使用單純形法確定公司每天應該組裝和分發每種印表機的數量，以使每日利潤最大化。

最大化 $z=30x_{1}+25x_{2}$

受制於，

$2x_{1}+x_{2}\leq 40$,

$x_{1}+3x_{2}\leq 45$,

$x_{1}\leq 12,x_{1},x_{2}\geq 0$

使用 PHPSimplex 求解（參見連結以瞭解逐步求解過程）：最優解為 $z$ = 635，其中 $x_{1}$ = 12 且 $x_{2}$ = 11

人工初始解

在前面的問題中，我們有一個方便的初始基本可行解來應用單純形方法，該解包含鬆弛變數。然而，如果問題包含剩餘變數，則透過將所有 $x_{i}$ 設定為零獲得的解將是基本的，但不可行（為什麼？）。在這種情況下，與其隨意尋找初始基本可行解，不如使用稱為人工變數的變數。它們在第一次迭代中扮演鬆弛變數的角色，並且是問題外部的，在以後的迭代中被丟棄（透過被驅動為零）。我們將討論一種稱為兩階段法的方法，它通常用於處理人工變數問題。

讓我們考慮以下問題

最小化 z = $4x_{1}+x_{2}$

受制於，

$3x_{1}+x_{2}=3$,

$4x_{1}+3x_{2}\geq 6$,

$x_{1}+2x_{2}\leq 4$,

$x_{1},x_{2}\geq 0$.

現在，將問題轉換為標準形式後，我們得到

最小化 z = $4x_{1}+x_{2}$

受制於，

$3x_{1}+x_{2}=3$,

$4x_{1}+3x_{2}-Sx_{3}=6$,

$x_{1}+2x_{2}+sx_{6}=4$,

$x_{1},x_{2},Sx_{3},sx_{6}\geq 0$.

現在，第一個和第二個約束沒有與它們關聯的任何鬆弛變數。這意味著我們沒有一個方便的初始基本可行解可用。因此，我們必須在問題中引入人工變數 $Rx_{4},Rx_{5}$ 來獲得初始 BFS。

$3x_{1}+x_{2}+Rx_{4}=3$,

$4x_{1}+3x_{2}-Sx_{3}+Rx_{5}=6$,

$x_{1}+2x_{2}+sx_{6}=4$.

兩階段法到底是什麼？顧名思義，它包含兩個階段：在第一階段，我們從一個初始的基本可行解（透過將鬆弛變數和人工變數設定為等式右邊的值，並將其他變數設定為零來獲得）開始，並努力消除人工變數。為此，我們必須最小化人工變數的總和。所以我們將目標函式更改為最小化 $z=Rx_{4}+Rx_{5}$。因此，我們的問題變成了

最小化 $z=Rx_{4}+Rx_{5}$

受制於，

$3x_{1}+x_{2}+Rx_{4}=3$,

$4x_{1}+3x_{2}-Sx_{3}+Rx_{5}=6$,

$x_{1}+2x_{2}+sx_{6}=4$.

$x_{1},x_{2},Sx_{3},sx_{6},Rx_{4},Rx_{5}\geq 0$.

當然，我們的初始 BFS 是透過將所有原始變數和剩餘變數設定為零來獲得的。但是，此時出現了一個問題。單純形法中的 z 行由 $z-Rx_{4}-Rx_{5}=0$ 給出，因此整個系統以矩陣形式表示為

${\begin{pmatrix}1&0&0&0&-1&-1&0\\0&3&1&0&1&0&0\\0&4&3&-1&0&1&0\\0&1&2&0&0&0&1\end{pmatrix}}{\begin{pmatrix}z\\x_{1}\\x_{2}\\Sx_{3}\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}$

顯然，如果我們將剩餘變數和原始變數設為零，那麼該系統的解將不是我們期望的右側，因為第一行中 $Rx_{4}$ 和 $Rx_{5}$ 的係數不為零。為了更準確地說明，我們將上述系統寫成如下形式：${\Bigg \{}z{\begin{pmatrix}1\\0\\0\\0\end{pmatrix}}+x_{1}{\begin{pmatrix}0\\3\\4\\1\end{pmatrix}}+x_{2}{\begin{pmatrix}0\\1\\3\\2\end{pmatrix}}+Sx_{3}{\begin{pmatrix}0\\0\\-1\\0\end{pmatrix}}+Rx_{4}{\begin{pmatrix}-1\\1\\0\\0\end{pmatrix}}+Rx_{5}{\begin{pmatrix}-1\\0\\1\\0\end{pmatrix}}+sx_{6}{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}{\Bigg \}}{\begin{pmatrix}z\\x_{1}\\x_{2}\\Sx_{3}\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}$.

現在我們將變數 $x_{1},x_{2},Sx_{3}$ 設為零，我們的解變為

${\Bigg \{}z{\begin{pmatrix}1\\0\\0\\0\end{pmatrix}}+Rx_{4}{\begin{pmatrix}-1\\1\\0\\0\end{pmatrix}}+Rx_{5}{\begin{pmatrix}-1\\0\\1\\0\end{pmatrix}}+sx_{6}{\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}{\Bigg \}}{\begin{pmatrix}z\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}$.

或者寫成如下形式

${\begin{pmatrix}1&-1&-1&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}}{\begin{pmatrix}z\\Rx_{4}\\Rx_{5}\\sx_{6}\end{pmatrix}}={\begin{pmatrix}0\\3\\6\\4\end{pmatrix}}$

現在這還沒有處於簡化行階梯形式，因此右側不直接提供基本可行解。在單純形表中，最後一列應該包含解。因此，在我們開始單純形法之前，第一行需要進行一些修改，以便系統得到簡化行階梯形式。明顯的必要初等變換是

新 z 行 = 舊 z 行（即 $z-Rx_{4}-Rx_{5}=0$) + (1×$Rx_{4}$ 行 + 1×$Rx_{5}$)

現在第一個方程變為 $z+7x_{1}+4x_{2}-Sx_{3}=9$，並且在將必要的變數置零後，我們發現右側提供了一個方便的初始 BFS。

基本變數	$x_{1}$	$x_{2}$	$Sx_{3}$	$Rx_{4}$	$Rx_{5}$	$sx_{6}$	BFS
z	7	4	-1	0	0	0	9
$Rx_{4}$	3	1	0	1	0	0	3
$Rx_{5}$	4	3	-1	0	1	0	6
$sx_{6}$	1	2	0	0	0	1	4

請注意，我們沒有費心在上面的表格中寫出 z 列。這是因為初等行變換的性質，z 列將始終是 $(1,0,\cdots 0)^{T}$ 的形式，因此該列可以在每次迭代中假定。

單純形法現在被用來得到解 $z=0,x_{1}=0.6,x_{2}=1.2,sx_{6}=1$。將獲得的最終表格

基本變數	$x_{1}$	$x_{2}$	$Sx_{3}$	$Rx_{4}$	$Rx_{5}$	$sx_{6}$	BFS
z	0	0	0	-1	-1	0	0
$x_{1}$	1	0	${\frac {1}{5}}$	${\frac {3}{5}}$	${\frac {-1}{5}}$	0	${\frac {3}{5}}$
$x_{2}$	0	1	${\frac {-3}{5}}$	${\frac {-4}{5}}$	${\frac {3}{5}}$	0	${\frac {6}{5}}$
$sx_{6}$	0	0	1	1	-1	1	1

由於人工變數為零，因此我們已經完成了第一階段。如果第一階段結束時目標函式的值不為零，則意味著人工變數無法消除，這意味著問題不可行。

第二階段涉及將當前可用的基本可行解作為原始問題的初始基本可行解。因此，目標函式將被改變，並且 z 行將反映這一點。由於人工變數已經完成了提供初始 BFS 的任務，因此它們現在不應該再成為進入變數。實際上，它們可以從問題中完全消除。因此，我們的原始問題現在可以重新表述為

最小化 z = $4x_{1}+x_{2}$

受制於，

$x_{1}+{\frac {1}{5}}Sx_{3}={\frac {3}{5}}$,

$x_{2}-{\frac {3}{5}}Sx_{3}={\frac {6}{5}}$,

$Sx_{3}+sx_{6}=1$,

$x_{1},x_{2},Sx_{3},sx_{6}\geq 0$.

現在表格可以寫成

基本變數	$x_{1}$	$x_{2}$	$Sx_{3}$	$sx_{6}$	BFS
z	-4	-1	0	0	0
$x_{1}$	1	0	${\frac {1}{5}}$	0	${\frac {3}{5}}$
$x_{2}$	0	1	${\frac {-3}{5}}$	0	${\frac {6}{5}}$
$sx_{6}$	0	0	1	1	1

在第一階段開始時出現的一個類似問題現在變得明顯了。由於基本變數$x_{1}$ 和 $x_{2}$ 在 z 行中具有非零係數，該系統未處於簡化行階梯形式。因此，我們必須首先應用初等行變換以使這些係數為零。明顯的行變換是

新 z 行 = 舊 z 行 + (4 × $x_{1}$ 行 + 1 × $x_{2}$)

因此表格變為

基本變數	$x_{1}$	$x_{2}$	$Sx_{3}$	$sx_{6}$	BFS
z	0	0	${\frac {1}{5}}$	0	${\frac {18}{5}}$
$x_{1}$	1	0	${\frac {1}{5}}$	0	${\frac {3}{5}}$
$x_{2}$	0	1	${\frac {-3}{5}}$	0	${\frac {6}{5}}$
$Sx_{3}$	0	0	1	1	1

現在可以應用單純形法。最終解決方案是：$z=3.4,x_{1}=0.4,x_{2}=1.8,Sx_{3}=1$.