2
$\begingroup$

I am trying to implement a simplex algorithm for solving LP task. I will post the question and my solution as well - what I need to know is whether my solution is correct, thanks in advance!

criterial function $min(x_1 - x_2 + 2x_3)$ subject to: $-3x_1 + x_2 + x_3 = 4$. $x_1 - x_2 + x_3 = 3$, $\forall x_i \geq 0$.

My simplex table (I added two slack variables in order to create a starting base):

 1  -1  2 0  0 | 0 .................. -3  1  1  1  0 | 4  1 -1  1  0  1 | 3 

I chose 1 (position 2,2) as pivot and made one step of algorithm:

-2  0  3  1  0 | 4 .................. -3  1  1  1  0 | 4 -2  0  2  1  1 | 7 

Now the first column in my table is negative -> this task cant be solve because X an open set (not sure if I can say it like this, dont know english notation that well) and minimum is -infinity.

Is this correct assumption or am I doint it wrong. Thanks...

1 Answers 1

3

You have a mistake at the very beginning. Since your constraints are equality constraints, you can't start with the initial solution $s_1 = 4$, $s_2 = 3$, where $s_1$ and $s_2$ are the slack variables. (This initial solution is encoded in your simplex table, as the columns for $s_1$ and $s_2$ are the ones that form the identity matrix.) The reason that $s_1 = 4$, $s_2 = 3$ doesn't work is that it's not a feasible solution! For instance, if $s_1 = 4$, then $-3x_1 + x_2 + x_3 = 0 \neq 4$.

Since the usual approach of setting the slack variables equal to the right-hand sides doesn't produce a feasible solution, you have to use a variant of the simplex method that incorporates first finding an initial feasible solution. Two of the standard approaches for doing this are the two-phase method and the Big-M method.