線性規劃，充斥著運籌學，在圖的單源最短路徑求解差分約束系統就是用到線性規劃。怎么樣問題可以建模為線性規劃來解決呢？在給定的有限的資源和競爭約束情況下，取得最大化或最小化目標的問題。導論中給出政治競選問題、航空航線調度問題、鉆井采油問題。最大化或最小化目標是函數的因變量，自變量就是資源的約束因素，其函數就是由這些制約因素構成的等式或不等式。下面數學定義下線性規劃。

在一般線性規劃問題中，最優化一個滿足一組線性不等式約束的線性函數。已知一組實數a₁,a₂,…,a_n和一組變量x₁,x₂,…,x_n，基于這些變量的一個線性函數f定義為：

如果b是一個實數而f是一個線性函數，則等式：

f(x₁,x₂,…,x_n)=b是一個線性等式。

f(x₁,x₂,…,x_n)≥b和f(x₁,x₂,…,x_n)≤b是線性不等式。

線性約束就是函數f和b的關系，就是求解n個變量m個線性不等式的最大化，約束為線性不等式的線性函數最大化稱為標準型；而約束為線性等式的線性函數的最大化稱為松弛型。

基于上面描述可知，線性規劃問題是要最小化或最大化一個受限于一組有限的線性約束的線性函數。最小化線性規劃和最大化線性規劃的分類，是基于目標的需求，同樣是m個線性不等式約束，去求解n個變量的值，達到目標（最大化或最小化）。

凸形區域：區域內的任何兩點之間連線上的點都屬于這個區域。

線性規劃中，二維空間（兩個變量）所構成的凸形區域為可行區域，要最大化的函數為目標函數。可行區域內的每個點都會去評估目標函數x₁+x₂，將目標函數的一個特點點上的值稱為目標值，識別出一個有最大目標值的點就是最優解。當然有二維線性規劃不等式所構成的可行區域上是有無數個點，不可能都去求值，因此需要找出一個有效的方式來尋找最大目標值的點。線性規劃的最優解必定是在可行區域的邊界上，所以只要沿著邊界尋找頂點就可以很快找到最大目標值的點。

如果有三個變量，則每個約束以三位空間的一個半空間來描述，三個半空間的交集構成了可行區域，目標函數取目標值的點集合是一個平面。因為可行區域也是凸的，取得最優目標值的點集合必然包含可行區域的一個頂點。延伸到n個變量的超平面，每個約束定義了n維空間中的一個半空間，這些半空間的交集形成的可行區域稱作單純形，目標函數是一個超平面，且是凸性，一個最優解也是在單純形的一個頂點上取得。理解下，無論多少維，找出凸形區域，目標函數的最優解就是在凸形區域的頂點集合之一或多個。

單純形算法輸入一個線性規劃（n個變量m個線性不等式），輸出一個最優解。算法從單純形的某個頂點開始，執行一系列迭代，每次迭代中，沿著單純形的一條邊從當前頂點移動到一個目標值不小于當前頂點的相鄰頂點。當達到一個局部最大值，即一個頂點的目標值大于其所有相鄰頂點的目標值時，算法終止。因為可行區域是凸的且目標函數是線性的，所以具備最優事實就是全局最優的。

單純形算法需要指數時間。線性規劃的第一類多項式時間算法是橢圓算法，運行緩慢；第二類指數時間的算法是內點法，在大型輸入上，性能優于單純形算法。如果在線性規劃中，所有的變量都取整數值，即整數線性規劃，對于該問題，找出一個可行解是NP難度的。目前還沒有已知的多項式時間算法能NP難度問題，所以沒有有效的整數線性規劃多項式時間算法。當然，一般的線性規劃可以在多項式時間內解決。

1）標準型和松弛型

標準型的線性規劃所有的約束條件都是不等式，而松弛型中的約束是等式。要用單純形算法求解線性規劃，需要將所有線性規劃轉化為標準型，再將標準型轉化為松弛型，線性方程組等式求解。

標準型定義：

已知n個實數c ₁,c ₂,…,c _n；m個實數b ₁,b ₂,…,b _m；以及mn個實數a _ij，其中i=1,2,…,m，而j=1,2…,n，希望找出n個實數x1,x2,…,xn來最大化目標函數：

用矩陣表示更緊湊：

最大化c^Tx，滿足約束：Ax≤b，x≥0。

滿足所有約束的變量x_s設定為可行解，而不滿足至少一個約束的變量x_s設定為不可解。稱一個解x_s擁有目標值c^Tx_s，在所有可行解中其目標值最大的一個可行解x_s是一個最優解，稱其為目標值c^Tx_s的最優目標值。如果一個線性規劃沒有可行解，則稱此線性規劃不可行，否則是可行的。如果一個線性規劃有一些可行解但沒有有限的最優目標值，則稱此線性規劃是無界的。

已知一個最小化或最大化的線性函數受若干線性約束，總可以將這個線性規劃轉換為標準型。換句話說，要將非標準型的線性規劃轉化為標準型的。為什么會有非標準型的線性規劃呢？可能目標函數是一個最小化而不是最大化；可能擁有的變量不具有非負性約束；可能有等式約束；可能有大于等于的不等式約束，而不是小于等于。

將非標準的線性規劃轉化線性規劃，最重要是確保轉換后的線性規劃最優解也是轉換前的線性規劃最優解，轉化前后的兩個線性規劃是等價的。轉化思路就是對目標函數系數取負，并將不具有非負約束性的變量轉換成具有非負性約束的變量。

為了利用單純形算法高效地求解線性規劃，需要將標準型轉換成松弛型，就是非負約束是不等式，其他約束都是等式。轉換思路就是利用松弛變量，就是將不等式的余量用s來接收，從而使不等式變成等式，形式如下：

基于松弛型線性規劃，就可以用單純形算法求解。

2）將問題表達為線性規劃：建模

既然定義了線性規劃，也知道線性規劃可以在多項式時間內求解，那么對于現實的問題，那些事如果形式化為線性規劃的問題來求解呢？這就涉及到建模了，現實中的問題如何建模為線性規劃來求解。建模：將問題轉化成數學形式來求解。

算法導論中對單源最短路徑變形的單對最短路徑、最大流以及最大流變形的最小費用流和多商品流形式化為線性規劃。這里描述下單對最短路徑和最大流的線性規劃形式化。

?? 單對最短路徑問題

在單對最短路徑問題中，已知一個帶權有向圖G=(V,E)，加權函數w:E->R將邊映射到實數值的權值、一個源頂點s、一個目的頂點t，要計算從s到t的一條最短路徑的權值d[t]。將該問題用線性規劃表示，要確定變量和約束的集合。在Belleman-Ford算法終止時，對每個頂點v，都一個值d[v]，使得每條邊(u,v)∈E，有d[v]≤d[u]+w(u,v)。源頂點初始得到一個值d[s]=0，如此有計算從s到t的最短路徑權值的線性規劃：

最大化：d[t]

滿足約束：d[v]≤d[u]+w(u,v)，每條邊(u,v)∈E成立

????????? d[s]=0

共有|V|個變量d[v]，每個頂點v∈V各有一個，有|E|+1個約束，每條邊各有一個再加上源頂點d[s]=0的額外約束。

?? 最大流問題

已知一個有向圖G=(V,E)，其中每條邊(u,v)∈E有一個非負容量c(u,v)≥0，以及源點s和匯點t。流是一個實數值函數f:VXV->R，滿足三個性質：容量限制、斜對稱性、流守恒性。最大流是滿足這些約束和最大化流流量的流，其中流量值是從源流出的總流量。因此，流滿足線性約束，且流的值是一個線性函數。當然如果(u,v)?E，則c(u,v)=0。可將最大流線性規劃為：

共有|V|²個變量，對應于每一對頂點之間的流，且有2|V|²+|V|-2個約束。

最小費用流是最大流的每條邊上加一個費用權值，多商品流是最大流的每條邊容量不止給一件商品是給多件商品。

3）單純形算法

單純形算法是求解線性規劃的古典方法。單純形算法和高斯消元法迭代原理類似，高斯消元法是從解未知的一個線性等式系統開始。可以將單純形算法看成是線性不等式系統上的高斯消元法。

單純形算法的迭代主要思想是：從線性規劃的松弛型中得到每次迭代關聯的基本解，將每個非基本變量設為0，并從等式約束中計算基本變量的值；一個基本解對應于單純形的一個頂點；代數上，一次迭代將一個松弛型轉換成一個等價的松弛型；相應的基本解的目標值不小于前一次迭代中的目標值，要實現迭代過程中目標值的遞增，要選擇一個非基本變量作為指示變量，從0開始增加這個變量的值，和目標值一起增加，增加到某個基本變量變為0為止再重寫松弛型，將這個基本變量和所選的非基本變量進行角色互換，就是重寫線性規劃直到最優解很明顯。

單純形算法主要關鍵是主元選擇，并且有三個關鍵點，第一確定線性規劃是可行的；第二確定線性規劃是具有可行解而不是無界；第三主元如何選擇換入變量和換出變量。這些到導論偽碼算法描述都有說明并證明。這里一般性地理解下，要通過單純形算法來求解，在算法之前要肯定線性是可行（單純性算法最初有一個初始化過程，會判斷線性規劃是否可行，返回一個初始基本解可行的松弛型），在算法之中要確保不陷入退化或說循環（目標值越迭代越小），能夠終止返回最優解。單純形算法輸入一個標準型線性規劃，返回線性規劃一個最優解，能夠順利找到最優解并終止算法，后續對偶型可以說明。

單純形整個算法過程是：

首先初始化標準型線性規劃，返回一個初始基本解可行的松弛型，或者返回這個線性規劃不可行，推出算法；

其次對松弛型線性規劃開始主元操作，選擇非負系數最緊約束的換出變量，和換入變量交換，得到新的線性規劃（和原來的線性規劃是等價的）；

不斷迭代這個過程，直到最優解確定，并終止返回一個最優解。

對于松弛型線性規劃通過主元操作生成的新線性規劃，二者是等價的證明可以看導論中說明。現在很重要的就是主元操作迭代，是如何選擇換出變量的。選擇一個在目標函數中系數為正值的非基本變量，盡可能增加其值而不違反任何約束。現在通過一個例子來理解單純形算法的過程。

第一：標準型線性規劃轉化為松弛型線性規劃

標準型：

最大化：3x₁+x₂+2x₃

滿足約束：x₁+x₂+3x₃≤30

_{????????????????????}2x₁+2x₂+5x₃≤24

????????????? 4x₁+x₂+2x₃≤36

????????????? x₁,x₂,x₃≥0

松弛型：

最大化：z=3x₁+x₂+2x₃

滿足約束：x₄=30-x₁-x₂-3x₃

????????? x₅=24-2x₁-2x₂-5x₃

????????? x₆=36-4x₁-x₂-2x₃

確定基本解：把等式右邊的所有變量設為0，可得基本解（x₁,x₂,x_3,x_4, x_5, x₆）=(0,0,0,30,24,36)，目標值z=0；

第二：主元操作迭代第一次，選擇增加x₁的值。當增加x₁值時，x_4, x_5, x₆的值隨之減小，但每個變量都有非負約束，所以不能減小到負值，這個時候就要在約束函數上選擇最緊約束（就是選擇最小增加值）。

如果x₁值增加到30，那么x₄是負值；增加到12，則x₅是負值；增加到9，則x₆是負值；這個就知道了，9是x₁值所能增加的最大值，就是最緊約束，對約束函數x₆=36-4x₁-x₂-2x₃互換變量x₁和x₆的角色，得到：x₁=9- x₂/4- x₃/2- x₆/4，代入原線性規劃據此可得新的松弛型線性規劃，如下：

最大化：z=27+x₂/4+ x₃/2- 3x₆/4

滿足約束：

??????? x₁=9- x₂/4- x₃/2-x₆/4

???? x₄=21-3x₂/4-5x₃/2+x₆/4

???? x₅=6-3x₂/2-4x₃+x₆/2

確定基本解，同樣把等式右邊的所有變量設為0，可得基本解（x₁,x₂,x_3,x_4, x_5, x₆）=(9,0,0,21,6,0)，目標值z=27；

第三：主元操作迭代第二次，選擇增加x₃的值，最緊約束是x₅=6-3x₂/2-4x₃+x₆/2，最大增加到3/2，否則x₅的值為負，和第一次迭代一樣，互換x₃和x₅并代入線性等式獲得新的線性規劃，可得基本解（x₁,x₂,x_3, x_4, x_5,x₆）=(33/4,0,3/2,69/4,0,0)，目標值z=111/4；

第四：主元操作迭代第三次，互換x₂和x₄并代入線性等式獲得新的線性規劃，可得基本解（x₁,x₂,x_3, x_4, x_5,x₆）=(8,4,0,18,0,0)，目標值z=28，為最優解，（x₁,x₂,x₃）=(8,4,0)。

最關心的問題還是具有可行解的線性規劃經過這樣的迭代，在算法終止時是否確實能找到最優解，這個就留給線性規劃對偶性來說明。

4）單純形算法分析

現在我們知道單純形算法可以在多項式時間內求解線性規劃最優解，那么關心兩點：一是算法終止時，獲得的是最優解，這個就是對偶性要回答；二是輸入一個線性規劃要判斷出是可行可解的，這個就是輔助線性規劃要回答的。任何線性規劃都可能是不可行的，或是無界的，或有一個優先目標值得最優解，針對這些個情況，單純形算法要能正確識別。

線性規劃的基本定理：以標準型給出任意的線性規劃L可能是以下三者之一：

第一：有一個有限目標值的最優解；

第二：不可行；

第三：無界；

如果L是不可行的，單純形算法在初始化中就會返回不可行；如果L是無界的，單純形算法返回無界，無界就是找不到最優解或者有無限個目標值；當然，滿足第一情況的，就會返回有限目標值的最優解。

單純形算法在初始化過程中，會確定線性規劃是否有可行解，如果有，則給出一個基本解可行的松弛型線性規劃。這個初始化過程其實就是對線性規劃測試可行解。那么是如何來確認存在可行解呢？通過構造輔助線性規劃，這個輔助線性規劃，比較容易找到一個基本解可行的松弛型。只要輔助線性規劃有可行解，則要輸入的線性規劃也就有可行解。如果線性規劃L沒有可行解，則初始化返回不可行，否則返回一個基本解可行的合法松弛型。怎么構造輔助線性規劃呢？

輔助線性規劃：令L是一個標準型的線性規劃，令L _aux是帶有n+1個變量的線性規劃：

最小化：-x₀

滿足約束：

則當且僅當L_aux的最優目標值為0時，L是可行的。

輔助線性規劃，增加一個x₀變量，并且令目標值為0。對輔助線性規劃求解可行解，也是按照主元操作，將標準型轉換成松弛型后不斷交換變量迭代。輔助線性規劃較容易找到可行解。算法導論中證明了輔助線性規劃存在可行解就是要求解的線性規劃存在可行解。

現在我們要引進線性規劃對偶性的概念。對偶性有一個很重要的性質：在一個最優化問題中，一個對偶問題的識別總是可以在一個多項式時間內發現。對偶性是用來證明某個解確實是最優解。還是動態規劃思想：已知一個最大化問題，定義個相關的最小化問題，來讓著兩個問題有相同的最優目標值。如最大流問題的最大流最小割原理。對偶的字面意義，就是我的解也是你的解，大問題的解是小問題的解。

已知一個目標是最大化的線性規劃，制定一個對偶線性規劃，其目標是最小化，而且最優值與原始線性規劃相同。給定一個標準的原線性規劃，定義對偶線性規劃為：

構造對偶，將最大化改成最小化，將約束右邊的與目標函數的稀疏角色互換，并且小于等于號變成大于等于號。在原問題的m個約束中，每一個在對偶問題中都一個對應的變量y_i，在對偶問題的n個約束中，每一個在原問題中都一個對應的變量x_j。

開始不是很能理解這個，對著文中例子看很久才知道主要是兩點：1）原線性規劃中的目標函數的系數變成對偶線性規劃中約束函數的右邊值，原線性規劃中的約束函數的右邊值變成對偶線性規劃中目標函數的系數；2）原線性規劃中每一個約束函數的左邊等于對偶線性規劃中的一個變量，就是原線性規劃中的m個約束函數等于m個對偶線性規劃中的變量，反之也是。

導論最后只能夠證明了對偶線性規劃的最優值總是等于原線性規劃的最優值。

線性規劃弱對偶性：原線性規劃的任意可行解的數值不大于對偶線性規劃的任意可行解的值。

基于線性規劃弱對偶性，原問題可行解的目標值不會超過對偶問題的可行解的目標值。而原線性規劃是一個最大化問題，對偶性線性規劃是一個最小化問題，如果原線性規劃的可行解等于對偶線性規劃的可行解，那這個可行解就是原線性規劃和對偶線性規劃的最優解。

通過構造對偶性線性規劃確認最優解，通過構造輔助線性規劃來確定可行解，單純形算法是可以對任意輸入一個標準型線性規劃，返回或不可行或無界或最優解的。

總結

以上是生活随笔為你收集整理的算法导论之线性规划的全部內容，希望文章能夠幫你解決所遇到的問題。

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