# Exercises 3.10.6 and 3.10.7 in Linear and NonLinear Programming by Luenberger and Ye.

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?