第一篇：單純形法和擬牛頓法

擬牛頓法(Quasi-Newton Methods)是求解非線性優化問題最有效的方法之一，于20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種算法在當時看來是非線性優化領域最具創造性的發明之一。不久R.Fletcher和M.J.D.Powell證實了這種新的算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。在之后的20年里，擬牛頓方法得到了蓬勃發展，出現了大量的變形公式以及數以百計的相關論文。

擬牛頓法和最速下降法(Steepest Descent Methods)一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優于最速下降法，尤其對于困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法(Newton's Method)更為有效。如今，優化軟件中包含了大量的擬牛頓算法用來解決無約束，約束，和大規模的優化問題。

擬牛頓法的基本思想如下。首先構造目標函數在當前迭代$x_k$的二次模型：m_k(p)=f_k+g_k^T p+p^T B_k p/2，這里f_k=f(x_k)，g_k=▽f(x_k)，B_k是一個對稱正定矩陣。于是我們取這個二次模型的最優解p_k=-B_k^{-1} g_k作為搜索方向，并且得到新的迭代點x_{k+1}=x_k+a_k p_k，其中我們要求步長a_k滿足Wolfe條件。這樣的迭代類似與牛頓法，區別就在于用近似的Hesse矩陣B_k代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣B_k的更新。現在假設得到一個新的迭代x_{k+1}，并得到一個新的二次模型：m_{k+1}(p)=f_{k+1}+g_{k+1}^T p + p^T B_{k+1} p/2。我們盡可能地利用上一步的信息來選取B_{k+1}。具體地，我們要求g_{k+1}-g_k=a_k B_{k+1} p_k，從而得到B_{k+1}s_k=y_k，其中s_k=x_{k+1}-x_k，y_k=g_{k+1}-g_k。這個公式被稱為割線方程。下面主要介紹這幾種方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。

純形法，求解線性規劃問題的通用方法。單純形是美國數學家G.B.丹齊克于1947年首先提出來的。它的理論根據是：線性規劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優解；若不是，則按照一定法則轉換到另一改進的基本可行解,再鑒別；若仍不是，則再轉換,按此重復進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解也可用此法判別。根據單純形法的原理，在線性規劃問題中，決策變量（控制變量）x1，x2，…x n的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目標函數達到最大值（或最小值）的可行解稱為最優解。這樣，一個最優解能在整個由約束條件所確定的可行區域內使目標函數達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。

最優解可能出現下列情況之一：①存在著一個最優解；②存在著無窮多個最優解；③不存在最優解，這只在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函數的值無限增大（或向負的方向無限增大）。

單純形法的一般解題步驟可歸納如下：①把線性規劃問題的約束方程組表達成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優的另一基本可行解。④按步驟3進行迭代,直到對應檢驗數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。⑤若迭代過程中發現問題的目標函數值無界，則終止迭代。

用單純形法求解線性規劃問題所需的迭代次數主要取決于約束條件的個數。現在一般的線性規劃問題都是應用單純形法標準軟件在計算機上求解，對于具有106個決策變量和104個約束條件的線性規劃問題已能在計算機上解得

第二篇：單純形法理論

單純形法

單純形法不用計算函數的導數，只需要計算目標函數的函數值，因此計算比較簡單，幾何概念也比較清晰，屬于直接法的無約束最優化方法。所謂n維歐氏空間E中的單純形，是指在n維空間中由n?1個線性獨立的點構成的簡單圖形或凸多面體。

基本思想：根據問題的維數n選取n?1個線性獨立的點，然后計算這n?1個點的函數值并進行比較，確定其中的最大值的點及函數的下降方向，再設法找到一個新的好點替換函數值最大的點，從而構成新的單純形。這個過程不斷進行，新的單純形將向極小點收縮。經過若干次迭代后，即可得到滿足收斂條件的極小點。

基本過程包括：反射、擴張和壓縮。下面以二維問題為例來說明單純形法的求優過程。設二維函數f(X)在平面上有線性獨立的三個點Xh，Xl，Xg，構成單純形（三角形），計算這三個點的函數值，若

nf(Xh)?f(Xg)?f(Xl)

則說明Xh是最差點，Xl是最好點，Xg為次差點，迭代應該找出好的點Xr來替換最差點Xh，構成新的單純形。Xr在Xh與除去最差點Xh以后所有頂點的形心點Xc連線的延長線上進行選取。

Xr?Xc??(Xc?Xh)

式中：?——反射系數，一般取??1。

這個步驟稱為反射。通常，反射點Xr的取法是使Xr點Xr點稱為最差點Xh的反射點，至Xc點的距離等于Xc點到Xh的距離。

反射點Xr對新單純形構造的影響，有以下幾種情況：（1）擴張

1若反射點的函數值f(Xr)小于最好點的函數值f(Xl)，即當 ○f(Xr)?f(Xl)

時，說明所取的方向是正確的，可進一步擴大效果，繼續沿XhXr向前進行擴張，在更遠處取一點Xe，并滿足 Xe?Xc??(Xr?Xc)

式中：?——擴張系數，??1.2~2.0，一般取??2.0。

如果f(Xe)?f(Xl)，說明擴張有利，就用Xe代替最差點Xh，構成新的單純形。否則，說明擴張不利，舍棄Xe，仍以Xr代替最差點Xh，構成新的單純形。

2若f(Xr)?f(Xl)不成立，則不能進行擴張，此時如果 ○f(Xr)?f(Xg)

則用反射點Xr替換最差點Xh，構成新的單純形。（2）壓縮

1若反射點的函數值f(Xr)小于最差點的函數值f(Xh)，但大于次差點的函數值○f(Xg)，即當

f(Xg)?f(Xr)?f(Xh)

時，則表示Xr點走得太遠，需縮回一些，即進行壓縮，并且得到的壓縮點應為

Xs?Xc??(Xr?Xc)

式中：?——壓縮系數，常取??0.5。這時若f(Xs)?f(Xh)

則用壓縮點Xs代替最差點Xh，構成新的單純形。

2若反射點的函數值f(Xr)大于最差點的函數值f(Xh)，即當 ○f(Xr)?f(Xh)

時，應當壓縮更加多些，即將新點壓縮至Xh與Xc之間，這時所得的壓縮點應為

Xs??Xc??(Xc?Xh)?Xc??(Xh?Xc)

如果f(Xs?)?f(Xh)，說明不能沿Xh的反射方向搜索，應進行縮邊。（3）縮邊

使單純形向最好點進行收縮，即使最好點Xl不動，其余各頂點皆向Xl移近為原距離的一半。

Xi?Xi?Xl

i?0,1,?,n 2從以上各步得到新的單純形后，再重復開始各步，逐漸縮小單純形直至滿足精度要求為止。

初始單純形的形成：

構成單純形的頂點應是線性獨立的，否則，如二維問題，三個點在一條直線上，就變成二維問題了，即在一條直線上找極小點的問題，稱為退化。為防止退化，一般取成等邊三角形，因為它是周長一定前提下包圍面積最大的布點方式。

把二維等邊三角形推廣到n維的情況是n?1個點中任兩個點的距離都相等，這種單純形就稱為正規單純形。選取正規單純形作初始單純形的方法如下：

給定一個初始點X0?[x1,x2,?,xn]T，其余n個點可取為：

X1?[x1?p,x2?q,x3?q?,xn?q]T

??

Xn?[x1?q,x2?q,x3?q?,xn?p]T

即第i個頂點的第i個坐標分量比初始點增加p，其他分量增加q。設正規單純形任意兩頂點的距離等于c，這時p，q的公式推導如下。對于點X2和X1，有X2?X1?c即

(x1?q?x1?p)2?(x2?p?x2?q)2?(x3?q?x3?q)2???(xn?q?xn?q)2?c

2化簡得

(q?p)2?(p?q)2?2(p?q)2?c2

對于X1和X0，有X1?X0?c，即

(x1?p?x1)2?(x2?q?x2)2?(x3?q?x3)2???(xn?q?xn)2?c2

化簡得

p2?(n?1)q2?c2

聯立求解得 p?(n?1?n?1)c

n2(n?1?1)c

n2q?初始單純形也可以采用下面的方法：設目標函數f(X)為n維向量，因此單純形應有n?1個頂點X1，X2，?，Xn?1。構造單純形時，現在n維空間中選取初始點X1(0)（盡量靠近最優點），從X1(0)出發沿各坐標軸方向ei、以步長h找到其余n個頂點X(0)j（j?2，3，…，n?1）：

(0)X(0)?Xj1?hei

式中：ei——第i個坐標軸的單位向量；

h——步長，一般取值范圍為0.5~15.0，接近最優點時要減小。構成初始單純形的步長可取1.6~1.7。

構成初始單純形后，可按以下步驟進行：

(k)(k)（1）計算各頂點的函數值并進行比較，找出最好點Xl(k)，最差點Xh，次差點Xg，(k)(k)(k)以及除最差點外其它各點的形心Xn?2。求Xh對形心點Xn?2的反射點：

(k)(k)(k)(k)Xn?3?Xn?2??(Xn?2?Xh)

(k)(k)(k)(k)（2）比較Xn，如果反射點Xn還好，即進行擴張，得擴張點?3和Xl?3比最好點Xl為：

(k)(k)(k)(k)Xn?4?Xn?2??(Xn?3?Xn?2)

(k)(k)(k)(k)(k)得到擴張點Xn，否則?4后，若f(Xn?4)?f(Xl)，用Xn?4代替Xh，并轉步驟（5）(k)(k)用Xn代替。X?3h后轉入步驟（5）(k)(k)若f(Xn?3)?f(Xl)，即反射點比最好點差，則轉下一步。

(k)(k)（3）將反射點Xn?3與次差點Xg比較，如果f(Xn?3)?f(Xg)，則用Xn?3代替最(k)(k)(k)差點Xh，并轉步驟（5）；若f(Xg)?f(Xn?3)?f(Xh)，則用Xn代替X?3h后進行

(k)(k)(k)(k)(k)(k)壓縮，否則直接進行壓縮，得壓縮點為：(k)(k)(k)(k)Xn?5?Xn?2??(Xh?Xn?2)

(k)(k)(k)(k)(k)（4）求得壓縮點Xn后與最差點比較，若，則用Xf(X)?f(X)X?5hn?5hn?5代替(k)以后轉下一步；否則使單純形向最好點Xl(k)收縮，收縮后的單純形頂點為： XhX(jk)?Xl(k)?0.5(X(jk)?Xl(k))

j?1，2，…，n?1

然后轉下一步。

（5）進行收斂性檢驗。若

?1n?12?(k)(k)??f(X)?f(X)??jn?2???? ??n?1j?1?則停止迭代并輸出Xl(k)及f(Xl(k))，否則使k?k?1后轉第1步。式中?為任意的小(k)數，Xn?2為形心。

12例

試用單純形法求解目標函數f(X)?4(x1?5)2?(x2?6)2的極小值。

Function f=fun(x)syms

x1

x2

f = 4*(x1-5)^2+(x2-6)^2;clear

x1= 0 x2= 0 z=0 e= [1;1] h=1.6 X0=[x1;x2] X1=X0 + h* e X2=X0 + h*e X3=X0 + h*e

第三篇：單純形法綜述

單純形法綜述

zy1415104-曹文亮

單純形法是1947年由George Bernard Dantzing(1914-2005)創建的，單純形法的創建標志著線性規劃問題的誕生。線性規劃問題是研究在線性約束條件下，求線性函數的極值問題。然而，對這類極值問題，經典的極值理論是無能為力的，只有單純形法才能有效解決這類極值問題的求解。線性規劃是數學規劃的一個重要分支，也是最早形成的一個分支，線性規劃的理論與算法均非常成熟，在實際問題和生產生活中的應用非常廣泛；線性規劃問題的誕生標志著一個新的應用數學分支——數學規劃時代的到來。過去的60年中，數學規劃已經成為一門成熟的學科。其理論與方法被應用到經濟、金融、軍事等各個領域。數學規劃領域內，其他重要分支的很多問題是在線性規劃理論與算法的基礎上建立起來的，同時也是利用線性規劃的理論來解決和處理的。由此可見，線性規劃問題在整個數學規劃和應用數學領域中占有重要地位。因此，研究單純形法的產生與發展對于認識整個數學規劃的發展有重大意義。

單純形法是從某一基可行解出發，連續地尋找相鄰的基可行解，直到達到最優的迭代過程，其實質是解線性方程組。

概述：

根據單純形法的原理，在線性規劃問題中，決策變量（控制變量）x1，x2，…x n的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目標函數達到最大值（或最小值）的可行解稱為最優解。這樣，一個最優解能在整個由約束條件所確定的可行區域內使目標函數達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。最優解可能出現下列情況之一：①存在著一個最優解；②存在著無窮多個最優解；③不存在最優解，這只在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函數的值無限增大（或向負的方向無限增大）。

無最優解與無可行解是兩個不同的概念。無可行解是指原規劃不存在可行解，從幾何的角度解釋是指 線性規劃問題的可行域為空集； 無最優解則是指線性規劃問題存在可行解，但是可行解的目標函數達不到最優值，即目標函數在可行域內可以趨于無窮大（或者無窮小）。無最優解也稱為無限最優解，或無界解。

無最優解判別定理：在求解極大化的線性規劃問題過程中，若某單純形表的檢驗行存在某個大于零的檢驗數，但是該檢驗數所對應的非基變量的系數列向量的全部系數都為負數或零，則該線性規劃問題無最優解。

無窮多最優解判別原理：若線性規劃問題某個基本可行解所有的非基變量檢驗數都小于等于零，但其中存在一個檢驗數等于零，那么該線性規劃問題有無窮多最優解。

退化與循環：如果在一個基本可行解的基變量中至少有一個分量為零，則稱此基本可行解是退化的基本可行解。產生的原因：在單純形法計算中用最小比值原則確定換出變量時，有時存在兩個或兩個以上相同的最小比值θ，那么在下次迭代中就會出現一個甚至多個基變量等于零。

退化可能出現以下情況：

① 進行進基、出基變換后，雖然改變了基，但沒有改變基本可行解（極點），目標函數當然也不會改進。進行若干次基變換后，才脫離退化基本可行解（極點），進入其他基本可行解（極點）。這種情況會增加迭代次數，使單純形法收斂的速度減慢。

② 在特殊情況下，退化會出現基的循環，一旦出現這樣的情況，單純形迭代將永遠停留在同一極點上，因而無法求得最優解。事實上，已經有人給出了循環的例子。

單純形法的一般解題步驟可歸納如下：①把線性規劃問題的約束方程組表達成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優的另一基本可行解。④按步驟3進行迭代,直到對應檢驗數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。⑤若迭代過程中發現問題的目標函數值無界，則終止迭代。

用單純形法求解線性規劃問題所需的迭代次數主要取決于約束條件的個數。現在一般的線性規劃問題都是應用單純形法標準軟件在計算機上求解，對于具有106個決策變量和104個約束條件的線性規劃問題已能在計算機上解得。

求解步驟：

（1）確定初始基可行解

① 從線性規劃標準形的系數矩陣中能直接找出m個線性獨立的單位向量；

② 對約束條件全為“<=”連接的LP，化為標準形，左端添加松弛變量后即形成一個單位子矩陣；

③ 約束條件中含有“<=”或“=”連接的方程，在插入剩余變量后找不到單位矩陣，則必須采用“人造基”法，也稱“人工變量”法。

（2）最優性檢驗及解的判別準則

① 最優性判定準則 ② 多重最優解判定準則 ③ 無界最優解判定準則（3）換基迭代

① 確定換入變量 ② 確定換出變量 ③ 樞運算（旋轉運算）

單純形法-正文：

根據單純形法的原理，在線性規劃問題中，決策變量（控制變量）x1，x2，…x n的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目標函數達到最大值（或最小值）的可行解稱為最優解。這樣，一個最優解能在整個由約束條件所確定的可行區域內使目標函數達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。

可能出現下列情況之一：①存在著一個最優解；②存在著無窮多個最優解；③不存在最優解，這只在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函數的值無限增大（或向負的方向無限增大）。

要縮小對最優解的搜索范圍，就必須認識最優解的一般性質，最優解如果存在的話，則它必然處于可行區域的邊界上。

任何一項約束條件的邊界方程是用“＝”號來替換該約束條件中的“≤”或“≥”號而得到的。每一個邊界方程確定一個超平面。因此，可行區域的邊界是由那些滿足一個或同時滿足幾個邊界方程（即處在作為邊界的一個或幾個超平面上）的可行解所組成，而且最優解必在其中。最優解不僅是在可行區域的邊界上，而且也在這個區域的一個隅角上。一個可行解，如果不處在由另兩個可行解連接起來的任何線段上，它就是一個角點可行解。如果連接兩個角點可行解的線段處在可行區域的邊界上，這兩個角點可行解就稱為相鄰的角點可行解。角點可行解具有下列三個重要性質：①如果存在著一個最優解，那么它必定是角點可行解。如果存在有多個最優解，那么至少有兩個最優解必定是相鄰的角點可行解。②只存在有限個數的角點可行解。③如果一個角點可行解按目標函數值來衡量時比其所有的相鄰角點可行解更好一些，那它就比所有其他角點可行解都更好，也就是最優解。

上述這些性質構成單純形法的原理基礎。最后一個性質的重要性在于它為一個角點可行解是否是最優解提供了一種簡便的檢驗標準，因而毋需列舉所有的可行解。單純形法正是利用了這個性質，只要檢查少數的角點可行解，并且一旦這個最優性檢驗獲得通過就可立即停止運算。

單純形法的運算步驟可歸結為：①起始步驟──在一個角點可行解上開始。②迭代步驟──移動至一個更好一些的相鄰角點可行解（根據需要反復進行這一步驟）。③停止法則──在當前角點可行解比所有相鄰角點可行解都更好些時停止。當前角點可行解就是一個最優解。

單純形法的優點及其成功之處在于它只需要較少的有限次數的迭代，即可找到最優解。

改進單純形法：

原單純形法不是很經濟的算法。1953年美國數學家G.B.丹齊克為了改進單純形法每次迭代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次迭代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了在計算機上的存儲量。

對偶單純形法：

（Dual Simplex Method）1954年美國數學家C.萊姆基提出對偶單純形法。單純形法是從原始問題的一個可行解通過迭代轉到另一個可行解，直到檢驗數滿足最優性條件為止。對偶單純形法則是從滿足對偶可行性條件出發通過迭代逐步搜索原始問題的最優解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。設原始問題為min{cx|Ax=b，x≥0}，則其對偶問題（Dual Problem）為 max{yb|yA≤c}。當原始問題的一個基解滿足最優性條件時,其檢驗數cBB-1A-c≤0。即知y=cBB-1（稱為單純形算子）為對偶問題的可行解。所謂滿足對偶可行性，即指其檢驗數滿足最優性條件。因此在保持對偶可行性的前提下，一當基解成為可行解時，便也就是最優解。

對偶單純形法的基本原則：在保持對偶可行的前提下進行基變換——每一次迭代過程中取出基變量中的一個負分量作為換出變量去替換某個非基變量（作為換入變量），使原始問題的非可行解向可行解靠近。

第四篇：單純形法matlab程序

算法實現與分析

算法1．單純形法 具體算例：

minz=?3x1+x2+2x3 3x1+2x2?3x3=6 x1?2x2+x3+x5=4

x1,x2,x3≥0標準化后：

min z=?3x1+x2+2x3+Mx4+Mx5

3x1+2x2?3x3+x4=6 x1?2x2+x3+x5=4

x1,x2,x3,x4,x5≥0用單純形法求解，程序如下： clear clc

M=1000000;

A=[3,2,-3,1,0;1,-2,1,0,1];%系數矩陣 C=[-3,1,2,M,M,0];%價值矩陣 B=[6;4];Xt=[4 5];

for i=1:length(C)-1 D=0;

for j=1:length(Xt)

D=D+A(j,i)*C(Xt(j));

end

xi(i)=C(i)-D;end s=[];

for i=1:length(xi)

if xi(i)<0 s=[s,i];

end end

f=length(s);h=1;

while(f)

for k=1:length(s)j=1;A x=[];

for i=1:length(Xt)

if A(i,s(k))>0 x(j)=i;j=j+1;

end end x

if(length(x)+1==1)break;end y=1 x

for i=1:length(x)

if B(x(i))/A(x(i),s(k))

end end y=x(y);end

y1=Xt(y);%??3?±?á? s k

aa=A(y,s(k))%s(k)?a??è?±?á? A(y,:)=A(y,:)./aa;B(y,:)=B(y,:)./aa;z=[];

for i=1:length(Xt)z=[z,i];end

z z(y)=[];z Xt

for i=1:length(z);yz=-A(z(i),s(k))

A(z(i),:)=A(z(i),:)+A(y,:).*yz B(z(i))B(y)yz

B(z(i))=B(z(i))+B(y).*yz end

for i=1:length(Xt)

if Xt(i)==y1 Xt(i)=s(k);break

end end Xt

disp('×a??oó')A=A B=B AB=[A,B];

for i=1:length(C)D=0;

for j=1:length(Xt)D=D+AB(j,i)*C(Xt(j));

end

xi(i)=C(i)-D;

end xi s=[];

for i=1:length(xi)-1

if xi(i)<0 s=[s,i];

end

end s

vpa([A,B;C]);f=length(s);h=h+1;

if h==5

break

end end

-xi(length(xi))

第五篇：單純形法課程論文

最優化方法課程論文

題目：單純形法的發展及其應用系別：理學院專業：信息與計算科學姓名：班級：信息

101班

單純形法的發展及其應用

一． 單純形法簡介：

單純形法，求解線性規劃問題的通用方法。單純形是美國數學家G.B.丹齊克于1947年首先提出來的。它的理論根據是：線性規劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優解；若不是，則按照一定法則轉換到另一改進的基本可行解，再鑒別；若仍不是，則再轉換，按此重復進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解也可用此法判別。

二． 單純形法在線性規劃中的應用 1.單純形法解線性規劃問題

在生產管理和經濟活動中，經常遇到這些問題，如生產計劃問題，即如何合理利用有限的人、財、物等資源，以便得到最好的經濟效果；材料利用問題，即如何下料使用材最少；配料問題，即在原料供應量的限制下如何獲取最大利潤；勞動力安排問題，即如何用最少的勞動力來滿足工作的需要；運輸問題，即如何制定調運方案，使總運費最小；投資問題，即從投資項目中選取方案，使投資回報最大等等。對于這些問題，都能建立相應的線性規劃模型。事實上，線性規劃就是利用數學為工具，來研究在一定條件下，如何實現目標最優化。單純形法是求解線性規劃問題的通用方法。

(1)單純形法解線性規劃問題的理論根據是：

線性規劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。

(2)單純形法的基本思想是：

先找出一個基本可行解，對它進行鑒別，看是否是最優解；若不是，則按照一定法則轉換到另一改進的基本可行解,再鑒別；若仍不是，則再轉換,按此重復進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解也可用此法判別。

(3)單純形法的一般解題步驟可歸納如下：

①把線性規劃問題的約束方程組表達成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優的另一基本可行解。④按步驟3進行迭代,直到對應檢驗數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。⑤若迭代過程中發現問題的目標函數值無界，則終止迭代。(4)概述

根據單純形法的原理，在線性規劃問題中，決策變量（控制變量）x1，x2，…x n的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目標函數達到最大值（或最小值）的可行解稱為最優解。這樣，一個最優解能在整個由約束條件所確定的可行區域內使目標函數達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。

最優解可能出現下列情況之一：①存在著一個最優解；②存在著無窮多個最優解；③不存在最優解，這只在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函數的值無限增大（或向負的方向無限增大）。

單純形法的一般解題步驟可歸納如下：①把線性規劃問題的約束方程組表達成典范型方程組，找出基本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優的另一基本可行解。④按步驟3進行迭代,直到對應檢驗數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。⑤若迭代過程中發現問題的目標函數值無界，則終止迭代。

用單純形法求解線性規劃問題所需的迭代次數主要取決于約束條件的個數。現在一般的線性規劃問題都是應用單純形法標準軟件在計算機上求解，對于具有10^6個決策變量和10^4個約束條件的線性規劃問題已能在計算機上解得。

2.線性規劃問題的標準化

使用單純形法求解線性規劃時，首先要化問題為標準形式 所謂標準形式是指下列形式：

maxz??cj?1njxj

?n??aijxj?bi(i?1,?,m)s?t??j?1

?x?0(j?1,2,?,n)?j當實際模型非標準形式時，可以通過以下變換化為標準形式： ①當目標函數為minz??cjxj時，可令Z′=-Z，而將其寫成為

j?1nminz????cjxj

j?1n求得最終解時，再求逆變換Z=-Z′即可。

②當s·t·中存在ai1x1?ai2x2???ainxn?bi形式的約束條件時，可引進變量

?xn?1?bi?(ai1x1?ai2x2???ainxn)??xn?1?0便寫原條件成為

?ai1x1?ai2x2???ainxn?xn?1?bi ?x?0?n?1其中的xn+1稱為松馳變量，其作用是化不等式約束為等式約束。同理，若該約束不是用“≤”號連接，而是用“≥”連接，則可引進松馳變量

?xn?1?(ai1x1?ai2x2???ainxn)?bi ??xn?1?0使原條件寫成

?ai1x1???ainxn?xn?1?bi ??xn?1?0

3.單純形法迭代原理（1）確定初始可行解

① 當線性規劃問題的所有約束條件均為≤號時，松弛變量對應的系數矩陣即為單位矩陣，以松弛變量為基變量可確定基可行解。

② 對約束條件含≥號或=號時，可構造人工基，人為產生一個m×m單位矩陣用大M法或兩階段法獲得初始基可行解。

（2）最優性檢驗與解的判別（目標函數極大型）

① 當所有變量對應的檢驗數均非正時，現有的基可行解即為最優解。若存在某個非基變量的檢驗數為零時，線性規劃問題有無窮多最優解；當所有非基變量的檢驗數均嚴格小于零時，線性規劃問題具有唯一最優解。② 若存在某個非基變量的檢驗數大于零，而該非基變量對應的系數均非正，則該線性規劃問題具有無界解（無最優解）。③ 當存在某些非基變量的檢驗數大于零，需要找一個新的基可行解，基要進行基變換。

4.確定初始可行解

確定初始的基本可行解等價于確定初始的可行基，一旦初始的可行基確定了，那么對應的初始基本可行解也就唯一確定，為了討論方便，不妨假設在標準型線性規劃中，系數矩陣Ａ中前m個系數列向量恰好構成一個可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，?Ｐm）為基變量x1，x2，?xm的系數列向量構成的可行基，Ｎ=(Ｐm+1，Pm+2，?Pn)為非基變量xm+1，xm+2，?xn的系數列向量構成的矩陣。

所以約束方程AX=b就可以表示為AX=(BN)??XB??=BXB+NXN=b ?XN?用可行基Ｂ的逆陣Ｂ-1左乘等式兩端，再通過移項可推得：XB=B-1b-B-1NXN

若令所有非基變量XN=0，則基變量XB=B-1b

?B?1b?由此可得初始的基本可行解X=??

?0?

5.最優性檢驗

?B?1b?假如已求得一個基本可行解X=?將這一基本可行解代入目?，?0??B?1b?-1標函數，可求得相應的目標函數值Z=CX=(CBCN)??=CBBb

?0?其中CB=(c1,c2,cm), CN=(cm+1,cm+2,cn)分別表示基變量和非基變量所對應的價值系數子向量。

要判定Z=CBB-1b是否已經達到最大值，只需將XB=B-1b-B-1NXN代入目標函數，使目標函數用非基變量表示，即：

?X?Z=CX=(CBCN)?B??XN?=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN

CBB-1b+σNXN?CBB-1b+(σm+1,σm+1,?xm+1???xm+2? σn)?????x?n?其中?N=CN-CBB-1N=(?m+1,?m+1,?n)稱為非基變量ＸN的檢驗向量，它的各個分量稱為檢驗數。若σN的每一個檢驗數均小于等于0，即σN≤0，那么現在的基本可行解就是最優解。

6.解的判別

定理1：最優解判別定理

對于線性規劃問題maxZ=CX,D=?X?Rn/AX=b,X?0?，若某個基本可行解所對應的檢驗向量?N=CN-CBB-1N?0，則這個基本可行解就是最優解。

定理2：無窮多最優解判別定理

?B?1b?若X=??是一個基本可行解，所對應的檢驗向量?0??N=CN-CBB-1N?0，其中存在一個檢驗數σm+k=0，則線性規劃問題有無窮多最優解。定理3：無最優解判別定理

?B?1b?若X=??是一個基本可行解，有一個檢驗數?m+k?0，但是?0?B-1Pm+k?0，則該線性規劃問題無最優解。

7.基本可行解的改進

如果現行的基本可行解Ｘ不是最優解，即在檢驗向量?N=CN-CBB-1N中存在正的檢驗數，則需在原基本可行解Ｘ的基礎上尋找一個新的基本可行解，并使目標函數值有所改善。具體做法是：

（1）先從檢驗數為正的非基變量中確定一個換入變量，使它從非基變量變成基變量（將它的值從零增至正值）。

（2）再從原來的基變量中確定一個換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。

?xm+1???xm+2?σn)?????x?n?由此可得一個新的基本可行解，由Z?CBB-1b+(σm+1,σm+1,可知，這樣的變換一定能使目標函數值有所增加。

8.換入變量的確定--最大增加原則

把基檢驗數大于0的非基變量定為入基變量。若有兩個以上的σj＞0，則選其中的σj最大者的非基變量為入基變量。

從最優解判別定理知道，當某個σj＞0時，非基變量xj變為基變量不取零值可以使目標函數值增大，故我們要選基檢驗數大于0的非基變量換到基變量中去（稱之為入基變量）。若有兩個以上的σj＞0，則為了使目標函數增加得更大些，一般選其中的σj最大者的非基變量為入基變量。

9.換出變量的確定--最小比值原則

把已確定的入基變量在各約束方程中的正的系數除以其所在約束方程中的常數項的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。

即若

?b?bxk?min?i|aik?0??l?aik?alk

則應令xl出基。其中bi是目前解的基變量取值，aik是進基變量xk所在列的各個系數分量，要求僅對正分量做比，（這由前述作法可知，若aik≤0，則對應的xi不會因xk的增加減值而成為出基變量）。

10.兩階段法

用大M法求解含人工變量的LP時，用手工計算不會碰到麻煩，但用電子計算機求解時，對M就只能在計算機內輸入一個機器最大字長的數字，這就可能造成一種計算上的誤差，為克服這個困難，對添加人工變量后的LP分兩個階段來計算，稱為兩階段法。

第一階段：不考慮原問題是否存在基可行解，給原LP加入人工變量，并構造僅含人工變量的目標函數Minw,然后用單純形法求解，若得w=0，說明原LP存在基可行解，可進行第二階段計算，否則，停止計算。

第二階段：將第一階段計算得到的最終單純形表除去人工變量，將目標函數行的系數換成原LP的目標函數，作為第二階段計算的初始表。然后按照前面的方法進行計算。

11.大M法

大M法首先將線性規劃問題化為標準型。如果約束方程組中包含有一個單位矩陣I，那么已經得到了一個初始可行基。否則在約束方程組的左邊加上若干個非負的人工變量，使人工變量對應的系數列向量與其它變量的系數列向量共同構成一個單位矩陣。以單位矩陣為初始基，即可求得一個初始的基本可行解。

為了求得原問題的初始基本可行解，必須盡快通過迭代過程把人工變量從基變量中替換出來成為非基變量。為此可以在目標函數中賦予人工變量一個絕對值很大的負系數-Ｍ。這樣只要基變量中還存在人工變量，目標函數就不可能實現極大化。

以后的計算與單純形表解法相同，Ｍ只需認定是一個很大的正數即可。假如在單純形最優表的基變量中還包含人工變量，則說明原問題無可行解。否則最優解中剔除人工變量的剩余部分即為原問題的初始基本可行解。

三． 結論 單純形法的創建標志著線性規劃的誕生。單純形法的創建統一了以往運輸問題和營養問題等的算法，同時推進線性規劃理論的發展。反過來，理論的發展也刺激算法的更新。線性規劃在這樣理論與算法相互促進和相互作用中發展。單純形法有效地提升了數學規劃的應用。很多重大理論誕生之初遭到人們的質疑和反對，但是線性規劃不一樣，一誕生就得到人們的青睞。這是因為，單純形算法的計算簡潔明了，計算結果精確有效。它求出的是最優解，超乎很多人的期望和想象力。因此被各個領域頻頻應用來提高工作效率、節

約能量和減少損失，使利潤最大化。線性規劃加速了數學規劃的普及。線性規劃是有史以來傳播速度最快的學科之一。誕生后很快就普及五大洲，并幾乎應用到所有的行業，故后興起的整數規劃、二次規劃和非線性規劃等倍受關注、期待和歡迎。從而，促進了數學規劃的普及。