I was given this on an assignment sheet, and am now using it to revise from…I cannot remember the issues that arise from degeneracy of basic feasible solutions…
Let $P$ =$\{x\in \mathbb{R}^n :Ax=b,x\geq 0\}$,where $A$ is a $d×n$ matrix of rank $d$. Suppose that all basic feasible solutions are nondegenerate. Let $x \in P$ have exactly $d$ positive entries. Show that $x$ is a basic feasible solution. Give an example to show that this is false with the nondegeneracy assumption removed.
I also struggled with this question…
Let $x$ be a basic feasible solution corresponding to a set $I \subset \{1,…,n\}$. Let $d$ be the $i^{th}$ basic direction for some $i \in I.$ Show that if there is $\theta > 0$ with $x+\theta d ≥ 0$ then $\{x+\theta d : \theta ≥ 0,x+\theta d ≥ 0\}$ is an edge of the feasible region. Do this by giving an explicit vector $c$ for which this set is $face_c(P)$, where $P$ is the feasible region of the linear program.
Best Answer
I'm not sure how accustomed you are to degeneracy, but at a high level, they are caused by multiple constraints (more than necessary) intersecting at the same vertex. In 2d, this is 3 constraints interesecting. This results in iterations of the simplex algorithm doing essentially nothing, pivoting different basic feasible solutions while remaining at the same vertex (and same objective value).
In a degenerate solution one of the basic variables is 0 along with the nonbasic variables, and switching them therefore results in the same vertex/solution.
With respect to your specific problem (without writing anything down or trying to prove it myself) I would assume relating the full rank of the matrix (no linear dependency) to the possibility of having degenerate solutions would result in your contradiction.