1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)
$\endgroup$
  • 1
    $\begingroup$ Perfect, doubt solved. Useful links. Thanks! $\endgroup$ – Gibbs Oct 28 '18 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.