人工變數

人工變數

人工變數(artificial variable)亦稱人造變數。求解線性規劃問題時人為加入的變數。

定義


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

人工變數的作用


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

新LP與原LP的最優解


1.若新LP的最優解中,人工變數都處在非基變數位置(即取零值)時,原LP有最優解。
2..若新LP的最優解中,包含有非零的人工變數,則原LP無可行解。
3..若新LP的最優解的基變數中,包含有人工變數,但該人工變數取值為零。這時可將某個非基變數引入基變數中來替換該人工變數,從而得到原LP的最優解。

求解新LP的兩種方法


1.大M法

將目標函數修改為
M是一個很大的正數。
手工計算時,只要認定M是一個很大的數。
計算機計算時,必須對M給出一個具體數值,通常取比原問題中最大數據高1~2個數量級的數值。並視求解情況對M作適當調節。
大M法的不足:
在用計算機求解時,不容易確定M的取值,且M過大容易引起計算誤差。

2.兩階段法

將新LP的求解過程分成兩階段
求解第一個LP
目的:通過解輔助LP來獲得原LP的初始解
原LP:
輔助LP:
原LP的可行域D:
輔助LP的可行域D':
用單純形法計算輔助LP的結果有三種可能情形:
1.最優值且人工變數皆為非基變數。從第一階段的最優解中去掉人工變數后,即為原LP的個基本可行解。作為原LP的一個初始基本可行解,再求原問題,從而進入第二階段。
2.最優值 ,說明至少有一個人工變數不為零。原LP無可行解。不再需要進入第二個階段計算。
3.最優值 且存在人工變數為基變數,但取值為零把某個非基變數與該人工變數進行調換。