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 un graphique.

Pour cela, nous représentons chaque contrainte dans le graphe, en hachurant ou coloriant le côté qui ne satisfait pas la contrainte.
Ainsi, nous mettons en évidence un domaine de définition, n’importe quel point du domaine de définition satisfait toutes les contraintes du modèle mathématique.

graphique

Afin de résoudre le problème, nous représentons la fonction objectif au point (0,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.

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.

graphique2

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.
Publicités