人工變數

定義

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

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

稱新變數

為人工變數.

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

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

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

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

將目標函式修改為

M是一個很大的正數。

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

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

大M法的不足：

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

將新LP的求解過程分成兩階段

求解第一個LP

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

原LP：

輔助LP：

原LP的可行域D：

輔助LP的可行域D'：

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

1.最優值

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

2.最優值

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

3.最優值

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