I'm trying to understand the simplex iteration of a problem with n
variables and m
technological constraints by following this text. I understand well the geometric interpretation of the iteration - moving between adjacent vertices.
However, I fail to understand the algebraic intuition. Now we're pivoting
between adjacent basic feasible solutions
= bfs
to the standard form of AX + IS = b
, X,S >= 0
:
- Why is it that the bfs must have
n
variables equal to 0? - Why should the rest of the variables form a
basis
? Isn't a basis a set of linearly independent vectors spanning a sub-space? What are we spanning here, we're just looking for a vertex, aren't we?
Thanks!
The BFS should correctly have
n-m
non-basic variables set to0
. Some of them
basic variables may themselves be0
but that is a degenerate solution.The basis is indeed the minimal set of linearly independent variables that span vector
b
. Note thatb
is anm-vector
. So,m
of the vectors corresponding to the variables can form aBFS
. The total number of variables isn
. The number of bases is therefore exponentialn Choose m
.Pivoting or moving from one vertex to another is nothing but substituting one of the non-basic variables (the associated column vector) into the basis and removing a pre-existing variable out of the basis. Thus, the basis will always have
m
(column) vectors.At any one point in time, given a partition of A into basic and nonbasic variables, such as
A = [B|N]
, thenBx = b
and hence thex
variables are the coefficients of the span ofB
that givesb
.It is a fundamental result of linear programming that every vertex of a bounded linearly constrained LP's feasible polyhedron corresponds to basic solution and vice versa. Reference: https://press.princeton.edu/titles/413.html