Introduction à la programmation linéaire et à la dualité
La programmation linéaire (PL) est une méthode d'optimisation largement utilisée en recherche opérationnelle, en économie et en ingénierie. Elle consiste à maximiser ou minimiser une fonction linéaire sous des contraintes linéaires. Le simplexe de George Dantzig est l'algorithme le plus répandu pour résoudre ces problèmes. En parallèle, le concept de dualité permet d'associer à chaque problème primal un problème dual, offrant des interprétations économiques et des critères d'arrêt supplémentaires.
Le tableau du simplexe : variables d'écart et variables hors base
Variables d'écart (ou slack)
Dans un problème de maximisation, chaque contrainte d'inégalité du type "≤" est transformée en une contrainte d'égalité en ajoutant une variable d'écart. Cette variable mesure l'écart entre le côté gauche et le côté droit de la contrainte.
- Variable d'écart égale à zéro : cela signifie que la contrainte associée est saturée, c'est‑à‑dire qu'elle est active à la solution optimale.
- Si la variable d'écart est strictement positive, la contrainte n'est pas active et il existe un surplus de ressource.
Variables hors base (VHB)
Une variable hors base est une variable qui n'appartient pas à la base du tableau du simplexe. Dans une solution de base réalisable, chaque VHB est fixée à zéro. Cette propriété simplifie le calcul du vecteur solution et garantit que seules les variables de base peuvent prendre des valeurs strictement positives.
Choix de la variable entrante lors de la première itération
Le critère de sélection de la variable entrante repose sur les effets nets ou coûts réduits (cj − zj). Lors de la première itération du simplexe, on identifie la variable dont le plus grand coefficient (cj − zj) dans la ligne de coût réduit est positif. Cette variable promet la plus forte amélioration de la fonction objectif et devient donc la variable entrante.
Test d'optimalité à chaque itération
Après chaque pivot, le simplexe vérifie l'optimalité en s'assurant que tous les effets nets (cj − zj) sont négatifs ou nuls. Si tel est le cas, aucune amélioration supplémentaire n'est possible et la solution actuelle est optimale. Ce test remplace les vérifications plus intuitives comme la comparaison de la valeur de z entre deux itérations.
Dégénérescence, variables de base nulles et cyclage
Lorsque, après un pivot, une variable de base prend la valeur zéro, on parle de dégénérescence. La présence de variables de base nulles signale un risque de cyclage, phénomène où le simplexe peut revenir à une solution déjà rencontrée sans progresser vers l'optimum. Des stratégies comme la règle d'anti‑cyclage de Bland sont alors employées pour garantir la convergence.
Relation entre le primal et le dual
Construction du problème dual
Pour un problème primal de maximisation, les coefficients du second membre des contraintes du primal deviennent les coefficients de la fonction économique du dual. De même, les coefficients de la fonction objectif du primal se transforment en second membre du dual. Cette symétrie permet d'interpréter les contraintes du primal comme des variables du dual et vice‑versa.
Interprétation des variables d'écart dans le dual
Lorsque une variable d'écart sort de la base du tableau primal, son équivalent dans le tableau dual apparaît comme une variable de décision duale nulle. Cette correspondance reflète la complémentarité entre les contraintes actives du primal et les variables du dual.
Résolution graphique d'un problème à deux variables
Dans le cas où le problème ne comporte que deux variables de décision, la méthode graphique offre une visualisation intuitive du polyèdre des contraintes. Les sommets du polyèdre correspondent aux solutions de base réalisables. L'optimum se trouve toujours en un de ces sommets, ce qui justifie l'importance de l'analyse des coins dans la résolution graphique.
- Chaque contrainte définit une demi‑plan qui, combiné aux autres, forme le polyèdre.
- Les arêtes du polyèdre représentent les intersections de deux contraintes, tandis que les faces sont les régions admissibles.
- Le point où la fonction objectif est tangente au polyèdre indique la solution optimale.
Résumé des concepts clés
- Variable d'écart à zéro : contrainte saturée.
- Variable hors base : fixée à zéro dans la solution de base.
- Variable entrante : celle avec le plus grand (cj − zj) positif.
- Test d'optimalité : tous les (cj − zj) ≤ 0.
- Dégénérescence : variable de base nulle, risque de cyclage.
- Dualité : coefficients du RHS du primal deviennent coefficients de la fonction du dual.
- Variable d'écart sortante : correspond à une variable duale nulle.
- Résolution graphique : les sommets du polyèdre sont les solutions de base réalisables.
Approfondissements et bonnes pratiques
Pour maîtriser le simplexe et la dualité, il est recommandé de :
- Construire systématiquement le tableau initial en identifiant clairement les variables d'écart et les variables hors base.
- Vérifier à chaque itération que les effets nets respectent le critère d'optimalité.
- Surveiller les variables de base nulles afin de détecter la dégénérescence et d'appliquer, si nécessaire, la règle de Bland.
- Établir le problème dual dès le départ pour obtenir des bornes sur la valeur optimale et faciliter l'analyse de sensibilité.
- Utiliser la représentation graphique pour les petits problèmes afin de développer une intuition géométrique du polyèdre.
En combinant ces techniques, les étudiants et les praticiens gagnent en efficacité et en compréhension des mécanismes sous‑jacents à la programmation linéaire, ce qui est essentiel pour résoudre des problèmes réels complexes.
