Optimisation linéaire 1ère année ingénieur eisti 23 05 2013
Télécharger PDFIntroduction à l'Optimisation Linéaire : Simplexe, Dualité et Programmation en Nombres Entiers
L'optimisation linéaire est une branche fondamentale des mathématiques appliquées et de la recherche opérationnelle. Elle permet de trouver la meilleure solution possible (maximum ou minimum) pour une fonction objectif linéaire, tout en respectant un ensemble de contraintes linéaires. Cet article explore les méthodes de résolution classiques, la théorie de la dualité et les techniques de coupes pour les variables entières.
1. Résolution par la Méthode du Simplexe et Approche Géométrique
Considérons le programme linéaire suivant, noté (P1) :
Maximiser : Z = x₁ - 2x₂
Sous les contraintes :
- 2x₁ + 9x₂ ≤ 54
- -5x₁ + 4x₂ ≤ 12
- 4x₁ - x₂ ≤ 14
- x₁, x₂ ≥ 0
La méthode géométrique consiste à représenter graphiquement le domaine des solutions réalisables dans le plan (x₁, x₂). Chaque contrainte définit un demi-plan, et l'intersection de ces demi-plans forme un polyèdre convexe. La solution optimale se trouve nécessairement sur l'un des sommets de ce polyèdre. La méthode du simplexe, quant à elle, est un algorithme itératif qui se déplace de sommet en sommet le long des arêtes du polyèdre pour augmenter la valeur de la fonction objectif jusqu'à atteindre l'optimum.
2. Théorie de la Dualité et Méthode des Pénalités
À tout problème de programmation linéaire (le Primal) correspond un autre problème appelé le Dual. L'établissement du Dual repose sur un tableau de correspondances précis où les coefficients de la fonction objectif du Primal deviennent les seconds membres du Dual, et inversement.
Dans certains cas, notamment pour le Dual de (P1), l'algorithme du simplexe ne peut pas démarrer directement car l'origine n'est pas une solution de base réalisable. On utilise alors la méthode des pénalités (ou méthode du Grand M). Cette technique introduit des variables artificielles avec des coefficients de coût très élevés pour forcer l'algorithme à trouver une solution de base initiale valide.
Le théorème de complémentarité permet ensuite de lier les solutions optimales du Primal et du Dual : si une contrainte du Primal est satisfaite avec une marge (variable d'écart strictement positive), alors la variable duale correspondante doit être nulle à l'optimum.
3. Programmation en Nombres Entiers : La Méthode des Coupes
Dans de nombreux problèmes réels, certaines variables de décision doivent impérativement être des nombres entiers (par exemple, le nombre de machines à acheter). Si l'on impose x₁ ∈ ℕ dans le problème (P1), la solution continue trouvée par le simplexe n'est plus forcément valide.
La méthode des coupes de Gomory est alors employée. Elle consiste à :
1. Résoudre le problème sans la contrainte d'intégrité.
2. Si la solution n'est pas entière, générer une nouvelle contrainte (une "coupe") qui réduit le domaine des solutions continues sans éliminer de solutions entières.
3. Réitérer jusqu'à l'obtention d'un sommet aux coordonnées entières.
4. Modélisation d'un Problème de Production
Prenons l'exemple d'un industriel produisant trois biens (A, B, C) à partir de deux facteurs de production (X₁ et X₂).
- Bien A : nécessite 1 unité de X₁ et 1 unité de X₂.
- Bien B : nécessite 1 unité de X₁ et 2 unités de X₂.
- Bien C : nécessite 1 unité de X₁ et 5 unités de X₂.
Besoins minimums : 6 unités de A, 11 de B et 23 de C.
Coûts : X₁ coûte 100€ et X₂ coûte 400€.
Le modèle mathématique pour minimiser les coûts est :
Minimiser : C = 100x₁ + 400x₂
Sous contraintes :
- x₁ + x₂ ≥ 6 (Production de A)
- x₁ + 2x₂ ≥ 11 (Production de B)
- x₁ + 5x₂ ≥ 23 (Production de C)
- x₁, x₂ ≥ 0
Il s'agit d'un programme linéaire car la fonction objectif et les contraintes sont des combinaisons linéaires des variables de décision.
FAQ - Questions Fréquentes
Quelle est la différence entre le primal et le dual ?
Le primal est le problème original formulé. Le dual est une perspective alternative utilisant les contraintes du primal comme variables. À l'optimum, les valeurs de la fonction objectif du primal et du dual sont identiques.
Quand faut-il utiliser la méthode des pénalités ?
On utilise la méthode des pénalités (ou des variables artificielles) lorsque les contraintes de départ ne permettent pas d'identifier immédiatement une solution de base réalisable (par exemple avec des contraintes de type "supérieur ou égal" ou "égal").
À quoi sert une coupe de Gomory ?
Une coupe de Gomory est une contrainte supplémentaire ajoutée à un programme linéaire pour éliminer des solutions fractionnaires tout en conservant toutes les solutions entières possibles, facilitant ainsi la résolution des problèmes de programmation en nombres entiers.