Après avoir examiner comment on peut résoudre un programme linéaire par la méthode de simplexe, on s’intéresse dans cette section aux problèmes irréguliers, qu'on peut rencontrer lors de la résolution d’un programme linéaire par la méthode de simplexe. Donc, l’objet de cette section est de reconnaître ces problèmes et de les résoudre par la méthode de simplexe.

a. Les problèmes impossibles

Graphiquement, on a caractérisé ces problèmes par un ensemble de solutions réalisables vide. Avec la méthode de simplexe, on reconnaît que le problème est impossible si une ou plusieurs variables artificielles sont présentes dans la base dans le tableau de simplexe optimal, ce qui signifie que la solution donnée par ce tableau n’est pas réellement réalisable.

Vérifions à l’aide de la méthode de simplexe, que le problème suivant est réellement impossible :

Max 4x₁ + 3x₂ - MA₁

Le tableau de simplexe ci-dessus est optimal avec une variable artificielle dans la base.

b. Les problèmes à solutions multiples

Graphiquement, ce problème est caractérisé par le fait que la pente de la droite représentant la fonction objectif (z = 0) est égale à la pente de l’une des contraintes restrictives. Lorsqu’on utilise la méthode de simplexe, on identifie ce problème lorsqu’un des effets nets (relatif à une variable hors base) est nul. L’exemple de la section 3 du précédent chapitre représente un problème avec solutions multiples.

c. Les problèmes à solution infinie

Graphiquement, ce problème est caractérisé par le fait qu’on peut déplacer la droite de la fonction objectif indéfiniment de manière à accroître la valeur, en gardant toujours une intersection non vide avec l’ensemble des solutions réalisables.

Avec la méthode de simplexe, on reconnaît ce problème lorsque la variable entrante n’admet aucune limite sur sa valeur d’entrée, c’est à dire que tous les ratios Q_i/a_ijo sont négatifs ou nuls.

Max x₁ + 2x₂

Max x₁ + 2x₂ + 0S₁ + 0S₂ - Ma₁

Le dernier tableau montre que la variable x₁ n’admet aucune limite sur sa valeur de sortie.

Graphiquement, on appelle solution dégénérée le point où plusieurs contraintes concourent (un nombre supérieur ou égale à trois contraintes). Un programme linéaire est dit dégénérée si une ou plusieurs variables dans la base optimale sont nulles. Dans la résolution graphique ce problème n’est pas difficile à résoudre, mais avec la méthode de simplexe il peut causer des difficultés.

x₁ = 1

La forme standard du programme linéaire est

Max 2x₁ + 0 x₂ + 3/2x₃ + 0 S₁ + 0 S₂ + 0 S₃

La variable entrante est x₁, mais les deux premières contraintes donnent la même valeur minimale du ratio. Ceci indique que lorsque x₁ passe à 2, les variables d’écart S₁ et S₂ vont s’annuler malgré que l’un des deux demeure encore dans la base.

Choisissons arbitrairement de faire sortir de la base la variable d’écart S₁.

La nouvelle solution réalisable de base est :

x₁ = 0

et la valeur de la fonction objectif z = 4. Cette solution de base est dite dégénérée. Continuons les itérations relatives à la méthode de simplexe. La variable entrante est x₂.

Le problème est qu’un des ratios est nul ce qui indique qu’on ne peut pas augmenter la valeur de x₂ puisque la valeur de la fonction objectif ne va pas augmenter et reste égale à 4.

Si on réitère une autre fois, en remplaçant S₂ par x₂ dans la base on obtient :

Ce tableau n’est pas optimal, la variable entrante est x₃ et la variable sortante est x₂. On remarque aussi que ce passage d’une solution à une autre ne s’accompagne pas d’une augmentation de la valeur de la fonction objectif.

On peut facilement vérifier que nous somme en train de cycler sans atteindre la solution optimale. Ce genre de cyclage dans la méthode de simplexe est dangereux et on doit l’identifier avant de commencer à résoudre le problème, sinon on passera un temps énorme sans atteindre la solution optimale.

Pour terminer cette section, il faut noter que ce n'est pas tout problème de dégénérescence qui peut conduire à un cyclage.