單形法最佳化

單形法（Simplex method）是一種用於解決線性規劃問題的數學方法。它是由George Dantzig在1947年提出的，用於尋找線性規劃問題的最優解。

線性規劃問題的標準形式如下：

\max_{x} z = c^T x

s.t. Ax <= b

x >= 0

其中，x是決策變量向量，c是目標函數係數向量，A是係數矩陣，b是限制條件向量。

單形法的基本思想是通過建立一個搜尋空間的簡單形，並在簡單形內移動，尋找目標函數的最大值或最小值。簡單形是由k+1個頂點構成的k維簡單形，其中k是決策變量的維數。單形法通過不斷地改變簡單形的形狀和大小，以找到問題的最優解。

單形法的步驟如下：

1. 初始化：選擇一個可行解作為簡單形的初始頂點。
2. 疊代：在簡單形內尋找一個新的頂點，使得目標函數值至少不變差。
3. 檢驗：如果新頂點不滿足限制條件，則將其從簡單形中移除。
4. 更新：如果新頂點滿足限制條件且目標函數值更好，則更新簡單形，將新頂點加入並移除最差的頂點。
5. 終止：當簡單形不能再更新或達到某個終止條件時，停止疊代。

單形法是一種有效的線性規劃解決方法，但它並不是萬能的。在某些情況下，單形法可能會陷入局部最優解，或者在某些問題上效率不高。此外，單形法不適用於非線性規劃問題。