歡迎來到單純形法（Simplex Algorithm）的世界！
在之前的學習中，你可能已經習慣用圖解線性規劃（Graphical Linear Programming）來解決最佳化問題。當只有兩個變數（\(x\) 和 \(y\)）時，這種方法非常好用，但如果工廠需要決定 10 種不同產品的產量呢？你總不能畫出一個 10 維的圖表吧！
這就是單純形法（Simplex Algorithm）大顯身手的時候了。它是一套循序漸進的數學「食譜」，專門用來在多變數系統中找出最佳結果（例如最大利潤）。如果剛開始看到一堆數字覺得頭昏腦脹，別擔心——這其實只是一個邏輯過程：從形狀的一個頂點移動到更好的頂點，直到抵達頂端為止！
1. 事前準備：專有名詞
在建立第一張表格之前，我們需要先理解單純形法的語言。這裡通常是學生最容易搞混的地方，所以讓我們簡單拆解一下。
基本變數（Basic Variables）與非基本變數（Non-Basic Variables）
在演算法的任何特定步驟中，我們會將變數分為兩類：
- 非基本變數（Non-Basic Variables）：這些是我們透過將其設為零而「關閉」的變數。
- 基本變數（Basic Variables）：這些是目前有數值的變數。在單純形表（Simplex Tableau）（我們那張大表格）中，基本變數很容易辨認，因為該欄位除了唯一的 1 以外，其餘皆為 0。
- 基本可行解（Basic Feasible Solution, BFS）：這只是一個高大上的名稱，指的就是在 3D（或多維）形狀上，滿足所有限制條件的一個「頂點」坐標。
鬆弛變數（Slack Variables）
單純形法不喜歡不等式（例如 \(\le\)），它更喜歡等式（\(=\)）。為了修正這一點，我們會在每個限制條件中加入一個鬆弛變數（\(s\)）。 類比：想像你有 10 英鎊可以花。你花了 \(x\)。所謂的「鬆弛」就是你口袋裡剩下的零錢。花費 \(x \le 10\) 等同於說 \(x + s = 10\)，其中 \(s\) 就是你剩下的零錢。
快速回顧：關鍵術語
鬆弛變數：為了將 \(\le\) 轉換為 \(=\) 而加入的變數。
基本變數：處於「解」中的變數（該欄位有一個 '1'，其餘為 '0'）。
非基本變數：被設為零的變數。
2. 建立初始單純形表
首先，我們將所有數據放入一個單純形表（Tableau）中。課程大綱要求使用標準格式：
- 目標列（Objective Row）：通常是第一列。它顯示你想要最大化的利潤或數值。如果你的目標函數是 \(P = 3x + 2y\)，你必須先將其重寫為 \(P - 3x - 2y = 0\)，才能填入表格。
- 限制列（Constraint Rows）：緊接在目標列之後。每一列代表加入鬆弛變數後的其中一個限制條件。
- RHS 欄位：「右側（Right Hand Side）」欄位，顯示方程式右邊的數值。
你知道嗎？我們總是從原點 \((0, 0)\) 開始執行單純形法。這意味著我們初始的非基本變數是決策變數（\(x, y\)），而基本變數則是鬆弛變數（\(s_1, s_2\)）。這代表我們目前什麼都沒生產，所有資源都還剩著呢！
3. 疊代：改善你的解
一個疊代（Iteration）就是演算法的一個完整週期。每一次疊代都會讓我們沿著多維形狀的邊緣，移動到一個新的頂點（BFS），該點對目標函數來說數值更好。
逐步操作：如何進行疊代
1. 選擇主元欄（Pivot Column）：觀察目標列，找出最負的數值。這一欄告訴我們哪個變數能為利潤帶來最大的提升。這就是我們的入基變數（entering variable）。
2. 選擇主元列（Pivot Row）（比值測試）：對於每一列（目標列除外），用 RHS 的數值除以主元欄對應的數值。
規則：忽略主元欄中的零或負值！
得到最小正比值的那一列就是你的主元列。該變數就是我們的離基變數（leaving variable）。
3. 主元運算（Pivot!）：這是代數運算的部分。你必須利用列運算來達成：
- 讓主元元素（Pivot element）（主元列與主元欄的交點）等於 1。
- 讓該欄中的其他所有數字都等於 0。
如果起初覺得棘手，別擔心！這就像你以前學過的聯立方程式解法。你只是在轉換表格，讓一個新的變數變成「基本變數」（即該欄擁有唯一的 1）。
4. 何時停止？
你必須持續執行疊代，直到觀察目標列時，發現變數欄位中再也沒有負數為止。這代表沒有辦法再提高目標函數的數值了。你已經到達了最優解（optimum）！
解讀最終表格
要讀取最終答案：
- 找出那些只有一個 '1' 其餘皆為 '0' 的欄位（這些就是基本變數）。
- 該變數的值即為該列對應的 RHS 欄位數值。
- 任何非基本變數（即欄位內容雜亂的變數）的值皆為 0。
常見錯誤避坑指南
符號陷阱：將目標函數移入表格時（例如 \(P = 5x + 4y\)），學生經常忘記將符號變號為 \(-5\) 和 \(-4\)。如果你的目標列中沒有負數，你就無法啟動演算法！
5. 圖解與代數解釋
將發生的事情視覺化非常重要。線性規劃問題的可行區域是一個凸多邊形（Convex Polygon）（在 2D 中）或多面體（Polyhedron）（在 3D 中）。
單純形法的每一次疊代，其實就是沿著形狀的邊緣，從一個頂點（角落）跳躍到另一個相鄰的頂點。我們正在「爬」這個形狀，直到抵達最高點為止。
重點總結：單純形法只是你用圖解法做的事情的代數化版本，但它處理 100 個變數和處理 2 個變數一樣輕鬆！
摘要檢核表
• 鬆弛變數：用於將 \(\le\) 轉為 \(=\)。
• 表格佈局：目標列（需變號）、限制列、RHS。
• 主元欄：目標列中最負的數值。
• 主元列：RHS/主元比值中最小的正數。
• 停止條件：目標列中不再有負數。
• 解讀：基本變數 = RHS 的值；非基本變數 = 0。