Linear programming, artificial and slack variable, the difference

Question

I have a metaquestion: what is the difference between the slack and artificial variable in the standard LP problem?

Answer 1

If you apply the Simplex algorithm you need a basic feasible solution. Suppose you have the following problem:

$\texttt{Minimize} \ \ 4x+y$

$x+2y\leq 3$

$4x+3y\geq 6$

$3x+y=3$

$x,y\geq 0$

Firstly we only add a slack variable and a surplus variable.

$x+2y+s_1=3$

$4x+3y-s_2=6$

$3x+y=3$

$x,y,s_1,s_2\geq 0$

A basic feasible solution does not exist. To get a basic feasible solution we add an artificial variable for the $\geq-$constraint and the equality each.

$x+2y+s_1=3$

$4x+3y-s_2+a_2=6$

$3x+y+a_3=3$

$x,y,s_1,s_2, a_2, a_3\geq 0$

Here the BFS is $(x,y,s_1,s_2, a_2, a_3)=(0,0,3,0,6,3)$. Now you start with Phase I of the simplex algorithm.

For more detailed information see here.