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
The role of the unknown is played by a n×1 (column) vector x which is required to satisfy two constraints:
 Ax = b, and
 x ≥ 0,
the latter means that all the components of x are nonnegative. Vectors that satisfy constraints 1 and 2 are called feasible. We are interested in the situations where the set of feasible vectors is not empty.
Finally, the cost or objective function f is given by
(P) 
Maximize f(x) = c·x subject to Ax = b and 
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
How to position 28 fighters according to the symmetric arrangement above so as to have the maximum number of defenders on each side?
In a more formal manner, the problem is to maximize
F = {x: x_{1} + x_{2} = 7 and x_{1} ≥ 0 and x_{2} ≥ 0}. 
In the plane with orthogonal axes x_{1} and x_{2}, F is a straight line segment between two points:
The function f depends on two variables: x_{1} and x_{2}. Instead of drawing its graph in the threedimensional 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


References
 J. L. Casti, Five Golden Rules, John Wiley & Sons, 1996
 J. A. Paulos, Beyond Numeracy, Vintage Books, 1992
 G. Strang, Introduction to Applied Mathematics, WellesleyCambridge Press, MA, 1986.
Contact Front page Contents Algebra Up
Copyright © 19962018 Alexander Bogomolny