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 ${\displaystyle P}$ and a vector ${\displaystyle {\mathbf{𝐱}}^{*}\in {\mathbb{ℝ}}^n}$, ${\displaystyle {\mathbf{𝐱}}^{*}}$ is a basic solution if:

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

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

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

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