0

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?

glS
  • 6,818
Gibbs
  • 544

1 Answers1

2

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:

  1. Show that a polyhedron has at least one extreme point if and only if it does not contain a line (http://www-personal.umich.edu/~mepelman/teaching/IOE510/Handouts/510handoutF10-l7.pdf).
  2. Show that every nonempty bounded polyhedron has at least one extreme point.
  3. Show that extreme points and BFS are equivalent under the conditions mentioned above. (http://www.math.udel.edu/~angell/extr-basic.pdf)
Just_a_newbie
  • 116