1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Choose a better book! $\endgroup$ – NoChance Feb 22 at 20:27
  • 1
    $\begingroup$ Choose a better study subject! The simplex method and LP in general is a very algorithmic-ish area of maths in which concepts are more than often given without motivation. I remember taking a class in it and nobody really knew what was going on $\endgroup$ – Victor S. Feb 22 at 22:29
  • $\begingroup$ @NoChance But my simple question should have a simple answer, right? $\endgroup$ – user122424 Feb 23 at 18:24
  • $\begingroup$ @user122424, of course, your question is valid. It has been about 30 years since I did this, I wish I could help. There must be great books by now that explain this stuff in a more clear way. $\endgroup$ – NoChance Feb 23 at 20:32
  • $\begingroup$ @NoChance You don't need to ping OP by @user122424 since the post owner will be notified in any case. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 24 at 23:47
1
$\begingroup$

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