Close
A linear programming (LP) problem is a problem expressible in
the following form. Given an n × m real matrix A,
an m-vector b and an n-vector c, determine
minx {c · x | Ax ≥ b and x ≥ 0 }
where x ranges over all n-vectors
and the inequalities are interpreted component-wise, i.e., x
≥ 0 means that the entries of x are nonnegative.
There exists an entire collection of methods for solving such
problems. The most well known and used in practice is the Simplex
method devised by Dantzig.
minx {c · x | Ax ≥ b and x ≥ 0 }
Every linear program has a corresponding linear program called the dual.
For the program written above, the dual is:
maxy {b · y | ATy ≤ c and y ≥ 0 }
P1. For any solution x to the original linear program and any solution y
to the dual
we have the following property (which is known as weak
duality):
c · x ≥ (AT y)T x = yT(Ax) ≥ y · b
P2. For optimal x and y, equality holds. This is
known as strong duality.
maxy {b · y | ATy ≤ c and y ≥ 0 }
c · x ≥ (AT y)T x = yT(Ax) ≥ y · b