1
$\begingroup$

Consider this LP problem.

\begin{array}{cccll} \min & Z= & 8x & +10y+25z & \\ \text{s.t.} & & 2x & \phantom{+10y}+ 2z & \ge 60 \\ & & 2x & +4y+5z & \ge 70 \\ & & & \phantom{+}3y+z & \ge 27 \\ & & & x,y,z & \ge 0 \end{array}

I am confused as to why I have to do a revised simplex method here since the basic matrix has the identity form already.

But if I still apply the "rule" we learned in class to obtain the tableau, the tableau looks the same as our original tableau. Where am I doing wrong?

$\endgroup$
0
$\begingroup$

Add surplus variables $s_1,s_2,s_3$ into the LP.

\begin{array}{rrrrrll} \min & Z= & 8x & +10y & + 25z & & \\ \text{s.t.} & & 2x & & + 2z & - s_1 & = 60 \\ & & 2x & +4y & + 5z & - s_2 & = 70 \\ & & & 3y & + z & - s_3 & = 27 \end{array}

$$x,y,z,s_1,s_2,s_3 \ge 0$$

Initially, we have $s_1,s_2,s_3$ as basic variables. Multiplying the above three equations by $-1$ gives basic matrix $I_3$, but $s_1,s_2,s_3$ are all negative, so it's a basic infeasible solution. To find a BFS (basic feasible solution), you need the revised simplex method. In the intial simplex tableau below, we transform $\min Z$ to $\max Z = -8x - 10y - 25z$ without changing any constraints. (I note $x,y,z$ as $x_1,x_2,x_3$ respectively.)

\begin{array}{rrrrrrr|r} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \\ \hline s_1 & -2 & 0 & -2 & 1 & 0 & 0 & -60 \\ s_2 & -2 & -4 & -5 & 0 & 1 & 0 & -70 \\ s_3 & 0 & -3 & -1 & 0 & 0 & 1 & -27 \\ \hline & 8 & 10 & 25 & 0 & 0 & 0 & 0 \\ \end{array}

Using the two-phase method or the big-M method to find a basic feasible solution is much slower than the dual simplex method.

\begin{array}{rrrrrrr|r} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \\ \hline s_1 & -2 & 0 & -2 & 1 & 0 & 0 & -60 \\ s_2 & -2 & -4^* & -5 & 0 & 1 & 0 & -70 \\ s_3 & 0 & -3 & -1 & 0 & 0 & 1 & -27 \\ \hline & 8 & 10 & 25 & 0 & 0 & 0 & 0 \\ \hline\hline s_1 & -2^* & 0 & -2 & 1 & 0 & 0 & -60 \\ x_2 & 1/2 & 1 & 5/4 & 0 & -1/4 & 0 & 35/2 \\ s_3 & 3/2 & 0 & 11/4 & 0 & -3/4 & 1 & 51/2 \\ \hline & 3 & 0 & 25/2 & 0 & 5/2 & 0 & -175 \\ \hline\hline x_1 & 1 & 0 & 1 & -1/2 & 0 & 0 & 30 \\ x_2 & 0 & 1 & 3/4 & 1/4 & -1/4 & 0 & 5/2 \\ s_3 & 0 & 0 & 5/4 & 3/4 & -3/4^* & 1 & -39/2 \\ \hline & 0 & 0 & 19/2 & 3/2 & 5/2 & 0 & -265 \\ \hline\hline x_1 & 1 & 0 & 1 & -1/2 & 0 & 0 & 30 \\ x_2 & 0 & 1 & 1/3 & 0 & 0 & -1/3 & 9 \\ s_2 & 0 & 0 & -5/3 & -1 & 1 & -4/3 & 26 \\ \hline & 0 & 0 & 41/3 & 4 & 0 & 10/3 & -330 \end{array}

Therefore, the optimal solution is $(x^*,y^*,z^*)=(30,9,0)$.

$\endgroup$

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.