2
$\begingroup$

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.

Thanks in advance.

  • 0
    @ Mike Spivey: If possible, please do take a look at this result in the google book link given above.2011-09-10

2 Answers 2

2

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.

  • 1
    @ 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 :)2011-09-11
2

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.

  • 0
    @Robert: Right. I originally parsed your last sentence as "If you have a [basic] solution that is not $x^*$, the [new set of] nonbasic variables [for the new solution] can't all be $0$..., which of course is nonsense. I figured out what you meant, though (see my answer). My apologies.2011-09-11