Linear Programming

LP Modelling

Skills Modelling

Know the definitions associated to LP: feasible solution, optimal solution, feasible region…

Know the elements that form an LP: decision variables, objective function, constraints

Be able to model an LP from a simple problem described in natural language

Ressources pour les activités de modélisation auto-évaluées

Vous devez être inscrit dans le cours pour avoir accès à l'éditeur des exercices de programmation (une fois connecté, si vous voyez encore ce message, utilisez la roue dentée en haut à droite).

Training (a modelling problem)

OPL User guide: Modeling LP problems with OPL with external data

LP Solving

Skills Solving

Recognize the canonical and standard forms and know the transformations

Linearize an objective function of the form maximum of a minimum or minimum of a maximum

Solve graphically an LP with two variables:

• draw the feasible region
• draw the level lines for the objective function
• find the optimal solution(s) on the graphic

Know the definition of a basis, a basic and a non-basic variable a basic solution and a feasible basic solution

Make the connection between the graphical representation and the basic solutions (find the point corresponding to a basic solution and conversely)

Know the relation between the extreme points of the feasible region and the feasible basic solutions

Know the notion of pivoting and neighbor basis

Before pivoting, recognize the variable that can enter the basis in order to improve the current solution

While pivoting, know which variable can leave the basis

Master the pivoting algorithm and be able to interpret it graphically