在之前的算法博客中，結合案例和算法的圖形表示，獲得了較多同學的好評，例如之前寫的迪杰斯特拉算法這篇博客，能夠讓很多新同學和老同學通過直觀的方式去理解算法求解的過程，這樣理解起來會比較容易。最近關于求解線性規劃的單純形算法，在網絡中目前沒有發現比較好的圖解該算法的博客，很多相關的博客可能會長篇大論，很多同學閱讀的時候肯定很吃力，也很難堅持到最后，所以，想通過圖形更直觀的來講一下單純形算法。

1、線性規劃問題介紹

線性規劃問題是一個多變量線性函數的最優化問題，這些變量所滿足的約束條件都是線性等式或者線性不等式。線性規劃問題在我們的生活中非常常見，本文主要通過一個生活中的問題來講解線性規劃和單純形算法。

1.1 問題：

有一個司機師父，他要給一家公司運輸材料，運輸的材料為水和特殊液體化學材料，其中，運輸1立方水的利潤為3塊錢，運輸1立方化學材料的利潤為5塊錢，但是，貨車的最大容量為4立方，最大載重為6kg，其中，水的密度為1kg/立方，化學材質的密度為2kg/立方，那么，運輸師父每次運輸水和化學材料各多少立方時，總利潤是最大的？

1.2 建立數學模型：

描述符號表示

運輸水的總體積	x
運輸化學物質的總體積	y

根據運輸的總利潤，可以得到 總利潤=3x+5y
根據貨車體積限制，可以得到 x+y小于等于4
根據貨車載重限制，可以得到 x+2y小于等于6
最基本的限制，貨車運輸兩種物品的總體積為非負，即大于等于0

綜上，我們可以建立下面的模型：

1.3 約束區域可視化

我們將線性規劃問題區域通過圖像繪制出來，同時將3x+5y=0的函數圖像繪制出來，如下圖：

2 圖解單純形算法

2.1 單純形法約束條件：

具體表述

條件1	目標函數必須是一個線性的最大化問題
條件2	所有的約束都必須是線性等式（除了非負約束）
條件3	所有的變量都必須要求是非負的

關于上面的模型，可以看出，第一條和第三條滿足，不滿足第二條，因此我們需要它能夠給引入松弛變量 u,v將不等式變成等式：

進而將模型轉換成標準形式：

其中，標準形式的優勢在于，可以通過簡單的計算來確定可行區域的極點。

2.2 單純形算法中的名詞

表1 單純形名詞解釋

名詞詳細解釋

基本可行解	如果一個基本解的所有坐標值都非負，則成為是一個基本可行解
單純形表	來描述單純形算法求解過程中系數和可行解的表
目標行	單純形表的最后一行為目標行，前幾列初始化為目標函數系數的相反數，最后一列為當前的目標函數值
輸入變量	選擇目標行中最小負數所在列對應的變量，即單位變化對目標函數影響最大的變量
主元列	輸入變量所在的列稱為主元列
分離變量	在將輸入變量作為基變量的時候，需要將當前的一個基變量變為非基變量，該非基變量稱為分離變量
θ比率	系數除以主元列中非零的值作為θ比率，θ比率越小的行對應的基變量作為本次的分離變量
主元行	分離變量對應的行作為主元行
主元化	將新的輸入變量作為基變量的變換操作稱為主元化，主要采用的變換方法跟線性方程組的高斯-若爾當消去法類似

2.3 單純形算法求解線性規劃

借助上面的模型，結合圖像和單純形算法的計算過程，來看一下如果求解線性規劃問題。

初始化，設模型有m個等式約束，n個變量（n>=m），將等式中 n-m個變量設置為0，求解其他變量的值，從而得到一個基本可行解，上面模型的n=4，m=2，假設x和y都為0，因此來求解 u,v 得到的基本可行解為（0，0，4，6）, 此時目標函數值為0，u,v為基變量，如下圖中的O點。

生成對應的單純形表如下圖，其中，綠色格代表方程組中各個變量的系數，灰色格表示方程組等號右側的常數項，目標行中的黃色格初始化為目標函數對應變量系數的相反數，藍色格代表目標函數當前的值：

確定輸入變量
在上面表格中，0>-3>-5，因此選擇-5所在列對應的變量為y，因此將y作為輸入變量。 之所以這樣選擇，是因為該變量每個單位的增加能夠使得目標函數獲得最大的增大。 此時主元列如下圖：

確定分離變量
分別求u和v的 θ比率值，下圖中紅色框的兩列相除

計算結果如下：
θ(u) = 4/1 = 4
θ(v) = 6/2 = 3
θ(u) > θ(v)
因此，選擇v為分離變量

4) 主元化
主元y代替分離變量v來作為新的基變量，這一步是單純形算法中最復雜的一步，下面會詳細介紹每一步的操作。
首先，將主元行的所有數除以主元行和主元列相交格中的數值，將主元列的系數變為1，計算過程如下圖：



其次，對其他行的主元列進行消元，即將主元列的其他系數變成0

數據整理后得到下圖，此時的目標值變為15：

在這個過程中，我們的目標函數具體是怎么變化了呢？我們通過圖像直觀的看一下目標函數的變化，如下圖動畫，首先，本次選擇的主元列為y，此次目標函數所在位置為O點，從O點沿著y軸方向，建立了一個向量OH，沿著OH，進行移動，最終移動到極點H(0,3)上，此時的目標函數值為 3x+5y=30+53=15.

為什么是這樣操作呢？因為經過上面的主元化操作，我們的基本解從（0,0,4,6） 變成了（0,3,1,0），關于xy的二維坐標系，就從（0,0）移動到（0,3）

檢查是否是最優解
通過上面的動畫圖像，我們發現目前沒有達到最優解，從單純形表中發現，目標行中的系數值沒有完全變成非負數，因此，還未求得最優解。為什么呢？因為只要有變量在目標行的系數非負，此時該變量還是有可以增加的空間的。

因此，我們再次運行步驟2到步驟4，新的輸入變量變成x，求得輸入變量為u ,主元化操作如下：

將主元行對應的主元系數變成1，如下圖

列項消元得到下圖：

進行檢查發現，目標行中的所有系數都變成非負數，此時達到了最優解，目標函數的最優值為16。此時求得的解為（2,2,0,0）,因此函數的解從（0,3,1,0）變為（2,2,0,0），我們通過圖像來觀察一下目標函數最優解的變化過程，如下面動畫：

從上面的動畫可以看出，單純形算法一直從一個初始解，向最靠近目標函數最優解的極點靠近，每次迭代的解都是一個極點所對應的解。

3 單純形算法回顧

經過上面的講解，相信聰明的你應該對單純形算法有了初步的理解，下面回顧一下整個算法的流程：

1 將模型變換成標準型 2 初始化：確定基變量，將非基變量設為0，求基本解，然后初始化單純形表（基變量，變量系數，常數項列，目標行，目標函數值）中的五大變量 3 確定輸入變量：通過目標行系數中的最小負數所在列對應的變量 4 確定分離變量：選取當前θ比率最小的基變量作為分離變量 5 檢驗最優：判斷當前目標行的所有系數是否非負，如果有小于0，則繼續回到步驟2-4，否則，達到最優，輸出目標函數的最優值。

4 代碼

時間有點晚，后面代碼部分會找時間補上。

總結

以上是生活随笔為你收集整理的算法之图解单纯形算法C++的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。