A **linear program** is a problem of the form

minimize *c'x*

subject to *Ax* ≥ *r* and *x* ≥ 0

where *c*, *r*, and *x* are (column) vectors, *A*
is a matrix, and and *c'* is the transpose of *c*, so *c'x*
is the dot product of *c* and *x*. (This is the *canonical*
form, see Equation 2.2 in the text. If the matrix constraint is given as an
equality, it is said to be in *standard* form as in Equation 2.3.)

**Assumption 2.1**: The matrix *A* is of rank *m*,
the number of rows in *A.*

**Assumption 2.2**: The set *F* of feasible points is nonempty.

**Assumption 2.3**: The set of values of feasible solutions is
nonempty (this will later shown to be an unnecessary assumption).

**Definition 2.4**: A feasible solution with nonzero entries corresponding
to a set of columns of *A* that form a basis for the space spanned by
the columns of *A* is a* basic feasible solution* (bfs).

**Lemma 2.1**: The set of solutions is bounded.

**Lemma 2.2**: Given a basic solution to a linear program in standard
form (with equality constraints), there exists a cost vector that makes that
solution the unique optimal solution.

**Theorem 2.1**: Under assumptions 2.1 and 2.2 there is at least
one bfs.

**Theorem 2.2**: Gives a bound on *x* that we can add to
a linear program without changing the optimal value.

**Theorem 2.3**: Every convex polytope is the convex hull of its
vertices, and conversely, if *V* is a finite set of points, then the
convex hull of *V* is a convex polytope whose vertices are a subset of
*V*.

**Theorem 2.4**: Suppose *P* is a convex polytope and *F*
= {*x*|*Ax* = *b*, *x* ≥ 0}and *x** =
(*x*_{1}, *x*_{2},..., *x*_{n-m})
in *P*, then the following are equivalent

*x** is a vertex of*P**x** is not the convex combination of distinct points of*P*- The corresponding vector
*x*in*F*is a bfs of*F*

**Definition 2.5**: A bfs is called *degenerate* if it
has more than *n*-*m* zeroes.

**Theorem 2.5**: If two distinct bases correspond to the same
bfs, then it is degenerate.

**Theorem 2.6**: Under the given assumptions, every LP has an
optimal bfs, and if there is more than one optimal bfs their linear combinations
are also optimal.