0
$\begingroup$

The original LPP: $f = 2x_1+3x_2 \rightarrow \max$. The constrains: \begin{align} -x_1-x_2 &\le -1 \\ x_1+x_2&\le 6\\ x_1+2x_2&\le 8\\ x_2&\le 3\\ x_1\ge 0, x_2&\ge 0\\ \end{align}

In order to solve the original LPP, the auxiliary problem must be solved, because there is one constraint with negative RHS. It is done using simplex algorithm. Here is the final tableau:

\begin{array}{rr:rrrrrrr:r} T^1_p& h & x_1 & x_2 & x_3 & u & x_4 & x_5 & x_6 & b \\ \hline x_1 & 0 & 1 & 1 & -1& 1 & 0 & 0 & 0&1\\ x_4 & 0 & 0 & 0 & 1& -1 & 1 & 0 & 0&5\\ x_5 & 0 & 0 & 1 & 1& -1 & 0 & 1 & 0&7\\ x_6 & 0 & 0 & 1 & 0& 0 & 0 & 0 & 1&3\\ \hdashline h & 1 & 0 & 0 & 0& 1 & 0 & 0 & 0&0\\ \end{array}

From there, it is stated, that we can solve the original LPP by rewriting the objective function $f$ as a linear combination of variables outside of the base ( in this case $x_2$ and $x_3$) of the auxiliary problems' last simplex tableau. The function is rewritten as : $f = 2x_3+x_2+2 \rightarrow max$. All the constraints for this problem can be derived from the last simplex tableau ($T^1_p)$. I don't understand how is the objective function obtained in this instance? The original objective function for this problem is $f:2x_1+3x_2\rightarrow \max$. Maybe someone knows how to derive the objective function from the tableau above?

$\endgroup$

1 Answer 1

1
$\begingroup$

I cannot relate the variables $x_3,\ldots,x6$, $h$ and $u$ to your original problem, so it would have helped to provide the starting tableau.

There are two ways of starting the second phase of two phase simplex. The first one is to keep the original objective as a separate row and resume from there.

The second one (and this is what you seem to be doing) is to take the original objective $f=2x_1+3x_2$ and express it using nonbasic variables. To eliminate $x_1$, we use $x_1+x_2-x_3+u=1$ from the final tableau ( $x_2$ is already nonbasic), so the objective is $f = 2(1-x_2+x_3-u)+3x_2 = 2 + x_2 + 2x_3 - 2u$. Just put this as the final row and continue. This method is demonstrated here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .