Cas Particuliers de la Méthode du Simplexe : Dégénérescence, Solutions Non Bornées et Optima Multiples
Comment identifier et traiter les situations singulières dans le tableau simplexe : dégénérescence, absence de bornes et pluralité d'optima.
Essayez le Calculateur de Simplexe et de Sensibilité Étape par Étape
Saisissez votre fonction objectif et vos contraintes pour voir chaque tableau d'itération, les pivots et l'analyse de sensibilité en direct.
Introduction aux Singularités du Simplexe
Bien que l'algorithme du simplexe trouve de façon déterministe la solution optimale sur la plupart des problèmes concrets, certaines géométries particulières du polyèdre admissible créent des cas spéciaux qu'il convient d'identifier avec rigueur.
1. La Dégénérescence
La dégénérescence survient lorsqu'il y a égalité lors du test du ratio minimum pour déterminer la variable sortante. Par conséquent, à l'itération suivante, une ou plusieurs variables de base prendront une valeur nulle ($0$).
Sur le plan géométrique, la dégénérescence signale que plusieurs contraintes concourent exactement au même sommet. Pour prémunir le solveur contre un phénomène de cyclage infini, on recourt à la Règle de Bland (sélection de l'indice minimal).
2. Les Solutions Non Bornées
Un problème est dit non borné lorsque la fonction objectif peut croître indéfiniment vers l'infini sans violer aucune contrainte du modèle.
Dans le tableau simplexe, ce phénomène est immédiatement mis en évidence lorsqu'une variable candidate à l'entrée présente un coût réduit négatif, mais que tous les coefficients de sa colonne pivot sont inférieurs ou égaux à zéro ($a_{ik} \le 0$). Aucun ratio positif ne pouvant être calculé, aucune variable ne quitte la base, ce qui prouve l'infinité du domaine. Pour 2 variables, observez cette géométrie sur notre Calculateur de la Méthode Graphique.
3. Les Optima Multiples (Solutions Alternatives)
On rencontre des optima multiples lorsque la fonction objectif est strictement parallèle à l'une des contraintes actives sur le bord du domaine réalisable.
Dans le tableau optimal final, cette situation est décelable lorsqu'une variable hors base présente un coût réduit rigoureusement nul ($Z_j - C_j = 0$). En pivotant sur cette colonne, on atteint un autre sommet optimal avec la même valeur d'objectif $Z$, l'ensemble du segment joignant ces sommets formant des solutions équivalentes.
Prêt à résoudre votre propre programme linéaire ?
Obtenez instantanément des solutions pas à pas avec analyse de sensibilité et prix implicites pour tout problème de PL.