引言

很多運籌學的教材都是從線性規(guī)劃開始的， 我平時做算法策略的落地應用時也研發(fā)了一部分基于線性規(guī)劃的技術(shù)方案。 可以說，如果搞不懂線性規(guī)劃，很難成為一名優(yōu)秀的運籌優(yōu)化算法工程師。

但是我在體系化學習時，卻是先在其他地方轉(zhuǎn)了一大圈，才來到這里。

主要原因是，這線性規(guī)劃的原理著實有點難，之前看了很多遍，總有種好像懂了但又沒完全懂的挫敗感。 痛定思痛下終于決定，還是從最簡單的無約束問題開始，然后逐漸過渡到有約束問題，以及現(xiàn)在的線性規(guī)劃問題。

針對無約束優(yōu)化問題，我細分為一維問題和多維問題，并分別學習了適合解決一維問題的黃金分割法、切線法和進退法等，以及用于解決多維問題的坐標輪轉(zhuǎn)法、最速下降法和擬牛頓法等；針對約束優(yōu)化問題，相繼學習了拉格朗日乘子法和罰函數(shù)法。

線性規(guī)劃問題本質(zhì)上是一類特殊的約束優(yōu)化問題，這類優(yōu)化問題在實際場景中十分常見，同時由于問題的特殊性，也給問題的高效求解帶來了新思路。

前面提到過，線性規(guī)劃對我來說挺難的，只用一篇文章是很難講清楚。 所以打算分成上下兩篇：本篇著重講明白算法原理，下一篇著重研究實踐應用。

必須要預警的是，后續(xù)內(nèi)容很枯燥，因為夾雜著非常多的證明和推理過程。 我愿意花大量時間在這上面，是希望不僅能知其然，還能知其所以然。 不想看細節(jié)過程的，可以更多關(guān)注整體的邏輯框架：線性規(guī)劃問題相比一般約束問題的特殊性在哪里-->該特殊性使得線性規(guī)劃問題具有哪些特點-->基于這些特點，所設計的算法(單純形法)是如何實現(xiàn)高效求解的。

線性規(guī)劃標準型

線性規(guī)劃的標準型矩陣形式為

也可以寫成分量形式

從定義上可以看出，相比一般的約束優(yōu)化問題，線性規(guī)劃問題在目標函數(shù)、約束條件和變量范圍方面都增加了限制： (1)目標函數(shù)為線性加和的表達式； (2)約束條件只有線性等式； (3)優(yōu)化變量大于等于0。

問題特點

增加了上述限制后的線性規(guī)劃問題，具有哪些特點呢？

先說結(jié)論：問題的可行域為凸集-->最優(yōu)解在凸集的頂點上-->頂點和基本可行解一一對應。

接下來逐個詳細說明(證明)。

（1）可行域為凸集。

既然提到凸集，就需要先定義清楚凸集的含義：設是維歐式空間中的一個點集，若對于，以及任意，必有

則稱為凸集。

以下是凸集和非凸集的實例

對于線性規(guī)劃問題，根據(jù)標準型約束的定義

那么，針對任意，假設新變量，可做如下推導

即等式約束成立。

由于，下式顯然也成立

即大于等于0亦成立。

所以也在可行域內(nèi)。 根據(jù)凸集定義，線性規(guī)劃問題的可行域就是個凸集。

可行域是凸集，有什么好處呢——看下一條結(jié)論。

（2）最優(yōu)值一定在凸集的某個頂點上達到。

頂點這個詞在物理世界很容易理解，但為了后續(xù)推導，還是需要用數(shù)學語言描述清楚這一概念： 針對可行域內(nèi)的，如果不存在，使得

則這個為凸集上的頂點。

要證明以上結(jié)論，此處使用反證法。

假設凸集的頂點為，最優(yōu)解為。

因為在可行域的凸集范圍內(nèi)，所以它可以由頂點表示為

式中，，。能被頂點通過線性組合的方式表示，很容易想象，但證明起來有些難，這里就不深入了，有興趣的可以參考：多面集的表示定理。

上式兩邊同時左乘

設，上式可以做如下推導

但由于是最優(yōu)解，并且不在頂點上，所以

上述兩式互相矛盾，所以假設不成立，即最優(yōu)解必定在某個頂點上取到。

這個結(jié)論的最大優(yōu)點在于，把決策空間從一個非常大的可行域空間收縮到了可行域的頂點上，而頂點的數(shù)量在大部分情況下是比較有限的，這就極大降低了問題求解的復雜度。

這里其實我還有個小疑惑，就是從證明過程來看，好像并不需要目標函數(shù)是線性的，是否說明即使目標函數(shù)是非線性表達式，最優(yōu)解依然在頂點上取到？ 該疑惑目前暫未搞清楚，如有大佬，望不吝賜教。

（3）可行域凸集的頂點和基本可行解一一對應。

已經(jīng)知道最優(yōu)解在頂點上了，那頂點的數(shù)學表達式是怎樣的呢？ 上述結(jié)論告訴我們，頂點就是基本可行解。

接下來，先看一下基本可行解的定義。

是的約束矩陣，可以從中取到一個非奇異方陣，然后把剩下列組成一個子陣，它們對應的分別表示為基變量和非基變量。等式約束可以表示為

令，可以求出，組合和

如果，則被稱為基本可行解。

的維度是，理論上至多可以從任意列中隨機選取列，所以的數(shù)量上限是，即基本可行解的數(shù)量上限為個。

上述結(jié)論需要分兩步進行論證：(1)基本可行解都是頂點；(2)頂點都是基本可行解。

針對第一步，繼續(xù)使用反證法。

假設某個基本可行解不是頂點，即存在可行解和，使得基本可行解可以表示為

將寫成基變量和非基變量兩部分

等式中，因為，故

所以和都是基本可行解，即

由于為非奇異方陣，所以有唯一解，所以

即就是基本可行解，與基本假設不符，所以基本可行解必為可行解的頂點。

針對第二步，還是使用反證法。

假設是可行域的頂點，還是先拆解為非零項和零項

但由于不是基本可行解，所以對應應該是線性相關(guān)的，即存在一組非0向量，使得

上式乘以系數(shù)，然后和上上式分別做加法和減法，得到

先令，再令，首先可得

同時只要足夠小

即和都是可行解，這說明不能是頂點，兩者矛盾，所以頂點也必定都是基本可行解。

有了該結(jié)論后，理論上，只要算出所有基本可行解的目標函數(shù)值，并返回最小值，即得到了最優(yōu)解。 但基本可行解的數(shù)量上限是個，如果的數(shù)量比較大，用遍歷的方式尋找最小值貌似就有些吃不消了。

此時大名鼎鼎的單純形法就該登場了。

單純形法

同樣先給結(jié)論，單純形法最厲害的地方在于：任意給定一個基本可行解后，通過簡單的計算評估后，便可以告訴我們，該解是否還有改進空間，如果有，朝著哪個方向改進最好。 這樣的話，便不再需要去遍歷所有基本可行解，所以能極大提升問題求解的效率。

假設已經(jīng)得到一個基本可行解

對應的目標函數(shù)值為

先把寫成基本可行解的通用表達式，代入等式約束

移項，可以表示為

通用表達式結(jié)合上式后，再代入目標函數(shù)表達式

重組一下

上式可以描述為

其中，是非基變量集合，。

在當前的中，由于，即的后一項為0； 所以目標函數(shù)能繼續(xù)降低的基本條件是：至少存在一個，使得，同時也能夠從0增加為正數(shù)。

是參數(shù)不是變量，是否存在大于0的，是無法改變的； 但是的值理論上是可以優(yōu)化的，當然該值也不能隨意增大，其需要滿足的約束是

假設，將從0變?yōu)檎龜?shù)（專業(yè)術(shù)語叫入基），為了保證基本可行解的要求，中需要有一個值變?yōu)?（專業(yè)術(shù)語叫出基）

其中，，。 為了保證，的最優(yōu)值是

基于以上邏輯，我們可以描述為：如果存在，使得，此時令，可以使得目標函數(shù)值得到最大程度的降低。

這里還有一些特殊情況需要單獨考慮：

(1) 所有，即，此時當前基本可行解就是最優(yōu)解。

(2) 中，是原基本可行解的分量，所以其值≥0是毋庸置疑的；但是的大小是不確定的，如果其部分值≤0，結(jié)合的自身約束，原有流程還能繼續(xù)進行；但如果全部≤0，流程就無法再繼續(xù)進行了，事實上，即使取無窮大，的約束依然能夠滿足，將變?yōu)闊o窮小，所以此時原問題無下界，不存在最小值。

綜上，單純形法的基本步驟可以概述為：

（1）將所給的線性規(guī)劃問題化為標準型；

（2）找出一個初始基本可行解。

（3）檢驗和，判斷當前解的狀態(tài)：最優(yōu)解或不存在最優(yōu)解，則退出；否則繼續(xù)。

（4）找到最佳，更新，得到一個新的基本可行解，轉(zhuǎn)至（3）。

好了，總算是搞明白求解線性規(guī)劃問題的算法原理了。