Next: A Linear Programming Example Up: Linear Programming Previous: Linear Programming

Introduction to Linear Programming

In a general linear-programming problem, we wish to optimize a linear function, subject to a set of linear inequalities. We are given an matrix A, an m-vector , and an n-vector . We wish to find a vector of nelements that maximizes the objective function: subject to the m constraints given by A , and .
This problem can be written formally as a linear-program of the following structure (also called the primal linear program):
Minimize:
Subject To:
and
Many problems can be expressed as linear programs, and for this reason much work has gone into algorithms for linear programming. Today we know some polynomial algorithms that can be used to solve this problem, and there are many software packages can solve it.
Each minimization problem can easily be transformed to a dual maximization problem of the form:
Maximize:
Subject To:
and

Theorem 6.7 (no proof)   , where and are the solutions of a minimization problem and its dual maximization problem.

The above theorem suggests that we can either solve the primal or the dual linear program.

Next: A Linear Programming Example Up: Linear Programming Previous: Linear Programming
Yishay Mansour
1999-12-18