人工變量法

其公式如下：

→

，其中X_s是x_s鬆弛變量組成的向量。

正如上式所展示的那樣，所有約束是(≤)，並且有非負右端項（b_i≥0）的線性規劃，化為標準形式是在每個不等式的左端添加一個鬆弛變量，這時約束等式左端的係數矩陣就含有一個單位矩陣I，取這個單位矩陣為初始基，很容易得到一個初始基本可行解，從而建立單純形表。 ^[1] 

但包含(=)和或（≥）約束條件則不是如此。對於（≥）型約束來説，標準化時需添加剩餘變量，其係數為-1，而對(=)型約束，則沒有鬆弛變量，因此存在這兩種約束條件標準化後缺少足夠的鬆弛變量的係數組成（諸如

）十分直觀的單位矩陣，也即無法不做變換地找到基本可行解。這時候可以利用人工變量x(artificial variables)類似鬆弛變量添加到等式中去，讓它們在第一次迭代起着鬆弛變量的作用，並隨後用某次迭代中再把這些人工變量去掉。 ^[2] 

由於人工變量存在於初始基本可行解，而且人工變量是虛擬變量，它們在目標函數取極值時不應該存在數值，因此需要將它們從基變量中替換出來。若人工變量可以從基變量中替換出來，即基變量中不含有非零的人工變量，表示原問題有解；若人工變量不可以從基變量中替換出來，則表示原問題無可行解。 ^[3] 

加入人工變量後，一般可採用大M法或兩階段法處理。

如果是求極大值，即假定人工變量在目標函數中的係數為-M（M是任意大正數）；如果是求極小值，人工變量在目標函數中的係數為M。用單純形法對模型求解，如基變量中還存在M，就不能實現極值。

用計算機處理數據時，只能用很大的數代替M，可能造成錯誤，故多采用兩階段法。

第一階段：在原線性規劃問題中加入人工變量，構造模型。構造模型的目標函數為：

用單純形法對上述模型求解。若W=0，説明問題存在基本可行解，可以進行第二個階段；否則，原問題無可行解，停止運算。

第二階段：在第一階段的最終表中，（1）去掉人工變量，（2）將目標函數的係數換成原問題的目標函數係數，作為第二階段計算的初始表，用單純形法計算。 ^[4] 

1、無可行解：運算到檢驗數全負為止，若仍含有人工變量在基可行解未進入非基變量，則無可行解。

2、退化：若計算出的用於確定換出變量的

有兩個以上最小值，會造成下一次迭代中有一個或幾個基變量等於零。

為避免退化，雖任意換出變量目標函數值不變，但此時不同的基卻表示為同一頂點，其特例是永遠達不到最優解，需作如下處理蘭特Bland規則：

(1)當

中出現兩個以上最大值時，選下標最小的非基變量為換入變量；

(2)當

中出現兩個以上最小值時，選下標最小的基變量為換出變量。 ^[4] 

當存在(=)和或（≥）約束條件時使用該方法。

雖然標準化後可能存在單位矩陣可以不需要添加人工變量，但是它不具有代表性，而且人工變量法具有普適性，即使添加上了不妨礙結果，人工變量法比起尋找單位矩陣，無論在人工還是計算機計算時都有更高的可操作性。 ^[4]