可按現代電子電腦標準程式求解線性規劃模型的一般方法。分為代數形式的單純形法和表格形式的單純形法。前者提供基本演算法所依據的邏輯規則,適用於在電子電腦上進行求解運算;後者將變數和資料列成表格,適用於筆算。兩者在數學上是等價的。單純形法是由美國數學傢G.B.丹齊克(1914~ )於1947年提出來的,它與蘇聯數學傢Л.Β.坎托羅維奇(1912~ )於1938年提出的解乘數法相類似。

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

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

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

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

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

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

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