The simplex algorithm--example

193 Views Asked by At

Here on the page 30, why $(z_3,z_3)=1$: as written on that page 30:

minimize the sum of the artificial variables, starting from the BFS where the absolute value of the artificial variable for each constraint, or of the slack variable in case there is no artificial variable, is equal to that of the right handside.

But the r.h.s. of it is $2$ and not $1$. What does it precisely mean that highlighted text above?

1

There are 1 best solutions below

0
On BEST ANSWER

Let me explain what's happening before getting back to the text. In the standard form,

\begin{align} \max z= \quad& -6 x_1 - 3 x_2 \tag{$\star$}\label{z1} \\ \text{s.t.} \quad& x_1+x_2-z_1 = 1 \tag{1}\label{c1} \\ & 2x_1-x_2-z_2 = 1 \tag{2}\label{c2} \\ & 3x_2+z_3 = 2 \tag{3}\label{c3} \\ & x_1, x_2, z_1, z_2, z_3 \geq 0. \tag{FC}\label{fc} \end{align}

To find an "obvious BFS" (p.29), we include $z_3$ as a basic variable, but not $z_1,z_2$ since we can't have $z_1 = z_2 = -1$ due to \eqref{fc}.

To start the , we need a BFS, so we add artificial variables $y_1$ and $y_2$ to LHS of \eqref{c1} and \eqref{c2} respectively, so that we get an "obvious BFS" $(y_1,y_2,z_3) = (1,1,2)$.

\begin{align} \min w= \quad& y_1 + y_2 \tag{#}\label{w1} \\ \text{s.t.} \quad& x_1+x_2-z_1+y_1 = 1 \tag{1'}\label{c12} \\ & 2x_1-x_2-z_2+y_2 = 1 \tag{2'}\label{c22} \\ & 3x_2+z_3 = 2 \tag{3}\label{c32} \\ & x_1, x_2, z_1, z_2, z_3, y_1, y_2 \geq 0. \tag{FC'}\label{fc2} \end{align}

This allows us to write a simplex tableau, in which the basic variables are $y_1$, $y_2$ and $z_3$. This explains why in the simplex tableau, the $z_3$-row $z_3$-column is $1$. The RHS of the intial simplex tableau echoes the "obvious BFS", so the RHS of $z_3$-row is $2$.

Now, let's decode the quoted text.

  • minimize the sum of the artificial variables ($\min y_1 + y_2$)
  • starting from the BFS ($(y_1,y_2,z_3)$)
    • the absolute value of the artificial variable for each constraint ($|y_1|,|y_2|$ in \eqref{c12} & \eqref{c22} respectively), OR
    • of the slack variable in case there is no artificial variable (\eqref3 has no artificial variable, $z_3$ is a slack variable)
  • is equal to that of the right handside ($=(1,1,2)$)