Operations Research (UGA)

LP Modelling

Compétences modélisation

Connaître les définitions associées aux PL : solution réalisable, solution optimale, région admissible...

Connaître les éléments qui forment un PL : variables de décision, fonction objectif, contraintes...

Être capable de modéliser un PL à partir d'un problème décrit en langage naturel.

La programmation linéaire propose un cadre de modélisation pour des problèmes d'optimisation sous contraintes et des outils pour trouver des solutions optimales. Cet outil fondamental de la recherche opérationnelle a émergé lors de la seconde guerre mondiale.

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

Les ateliers de modélisation, appelés labs dans ce cours, permettent de s’entrainer à modéliser. N’hésitez pas à en faire le plus possible. La première étape avant de faire un lab de modélisation est d’écrire le modèle sur papier pour bien séparer la difficulté de modélisation des éventuels problèmes techniques ou de syntaxe.

Les labs sont écrits dans le langage de modélisation OPL (Optimization Programming Language) de IBM. L'image OPL User Guide 1 décrit un exemple de programme linéaire en OPL avec la syntaxe nécessaire ainsi que l'écriture d’un modèle dans un lab de modélisation. Le lab Jouer avec l'exemple du OPL User Guide 1 permet de manipuler son premier lab de PL pré-rempli. Le manuel Short OPL Tutorial permet d’en savoir plus sur le langage de modélisation OPL. Vous pouvez modéliser et résoudre vos propres problèmes de PL dans le Bac à sable.

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)

Exercices de base sans difficulté particulière

Exercices avec notion supplémentaire

La difficulté est de trouver les bonnes variables

Séparer les modèles et les données

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