Has the subset of $\mathbb{R}$, defined as $P=\{x\in\mathbb{R}^n|Ax=b,x\ge0\}$, a basic feasible solution?
I think that no, because maybe P=$\emptyset$, so an empty polyhedron does not have basic solution. Am I wrong?
In the case $P\neq\emptyset$, then it's sure that P has a basic feasible solution?
Best Answer
By definition, a basic feasible solution (BFS from now on) must satisfy both $Ax=b$ and $x\ge0$. Therefore, if $P = \emptyset$, P has no BFS. However, by weakening the hypothesis one can show that $P$ will always have at a least one BFS.
If we let $A \in \mathbb{R}^{m \times n}$, rank $A = m$, $P = \{x \in \mathbb{R}^n|Ax=b, x\ge0\}$, $P \ne \emptyset$, then there exists at least one BFS.
One way to show this is to: