I want to solve the following LP problem by using the simplex method
$Maximize$ $ p = x + y +3z $
subject to
$$x + y +z \leq 15$$ $$x + 3y +2z \leq 45$$ $$2x- y -z \leq 15$$ $$2x + y +z = 12$$ $$4x + 4y +2z = 32$$
I was looking at this cool website to doublecheck my tableaus http://www.zweigmedia.com/RealWorld/simplex.html
and if you copy and paste the following
Maximize p = x + y +3z subject to
x + y +z <= 15
x + 3y +2z <= 45
2x- y -z <= 15
2x + y +z = 12
4x + 4y +2z= 32
you get :
=====================================================================
Optimal Solution: p = 28; x = 0, y = 4, z = 8
=====================================================================
which is what I get with linprog too.
However the pivotal operations I'm using are different, and I don't understand why.
In the website they always start from the the real variables of the problem for the selection of the pivot columns. Moreover they introduce two times artificial variables for equality constraints, in the form
$ 2x+y+z +s_1 = 15$
$4x+4y+2z+s_2 = 12 $
$2x+y+z - s_3 = 15$
$4x+4y+2z -s_4 = 12$
so when you evaluate the ratio between the RHS and the non-zero coefficients of the pivot column there is always ambiguity. I was simply looking at the most negative coefficient of the cost function to select the column and the minimum ration between RHS and coefficients of that column for the pivotal row.
So I think I'm missing a piece of information.
Why the artificial variables appear twice? and what is the pivotal selection / stop criteria when you also have equality constraints?
Thanks!
Edit: upon suggestion of @LinAlg I removed the extra artificial variables. Still, I don't get the right solution. I always come up with the initial tableau
x y z a_1 a_2 p RHS
2 1 1 1 0 0 12
4 4 2 0 1 0 32
-1 -1 -3 0 0 1 0
And by iterating on the column 3, row 4 I get the second and last Tableau
x y z a_1 a_2 p RHS
2 1 1 1 0 0 12
0 2 0 -2 1 0 8
5 2 0 3 0 1 36
which leads to
$x = 0, y = 0, z = 12$,
which clearly does not satify the second equality constraint
N:B: this is the relaxed version, where I discarded the inequalities.
Edit 2:
With inequality constraints too I get only two iterations.
Iter #0:
Tableau =
x y z s1 s2 s3 a1 a2 p RHS
1 1 1 1 0 0 0 0 0 15
1 3 2 0 1 0 0 0 0 45
2 -1 -1 0 0 1 0 0 0 15
2 1 1 0 0 0 1 0 0 12
4 4 2 0 0 0 0 1 0 32
-1 -1 -3 0 0 0 0 0 1 0
here the solution should be
$x = y = z = 0, s_1 = 15, s_2 = 45, s_3 = 15, a_1 = 12, a_2 = 32$
that is, already not feasible.
Iter #1 (the last one)
Tableau =
x y z s1 s2 s3 a1 a2 p RHS
-1 0 0 1 0 0 -1 0 0 3
-3 1 0 0 1 0 -2 0 0 21
4 0 0 0 0 1 1 0 0 27
2 1 1 0 0 0 1 0 0 12
0 2 0 0 0 0 -2 1 0 8
5 2 0 0 0 0 3 0 1 36
$ x = 0, y = 0, z = 12, s_1 = 3, s_2 = 21, s_3 = 27, a_1 = 0, a_2 = 8$
There is no reason why the artificial variables appear twice. Knowing the right hand side is positive you can use artificial slack variables and skip the artificial excess variables.
Ambiguity in the simplex method is unavoidable. It is the main reason anti-cycling methods have been developed (such as Bland's rule).