1

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?

GNUSupporter 8964民主女神 地下教會
  • 17,627
Jordy Nelson
  • 41

1 Answers1

0

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

GNUSupporter 8964民主女神 地下教會
  • 17,627