LP : 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. Le processus de résolution se déroule en trois étapes :

  1. Domaine réalisable
  2. Tracer la fonction objectif
  3. Déterminer la solution optimale

Domaine réalisable

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 ou domaine réalisable, n’importe quel point du domaine de définition satisfait toutes les contraintes du modèle mathématique.

Prenons le programme linéaire suivant :

lineaire8

Traçons le domaine de définition :

Ajout de la première contrainte et le type de variables

lineaire9

Ajout de la deuxième contrainte

lineaire10

Ajout de la troisième contrainte

lineaire11

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.

lineaire12

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.

lineaire13

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.

lineaire14

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 :

lineaire15

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.