1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – user122424 Oct 4 '18 at 15:53
  • $\begingroup$ @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$). $\endgroup$ – callculus Oct 4 '18 at 16:44
  • $\begingroup$ here in your reference on page 30, how was cretaed the row signed II with $-6,-3,0,0,0,0,0,0$? $\endgroup$ – user122424 Oct 4 '18 at 19:32
  • $\begingroup$ @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$ $\endgroup$ – callculus Oct 4 '18 at 22:52
  • $\begingroup$ OK. And the I row: why is it $3,0,-1,-1,0,0,0,2$? $\endgroup$ – user122424 Oct 5 '18 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.