目前，運用最廣的線性規劃方法就是著名的單純形方法。這種方法是G.B.Dantzig在1947年提出的。幾十年的實踐證明，單純形方法的確是一種使用方便、行之有效的重要算法。如今，它已經成為線性規劃的中心內容。 單純形法的基本思路是有選擇地取（而不是枚舉所有的）基本可行解，即是從可行域的一個頂點出發，沿著可行域的邊界移到另一個相鄰的頂點，要求新頂點的目標函數值不比原目標函數值差，如此迭代，直至找到最優解，或判定問題無界。 ### 線性規劃問題及其表示 線性規劃問題可表示為如下形式：  變量滿足約束條件(8.2)-(8.5)式的一組值稱為線性規劃問題的一個可行解。 所有可行解構成的集合稱為線性規劃問題的**可行區域**。 使目標函數取得極值的可行解稱為**最優解**。 在最優解處目標函數的值稱為**最優值**。 有些情況下可能不存在最優解。 通常有兩種情況： (1)根本沒有可行解，即給定的約束條件之間是相互排斥的，可行區域為空集； (2)目標函數沒有極值，也就是說在n 維空間中的某個方向上，目標函數值可以無限增大，而仍滿足約束條件，此時目標函數值無界。 例：  這個問題的解為 (x1,x2,x3,x4)=(0,3.5,4.5,1)最優值為16。 ### 線性規劃基本定理 約束條件(8.2)-(8.5)中n個約束以等號滿足的可行解稱為線性規劃問題的基本可行解。 若n>m，則基本可行解中至少有n?m個分量為0，也就是說，基本可行解中最多有m個分量非零。 *線性規劃基本定理：*如果線性規劃問題有最優解，則必有一基本可行最優解。 上述定理的重要意義在于，它把一個最優化問題轉化為一個組合問題，即在(8.2) -(8.5)式的m+n個約束條件中，確定最優解應滿足其中哪n個約束條件的問題。 由此可知，只要對各種不同的組合進行測試，并比較每種情況下的目標函數值，直到找到最優解。 Dantzig于1948年提出了線性規劃問題的單純形算法。 單純形算法的特點是： （1）只對約束條件的若干組合進行測試，測試的每一步都使目標函數的值增加； （2）一般經過不大于m或n次迭代就可求得最優解。 ### 約束標準型線性規劃問題的單純形算法 當線性規劃問題中沒有不等式約束(8.2)和(8.4)式，而只有等式約束(8.3)和變量非負約束(8.5)時，稱該線性規劃問題具有標準形式。 先考察一類更特殊的標準形式線性規劃問題。這一類線性規劃問題中，每一個等式約束中，至少有一個變量的系數為正，且這個變量只在該約束中出現。 在每一約束方程中選擇一個這樣的變量，并以它作為變量求解該約束方程。 這樣選出來的變量稱為左端變量或基本變量，其總數為m個。剩下的n-m個變量稱為右端變量或非基本變量。 這一類特殊的標準形式線性規劃問題稱為約束標準型線性規劃問題。 雖然約束標準型線性規劃問題非常特殊，但是對于理解線性規劃問題的單純形算法是非常重要的。 任意一個線性規劃問題可以轉換為約束標準型線性規劃問題。 例：   任何約束標準型線性規劃問題，只要將所有非基本變量都置為0，從約束方程式中解出滿足約束的基本變量的值，可求得一個基本可行解。 單純形算法的基本思想就是從一個基本可行解出發，進行一系列的基本可行解的變換。 每次變換將一個非基本變量與一個基本變量互調位置，且保持當前的線性規劃問題是一個與原問題完全等價的標準線性規劃問題。 基本可行解x=(7,0,0,12,0,10)。 ### 單純形法計算步驟如下：  #### **單純形算法的第1步：** 選出使目標函數增加的非基本變量作為**入基變量**。 查看單純形表的第1行（也稱之為z行）中標有非基本變量的各列中的值。 選出使目標函數增加的非基本變量作為入基變量。 z行中的正系數非基本變量都滿足要求。 在上面單純形表的z行中只有1列為正，即非基本變量相應的列，其值為3。 選取非基本變量x3作為入基變量。 #### **單純形算法的第2步：** 選取離基變量。 在單純形表中考察由第1步選出的入基變量所相應的列。 在一個基本變量變為負值之前，入基變量可以增到多大。 如果入基變量所在的列與基本變量所在行交叉處的表元素為負數，那么該元素將不受任何限制，相應的基本變量只會越變越大。 如果入基變量所在列的所有元素都是負值，則目標函數無界，已經得到了問題的無界解。 如果選出的列中有一個或多個元素為正數，要弄清是哪個數限制了入基變量值的增加。 受限的增加量可以用入基變量所在列的元素（稱為主元素）來除主元素所在行的“常數列”（最左邊的列）中元素而得到。所得到數值越小說明受到限制越多。 應該選取受到限制最多的基本變量作為離基變量，才能保證將入基變量與離基變量互調位置后，仍滿足約束條件。 上例中，惟一的一個值為正的z行元素是3，它所在列中有2個正元素，即4和3。 min{124,103}=4，應該選取x4為離基變量； 入基變量x3取值為3。 #### **單純形算法的第3步:** 轉軸變換。 轉軸變換的目的是將入基變量與離基變量互調位置。 給入基變量一個增值，使之成為基本變量； 修改離基變量，讓入基變量所在列中，離基變量所在行的元素值減為零，而使之成為非基本變量。 解離基變量所相應的方程，將入基變量x3用離基變量x4表示為x1?12x2+14x4=3 再將其代入其他基本變量和所在的行中消去x3， x1+52x2+14x4+2x5=10x6?52x2?34x4+8x5=1 代入目標函數得到z=9+12x2?34x4?2x5 形成新單純形表  #### **單純形算法的第4步：** 轉回并重復第1步，進一步改進目標函數值。 不斷重復上述過程，直到z行的所有非基本變量系數都變成負值為止。這表明目標函數不可能再增加了。 在上面的單純形表中，惟一的值為正的z行元素是非基本變量x2相應的列，其值為12。 因此，選取非基本變量x2作為入基變量。 它所在列中有惟一的正元素52，即基本變量x1相應行的元素。 因此，選取x1為離基變量。 再經步驟3的轉軸變換得到新單純形表。 新單純形表z行的所有非基本變量系數都變成負值，求解過程結束。 整個問題的解可以從最后一張單純形表的常數列中讀出。 目標函數的最大值為11； 最優解為：x?=(0,4,5,0,0,11)。  ### 例子  上述方法嚴格按照步驟，雖然思路清晰，但過程冗長，不方便操作。下面用表格形式的單純形方法來解上題。 在引進松弛變量，并將問題轉化成標準形式后，建立初始單純形表：   上述題目求解的是目標函數的min,下面再分享一道求解目標函數max的情況。兩種情況極其類似，只是在判別式選擇上的差異。