人工變量

人工變量(artificial variable)亦稱人造變量.求解線性規劃問題時人為加入的變量.用單純形法求解線性規劃問題，都是在具有初始可行基的條件下進行的，但約束方程組的係數矩陣A中所含的單位向量常常不足m個，此時可加入若干(至多m)個新變量，稱這些新變量為人工變量.如設(LP)為

引入新變量將(1)變為（2）

稱新變量

^[1]  為人工變量.

人工變量是為了湊成單純形表中的基變量而人工加入的單位向量，在目標函數中係數為-M，最後化簡結果中基變量要為0，否則無可行解。化簡單純形表就可以解決，若用對偶單純形表的話就直接能解單純形表，不用添加人工變量。

1.若新LP的最優解中,人工變量都處在非基變量位置(即取零值)時,原LP有最優解。

2..若新LP的最優解中,包含有非零的人工變量,則原LP無可行解。

3..若新LP的最優解的基變量中,包含有人工變量,但該人工變量取值為零。這時可將某個非基變量引入基變量中來替換該人工變量,從而得到原LP的最優解 ^[2]  。

將目標函數修改為

M是一個很大的正數。

手工計算時,只要認定M是一個很大的數。

計算機計算時,必須對M給出一個具體數值,通常取比原問題中最大數據高1~2個數量級的數值。並視求解情況對M作適當調節 ^[2]  。

大M法的不足：

在用計算機求解時，不容易確定M的取值，且M過大容易引起計算誤差。

將新LP的求解過程分成兩階段 ^[2] 

求解第一個LP

目的：通過解輔助LP來獲得原LP的初始解

原LP：

輔助LP：

原LP的可行域D：

輔助LP的可行域D'：

用單純形法計算輔助LP的結果有三種可能情形:

1.最優值

=0且人工變量皆為非基變量。從第一階段的最優解中去掉人工變量後,即為原LP的個基本可行解。作為原LP的一個初始基本可行解,再求原問題,從而進入第二階段。

2.最優值

≠0,説明至少有一個人工變量不為零。原LP無可行解。不再需要進入第二個階段計算。

3.最優值

=0且存在人工變量為基變量,但取值為零把某個非基變量與該人工變量進行調換。