單純形法

一般線性規劃問題中當線性方程組的變數數大於方程個數，這時會有不定數量的解，而單純形法是求解線性規劃問題的通用方法。

具體步驟是，從線性方程組找出一個個的單純形，每一個單純形可以求得一組解，然後再判斷該解使目標函式值是增大還是變小了，決定下一步選擇的單純形。通過最佳化疊代，直到目標函式實現最大或最小值。

換而言之，單純形法就是秉承“保證每一次疊代比前一次更優”的基本思想：先找出一個基本可行解，對它進行鑑別，看是否是最優解；若不是，則按照一定法則轉換到另一改進後更優的基本可行解，再鑑別；若仍不是，則再轉換，按此重複進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解，也可用此法判別。

基本介紹

• 中文名：單純形法
• 外文名：Simplex algorithm
• 提出者：G.B.丹齊克(George Bernard Dantzig)
• 提出時間：1947年
• 套用學科：數學
• 適用領域範圍：運籌學線性規劃
• 適用領域範圍：數學 統計學

發展簡史

原單純形法

線性規劃問題是研究線上性約束條件下，求線性函式的極值問題。線性規劃是運籌學的一個重要分支， 也是最早形成的一個分支。線性規劃的最優性條件，又稱為Karush-Kuhn-Tucker(KKT)條件。不等式約束問題的必要和充分條件初見於卡羅需(William Karush)的博士論文，之後在一份由W.庫恩(Harold W. Kuhn)及塔克(Albert W. Tucker)撰寫的研討生論文出現後受到重視。

線性規劃的集大成者是G.B.丹齊克(George Bernard Dantzig)。1947 年，面對美國制定空軍軍事規劃時提出的問題，丹齊克首次提出了單純形法來解決這類極值問題的求解。單純形法是年由創建的對所有一般線性規劃問題的最早的可行算法。1953年，他又提出了改進單純形法。

但原單純形法不是很經濟的算法。許多數學家在隨後提出更有效率的算法，如改進單純形法、對偶單純形法等。

改進單純形法

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

對偶單純形法

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

下山單純形法

數學最佳化中，由George Dantzig發明的單純形法是線性規劃問題的數值求解的流行技術。有一個算法與此無關，但名稱類似，它是Nelder-Mead法或稱下山單純形法，由Nelder和Mead發現（1965年），這是用於最佳化多維無約束問題的一種數值方法，屬於更一般的搜尋算法的類別。

這二者都使用了單純形的概念，它是N維中的N+1個頂點的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，三維空間中的一個四面體，等等。

定理定義

標準形式

由於目標函式和約束條件內容和形式上的差別，線性規劃問題可以有多種表達式。因此，為了便於討論和制定統一的算法，在制定單純形法時，規定使用單純形法求解的線性規劃問題需要有一個標準形式，它有下面三個特徵：

(1) 標準形式目標函式統一為求極大值或極小值，但單純形法主要用來求解極大值；

(2) 所有約束條件（除非負條件外）都是等式，約束條件右端常數項b_i全為非負值；

(3) 所有變數的取值全為非負值。

下式為滿足上述特徵的線性規劃問題的標準形式：

其中，目標函式中的變數x_j(x₁,x₂,…x_n)稱為決策變數（控制變數），它的取值受m項資源的限制，它的係數稱為價值係數c_j。s.t.括弧下的內容是約束條件，用b_i(i=1,···,m)表示第i種資源的擁有量，用aij表示變數xj取值為1個單位時所消耗或含有的第i種資源的數量，通常稱a_ij為技術係數或工藝係數。

除非負條件外的n個約束條件所組成的n元方程組，若可解可求出n個變數xj的值。求出的n個變數所構成的列向量X=（x₁，···x_n）^T，若能再滿足非負條件(即決策變數滿足所有約束條件)，稱為線性規則問題的可行解。使得目標函式值z達到max最大的可行解即為最優解，求解線性規劃問題的目的就是要找出目標函式的最優解。

下圖為上式標準形式的線性規劃問題的展開型：

但是線性規劃問題往往並非標準形式的，如下圖所示。

因此，在用單純形法求解前，需要將目標函式轉化為標準形式。這個過程包括四個個部分的轉換：

（1） 目標函式的轉換：統一求極大值，若是求極小值，則可將目標函式乘以（-1），即化為。

（2）變數的轉換：對於已經是大於等於零的變數x_j≥0不做變化。

對於小於等於零的變數x_j，取負號令其變為大於等於的變數x_j'，若x_j≤0,則x_j'=-x_j,x_j'≥0；

若x_j取值無約束，可令新的兩個非負變數x_j'和x_j''相減，即x_j=x_j'-x_j''，其中x_j',x_j''≥0。

（3）約束條件的右端項常數的轉換：b_i<0時，只需將等式或不等式兩端同乘(-1)，則

（4） 約束條件的轉換：將所有不等式全部轉換為等式。

為此，對於“≤ ”型約束加入一個變數x_s，對於“≥ ”型約束則減去一個變數x_s。加到原約束條件中的變數，稱為剩餘變數或鬆弛變數，在實際問題中它表示未被充分利用的資源和超出資源數。由於此部分資源均未轉化為價值和利潤，所以在引進模型後這些變數在目標函式中的係數均為零_。

此外，為了構造出初始基變數，對於“ = ”型約束和“≥ ”型約束還需要加上人工變數。人工變數構成天然的初始基變數，其係數為1和其它行的人工變數的係數為0（故因此一般省略，不寫出）的特殊構造，組成最簡單的線性無關矩陣——單位矩陣。對於原約束條件中若已有線性無關的基向量，可以不需要再加入人工變數。但為避免出錯和算法的統一性，一般情況下面對“ = ”型約束和“≥ ”型約束不應省略人工變數。

按照以上的轉規則，將上述的列線性規劃問題化為標準形式，其結果如下：

矩陣形式

為了運算簡潔，單純性法的表示與定理的說明往往用矩陣形式說明。上述的標準形式的單純形法用矩形形式表示如下：

其中，C=(c₁,c₂,c_m)為行向量，X=(x₁,x₂,x_m)^T，b=(b₁,···,b_m)≥0均為列向量；

為m×n矩陣；假設A的秩為m，即假設不存在多餘的約束條件。

且只討論m<n的情形，因為方程數量比變數數目多，必定有唯一解，不需要單純形法來計算最優解。

向量形式

如果向量形式表示係數，那么即可將矩陣A分塊，A=(P₁,P₂,···,P_n)。可用向量將約束條件改寫為。

故標準形式的單純形法用向量形式表示如下：

約束方程組的係數矩陣A的任意一個m ×m階的非奇異（滿秩）子方陣B，其列向量線性無關，即方程中任一向量可由這些向量線性表出，故稱為線性規劃的一個基矩陣，簡稱為基。基矩陣B中的每一個列向量P_j=(j=1,...,m)稱為基向量，與基向量Pj對應的變數x_j稱為基變數。不失一般性，可假設：

除基變數以外的變數P_i=(i=m+1,...,n)稱為非基變數。並記非基矩陣為：

係數矩陣A可以寫成分塊形式A=(B,N)，將基變數的向量記為X_b=(x₁,x₂,···,x_m)^T，

非基變數組成的向量記為，向量X也可以寫成分塊形式

將此A和X的分塊形式帶入到約束方程組AX=b，得。由矩陣的乘法得。又因為B是非奇異矩陣，所以B^-1存在，將此式兩邊乘以B^-1，移項後得。可以把X_N看作一組自由變數（又稱獨立變數），給它們任意一組值，於是。這就是約束方程組的一個解。

特別地，令所有的非基變數為時，則，把約束方程組的這種特殊形式的唯一解，把約束方程組的這種特殊形式的解，稱為基解。或者說，因為滿秩，根據克萊姆法則或高斯消去法，由m個約束變數可解出m個基變數的唯一解。則方程組有唯一解X_B=（x₁,...,x_m)^T，將這個解加上非基變數取0的值是Ax=b的一個解：X=(x₁,x₂,...,x_m,0,...,0)^T，稱X為線性規劃問題的一個基解或基本解。而滿足標準形式的非負約束條件x≥0的基解稱為基本可行解，簡稱基可行解，對應於基可行解的基稱為可行基。

由此可見，有一個基就可以求出一個基解。基解的非零分量的個數不大於方程個數m，基B的列是從A的n列中選取線性無關的m列，其選法最多共有種，故基的個數或者說一個線性規劃問題的基本解的總數不超過個。

驗證推導

圖解法

從二維的線性規劃問題的圖解法簡單直觀，有助於了解線性規劃問題的基本原理。非負條件x₁、x₂≥0是指坐標軸的第一象限。在以x₁、x₂為坐標軸的直角左邊系，，每個約束條件都代表一個半平面。右圖中同時滿足x₁+x₂≤150，x₁+2x₂≤170，3x₂≤180和x₁、x₂≥0的約束的點，必然落在x1、x2坐標軸和這個三個半平面教程的區域見右圖的藍色框部分，藍色部分區域（包括邊界點的每一個點）都是這個問題的可行解，因此這個區域是線性規劃問題的解集合，稱它為可行域。

對於此例求解得到的最優解，但對一般線性規劃問題，最優解可能出現下列情況：

①有且僅有一個最優解。

②多重最優解，存在著無窮多個最優解，不存在有限最優解；當目標函式平行於非冗餘的緊約束，如果目標函式只有兩個變數，在坐標軸中目標函式一定平行於某一個約束條件。在實踐中，可選擇最優解是有用的，可從眾多解中做出選擇而不會損害最優值。如模型描述的是產品利潤問題，生產兩種產品比生產一種產品在市場競爭中更占有多樣性的優勢。

③無解或無可行解，其原因在模型的約束條件之間存在著矛盾，模型的構建是不正確的。假如所有的約束都是《類型的並具有非負的右端項，則這種情況永遠不會出現，因為鬆弛變數已經提供了一個可行解。對於其他類型的約束，使用人工變數，只有有一個人工變數在最優疊代中取值為正。

④無界解或無有限最優解，即沒有可行解或各項約束條件不阻止目標函式的值無限增大（或向負的方向無限增大）。這是因為解空間中至少有一個解是無界的，這意味著可以無限制的增加變數的值但不破壞任何一個約束，這種情況下，解空間和最有目標值都是無界的。

⑤退化解，按最小比值θ來確定換出基的變數時，有時出現存在兩個以上相同的最小比值，從而使下一個表的基可行解中出現一個或多個基變數等於零的退化解。退化解出現的原因是模型中存在多餘的約束，使多個基可行解對應同一定點。當存在退化解時，就有可能出現疊代計算的循環，儘管可能性極其微小。

定理證明

從圖解法可以直觀地看到可行域和最優解的幾何意義：所有可行解構成的集合是凸集，也可能為無界域；它們有有限個頂點，線性規劃問題的每個基可行解對應可行域的一個頂點；若線性規劃問有最優解，必在某頂點上得到。這個結論是通過凸集的定義和三個定理的證明所得出的，下面是詳細的證明過程。

凸集及其頂點

1.凸集

凸集的概念為，集合K中任意兩個點，其連線上的所有點都是集合K中的點，稱集合K是凸集。雖然對簡單的集合形體可以直觀地判斷其凹凸性，但在高維空間，只能給出點集的解析表達式，因此只能用數學解析式判斷。設K是n維歐式空間的一點集，若任意兩點X₁∈K，X₂∈K，其連線可表示為 則稱K為凸集。

凸集

2.凸組合

設X₁,X₂,···,X_k是歐式空間Eⁿ中的k個點。若存在μ₁,μ₂,μ_k，且0≤μ_i≤1，i=1,2,···,k； ，使X=μ₁X₁+μ₂X₂+···+μ_kX_k，則稱X為X₁,X₂,···,X_k的凸組合。

3.頂點

凸集K中滿足下述條件的點X稱為頂點：如果K中不存在任何兩個不同的點X₁，X₂，使X成為這兩個點連線上的一個點。或者這樣敘述：對於任何X₁∈K，X₂∈K，不存在 ，則稱X是凸集K的頂點。

定理一

若線性規劃問題存在可行解，則問題的可行域 是凸集。

證：為了證明滿足線性規劃約束條件 的所有點組成的幾何圖形D是凸集。只要證明D內任意兩點X₁，X₂的連線上的點也必定在D內即可，下面給予證明。

設X₁=(x₁₁,x₁₂,...,x_1n)^T,X₂=(x₂₁,x₂₂,...,x_2n)^T為D內任意兩點，即X₁∈D，X₂∈D，且X₁≠X₂。

將X₁，X₂帶入約束條件AX=b，則有

由凸集的定義，X₁,X₂連線上任意一點可以表示為：X=aX₁+(1-a)X₂(0<a<1)

兩邊同乘A：AX=A[aX₁+(1-a)X₂]，將此式用向量展開式表示：

所以集合中任何兩點連線上的點滿足約束條件，即均在集合內，即X=aX₁+(1-a)X₂∈D，所以可行域是凸集。

引理一

線性規劃問題的可行解X=(x₁,x₂,...,x_n)^T為基可行解的充要條件的是X的正分量所對應的係數列向量是線性獨立的。

證 （1）必要性：由於基解的列向量是線性獨立的，並且可行解的分量即是正分量。

（2）充分性：若向量P₁,P₂,···,P_k線性獨立，則必定k≤m；當k=m時，它們恰構成一個基，從而X=(x₁,x₂,...,x_k,0...0)為相應的基可行解。當k<m時，由於矩陣A的秩R(A)=m，即極大無關組的向量為m，則一定可以從其餘的列向量中取出m-k個與P₁,P₂,···,P_k構成最大的的獨立向量組（基），其對應的解恰為X，所以根據定義它是基可行解。

定理二

（極點與基可行解的等價性定理）線性規劃問題基可行解X對應於線性規劃問題可行域（凸集）D的頂點。

證：本定理需要證明：X是可行域頂點⇔X是基可行解，這一定理可由反證法證明。即證明：X不是可行域的頂點⇔X不是基可行解。

不失一般性，假設基可行解X的前m個分量為正。故 。

分兩步來討論，分別用反證法。

（1）若X不是基可行解，則它一定不是可行域D的頂點。

根據引理1，若X不是基可行解，則其正分量所對應的係數列向量P₁,P₂,···,P_m線性相關，即存在一組不全為令的數α_i,i=1,2,···,m 使得α₁P₁+α₂P₂+···+α_mP_m=0。

用一個μ>0的數乘以上式，再分別與 相加或相減，分別得到下列兩式：

(x₁-μα₁)P₁+(x₂-μα₂)P₁+···+(x_m-μα_m)P_m=b

(x₁+μα₁)P₁+(x₂-μα₂)P₁+···+(x_m-μα_m)P_m=b

現取X₁=[(x₁-μα₁),(x₂-μα₂),···,(x_m-μα_m),0,···0]

X₂=[(x₁+μα₁),(x₂-+μα₂),···,(x_m-+μα_m),0,···0]

可以得出X=X₁/2+X₂/2，即X是X1，X2連線的中點。

另一方面，當μ充分小時，可保證x_i+μα_i≥0,i=1,2,···,m

即X₁，X₂是可行解。這證明了X不是可行域D的頂點。

（2）若X表示可行域D的頂點，則它一定不是基可行解。

因為X=(x₁,x₂,...,x_m,0...0)不是可行域D的頂點，故在可行域D中找到不同的兩點Y和Z，使 ，或可寫成 。

因為Y和Z是可行域的兩點，應滿足：

將這兩式相減，即得

因Y≠Z，所以上式係數y_i-z_i不全為零，故向量組P1,P2,···,Pm線性相關，與假設矛盾。即X不是基可行解。

推論：設 的秩為m，在非退化情況下，則X是S的頂點的充要條件是X的非0元為m個。

定理三

設線性規劃問題有解，一定存在一個基可行解是最優解，由定理二可知必在可行域D={X|AX=b,X≥0}的某個頂點上取得最優值。這個定理分為三個部分。

定理3.1若一個問題(LP)有可行解，則它必有基可行解。

證 設X是線性規劃問題的一個可行解，如果其正分量所對應的列向量P₁,P₂,···,P_k線性無關，由引理一可知，X是一個基可行解，定理成立。否則，需證明：從X出發，必可找到LP的一個基可行解。

因為P1,P2,···,Pk線性相關，即存在不全為零的數δ₁,δ₂,···,δ_k，使得 。

則X在可行域內必能找到兩點，X₁=X+εб,X₂=X-εб ，其中δ=(δ₁,δ₂,···,δ_k,0,···,0)^T

其中有δ_i≠0，取 ，且必有x_j±εб≥0(j=1,2,···,n) ，即X₁≥0，X₂≥0。

又因為 ，所以 ，

故有AX₁=b，AX₂=b，所以X₁，X₂是LP的兩個可行解。

再由ε的取法可知，x_j±εб≥0中，至少有一個等於零，於是所做的可行解X₁和X₂中，它的非零分量至少比X的減少1。如果這些非零分量所對應的列向量線性無關，則X₁和X₂為基可行解，定理成立。

否則，又可以X₁或X₂出發，重複上述步驟，再構造一個新的可行解X₃或X₄，使它的非零分量的個數繼續減少。這樣經過有限次重複之後，比可找到一個可行解X_l或X_(l+1)，使它的非零分量對應的列向量線性無關。因為在最壞的情況下，只有一個非零分量時，對應的只有一個非零的列向量，它必然是線性無關的，故X_l或X_(l+1)必為基可行解。

定理3.2若線性規劃問題有最優解，一定存在一個基可行解是最優解。

證 設X是線性規劃的一個最優解，Z=CX是目標函式的最大值。若X不是基可行解，由定理二可知，X不是頂點，一定能在通過X的直線上的另外兩個點，將這兩個點帶入目標函式有

C(X+εδ)=CX+Cεδ ， C(X-εδ)=CX-Cεδ

因CX為目標函式的最大值，故有CX≥CX+Cεδ ，CX≥CX-Cεδ

Cεδ不可能為正數或負數，因此Cεδ=0，即有C(X+εδ)=CX=C(X-εδ)。

如果(X+εδ)或(X-εδ)仍不是最優解，按上面方法繼續做下去，則根據定理3.1的證明方法，它的非零分量的個數比X的減少1。在最壞的情況下，只有一個非零分量時，對應的只有一個非零的列向量，它必然是線性無關的。所以一定可以找到一個基可行解，其目標函式值等於CX，問題得證。

根據定理二和定理三，可以得出如下結論：

推論一：若問題的可行域有界，則此問題的最優解一定可以在其可行域D的頂點上達到。

定理3.3設問題(LP)在多個頂點X₁,X₂,···,X_k出達到最優，則任意一點 也是(LP)的最優解。

證 設目標函式的最優值為Z，則有假設有CX_i=Z

由上式可知，有

故任意一點X也是LP的最優解。X稱為X₁,X₂,···,X_k的凸組合。

這定理說明若問題有兩個或多於兩個的最優解，則它就有無窮多個最優解。另外，若問題的可行域無界，則可能無有限解，也可能有有限解。若有有限解，則必可在可行域的某個頂點上達到。

疊代原理

由上述的定理3可知，如果線性問題存在最優解，一定有一個基可行解是有最優解。因此單純形法疊代的基本思路是：先找出一個基可行解，判斷其是否為最優解。如為否，則轉換到相鄰的基可行解，並使目標函式值不斷增大，一直找到最優解為止。

初始可行基確定

對於標準型線性規劃問題

在約束條件的變數的係數矩陣總會存在一個單位矩陣作為初始可行基

這是因為當線性規劃的約束條件均為≤號，利用化為標準型的方法，在每個約束條件的左端加上一個鬆弛變數。經過整理，重新對x_j和a_ij(i=1,2,···,m;j=1,2,···,n)進行編號，可得到以下方程組。

移項可得

其鬆弛變數x₁.···,x_m的係數矩陣顯然為m×m單位矩陣。 令x_m+1=x_m+2=···=x_n=0，可得x_i=b_i(i=1,2,···m)，又因為b_i≥0，所以得到一個初始基可行解。

對約束條件為≥或=的情況，為便於初始基可行解，可以構造人工基，人為產生一個單位矩陣，可參見人工變數法。

最優性檢驗

對線性規劃問題的求解結果可能出現唯一最優解、無窮多最優解、無界解和無可行解四種情況，為此需要建立對解的判別標準。一般情況下，經過疊代之後變成

一般式為

將其帶入目標函式 ，整理後得

令 ，於是

再令σ_j=c_j-z_j(j=m+1,···,n)，則

因此可以將線性規劃問題的標準形式化為典式：

其中，稱σ_j為檢驗數或判別數，它是典式的目標函式的非基變數x_j(j=m+1,···,n)的係數，它又表示當某個非基變數的值改變1個單位，所引起的目標函式值的該變數，因此又稱為相對價值係數。

1.最優解的判別定理

設X⁰=(b₁',b₂',···b_m',0,···,0)^T為對應基B的一個基可行解，且對於一切j=m+1,···,n，有σ_j≤0，或用向量表示σ=(0,···,0,σ_m+1,σ_m+2,···,σ_n)≤0，則X₀為最優解。

證：設X為線性規劃的任一可行解，X≥0,σ≤0,σX≤0，從而最大值z*=CX⁰=z⁰≥z⁰+σX=CX=z。

因為x_j為正數，當σ_j≤0，當疊代恰好會使得z會變小（無法更優），其解即為最優。

因此σ_j≤0稱為最優性條件，它是判別當前接是否為最優解的標準。檢驗數還可以寫成矩陣形式σ=(σ_B,σ_N)=C-C_BB^-1A=(0,C_N-C_BB^-1N)≤0，其中σ_B=0為基變數對應的檢驗數向量；σ_N=C_N-C_BB^-1N為非基變數對應的檢驗數向量。這說明基變數的檢驗數必為0，並且非基變數的檢驗數都為負數時，才有唯一最優解。

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

若X⁰=(b₁',b₂',···b_m',0,···,0)^T為一個基可行解，對於一切j=m+1,···,n，又存在某個非基變數的檢驗數σ_m+k=0，則線性規劃問題有無窮多最優解。

證 只需將非基變數x_m+1換入基變數中_，找到一個新基可行解X¹。σ_m+k=0，z=z₀，故X也是最優解。故X也是最優解。根據定理3.3可知X⁰和X¹連線上所有點都是最優解，故有無窮多最優解。

3.基可行解的改進定理

若初始可行解X不是最優解時，需要找一個新的可行基。具體做法是從原可行解基換一個列向量（當然要保證線性獨立），得到一個新的可行基，這稱為基變換。為了換基，先要確定換入變數，再確定換出變數，讓它們相應的係數向量進行對換，就得到一個新的基可行解。

定理內容：X⁰=(b₁',b₂',···b_m',0,···,0)^T對應於基B的一個基可行解，若滿足下列條件：

(1)有某個非基變數x_k的檢驗數σ_k>0(m+1≤k≤n)；

(2)a_ik(i=1,2,···,m)不全小於或等於零，即至少有一個a_ik>0(1≤i≤m)；

(3)b'_i>0(i=1,2,···,m)，即X⁰為非退化的基可行解。則從X⁰出發，一定能找到一個新的基可行解X¹，使得CX¹>CX⁰。

證 我們採用一種構造性的證明方法，即將X₁具體地找出來，為此，我們作換基運算：

由 ，當某些σ_j>0時，增加則目標函式還可以增大，這時要將某個非基變數xj喚到基變數中去，稱為換入變數。

3.無界解判別定理

若X=(b₁',b₂',···b_m',0,···,0)^T為一基可行解，有一個σ_m+k>0，並且對i=1,2,···,m，都有a‘_i,m+k≤0，那么該線性規劃問題具有無界解（或稱無最優解）。

證 構造一個新的解X，它的分量為x_i=b‘_i-λα‘_i,m+k(λ>0)

x_m+k=λ

x_j=0,j=m+1,···,n

因a‘_i,m+k≤0，所以對任意的λ>0都是可行解，把x帶入目標函式內得z=z₀+λσ_m+k。

因σ_m+k>0，λ→+∞，則z→+∞，故該問題目標函式無界。

單純形表

為檢驗一個基可行解是否最優，需要將其目標函式值與相鄰基可行解的目標函式進行比較。為了書寫規範和便於計算，對單純形法的計算設計了一個種專門表格，稱為單純形表。疊代計算找出一個新的基可行解，就畫一張單純形表。含初始基可行解的單純形表，稱為初始單純形表，含最優解的單純形表，稱為最終單純形表。下圖即為單純形表的一般格式。

Cj→	X	...	c1	...	cm	...	cj	...	cn
CB	基	b	x1	...	xm	...	xj	...	xn
c1	x1	b1	1	...	0	...	a1j	...	a1n
c2	x2	b2	0	...	0	...	a2j	...	a2n
...	...	...	...		...		...		...
cm	xm	bm	0	...	1	...	amj	...	amn
cj-zj			0	...	0	...		...

單純形表結構為：表的第2行列出所有基變數，表的第1-3列分別列出基可行解中基變數係數、基變數和每個約束的取值（右端值）。表的第4-6列寫在基變數下面是單位矩陣，非基變數x_j下面數字是該變數係數向量P_j表示為基向量線性組合時的係數，即化出單位矩陣後的係數。因為P₁,...,P_m是單位向量，故有：

最後一行(c_j-z_j)寫的是檢驗數σ_j。例如求第j列的檢驗數，只需將變數x_j的係數即數字(a_1j,...,a_mj)與C_B中同行的數字(c₁,...,c_m)分別相乘加和，再用它上端的c_j值減去乘積加和，即可得出：

方法步驟

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

①把線性規劃問題的約束方程組表達成典範型方程組，典範型方程組要實現變數轉換（所有變數為非負）、目標轉換（統一為求極大值，若求極小值可乘以(-1)）、約束轉換（由不等式轉化為等式）。然後，找出基本可行解作為初始基可行解。列出初始單純形表。

②若基本可行解不存在，即約束條件有矛盾，則問題無解。

③若基本可行解存在，從初始基可行解作為起點，根據最優性條件和可行性條件，引入非基變數取代某一基變數，找出目標函式值更優的另一基本可行解。

④按步驟3進行疊代，直到對應檢驗數滿足最優性條件（這時目標函式值不能再改善），即得到問題的最優解。

⑤若疊代過程中發現問題的目標函式值無界，則終止疊代。

圖示表示如下：

單純形法的一般求解步驟

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

套用例子

例1：求解下述線性規劃問題，只有唯一最優解的情況。

第一步：將一般形式轉換為標準形式：

例題1

由於都為"≤"型，所以在三個約束式分別加上三個剩餘變數x₃、x₄、x₅，將不等式轉化為等式。

第二步：列出初始單純形表。

下圖為一張完整的單純形表，不同的教材畫法有所差異，例如可以省略對b值和θ的部分單獨進行列式計算。這裡用最為全面的畫法進行講解。其中紅色部分為約束條件原本的常數值，最後一行為檢驗數。中間的數值為各個變數的原始數值，其中基變數的係數，即藍色數值(3×3)恰好構成一個單位矩陣，其檢驗數也恰好都為0。

例一步驟1

第三步：更換基變數

最後一行中x₁、x₂檢驗數為不為負數或零，因此尚未取得最優值。需要去找另一個基本可行解，即將非基變數換入基變數中。如此循環下去，直到找到最優解為止。

通過基變數換入換出的操作需要有兩個原則。第一，如果有多個檢驗數為正，那么從最大的一個開始調整，因為變動檢驗數大的變數對於z值的變化越大，這道題目中x₂的這一列的檢驗數最大，因此選擇x₂入基變數。但是為了保證係數的非負，b值與係數的比值θ即最右邊的一行，應該選擇數值最小的一個，因此這裡選擇4(<5)，因此x₄為出基變數。由3（最大檢驗數σ_j）和3（最小比值θ）確定的數值4稱為主元，進行變換的方法稱為高斯消元法，即用行的初等變換進行列消元。

例一步驟2

第四步：繼續疊代。

消元後x₁、x₃、x₅變成基變數，同時係數和b值也發生了相應的變化，計算出檢驗數。發現x₂的檢驗數仍為正數，將x₂作為入基變數。通過θ最小法則，確定x5為出基變數。繼續畫出消元後的單純形表。

例一步驟3

第五步：確定所有檢驗數σ_j≤0，計算最優值Z*。

例一步驟4

算法效率

在採用Bland's法則選擇用於轉軸操作的d和e（相同值的情況下取字典序最小）之後，可以證明單純形法一定能夠在有限步之後終止，但是最壞情況算法的時間複雜度為指數級別的，而且可以構造出讓單純形法的時間複雜度達到指數級別的具體實例。不過實踐證明在絕大多數情況下單純形法的效率非常令人滿意。

單純形法的最壞時間複雜度為指數級別，並不意味著線性規劃不存在多項式級別的算法。橢球算法和內點算法均為解決線性規劃的多項式時間算法。

定理意義

如今線性規劃的理論與算法均非常成熟，在實際問題和生產生活中的套用非常廣泛；線性規劃問題的誕生標誌著一個新的套用數學分支———數學規劃時代的到來。過去的 60 年中，數學規劃已經成為一門成熟的學科。其理論與方法被套用到經濟、 金融、 軍事等各個領域。數學規劃領域內，其他重要分支的很多問題是線上性規劃理論與算法的基礎上建立起來的， 同時也是利用線性規劃的理論來解決和處理的。由此可見， 線性規劃問題在整個數學規劃和套用數學領域中占有重要地位。因此， 研究單純形法的產生與發展對於認識整個數學規劃的發展有重大意義。