Graphes et Recherche Op´erationnelle
Graphes et Recherche Op´erationnelle
Programming, Math, Optimization · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
La programmation linéaire est une méthode utilisée en recherche opérationnelle pour optimiser un objectif sous des contraintes linéaires. Ce cours aborde la modélisation de problèmes, la résolution graphique, et les différentes formes d'un programme linéaire. Des exemples concrets, tels que des problèmes de production, illustrent les concepts clés. Les étudiants apprendront également la méthode du simplexe pour résoudre efficacement des problèmes de programmation linéaire.
En recherche opérationnelle, modéliser un problème consiste à identifier les éléments suivants :
Par exemple, considérons une usine qui fabrique deux produits, P1 et P2. L'objectif est de maximiser le bénéfice total provenant de la vente de ces produits. Les ressources disponibles (équipement, main-d'œuvre, matières premières) sont limitées, ce qui constitue les contraintes du problème.
Une usine fabrique deux produits P1 et P2, nécessitant des ressources d'équipement, de main-d'œuvre et de matières premières disponibles en quantité limitée :
| Ressources | P1 | P2 | Disponibilité |
|---|---|---|---|
| Équipement | 3 | 4 | 81 |
| Main d'œuvre | 2 | 9 | 55 |
| Matière première | 5 | 1 | 20 |
Les produits rapportent respectivement 6 euros pour P1 et 4 euros pour P2. Nous devons déterminer les quantités de P1 et P2 à produire pour maximiser le bénéfice total.
La fonction objectif à maximiser est :
F(x1, x2) = 6x1 + 4x2
Les contraintes sont :
Nous cherchons donc à maximiser F sous ces contraintes.
Pour résoudre un problème de programmation linéaire à deux variables, on peut utiliser une méthode graphique. Les contraintes, représentées par des inégalités, correspondent géométriquement à des demi-plans. L'intersection de ces demi-plans forme un polygone convexe, qui représente l'ensemble des solutions réalisables.
Pour déterminer le maximum de F, on fait glisser la droite de la fonction objectif (translation parallèle) jusqu'à rencontrer l'ensemble des variables satisfaisant les contraintes. La solution optimale est atteinte en un sommet du polygone convexe des contraintes.
Dans notre exemple, la solution optimale est :
(x1, x2) = (15/2, 5) avec max(F) = 65.
Un programme linéaire peut être exprimé sous plusieurs formes :
Un programme linéaire sous forme canonique mixte s'écrit :
max (x1, ..., xn)
F(x1, ..., xn) = c1x1 + ... + cnxn
sous les contraintes :
aij xj ≤ bi (pour i ∈ I1)
aij xj = bi (pour i ∈ I2)
xj ≥ 0 (pour j ∈ J1)
Un programme linéaire est dit sous forme canonique pure s'il s'écrit :
max x
F(x) = c^T x
sous les contraintes :
Ax ≤ b
x ≥ 0
Un programme linéaire est dit sous forme standard s'il s'écrit :
max x
F(x) = c^T x
sous les contraintes :
Ax = b
x ≥ 0
La méthode du simplexe est une technique efficace pour résoudre des problèmes de programmation linéaire. Elle explore uniquement les sommets qui permettent d'augmenter la fonction objectif, réduisant ainsi le nombre de solutions de base à examiner.
Il existe trois situations possibles lors de l'application de la méthode :
Une solution de base réalisable est un vecteur qui satisfait les contraintes du programme linéaire. Pour un programme sous forme standard, on note :
DR = {x ∈ R^n | Ax = b, x ≥ 0}
Le nombre de solutions de base réalisables est limité, et la méthode du simplexe permet de les explorer efficacement.
La programmation linéaire est une méthode d'optimisation qui permet de maximiser ou minimiser une fonction linéaire sous des contraintes également linéaires.
Un problème de programmation linéaire peut être résolu graphiquement pour deux variables ou par la méthode du simplexe pour des problèmes plus complexes.
Les programmes linéaires peuvent être exprimés sous forme canonique mixte, canonique pure, ou standard, selon la nature des contraintes.
Une solution de base réalisable est un vecteur qui satisfait les contraintes d'un programme linéaire, souvent associé à un sommet du polyèdre des solutions réalisables.