Linear Programming

Linear Programming is a particular case of constrained optimization problems. What sets the linear programming aside is that optimal values are sought for a linear function subject to linear constraints. To have a general formulation let's assume that we are given

1. an m×n matrix A
2. an m×1 (column) vector b
3. a 1×n (row) vector c

The role of the unknown is played by a n×1 (column) vector x which is required to satisfy two constraints:

1. Ax = b, and
2. x0,

Finally, the cost or objective function f is given by f(x) = c·x, where c·x is the scalar product of two vectors c and x: c·x = c₁x₁ + ... + c_nx_n. In linear programming, one is requested to maximize (or minimize) the cost function f subject to constraints 1 and 2:

(P)	Maximize f(x) = c·x subject to Ax = b and x0

Example

Assume that we have decided to position defenders of a square castle according to the following plan:

so that the total number of defenders is 4(p+q) while (2p+q) fighters face the enemy on every side. Let's denote p = x₁ and q = x₂. Let also A = (4 4), be a 1×2 matrix, and c = (2 1), a 1×2 row vector. Assume that a 1×1 vector b is equal to (28). The linear programming problem (P) is then interpreted as:

In a more formal manner, the problem is to maximize f(x) = 2x₁ + x₂ subject to 4(x₁ + x₂) = 28 and x₁0 and x₂0. Geometrical solution to the problem is easy and illuminating. The set F of feasible vectors is defined by

F = {x: x1 + x2 = 7 and x10 and x20}.

In the plane with orthogonal axes x₁ and x₂, F is a straight line segment between two points: (0,7) and (7,0).

The function f depends on two variables: x₁ and x₂. Instead of drawing its graph in the three-dimensional space, we'll draw a series of its level lines in the plane. The function is constant on each of the lines as shown on the diagram at the left. The function attains the maximum value 14 on the line 2x₁ + x₂ = 14 that passes through one of the endpoints (7,0) of the interval F. This is always the case in linear programming problems - solution is found at one (or more) vertices of the set of feasible vectors. Note that if we were looking to minimize f the solution would be located at the other endpoint (0,7) of F. Thus for the arrangement (*) we have two extreme configurations: a minimum and a maximum:

References

1. J.L.Casti, Five Golden Rules, John Wiley & Sons, 1996
2. J.A.Paulos, Beyond Numeracy, Vintage Books, 1992
3. G.Strang, Introduction to Applied Mathematics, Wellesley-Cambridge Press, MA, 1986.