Basic solution (linear programming)

In linear programming, a discipline within applied mathematics, a basic solution is any solution of a linear programming problem satisfying certain specified technical conditions.

For a polyhedron $P$ and a vector $\mathbf {x} ^{*}\in {\mathcal {R}}^{n}$ , $\mathbf{x}^*$ is a basic solution if:

All the equality constraints defining $P$ are active at $\mathbf{x}^*$
Of all the constraints that are active at that vector, at least $n$ of them must be linearly independent. Note that this also means that at least $n$ constraints must be active at that vector.^[1]

A constraint is active for a particular solution $\mathbf {x}$ if it is satisfied at equality for that solution.

A basic solution that satisfies all the constraints defining $P$ or in other words, one that lies within $P$ is called a basic feasible solution.

References

↑ Bertsimas, Dimitris; Tsitsiklis, John N. (1997). Introduction to linear optimization. Belmont, Mass.: Athena Scientific. p. 50. ISBN 978-1-886529-19-9.

This article is issued from Wikipedia - version of the 5/30/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.