Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 29

The authors start with a discussion of linear programming. The authors define the concepts of linear function, linear equality and linear inequality and linear programming problem. The author defines feasible region, feasible solution, objective solution and objective value.

The author then describes simplex algorithm which takes linear program as an input and generates an optimal solution.

The author then describes uses of linear programming ranging from operations research, solving graph and combinatorial problems. The author then discusses algorithms for linear programming like ellipsoid algorithm, interior-point methods, and integer linear program.

The author then describes two formats:

• Standard Form
• All the constraints in this form are inequalities. The author provides the description of the problem in standard form and then provides a method to convert linear program to a standard form.
  
• Slack Form
• All the constraints in this form are equalities. The author provides a method to convert linear program to a slack form.

The author then formulates following four problems as linear program:

1. Shortest paths
2. Maximum flow
3. Minimum cost flow
4. Multicommodity flow

The author then describes simplex algorithm and prove some lemmas.

The author then discusses about linear programming duality. The author then prove some lemmas and theorem and prove them.

The author then describes a method to find a basic feasible solution to test that a linear program is feasible. The author then defines and proves some lemmas.

The author then defines fundamental theorem of linear programming as follows:
Any linear program L, given in standard form, either

1. has an optimal value with a finite objective value.
2. is infeasible or
3. is unbounded.

The author also provides a proof for it.