1
$\begingroup$

Take a look at the following simplex tableau:

enter image description here

The pivot element is at (1,1) with a value of 2. Eliminating other rows I get the next tableau: enter image description here

That is the last step since there is no negative values in the last row, so it's time to extract the solution.

I read from many sources that in order to extract solutions for $X_i$ variables you need to compute $X_i=\frac{b_i}{x_i}$ ($X_i$ is a solution, $x_i$ is a value in the tableau) for variables that are basic, while solution for variables that are non-basic is zero. And often it is the case.

But that is not the case for my tableau. Here you can see that $x_2,s_1,s_3$ are basic variables. So solution for $x_1$ should be zero, right?

Even though the $x_1$ is non-basic variable, I can solve for it from the first equation (the first tableau row): $$ 4x_1+s_1+s_2=8 $$ Having slack variables as zeros, I get $x_1=2$. Substituting $x_1$ into the second equation (the second row in the tableau): $$ -x_1+2x_2+s_2=4 $$ I solve for $x_2$ and get $x_2=3$. Which is the correct result.

To confirm that, I solved the linear programming problem using graphical method and got the result $X=(2,3)$: enter image description here

So $x_1$ has a non zero solution even though it was non-basic variable. What then is the algorithm for extracting the solution from the tableau above? Having written a program, how should it read the solution from the tableau?

$\endgroup$
1
  • $\begingroup$ At the simplex method you usually add artificial variables if you have $\geq$ constraints. At the start the 3. constraint is $-x_1-x_2\leq -4$ The RHS has to be non-negative. Multiplying the constraint by (-1): $x_1+x_2\geq 4$ Now we add a surplus variable and a slack variable to obtain an equality: $x_1+x_2+s_3+a_1=4$. The initial solution is $(x_1,x_2,x_3,s_1,s_2,s_3,a_1)=(0,0,0,4,4,0,4)$ $\endgroup$ Commented May 29, 2023 at 19:40

1 Answer 1

Reset to default
1
$\begingroup$

When you pivot you divide the pivot row by the pivot entry, so the pivot entry becomes $1$. The nonbasic variables are indeed $0$ in the basic solution, the basic variables are $s_1=8$, $x_2=2$, $s_3=−2$.

However, this is not a feasible solution because negative values are not allowed. You would normally use a Phase I to make the basic solution feasible before starting Phase II to make it optimal. There are several ways of organizing this: consult your textbook.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.