運籌學單純形法（單純形法各個步驟詳解）
R帷幄』原創
作者：臧永森
作者：臧永森，清華大學工業工程系在讀博士，研究方向：運籌優化算法的設計與應用、數據統計分析、大數據技術與應用，戚銘堯老師團隊
編者按
此文屬于電子書線性規劃專題第三章單純形法的內容。在前面的文章中，我們為引入單純形法介紹了可行域、最優解、可行解、基解、基可行解等基礎概念，也闡述了它們之間的關系（具體可見文章《在單純形法之前》）。在明確了這些基本概念之后，這一節我們來探討單純形法的思想邏輯和求解步驟。
我們已經知道，優化問題的最優解一定是基可行解，那么如何找到最優的基可行解就是最優化問題的求解思路。因此，單純形法在求解過程，就是不斷地尋求變量出入基的循環迭代過程，每次迭代都達到降低目標函數值（或增大目標函數值）的目的，最終得到最優解。那么在迭代過程中，如何使解在改善過程中向著最優解的方向盡快地收斂呢？我們下面用比較直觀的方式來解析這個過程。
單純形法的基本思想與邏輯
本文采用的思路參考Dimitris Bertsimas和 John N. Tsitsiklis在 Introduction to Linear Optimization一書中提出的方法[1]。考慮如下標準線性規劃問題：
我們將矩陣A拆分為n個列元素：A1, A2, A3,, An，那么我們可以將問題看成是滿足非負約束（4）、凸約束（3）以及約束（5）的最小化問題。
結合式（3）和（5）我們可以看出，原優化問題轉化為求解能夠構造出（b, z）的使得z值最小的關于（Ai, ci）的凸組合。為了更好地理解它們之間的幾何關系，我們將一個平面視作包含A的一個m維空間，將與ci相關的成本項看作是一維垂直數軸，這時每一個點（Ai, ci）都可以唯一在該三維坐標系中表示出來，如圖1所示：
圖1 線性規劃問題1—4的“列幾何”圖示
我們將（b, z）同樣視為一條垂直線表示在圖1中，這條垂直線叫做需求線，其與平面的交點是（b, 0）點。需求線與（Ai, ci）的凸組合在幾何上有一定的關系，它們或相交或相離，這取決于我們對（Ai, ci）凸組合的選取，選取的凸組合不一樣，幾何關系就不同。很容易能理解，如果需求線和凸組合相交，說明（b, z）可以用相應的凸組合表示出來，也就表明這個凸組合就是原問題的一個可行解；而如果相離，則說明這個凸組合不滿足能夠表達（b, z）的條件，也就不是原問題的可行解。所有的凸組合構成了一個凸包，如果需求線能夠與凸包相交，那么原問題就存在可行解，如果需求線不能與凸包相交，說明原問題無解。進一步將圖1抽象，得到圖2，從圖中我們可以看出，點I、H、G就是三個不同的凸組合與需求線的交點，也就是原問題的三個可行解。
圖2 可行解的“列幾何”圖示
經過上面的分析我們得知，要找到最優解，就是找到與需求線相交的使得z值最小的凸組合。那么如何找這樣的凸組合呢？首先引入兩個定義：
如果向量
是線性獨立的，那么向量
被稱為Rn空間中的仿射獨立或者仿射無關，其中k<=n。
在Rn空間中由k+1個仿射無關向量組成的凸包被稱為k維單純形。
對模型（1—4）來說，總共有m+1個等式約束，假定約束系數矩陣是滿秩的，那么一個基可行解將對應m+1個線性獨立的列向量，也就意味著有m+1個基點，根據上述定義，由基點之間的差向量線性獨立可以得到其仿射獨立，由此可以知道它們組成的凸包是m維單純形。
假設m維單純形與需求線相交于點（b, z），由（5）知用來表示（b, z）的線性組合的權重向量是xi ，該向量就是一個基可行解，也就對應我們上節所分析的基變量的內容，當然z就是相應的目標函數值。我們用圖2做一個解釋，陰影區域的三角形CDF，就是一個2維單純形，其與需求線的交點H點就是基可行解，點C、D、F是基點。
我們對二維單純形CDF做一些改變，會發現相應的z值（與需求線的交點）也會變化，比如我們令基點B取代基點F，單純形變為BCD，這時可行解變為I點，相應的z值較之前有所增長。類似地，若點E取代點C成為基點，單純形由CDF變為EDF，可行解就出現在G點，此時z值有所減小。從這些變化中我們找出這樣一個規律，當且僅當新加入基的點在當前單純形平面上方（下方）時，所得的交點（即可行解）對應的z值會增大（減小）。
如果我們更加形象地描述這個基點變化的過程，就如同用手抓住單純形CDF的基點C，保持D點和F點固定不變，用力向上拉（向下拉），將C點拉到B點（E點），也就產生了新的單純形BCD（EDF）。單純形法的旋轉迭代過程，就是不斷找到基點向上拉（向下拉）到新基點形成新單純形的過程。
單純形法的求解過程
簡單總結一下單純形法的求解原理。先找到一個基可行解，然后從非基解中找一個比較有前途的點入基，替換掉基可行解中有待改善的基點，從而達到改善目標函數的目的，如此重復迭代，直至無法找到可以入基的點。
