[Math] Optimality Criterion and the Simplex Method

linear algebralinear programmingoptimization

The optimality criterion states:

If the objective row of a tableau has zero
entries in the columns labeled by basic variables and no
negative entries in the columns labeled by nonbasic variables,
then the solution represented by the tableau is optimal.

How do we know this guarantees the solution is optimal?

Best Answer

Here's the key principle: The number in column $i$ in the objective row tells you how the current objective value changes by letting variable $i$ enter the basis.

Let's take an example. Suppose you're maximizing, and the objective row looks like 

1 4 0 0 2 0 | 12

This is encoding the objective equation $Z + 4x_1 + 0 x_2 + 0 x_3 + 2x_4 + 0 x_5 = 12$, or, alternatively, $Z = 12 - 4x_1 + 0 x_2 + 0 x_3 - 2x_4 + 0 x_5.$

Here the basic variables are $x_2, x_3,$ and $x_5$, and the nonbasics are $x_1$ and $x_4$.

Now, let's look at the two cases, given the key principle I mentioned above.

  • Any basic variable is already in the basis, so letting one of them enter the basis doesn't change the objective value. This is why there are zeros in the columns labeled by basic variables.
  • If none of the nonbasic variables have negative entries, then none of them have positive coefficients when you rewrite the objective equation in the second way I did. So letting any of them enter the basis means that you would not be increasing the value of the objective function. For example, letting $x_1$ enter the basis would entail a decrease of $4$ in $Z$ for every unit that $x_1$ decreases. Thus if all of the nonbasic variables have positive or zero entries, then you can't make the objective function larger by letting one of them enter the basis.

All together, then, if the objective row of a tableau has zero entries in the columns labeled by basic variables and no negative entries in the columns labeled by nonbasic variables, then there's no way to increase the value of the objective function by changing the basis. Since changing the basis is how you change the solution, there must not be any solutions better than the current one. Therefore, the solution represented by the tableau must be optimal.

Related Question