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 𝐱*∈ℝn, 𝐱* is a basic solution if:

1. All the equality constraints defining P are active at 𝐱*
2. 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 𝐱 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

1. ↑ Bertsimas, Dimitris; Tsitsiklis, John N. (1997). Introduction to linear optimization. Belmont, Mass.: Athena Scientific. pp. 50. ISBN 978-1-886529-19-9. http://athenasc.com/linoptbook.html.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Basic solution (linear programming). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Basic_solution_(linear_programming)&oldid=293876"