Linear programming and unimodularity

• Model simple problems using linear programs, translating the constraints of the problem into systems of linear equations or linear inequalities
• Solve these programs using the graphical method for the special case with two variables and using the simplex algorithm for the general case
• Provide geometric and economic interpretations of the different outputs of this algorithm, based in particular on duality.
• Understand the property of unimodularity and know how to solve classic maximum flow and minimum cost flow problems

Linear programming is the fundamental tool for modeling and solving optimization problems in operations research, which are of great practical importance: assignment problems, transportation, networks, production, etc. This course is limited to problems with continuous variables. The case of binary or integer variables, which is very common in practice, is covered in the course “Combinatorial Optimization,” for which this course is a prerequisite.

Linear algebra