The question from this exercise is as follows:

If $r_j>0$ (where $r_j$ is the relative cost coefficient or the reduced cost coefficient) for each $j$ corresponding to a variable $x_j$ that isn't basic, show that the corresponding basic feasible solution is the unique optimal solution.

Now there is this theorem in the text that seems useful here; i.e:

Optimality Condition Theorem If for some basic feasible solution $r_j \ge 0 $ for all $j$ then that solution is optimal.

So from the above last theorem we can deduce that a basic feasible solution is optimal since for each $j$ we have $r_j>0$, now for the uniqueness part of this optimal solution.

Suppose we have two basic optimal feasible solutions, $Ax = b , x \ge 0 , Ay=b , y \ge 0$.

Now I assumed without loss of generality that $x \ge y$ (can I do it? it's an assumption that all the components of $x$ are greater than those of $y$'s, i.e $x\ge y \Leftrightarrow \forall i: x_i \ge y_i$), then we have: $A(x-y) = 0$ and $x-y \ge 0 $, thus optimal solution is obviously one for which $x-y=0$ and we are done with the uniqueness part; are we really? How can I justify this assumption that $x \ge y$?

I have another question from Exercise 3.10.7, I don't see how to solve it:

Show that a degenerate basic feasible solution may be optimal without satisfying $\forall j:\ r_j \ge 0$.

I don't see how to prove the last exercise; a degenerate basic solution is one which its basic variables are zero, but other than that I don't see how to prove this claim. What am I missing to show this claim?

Thanks in advance.


3.10.6 Since r_j > 0 for all non-basic variables, all optimal solutions must have the same basis. If there are two different optimal solutions x and y then A_B(x_B-y_B)=0 but x_B-y_b\not= 0, which implies that basis A_B is not a basis (rank-deficient), which is a contradiction.

3.10.7 min - 1*x_2 s.t. x_1 + x_3 =1 x_2 + x_3 =0 the current basic variables are x_1 and x_3, with solution values x_1=1, x_3=0, x_2=0, and it is optimal. However, r_2=-1.

  • $\begingroup$ Please consider using LaTeX markup to impove readability and also improve your chances for upvotes! $\endgroup$ – The Count Dec 7 '16 at 20:04

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.