Optimisation linéaire td1 eisi -Programmation linaire - Rech
Télécharger PDFIntroduction à l'Optimisation Linéaire : Modélisation et Résolution
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 exprimées sous forme d'équations ou d'inégalités linéaires.
Représentation Géométrique des Systèmes d'Inégalités
Avant d'utiliser des algorithmes complexes, il est essentiel de comprendre comment visualiser l'espace des solutions. Un système de contraintes définit une région admissible, souvent appelée polyèdre, dans l'espace des variables.
Considérons les systèmes suivants pour s'exercer à la représentation graphique :
- Système A :
- 2x + 4y ≤ 10
- 3x - 4y ≥ 2
- x + y ≥ 0
- Système B :
- 2x + 3y ≤ 12
- 3x + y ≤ 9
- x + y ≥ 2
- x ≥ 0, y ≥ 0
- Système C (Valeurs absolues) :
- |x + 2y| ≤ 6
- |x - 2y| ≥ 2
La Méthode Géométrique du Simplexe
La méthode géométrique consiste à tracer la droite de la fonction objectif et à la déplacer parallèlement à elle-même jusqu'à atteindre le dernier point de contact avec la zone admissible (pour un maximum) ou le premier point (pour un minimum).
Exemple d'application : Maximiser Z = x + 3y sous les contraintes suivantes :
- 2x + 5y ≤ 10
- 3x + 4y ≤ 12
- x ≥ 0, y ≥ 0
Modélisation de Problèmes Réels
La modélisation transforme un problème métier en langage mathématique. Voici deux cas d'étude classiques :
Cas 1 : L'Optimisation de la Production (Le Fleuriste)
Un fleuriste dispose de 50 lys, 80 roses et 80 jonquilles. Il propose deux types de bouquets :
- Bouquet 1 (Prix : 40 €) : 10 lys, 10 roses et 20 jonquilles.
- Bouquet 2 (Prix : 50 €) : 10 lys, 20 roses et 10 jonquilles.
L'objectif est de déterminer la combinaison de bouquets qui maximise la recette totale tout en respectant le stock de fleurs disponible.
Cas 2 : Gestion de Portefeuille d'Investissement
Un investisseur choisit entre deux actifs : Ilog et BNP-Paribas. L'action Ilog rapporte 80 € pour un coût de 5 € et une commission bancaire de 2 €. L'action BNP-Paribas rapporte 60 € pour un coût de 10 € et une commission de 1 €. Les contraintes sont :
- Maximum de 100 actions au total.
- Budget maximal de 800 €.
- Plafond de commissions de 150 €.
La Méthode des Tableaux du Simplexe et les Pénalités
Lorsque le nombre de variables dépasse deux, la résolution graphique devient impossible. On utilise alors l'algorithme du simplexe via des tableaux. Dans certains cas, il est impossible de trouver une base réalisable immédiate (par exemple avec des contraintes d'égalité ou de type "supérieur ou égal"). On applique alors la méthode des pénalités (ou méthode du Grand M) pour initier l'algorithme.
Théorie de la Dualité et Complémentarité
À tout problème de programmation linéaire (appelé Primal) est associé un autre problème appelé Dual. La résolution du Dual fournit des informations précieuses, notamment sur la valeur marginale des ressources (prix fictifs). Le théorème de dualité stipule que si le Primal possède une solution optimale, le Dual en possède une aussi, et les valeurs des fonctions objectifs sont égales à l'optimum.
Les principes de complémentarité permettent de vérifier la cohérence entre les variables du Primal et celles du Dual.
Programmation Linéaire en Nombres Entiers
Dans de nombreux scénarios réels, les variables doivent être des nombres entiers (ex: nombre de voitures produites). On utilise alors la méthode des coupes de Gomory. On résout d'abord le problème en continu, puis on ajoute des contraintes supplémentaires (coupes) pour réduire le domaine aux solutions entières sans éliminer de points valides.
Exemple d'Optimisation des Coûts (Alimentation Animale)
Un éleveur doit nourrir ses animaux avec deux types d'aliments (Royal-Caribou et Kebab-Caribou) pour satisfaire des besoins nutritionnels en sel, sucre, gras et basilic au coût minimum. Ce problème se modélise par une minimisation de fonction objectif sous contraintes de "plus grand ou égal", ce qui nécessite souvent le passage par le dual ou l'usage de variables artificielles.
FAQ sur l'Optimisation Linéaire
Qu'est-ce que la variable d'écart dans le simplexe ?
Une variable d'écart est ajoutée à une contrainte d'inégalité (≤) pour la transformer en égalité. Elle représente la différence entre la ressource disponible et la ressource réellement utilisée.
Pourquoi le problème dual est-il utile ?
Le problème dual permet souvent de résoudre plus facilement des problèmes complexes et offre une interprétation économique des contraintes, révélant comment l'objectif change si l'on augmente une ressource d'une unité.
Quand utiliser la méthode des pénalités ?
On l'utilise lorsque le point d'origine (0,0) ne fait pas partie de la zone réalisable, notamment à cause de contraintes de type ≥ ou =, ce qui empêche d'avoir une base de départ évidente pour le simplexe.