8
Linear Programming
A Linear Programming problem, or LP, is a problem of optimizing a given
linear objective function over some polyhedron. We will present the forms
of LPs in this chapter. Consequently, we will focus on the simplex method
of G. B. Dantzig, which is the algorithm most commonly used to solve LPs;
in practice it runs in polynomial time, but the worst-case running time is
exponential. Following the various variants of the simplex method, the duality
theory will be introduced. We will concentrate on the study of duality as a
means of gaining insight into the LP solution. Finally, the series of Farkas'
Lemmas, the most important theorems of alternatives, will be stated.
8.1 The Simplex Method
This section is about linear programming: optimization of a linear objective
function subject to finite number (m) of linear constraints with n unknown
and nonnegative decision variables.
Example 8.1.1 The following is an LP:
Min z =2x + 3y
s.t.
2x + y>Q
x + 2y>6
x,y>0.
Standard Form:Min z —ex
s.t.
Ax>b
x>9