人工變數
人工變數
人工變數(artificial variable)亦稱人造變數。求解線性規劃問題時人為加入的變數。
人工變數(artificial variable)亦稱人造變數。求解線性規劃問題時人為加人的變數。用單純形法求解線性規劃問題，都是在具有初始可行基的條件下進行的，但約束方程組的係數矩陣A中所含的單位向量常常不足m個，此時可加人若干(至多m)個新變數，稱這些新變數為人工變數。如設(LP)為
人工變數
人工變數
稱新變數 為人工變數.
人工變數是為了湊成單純形表中的基變數而人工加入的單位向量，在目標函數中係數為-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.最優值且人工變數皆為非基變數。從第一階段的最優解中去掉人工變數后，即為原LP的個基本可行解。作為原LP的一個初始基本可行解，再求原問題，從而進入第二階段。
2.最優值 ,說明至少有一個人工變數不為零。原LP無可行解。不再需要進入第二個階段計算。
3.最優值 且存在人工變數為基變數，但取值為零把某個非基變數與該人工變數進行調換。