# Linear programming, artificial and slack variable, the difference

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

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.

• Where is in your 1st equation with r.h.s. $3$ $a_1$? Moreover, how do you know that BFS is $(0,0,3,0,6,3)$? – user122424 Oct 4 '18 at 15:53
• @user122424 For $\leq$-constraints you don´t need artificial variables, since $+s_1$ is $> 0$ and the RHS is always $>0$ as well. Thus $s_1$ is always part of the initial BFS ($>0$). – callculus Oct 4 '18 at 16:44
• here in your reference on page 30, how was cretaed the row signed II with $-6,-3,0,0,0,0,0,0$? – user122424 Oct 4 '18 at 19:32
• @user122424 This is just the objective function: $-6x_1-3x_2...$. The other coefficients are zero: $...+0z_1+0z_2+0z_3+0y_1+0y_2$ – callculus Oct 4 '18 at 22:52
• OK. And the I row: why is it $3,0,-1,-1,0,0,0,2$? – user122424 Oct 5 '18 at 12:49