Website under construction. The material is still being written: slides and notebooks will follow later; the interactive lab is already open and will grow.
Linear Programming¶
Teaching material conceived and developed by Fabio Furini, associate professor at DIAG, Sapienza University of Rome.
The course lecture notes, online: linear programming problems, polyhedra, the simplex algorithm, duality, advanced methods and modelling techniques, with definitions, theorems with their proofs, examples worked out step by step and exercises with solutions.
Start with the LP problems The exercises Try an interactive graph Download the lecture notes (PDF)
How each chapter is organized¶
Each chapter is one of the course notes, with the same numbers and the same colors as the lecture notes: on the website and in the PDF you find everything in the same place.
Definition
The precise meaning of a new concept.
Theorem, proposition, observation
A result to remember, with its hypotheses.
Example
A computation worked out in full, one step at a time.
In green the key point to take away.
Proof — opens with a click
All proofs are included, but folded: first read the statement, then open the proof when you want to study it. The same holds for the solutions of the exercises.
The parts of the course¶
-
1 · Linear functions, polyhedra and linear programming problems
Linear functions (gradient, Hessian and level sets), half-spaces and polyhedra, linear optimization problems with their optimal solutions, examples and properties, the canonical and standard forms with the graphical method, possible outcomes and equivalences between forms.
1. Linear functions · 2. Half-spaces and polyhedra · 3. Linear optimization problems · 4. Linear Programming problems · 5. Possible outcomes and equivalent formulations
-
2 · The simplex algorithm
The simplex algorithm on dictionaries, optimality conditions, pivot rules and cycling, Phase 0 with the auxiliary problem. Examples worked out step by step and exercises with complete solutions at the end of each chapter.
6. Simplex algorithm · 7. Optimality conditions and pivot rules · 8. Phase 0 of the simplex algorithm
-
3 · Duality and the dual simplex
The dual problem, weak and strong duality, the possible outcomes of a primal-dual pair, complementary slackness; the dual simplex algorithm, infeasibility certificates and re-optimization. Examples worked out step by step and exercises with complete solutions at the end of each chapter.
9. Duality theory · 10. Dual Simplex algorithm
-
4 · Matrix methods, sensitivity and geometry
The revised primal and dual simplex, the primal-dual method, sensitivity analysis, the geometry of linear programming (faces, vertices and basic solutions). Examples worked out step by step and exercises with complete solutions at the end of each chapter.
11. Revised simplex algorithm · 12. Revised dual simplex algorithm · 13. The primal-dual method · 14. Sensitivity analysis · 15. The geometry of Linear Programming
-
5 · Modelling
Techniques for writing a linear programming model from the description of a problem (production, blending, transportation, multi-period planning, linearizations), with worked examples. Complete models are in Exercises 5.
16. Linear Programming modeling techniques
Don't miss¶
-
Exercises with solutions
Exercises for every chapter, each with a worked solution that opens with a click.
-
Interactive lab
Move the parameters with the sliders, drag the points and watch polyhedra, level lines, optimal vertices and dual problems change before your eyes.
-
Lecture notes and exercise books in PDF
Five volumes of lecture notes, five exercise books and the problem catalogue, with the same numbering as the website.
-
Problem catalogue
The problems P0–P86 used in the examples and exercises, with the figure of the feasible region.
-
Full index
All chapters with their sections, on one page.
By the same author:
- Convex Optimization — convex sets and functions, convex optimization problems, with interactive graphs;
- Algorithms — number representation, pseudo-code, sorting and searching, analysis and recursive algorithms;
- Integer Linear Programming — LP relaxation, valid inequalities, cutting planes, branch-and-bound and branch-and-cut;
- Combinatorial Optimization — knapsack, bin packing, coloring, TSP, scheduling and lot sizing, solved in every way;
- Network Optimization — graphs, spanning trees, shortest paths, network flows, the network simplex and project management;
- MIP Modelling — integer linear programming models, from the formulation to the solution with solvers;
- Operations Research Lab — modelling and solving optimization problems with Python and solvers;
- Mathematical Analysis 1 — real numbers, functions, limits, derivatives and series, with interactive graphs;
- Linear Algebra — vectors, matrices, determinants, linear systems and eigenvalues, with the computation lab.
Teaching material by Fabio Furini — DIAG, Sapienza University of Rome.
Questo sito è disponibile anche in italiano.