Why A Basic Solution Is A Vertex?

Question

A basic solution is a vector with $n$ components ($n=$ the number of variables), in which $m$ of them ($m=$ the number of functional constraints) are positive and the remaining ($n-m$) components are zero.

How does this implies that it must be a vertex point?

Answer 1

The idea is, the $m$ positive components identify the vertex point, which is the exact solution of those $m$ equations.

Answer 2

Assuming the LP is written in standard form (all functional constraints are $\le$, all decision variables are $\ge 0$), then there are a total of $m+n$ constraints ($m$ functional and $n$ non-negativity), and each constraint corresponds to a variable (either a slack variable or a "regular" variable).

A basic solution is the solution you obtain by:

• choosing $m$ of the constraints (out of the total of $m+n$ functional and non-negativity constraints)
• setting them to equalities
• forcing the $n-m$ variables that do not correspond to your $m$ constraints to 0, and
• solving the resulting system of equations for the $m$ variables that do correspond to your $m$ constraints.

Since you are solving a system with $m$ equations and $m$ unknowns, there is a single unique solution (assuming there's nothing funny going on like degeneracy), and that is your basic solution. Graphically, the basic solution is a vertex of the feasible region because it is the single point that is on the boundary of all $m$ of those constraints.