Résolution graphique
Il est possible de résoudre les problèmes ayant deux variables (ou deux contraintes pour un problème dual) directement par une résolution graphique. Le processus de résolution se déroule en trois étapes :
- Domaine réalisable
- Tracer la fonction objectif
- Déterminer la solution optimale
Domaine réalisable
Prenons le programme linéaire suivant :
Traçons le domaine de définition :
Ajout de la première contrainte et le type de variables
Ajout de la deuxième contrainte
Ajout de la troisième contrainte
Tracer la fonction objectif
Afin de résoudre le problème, nous représentons la fonction objectif au point (100,0) puis en divers points (en suivant le gradient de la fonction objectif) jusqu’à ce que la fonction objectif ne possède qu’un point ou une facette du domaine de définition.
Le gradient de la fonction objectif est (350,300). La valeur z augmente donc lorsque la fonction objectif est déplacé dans le même sens que le vecteur (350,300), donc en se déplaçant vers le coin nord-est. Nous voyons bien sur la figure suivant que la valeur de z a augmenté en prenant une autre droite de la fonction objectif.
Nous obtenons alors la ou les solutions optimales globales. Si l’on trace une nouvelle fois la fonction objectif en suivant le gradient, la droite sera hors du domaine de définition.
Solutions optimales
La ou les solutions optimales sont le/les derniers points avant que la droite de la fonction objectif ne quitte le domaine de définition.
La solution optimale se trouve à l’intersection de la première et deuxième contrainte, donc satisfait les deux contraintes. Le vecteur solution est la solution du système :
La solution de ce système est (122,78) ce qui donne z = 66100.
Les quatre possibilités de solution optimale
Il existe quatre possibilités :
- soit une unique solution existe (un point);
- soit une infinité de solutions (une facette);
- soit la solution n’est pas bornée, la droite de la fonction objectif sera toujours dans le domaine de définition en suivant le gradient;
- soit il n’existe pas de solution, par exemple si le domaine est vide.
FR 
EN 
ES