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.