# Selection of Pivotal Elements in SIMPLEX method

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


$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$

• Can you show the first iteration in which the solution no longer satisfies the equality constraint, and the iteration right before it? Where are the inequality constraints in the initial tableau? – LinAlg Jul 3 '18 at 20:27
• Hi @LinAlg, I generated the two Tableaus I get with inequalities too. In the previous example I disabled the inequalities to see whether I got better results. – venom Jul 3 '18 at 20:39
• you have to drive the artificial variables out of the basis; two methods for that can be found in coral.ie.lehigh.edu/~ted/files/ie316/lectures/Lecture9.pdf – LinAlg Jul 3 '18 at 20:58
• If you have an LP, just throw it in a solver or optimization modeling tool. Forget the stupid tableaus. Does your professor think this is still 1975? – Mark L. Stone Jul 4 '18 at 0:38
• @venom See here how to manage equality constraints (and $\geq$-constraints). If you still have question, feel free to ask. – callculus Jul 4 '18 at 11:15