2

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

GNUSupporter 8964民主女神 地下教會
  • 17,627
user122424
  • 3,926

1 Answers1

3

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.

callculus42
  • 30,550
  • 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 04 '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$). – callculus42 Oct 04 '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 04 '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$ – callculus42 Oct 04 '18 at 22:52
  • OK. And the I row: why is it $3,0,-1,-1,0,0,0,2$? – user122424 Oct 05 '18 at 12:49
  • I would say that this is just the sum of rows $y_1$ and $y_2$ but $y_1$'st and $y_2$'nd columns are zeroes and not 1's as the mere sum would yield. – user122424 Oct 05 '18 at 16:59
  • @user122424 You´re absolutely on the right track. You have to sum the negative artificial variables. The first row: $x_1+x_2 -z_1+y_1=0\Rightarrow x_1+x_2 -z_1=-y_1$. Second row: $2x_1-x_2-z_2+y_2=0\Rightarrow 2x_1-x_2-z_2=-y_2$. And then $-y_1-y_2=3x_1-z_1-z_2$ – callculus42 Oct 05 '18 at 17:42
  • In your last equation there is still the term $-y_1-y_2$ but in the table in row I there are both 0.Why (it is a bit mind-boggling)? – user122424 Oct 09 '18 at 17:18
  • @user122424 You just insert the term $3x_1-z_1-z_2$ for $-y_1-y_2$. This (second) objective function you maximize. Just take it as a part of the simplex algorithm. – callculus42 Oct 09 '18 at 17:44
  • So now, we have 2 objective functions? $-6x_1-3x_3$ and $3x_1-z_1-z_2$?? – user122424 Feb 22 '19 at 15:10