1. 首頁 > 生活百科 > >

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

詳解運籌學單純

運籌學單純形法(單純形法每一步的詳細解釋)
r薇薇原創
作者:臧永森
作者簡介:臧永森，清華大學工業工程系博士，研究方向:運行優化算法的設計與應用，數據統計分析，大數據技術與應用，齊老師團隊 。
編輯評論/注釋
本文屬于電子書線性規劃項目第三章單純形法的內容 。在上一篇文章中，我們介紹了單純形法引入的可行域、最優解、可行解、基解、基可行解等基本概念，也闡述了它們之間的關系(詳見“單純形法之前”一文) 。在明確這些基本概念后，本節我們將討論單純形法的思想邏輯和求解步驟 。
我們已經知道優化問題的最優解一定是基可行解，那么如何找到最優基可行解就是優化問題的求解思路 。所以求解過程中的單純形法是一個不斷尋找變量進出基的循環迭代過程 。每次迭代達到降低目標函數值(或增加目標函數值)的目的，最終獲得最優解 。那么，在迭代過程中，如何在改進過程中使解盡快收斂到最優解？讓我們用更直觀的方式來分析這個過程 。
單純形法的基本思想和邏輯
本文采用的思路參考了Dimitris Bertsimas和John N. Tsitsiklis在《線性最優化導論》一書中提出的方法[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是三個不同凸組合與需求線的交點，即原問題的三個可行解 。

圖2可行解決方案的“柱幾何”圖
通過上面的分析我們知道，要找到最優解，就是要找到與需求線相交且使Z值最小的凸組合 。那么如何找到這樣的凸組合呢？首先，引入兩個定義:
如果矢量

是線性無關的，那么向量

【單純形法各個步驟詳解 運籌學單純形法】被稱為Rn空間中的仿射獨立或者仿射無關，其中k

    推薦閱讀