Navigation Panel: Down to First Subsection | Graphical Version | PostScript version | SIMMER Home Page | Fields Institute Home | U of T Math Network Home

SIMMER

Society Investigating Mathematical Mind-Expanding Recreations

# October 1997 Feature PresentationLinear Programming: The Cornerstone of OptimizationN. Derzko*

In 1949 George B. Dantzig published the "simplex" method for solving linear programming problems. He is also usually credited with recognizing the importance of the general linear programming problem and identifying its early applications. Simply stated, the problem is one of optimizing a linear objective function on a domain defined by linear constraints.

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.

• Problems
• Solution to Question 3 (the hard problem)
• * Edited for SIMMERby Philip Spencer.