Basic solution (linear programming) explained

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

P and a vector x ^{*} \in R ^{n} , x ^{*} is a basic solution if:

1. All the equality constraints defining

P are active at x ^{*}

1. 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

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.

Notes and References

1. Book: Bertsimas. Dimitris. Tsitsiklis. John N.. Introduction to linear optimization. 1997. Athena Scientific. Belmont, Mass.. 978-1-886529-19-9. 50.