A Short Course in Linear Programming

There presently are two primary strategies: (1) Simplex Method and (2) Interior Point Method.

First, lookup these methods in the glossary, and chain through other terms to which they are linked. Second, look at each of the following introductions to the simplex method and use the interactive solvers.

• JavaORjava, by WORMS
• S.B. Kei, L.W. Keung, L.H. Pui, and S. Yeung - see Chapter 2 in their documentation before and after using their program.
• NEOS Guide to the Simplex Method ... try their Simplex Java Applet
• Simplex Place at Melbourne
• RIOT at Berkeley

Fourth, look at Richard Weber's notes - Chapters 1-4.

For insights into pathological behavior, see two notes by Charles Blair: ``Some pathological examples for the simplex algorithm'' (pure text), and ``Notes on the Karmarkar Algorithm'' (for this one, you will need to download the tex file and compile it).

Test your knowledge of these terms (in the glossary):

• Adjacent basis
• Central path
• Cycling (in the simplex method)
• Degeneracy
• Elementary simplex method
• Extreme point
• Interior (point) methods
• Karmarkar's algorithm
• Optimal partition
• Phase I
• Pivot
• Polyhedron
• Pricing
• Primal method
• Tableau