Course: Linear Programming

Topic outline

Linear Programming Open course

Collapse all Expand all
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
- One idea, one story: He did not know it was impossible, so he did it Page
  
  View
- Course supports
- Slides on Linear Programming (N. Brauner) File
- 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).
LP modelling
- Short OPL Tutorial File
  
  View
- OPL User Guide 1: Modeling LP problems with OPL using Caseine editor File
  
  View
- Mode d'emploi d'une activité de modélisation File
  
  View
- Play with the example of the user guide Virtual programming lab
  
  Receive a grade
- Sand Box Virtual programming lab
- 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
- I read the course Quiz
  
  Receive a grade
- Self training (a modelling problem)
- Cucumbers and onions Virtual programming lab
  
  Receive a grade
- Usine chimique Virtual programming lab
  
  Receive a grade
- German Wines Virtual programming lab
  
  Receive a grade
- Perfumes Virtual programming lab
  
  Receive a grade
- Advertizing Virtual programming lab
  
  Receive a grade
- Dairy Products Virtual programming lab
  
  Receive a grade
- Airline - Compagnie aérienne Virtual programming lab
  
  Receive a grade
- Apples Virtual programming lab
  
  Receive a grade
- The teapot - Le pot de terre et la théière Virtual programming lab
  
  Receive a grade
- OPL User guide: Modeling LP problems with OPL with external data
- Production of wines with external data Virtual programming lab
  
  Receive a grade
- Bill Of Materials Virtual programming lab
  
  Receive a grade
LP solving
- One idea, one story: the simplex algorithm is in the top 10 Page
  
  View
- 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
- Playing with forms Quiz
  
  Receive a grade
- Forms step by step Quiz
- 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
- Draw LPs in 2D with Geogebra
- Graphical representation of Cucumbers and onions with Geogebra
  
  Receive a grade
- Towards a solution Quiz
  
  Receive a grade
- 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
- Bases Quiz
  
  Receive a grade
- Go further with bases ** Quiz
  
  Receive a grade
- 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
- Interactive illustration of the simplex method Page
- I read the course again Quiz
  
  Receive a grade
- Let's pivot Quiz
  
  Receive a grade
- Phase I * Quiz
  
  Receive a grade
- "software without mathware is only footware"
  Philosophe contemporain inconnu
  Go further with linear Programming
- A CPLEX Example Virtual programming lab
- A song to understand simplex method (based on the tableau method) URL
Duality ☯
- One idea, one story: the physics of shortest paths to detect useless streets ! Page
  
  View
- 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 variables
- 5 minutes pour apprendre à écrire le dual d'un programme linéaire (in French) URL
  
  View
- Vidéo (12min): Une façon de comprendre la construction du dual Page
- Dual program Virtual programming lab
  
  Receive a grade
- Vitamins Virtual programming lab
  
  Receive a grade
- Vitamins (Q2) Virtual programming lab
  
  Receive a grade
- Cucumber and onions culture (again!) Virtual programming lab
  
  Receive a grade
- Wines (Q1) Virtual programming lab
  
  Receive a grade
- Wines (Q2) Virtual programming lab
  
  Receive a grade
- 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
- Le théorème des écarts complémentaires (in French) Lesson
  
  Go through the activity to the end
- I read the Duality course Quiz
  
  Receive a grade
- A transportation problem
- The primal Quiz
  
  Receive a grade
- The dual Quiz
  
  Receive a grade
- A lab for the primal Virtual programming lab
  
  Receive a grade
- A lab for the dual Virtual programming lab
  
  Receive a grade
- Dualité en théorie des jeux (in french) Lesson
  
  View Go through the activity to the end
Sensitivity analysis
- 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
- Discover Exel Solver Page
  
  View
- Sensitivity Analysis Quiz
  
  Receive a grade Receive a passing grade
- Sensitivity analysis training Quiz
  
  Receive a grade
- Sensitivity analysis training (old, do not use) Quiz
  
  Receive a grade
- A complete exercice Quiz
  
  Receive a grade
Place for contributors
This section is dedicated to new contributions on linear programming. You can add ideas in the forum and activities or course documents below.
- Ideas and contributions for linear programming Forum
- Collections collaborative d'exercices de programmation linéaires Database

Topic outline

Linear Programming Open course

LP modelling

LP solving

Duality ☯

Sensitivity analysis

Place for contributors