Contributors: Nadia Brauner (UGA, Grenoble), Hadrien Cambazard (Grenoble-INP), Nicolas Catusse (Grenoble-INP), Aurélie Lagoutte (UCA, Clermont), Pierre Lemaire (Grenoble-INP)
Contact: Nadia Brauner
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).
L’objectif est d’apprendre à modéliser un problème décrit en langage naturel en un Programme Linéaire.
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
This lesson presents what linear programming is, an example of modeling (cucumber and onions), the different representations of a linear program and the associated vocabulary. The modeling examples (with corrections) are the following.
Looking at the answers is only interesting if you have tried to do the exercise. The milk bottle means that they are also proposed in a modeling lab.
Basic exercises without particular difficulty (green track):
The difficulty is to find the correct variables (red track):
The modeling labs allow you to practice modeling. Feel free to do as many as you can. The first step before doing a modeling lab is to write the model on paper to separate the difficulty of modeling from possible technical or syntax problems.
The labs are written in IBM's OPL (Optimization Programming Language). The OPL User Guide 1 image describes an example of a linear program in OPL with the necessary syntax as well as how to write a model in a modeling lab. The Playing with the Example lab of the OPL User Guide 1 allows you to manipulate your first pre-filled OPL lab. The Short OPL Tutorial manual allows you to learn more about the OPL modeling language. You can model and solve your own PL problems in the Sandbox.
Un problème de modélisation (in french)
Basic exercises with no special difficulty
Exercises with additional concepts
The difficulty is to find the correct variables
Separate models and data
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:
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 variables 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
"software without mathware is only footware"
Philosophe contemporain inconnu
OPL User Guide: Analyse the value of the dual variables
Write the dual of a linear program
Calculate the units of the dual variables
Give an economical interpretation of the dual program and of the optimal values of the dual variables
Know the weak duality theorem and its application to make a proof of optimality
Know the strong duality theorem and understand its interest
Apply the complementary slackness property to find the values of the dual variables
Describe an optimality proof for a given basis
A transportation problem
Understand the relation between the dual variable and the shadow price
Understand why the value of the dual variable does not change when the second member of the constraint is changed in the primal as long as the basis remains the same
Understand the meaning of the complementary slackness property on the example
Be able to calculate the validity bounds of the value of a dual variable
This section is dedicated to new contributions on linear programming. You can add ideas in the forum and activities or course documents below.
"software without mathware is only footware"
Philosophe contemporain inconnu