LP : origine non réalisable

Origine non réalisable

Les problèmes dont tous les b_я sont positifs sont fait avec Origine Réalisable. Il est facile d’avoir une solution de base et le simplexe est compatible. Pour les problèmes à l’origine non réalisable, on cherche d’abord à résoudre le Problème Auxiliaire.

Dans le problème auxiliaire, on ajoute une variable auxiliaire x₀. Cette variable rentre dans toutes les contraintes. Nous cherchons à minimiser sa valeur (maximiser son contraire).

La première itération est spécifique, on force la variable auxiliaire à rentrer. La ligne pivot est celle dont le b_я est le plus petit. La suite suit la résolution classique d’un simplexe.

Une fois que le simplexe est optimal, on exprime z en fonction des variables hors base. L’origine des variables en base est alors réalisable (ici les cadres bleus montrent l’évolution des contraintes par la résolution du simplexe).

Le nouveau problème à résoudre est le suivant :