0
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – LinAlg Jul 3 '18 at 20:27
  • $\begingroup$ 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. $\endgroup$ – venom Jul 3 '18 at 20:39
  • 1
    $\begingroup$ 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 $\endgroup$ – LinAlg Jul 3 '18 at 20:58
  • 1
    $\begingroup$ 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? $\endgroup$ – Mark L. Stone Jul 4 '18 at 0:38
  • 1
    $\begingroup$ @venom See here how to manage equality constraints (and $\geq$-constraints). If you still have question, feel free to ask. $\endgroup$ – callculus Jul 4 '18 at 11:15
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Hi, Thanks! it seemed weird to me too. so you're saying I can simply remove those two rows and keep applying the standard logic of pivoting to remove the negative elements of the cost function? $\endgroup$ – venom Jul 3 '18 at 16:19
  • 1
    $\begingroup$ yes, their only purpose is to create a basic feasible starting point and you can do that with slack variables $\endgroup$ – LinAlg Jul 3 '18 at 16:23
  • $\begingroup$ Thanks a lot, I'll try out right now! $\endgroup$ – venom Jul 3 '18 at 17:13
  • $\begingroup$ mmh. still not working. I just removed the extra variables, and I only augmented with slack variables for inequalities and one artificial variable per equality constraint. When I perform the pivot in 3-4 iterations I have no negative coefficients in the cost function, but the solution does not satisfy equality constraints. $\endgroup$ – venom Jul 3 '18 at 19:43
  • $\begingroup$ Hi @LinAlg, I copied the tableau I got now, do you see anything weird that could give me an hint, please? $\endgroup$ – venom Jul 3 '18 at 20:11

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.