【演算法】求解線性規劃問題：單形法

簡介
單形法(Simplex medthod)是1947年由George Dantzig所發展出來的方法。它是效率很高的解題方法，時常在腦上求解非常龐大的問題。
單形法是一種代數解題程序，但是其基本概念卻是幾何觀念。

解答的主要觀念
解答的觀念 1：
單形法只尋求CPF解。對於任何至少擁有一個最佳解的問題來說，只要找到一個最好的CPF解，即可找到一個最佳解。

解答的觀念 2：
單形法是一種疊代演算法(Iterative Algorithm)，指有系統的求解程序，亦即重複一系列的固定步驟，稱為一次反覆，直到獲得結果，其架構如下。


解答的觀念 3：
如果可能的話，單形法的初始化應選擇原點(所有的決策變數都為零)為起始CPF解。若有很多決策變數時，選擇原點可以免除需要使用代數程序求出CPF解的過程。

解答的觀念 4：
對於一已知CPF解，相較於所有其他CPF解而言，其相鄰CPF解的資訊較易取得。因此，當單形法每執行一次反覆，從目前的CPF解移動到一較優之解時，它總是選擇一相鄰CPF解，而不考慮其他CPF解。因此，整個求解路徑是沿著可行區邊緣移動，以找到最佳解。

解答的觀念 5：
對於目前的CPF解而言，單形法檢查此CPF解所伸出之每一可行區邊緣。每一邊的另一端是一相鄰CPF解，但是單形法並不找出所有的相鄰CPF解；它只是找出若沿各邊綠向前移動，所獲得之Z改善率。在所有Z改善率為正值的邊緣中，選取改善率最大者，以沿該邊緣移動。找出該邊緣另一端相鄰之CPF解後，以該解為目前的CPF解，然後進行最佳性檢測。必要的話，進行下一反覆。

解答的觀念 6：
觀念5敘述如何利用單形法檢查從目前的CPF解伸出之所有可行區邊緣中，以得知沿各邊緣移動至相鄰CPF解時，所產生的Z值改善率。正值的Z改善率表示該CPF解較目前的CPF解為優；負值的Z改善率則表示該CPF解較現行的CPF解為差。因此，最佳性檢測只是單純的檢查是否有任何邊緣會產生正值的Z改善率。如果沒有，則此目前的CPF解為最佳解。

設立單形法
此演算法一般都是利用電腦執行。電腦只能根據代數指令執行；因此，必須把觀念性的幾何程序轉換成為可執行的代數程序。此代數程序是以求解聯立方程式系統的方法為基礎。因此，設立單形法的首要步驟是轉換函數不等式限制式(Inequality constraints)成為等式限制式。(因為非負數限制式是分開處理，所以仍保留為不等式)。此轉換必須加入差額變數(Slack variables)。

如：
X1 <= 4

差額變數定義為
X3 = 4 - X1

所以 X1 <= 4 就完全等於 X1 + X3 = 4 和 X3 >= 0