3

Assume that the feasible set is not empty. My textbook says if a basic solution satisfy nonnegative condition, then it is a basic feasible solution. I am wondering whether there are some theorems that can assure a LPP has at least one basic feasible solution as long as the feasible set is not empty. Thanks!

王一川
  • 33
  • When you say a LP problem, that implies that all variables are non-negative, right? Also, can you have any kind of restrictions ($\ge$, $\le$, $=$) or does your book refer to some standard form LP problem? – Alejandro Nasif Salum Feb 29 '20 at 05:26
  • Yes in standard form. I may not have made it clear, sorry. Though a standard form contains constraints Ax=b and x≥0, in my book the basic solution is obtained only from the equation set Ax=b, by using Gaussian Elimination. But what if some variables in this basic solution are negative? I just don't know whether this will happen. Thanks. – 王一川 Feb 29 '20 at 06:18
  • An LPP with a non empty feasible set will not have a basic feasuble solution if the feasible region is unbounded. If not unbounded, for every feasible solution it is possible to find a basic feasible solution with a more optimal value. – reyna Feb 26 '24 at 19:11

1 Answers1

1

That is not true.

Consider $\min_{x,y} y$ subject to $x \ge 0$.

It has no BFS at all though it is feasible.

Edit:

  • We know that every non-empty polyhedron in standard form has at least one BFS.
Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Thanks for your answer! But I just find that there is a theorem called Fundamental Theorem of LPP, which says: If there exists a feasible solution, then there exists a basic feasible solution. Does this contradict with yours? Assume in standard form, I didn't say this, sorry. – 王一川 Feb 29 '20 at 08:34
  • My instance was not in the standard form, so there is no contradiction. If it is in standard form, then yes, there is at least one BFS as stated by the theorem. – Siong Thye Goh Feb 29 '20 at 08:49