**Society Investigating Mathematical
Mind-Expanding Recreations**

Linear Programming: The Cornerstone of Optimization

N. Derzko*

In an example of three or four variables, the linear programming problem does not reveal the depth of some of the concepts needed to solve it, nor does it foretell the enormous importance the problem has achieved in industry. Its significance becomes more apparent with the realization that the simplex method is capable of solving optimization problems with hundreds of thousands of variables and tens of thousands of constraints.

Stories of improvements in efficiency and cost saving abound in industry. When Standard Oil introduced linear programming in its refinery control systems in the early sixties, the savings amounted to millions of dollars each month. More recently, in 1992 American Airlines designed a system of rare structures, overbooking and flight coordination which uses linear programming and other techniques of operations research. The annual increase in revenue attributed to the system exceeds $500 million.

Since linear programming is one of the few optimization techniques that can routinely solve problems with an enormous number of variables, it is not surprising that considerable effort goes into translating problems which do not at first look like LP-s into LP form. This translation in many cases requires considerable mathematical insight.

These notes present some examples ranging from the obvious to the obscure to illustrate my point. A solution is given for the hardest and most important problem.

* Edited forNavigation Panel:

Go down to first subsection Problems

Switch to graphical version (better pictures & formulas)

Access printed version in PostScript format (requires PostScript printer)

Go to SIMMER Home Page

Go to The Fields Institute Home Page

Go to University of Toronto Mathematics Network Home Page