Cours : Linear Programming

Aperçu des sections

Programmation Linéaire - cours ouvert

Tout replier Tout déplier
Contributeurs 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).
- One idea, one story: He did not know it was impossible, so he did it Page
  
  Consulter
- Diapositives de cours sur la programmation linéaire (N. Brauner) Fichier
Modélisation en PL
L’objectif est d’apprendre à modéliser un problème décrit en langage naturel en un Programme Linéaire.
- 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 LP à partir d'un problème simple décrit en langage naturel.
- Modélisation en programmation linéaire (cours et exercices corrigés) Leçon
- 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.
  
  Cette leçon présente ce qu'est la programmation linéaire, un exemple de modélisation (concombre et oignons), les différentes représentations d'un programme linéaire et le vocabulaire associé.
  
  Une série de 3 vidéos présente comment modéliser un problème décrit en langage naturel en programme linéaire et 3 exemples types :
  
  vidéo Introduction et exercice introductif (12 minutes)
  
  vidéo exercice 1 (alliage) (9 minutes)
  
  vidéo exercice 2 (gestion d'un réseau d'eau) (12 minutes)
- I read the course Test
  
  Recevoir une note
- 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.
- Mode d'emploi d'une activité de modélisation (in french) Fichier
  
  Consulter
- OPL User Guide 1: Modeling LP problems with OPL using Caseine editor Fichier
  
  Consulter
- Play with the example of the user guide Virtual programming lab
  
  Recevoir une note
- Short OPL Tutorial Fichier
  
  Consulter
- Sand Box Virtual programming lab
- Un problème de modélisation (in french)
- Exercices de base sans difficulté particulière
- Cucumbers and onions (example from the course) Virtual programming lab
  
  Recevoir une note
- Légumes (exemple du cours) Virtual programming lab
  
  Recevoir une note
- Usine chimique Virtual programming lab
  
  Recevoir une note
- Production de vin Page
- German Wines - Vins allemands (solution available) Virtual programming lab
  
  Recevoir une note
- Parfum Virtual programming lab
  
  Recevoir une note
- Publicité Page
- Advertizing - Publicités (solution available) Virtual programming lab
  
  Recevoir une note
- Exercices avec notion supplémentaire
- Dairy Products Virtual programming lab
  
  Recevoir une note
- Airline - Compagnie aérienne Virtual programming lab
  
  Recevoir une note
- Alliage Virtual programming lab
  
  Recevoir une note
- La difficulté est de trouver les bonnes variables
- Fabrication d'huile d'olive Page
- Apples (mélanges) Virtual programming lab
  
  Recevoir une note
- Recyclage de plastique (mélanges) Virtual programming lab
  
  Recevoir une note
- The teapot - Le pot de terre et la théière (flot) Virtual programming lab
  
  Recevoir une note
- Séparer les modèles et les données
- OPL User guide 2: Modeling LP problems with OPL with external data Fichier
- Airline - Compagnie aérienne with external data Virtual programming lab
  
  Recevoir une note
- Gestion d'un réseau d'eau Virtual programming lab
  
  Recevoir une note
- Production of wines with external data Virtual programming lab
  
  Recevoir une note
- Bill Of Materials Virtual programming lab
  
  Recevoir une note
- Pour aller plus loin : un problème agricole (étude de cas, gestion des stocks) URL
Résolution d'un PL
- One idea, one story: the simplex algorithm is in the top 10 Page
  
  Consulter
- Reconnaître les formes canonique et standard et connaître les transformations.
  Linéariser une fonction objectif de la forme maximum d'un minimum ou minimum d'un maximum.
- Transformation betweeen forms Test
  
  Recevoir une note
- Changing forms step by step Test
- Linéarisation (exercices et corrigés) Page
- Formes canoniques et standards (exercices et corrigés) Page
- Résoudre graphiquement un PL à deux variables :
  
  dessiner la région réalisable
  
  dessiner les lignes de niveau de la fonction objectif
  
  trouver la ou les solutions optimales graphiquement
- Draw LPs in 2D with Geogebra
- Graphical representation of Cucumbers and onions with Geogebra
  
  Recevoir une note
- Towards a solution Test
  
  Recevoir une note
- Connaitre la définition d'une base, d'une variable de base et d'une variable hors base, une solution de base et une solution de base réalisable.
  
  Faire le lien entre la représentation graphique et les solutions de base (trouver le point correspondant à une solution de base et inversement).
  
  Connaître la relation entre les points extrêmes de la région réalisable et les solutions de base réalisables.
- Bases Test
  
  Recevoir une note
- Go further with bases ** Test
  
  Recevoir une note
- Connaître la notion de pivotage et de base voisine.
  
  Avant de pivoter, reconnaître les variables qui peuvent entrer dans la base afin d'améliorer la solution actuelle.
  
  Pendant le pivotage, savoir quelle variable peut sortir de la base.
  
  Maîtriser l'algorithme de pivotage et être capable de l'interpréter graphiquement.
- One idea, one story : Un article du journal le Monde qui parle de l'algorithme du simplexe (pourquoi il fonctionne si bien en pratique) URL
- I read the course again (basis and simplex algorithm) Test
  
  Recevoir une note
- Let's pivot Test
  
  Recevoir une note
- Phase I * Test
  
  Recevoir une note
- "software without mathware is only footware"
  Philosophe contemporain inconnu
  
  Allez plus loin avec la programmation linéaire
- A CPLEX Example Virtual programming lab
- A song to understand simplex method (based on the tableau method) URL
- Understand the LP modelling evaluation system URL
dualité ☯
- One idea, one story: the physics of shortest paths to detect useless streets ! Page
  
  Consulter
- OPL User Guide: Analyse the value of the dual variables
- Ecrire le dual d'un programme linéaire
  
  Calculer les unités des variables duales
  
  Donner une interprétation économique du programme dual et des valeurs optimales des variables duales
- 5 minutes pour apprendre à écrire le dual d'un programme linéaire (in French) URL
  
  Consulter
- Dual program Virtual programming lab
  
  Recevoir une note
- Vidéo (12 min): Interprétation économique du dual dans un cas simple URL
- Vitamins Virtual programming lab
  
  Recevoir une note
- Vitamins (Q2) Virtual programming lab
  
  Recevoir une note
- Cucumber and onions culture (again!) Virtual programming lab
  
  Recevoir une note
- Wines (Q1) Virtual programming lab
  
  Recevoir une note
- Wines (Q2) Virtual programming lab
  
  Recevoir une note
- Connaître le théorème de dualité faible et son application pour faire une preuve d'optimalité.
  
  Connaître le théorème de la dualité forte et comprendre son intérêt
  
  Appliquer la propriété des écarts complémentaire pour trouver les valeurs des variables duales
  
  Décrire une preuve d'optimalité pour une base donnée
- Vidéo (12min): Une façon de comprendre la construction du dual Page
- Le théorème des écarts complémentaires (in French) Leçon
  
  Effectuer l’activité jusqu’à la fin
- I read the Duality course Test
  
  Recevoir une note
- Application du théorème des écarts complémentaires Test
  
  Recevoir une note
- A transportation problem
- The primal Test
  
  Recevoir une note
- The dual Test
  
  Recevoir une note
- A lab for the primal Virtual programming lab
  
  Recevoir une note
- A lab for the dual Virtual programming lab
  
  Recevoir une note
- Dualité en théorie des jeux (in french) Leçon
  
  Consulter Effectuer l’activité jusqu’à la fin
Sensitivity analysis
- Comprendre le lien entre variable duale et prix caché
  
  Quand on change le second membre d'une contrainte, comprendre pourquoi la valeur de la variable duale ne change pas tant qu'on ne change pas de base
  
  Comprendre la signification de la propriété des écarts complémentaires sur l'exemple
  
  Savoir calculer les domaines de validité de la valeur d'une variable duale
- Discover Exel Solver Page
  
  Consulter
- Sensitivity Analysis Test
  
  Recevoir une note Obtenir une note minimale de réussite
- Sensitivity analysis training Test
  
  Recevoir une note
- A complete exercice Test
  
  Recevoir une note
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.
- "software without mathware is only footware"
  Philosophe contemporain inconnu
  Pour aller plus loin avec la programmation linéaire
- Ideas and contributions for linear programming Forum
- One idea, one story: the simplex algorithm is in the top 10 (doublon ?) Page
  
  Consulter
- Collections collaborative d'exercices de programmation linéaires Base de données

Aperçu des sections

Programmation Linéaire - cours ouvert

Modélisation en PL

Résolution d'un PL

dualité ☯

Sensitivity analysis

Place for contributors