Basic solution (linear programming)

src: i.ytimg.com

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 {x} ^{*}\in \mathbb {R} ^{n}}$, ${\displaystyle \mathbf {x} ^{*}}$ is a basic solution if:

1. All the equality constraints defining ${\displaystyle P}$ are active at ${\displaystyle \mathbf {x} ^{*}}$
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.

A constraint is active for a particular solution ${\displaystyle \mathbf {x} }$ 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. let Ax=b the system of the 'm' equation with 'n' unknown variables here the 'm' variables associated with the columns of above non singular matrix which may be different from 0 and called the basic variables.

Video Basic solution (linear programming)

References

Source of the article : Wikipedia