Standard forms and basic feasible solutions

Our equality standard form minimizes $c^Tx$ subject to $Ax=b$ and $x\ge0$. A constraint $a^Tx\le b$ becomes $a^Tx+s=b$ with slack $s\ge0$; a greater-than inequality uses a nonnegative surplus subtracted instead. An unrestricted coordinate becomes $u-v$ with $u,v\ge0$, and a lower bound can be removed by a shift. A maximization objective can be negated. Keep an explicit reconstruction map back to original variables and retain any constant introduced into the objective by shifts.

Splitting a free variable is not a one-to-one correspondence: adding the same positive number to both parts leaves the original coordinate unchanged. Nevertheless every original feasible point has an extended feasible representative, and every extended feasible point reconstructs a valid original point with the same objective. This is the right equivalence for optimization. Added redundancy can affect rank and algorithm behavior, so a translation should be economical. Equalities that contradict one another must be detected rather than silently deleted when preparing a full-row-rank system.

Assume $A$ has $m$ independent rows and $n$ columns. A basis is a set of $m$ column indices whose square submatrix $B$ is invertible. Set every nonbasic coordinate to zero and solve $Bx_B=b$. This is a basic solution. It is a basic feasible solution only if every basic coordinate is nonnegative. No sign condition on $B^{-1}$ alone is required: the sign of the particular product with $b$ is what matters. Factorizations normally solve this system without explicitly storing an inverse.

For equality standard form with full row rank, the basic feasible solutions are exactly the extreme points. One direction follows because a feasible perturbation supported only on independent basic columns must vanish. For the other direction, the positive-coordinate columns of an extreme point must be independent; a dependence would permit small positive and negative perturbations while keeping nonnegativity. Extend those columns to a basis using full row rank. This argument also explains why a vertex has at most $m$ positive coordinates, even when many variables are available.

A basic feasible solution is degenerate when at least one basic coordinate equals zero. Several different bases may then describe the same vector, because a zero coordinate can exchange its role with another zero coordinate without moving the point. Do not identify the number of bases with the number of vertices. In a nondegenerate basic feasible solution all $m$ basic coordinates are positive, making its positive support determine the basis uniquely. Degeneracy is common when a model contains redundant-looking active restrictions or balances that force zero activity.

A feasible starting basis is not always visible. Phase I introduces artificial variables and minimizes their sum after arranging a convenient nonnegative right-hand side. A zero Phase I optimum establishes feasibility of the original equalities with nonnegative variables; a positive optimum certifies infeasibility, provided the auxiliary optimization was itself solved correctly. Artificial variables must then be removed or handled through redundant-row cleanup before optimizing the original objective. Numerical tolerances complicate the distinction between zero and a small positive residual, so report residuals and scaling rather than asserting exact feasibility from a rounded display.