Linear programming

A linear program is a problem of the form

minimize c'x

subject to Axr 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* = (x1, x2,..., xn-m) in P, then the following are equivalent

  1. x* is a vertex of P
  2. x* is not the convex combination of distinct points of P
  3. 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.

Python code for pivoting