單純形法各個步驟詳解運籌學單純形法

r維維原創
作者:臧永森
作者:臧永森，博士，清華大學工業工程系，研究方向:運籌學優化算法設計與應用，數據統計分析，大數據技術與應用，師從祁團隊。
編輯評論/說明
本文屬于電子書線性規劃項目第三章單純形法的內容。在上一篇文章中，我們為單純形法的引入介紹了可行域、最優解、可行解、基解、基可行解等基本概念，也闡述了它們之間的關系(詳見“單純形法之前”一文) 。闡明這些基本概念后，本節將討論單純形法的思想邏輯和求解步驟。
【單純形法各個步驟詳解運籌學單純形法】我們已經知道優化問題的最優解一定是基可行解，所以如何找到最優基可行解是優化問題的求解思路。因此，單純形法在求解過程中是一個不斷尋找變量進出基的循環迭代過程。每次迭代達到降低目標函數值(或增加目標函數值)的目的，最終得到最優解。那么，在迭代過程中，如何在改進過程中使解盡快向最優解收斂呢？讓我們以更直觀的方式來分析這個過程。
單純形法的基本思想和邏輯
本文所采用的思路參考了迪米特里斯·貝塔西馬斯和約翰·恩·齊次克里斯在《線性優化導論》一書中提出的方法[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的“列幾何”圖
我們還在圖1中將(b，z)顯示為一條垂直線。這條垂直線稱為需求線，它與平面的交點是(b，0)點。需求線與(Ai，ci)的凸組合之間存在一定的幾何關系。它們要么相交，要么彼此分離，這取決于我們對(Ai，ci)的凸組合的選擇。如果選擇的凸組合不同，幾何關系也會不同。很容易理解，如果需求線與凸組合相交，意味著(b，z)可以用對應的凸組合來表示，這意味著這個凸組合是原問題的可行解。如果它們相互分離，就意味著這個凸組合不滿足(b，z)可以表示的條件，所以不是原問題的可行解。的所有凸組合形成一個凸包。如果需求線能與凸包相交，那么原問題就有了可行解。如果需求線不能與凸包相交，說明原問題無解。通過進一步抽象圖1，我們得到圖2 。從圖中可以看出，點I、H、G是三種不同凸組合與需求線的交點，即原問題的三種可行解。