# Simplex method: Optimality criterion

I have to show that if for a minimization problem, $z_j - c_j <0$, for all non basic variables then it has a unique optimal solution.

The proof says "If we start with a feasible point $x$ distinct from the current optimal solution $x^*$, then at least one of the non basic component xj is positive, otherwise if all non basic components are zero, x would not be distinct from x*."

Please explain how does the distinct nature ensure that one of the non basic component is positive.

• I don't like the proof your source states. I think it's assuming what is to be proved (see my comment on Robert Israel's answer). And I think showing the claim is trickier than it appears at first - perhaps depending on what you can assume. Would you give your source? – Mike Spivey Sep 10 '11 at 5:30
• @Tav: what are $z_j, c_j$? Could you give some more details? – Jiri Kriz Sep 10 '11 at 7:51
• @ Mike Spivey : My source Linear Programming and Network Flows: Bazaraa, Jarvis and Sherali .books.google.co.in/… – Tav Sep 10 '11 at 16:32
• @ Mike Spivey: If possible, please do take a look at this result in the google book link given above. – Tav Sep 10 '11 at 16:44

Now that I see the context in which the argument appears, it makes sense.

If ${\bf x}^*$ is an optimal basic feasible solution with objective value $z^*$, and ${\bf x}$ is any other feasible solution with objective value $z$, then (from derivations earlier in the text), they say

$$z^* - z = \sum_{j \in J} (z_j - c_j) x_j,$$

where $J$ is the index set for the variables that are nonbasic for the optimal solution $x^*$ and not necessarily for any other basic solution. For the rest of their argument (and the one below), $J$ retains this interpretation.

The other piece of information they are relying on (and this is the point I think Robert Israel is trying to make in his answer) is that the values of the basic variables for any basic solution are obtained by setting the nonbasic variables to $0$ and then solving the resulting set of linear equations. (The simplex tableau makes this automatic for you, so that you can just read the solutions off of the right-hand side.) The point is that if $x_j = 0$ for all $j \in J$ then ${\bf x}^*$ is the solution you get. Thus if we have a feasible solution ${\bf x}$, distinct from ${\bf x}^*$, then there is at least one $x_j$ for $j \in J$ that is nonzero.

Since all the variables have to be nonnegative in order for ${\bf x}$ to be feasible, $x_j > 0$. With the assumption that $z_j - c_j < 0$ the equation above forces $z^* < z$. Thus any other feasible solution has a strictly larger objective function value and so cannot be optimal.

• @ Mike Spivey: Thank you for the detailed and informative reply. I have a small doubt. I quote: "Thus if we have a feasible solution x, distinct from x* , then there is at least one xj that is nonzero." Does this hold in case of alternative optima, where the set of non basic variables may remain the identical. – Tav Sep 11 '11 at 10:48
• @Tav: Any time you change the current basic feasible solution, the set of nonbasic variables and the set of basic variables has to change. This is true regardless of whether the basic feasible solutions in question are optimal. So, yes, it holds in the case of alternative optima. – Mike Spivey Sep 11 '11 at 12:56
• @ Mike Spivey: Thanks ! I guess I was getting confused thinking of two interior optimal points on the line joining two optimal solutions. However, in this case, we need x* to be an extreme point (basic feasible solution) and x to be a feasible solution which can be an interior point (which is not basic). Then, of course, the set of basic and non basic variables will change. Many thanks for the explaining everything in detail. I appreciate your help :) – Tav Sep 11 '11 at 16:38

The essential point is that the simplex tableau describes all solutions, not just the basic solution, giving the basic variables and the objective as functions of the values of the nonbasic variables. The variables must be nonnegative in order for the solution to be feasible. The basic solution $x^*$ is the one where the nonbasic variables are all 0. If you have a solution that is not $x^*$, the nonbasic variables can't all be 0; if it is feasible, those nonbasic variables must all be nonnegative, so the ones that are not 0 will be positive.

• Thanks for your reply. i agree with your reply. But I am confused thinking of the case of an alternative optima, where non basic variables may remain zero for the new solution. The values of the basic variables change but non basic variables remains the same. – Tav Sep 10 '11 at 1:54
• Do you mean "optimal" instead of "basic" and "coefficients of the nonbasic variables" instead of "nonbasic variables" in the third sentence? Otherwise, what you say doesn't make sense. The nonbasic variables are always 0. That's part of what it means for a variable to be nonbasic. – Mike Spivey Sep 10 '11 at 3:46
• @ Robert Isarel: If possible, please do take a look at the result in the google book link given. books.google.co.in/… – Tav Sep 10 '11 at 16:47
• @Mike Spivey: "...then the coefficients of the nonbasic variables can't all be 0 unless the other solution is also optimal" . Please explain how this works. – Tav Sep 10 '11 at 16:49
• @Mike Spivey: Please take a look at the proof of the result in the link provided. – Tav Sep 10 '11 at 17:30