Why linear programming is important

Linear programming problems can be solved by fast and efficient methods. The simplex algorithm is a general method that will solve any linear programming problem. Other methods are also available for specialized classes of linear programming problems.

Some definitions

objective function = the function being minimized or maximized
constraints, equality constraints, inequalitity constraints, nonnegativity constraints
A feasible solution is a point that satisfies the constraints. The feasible set is the set of all feasible points.
An optimal solution (or maximizer or minimizer) is a point where the optimal value occurs.

Example:

max x+y subject to x^2+y^2 <= 2

The optimal solution is (1,1). The optimal value is 1+1=2. There is one inequality constraint. The feasible set is the disk of radius sqrt(2) centered at the origin. The objective function is the function f(x,y) = x+y.

Example:

max x+y subject to x >= 0, y >= 0, x <= -2

The problem is infeasible. (There are no feasible solutions -- no points satisfy all of the inequalities.)

Example:

A rectangular lot is to be fenced in by a river. The total length of the fence is 100ft. What is the maximum area?

When you took calculus I, you probably solved this as a one variable problem. It can also be solved as a two-variable problem: max xy subject to x>=0, y>=0, 2x+y=100. The feasible set is a line segment. At the optimizer, the gradient of the objective function is perpendicular to the line segment. This fact is called the Lagrange multiplier principle. This fact can be exploited to find the optimizer.

Example: Transportation Problem