Résolution graphique de programmes linéaires

1. Introduction

Les programmes linéaires sont des fonctions linéaires à plusieurs variables à

maximiser ou minimiser sous contraintes.

Question : Que représentent les contraintes ?

Réponse : Chaque contrainte représente une moitié de l’espace de dimension n

(nombre de variables de décision). En effet, une contrainte va diviser l’espace en
deux parties, une partie qui va vérifier la contrainte et l’autre qui ne va pas la vérifier.
Ces deux parties sont séparées par un hyperplan (de taille (n-1)) ayant pour équation
la contrainte dont l’inégalité est remplacée par une égalité.

L’intersection de l’ensemble des contraintes permet de définir un domaine des

solutions possibles au PL que l’on notera DSR (Domaine des Solutions Réalisables). Il
s’agit d’un polyèdre convexe qui est l’ensemble des solutions d’un système fini
d’inégalités linéaires.

Question :

Quelle est la forme géométrique de l’hyperplan pour n =2 et pour n = 3.

Réponse :

Pour n = 2 (plan), l’hyperplan est de dimension 1. Géométriquement, cela correspond

à une droite qui va diviser le plan en deux parties.

Pour n = 3, l’hyperplan est de dimension 2. Géométriquement, cela correspond à un

plan qui va diviser l’espace en deux parties.

Question :

Quelle est la forme géométrique du domaine des solutions réalisables (DSR) pour n =
2 et pour n = 3 ?

Réponse :

Pour n = 2 (plan), le DSR est un polygone convexe.

1/11
 Pour n = 3, le DSR est un polyèdre convexe de dimension 3 (volume).

Question :

Est-il possible de représenter graphiquement un polyèdre de dimension supérieure à

3.

Réponse :

Il est impossible de représenter graphiquement n’importe quel espace ayant une

dimension supérieure à 3.

Par conséquent, la résolution graphique des PL ne concerne que les PL ayant moins
que 4 variables de décision. Généralement, seuls les PL ayant 2 variables de décision
peuvent être résolus graphiquement.

2. Représentation graphique du DSR

La représentation graphique des DSR est réalisé à partir du système de contraintes.

Soit le PL suivant :

Max Z  6 x1  4 x2
2 x1  3x2  120 contrainte1 équation d'un demi plan

s.c. 4 x1  2 x2  100 contrainte 2
x , x  0
 1 2

Les contraintes de non-négativité ( x1 , x2  0 ) exigent que le DSR ne peut se trouver

que dans le Quart de plan positif. Dans la figure 1, la partie hachurée en rouge
correspond au domaine des solutions non réalisables.

2/11
 Figure 1 -

La contrainte 1 représente un demi-plan dont la frontière est la droite

2 x1  3x2  120 qui est représentée dans la figure 2. La partie hachurée en rouge est

celle dont les points ne peuvent pas être des solutions réalisables. Afin de déterminer
lequel des demi-plans vérifie la contrainte, il suffit de choisir un point quelconque du
demi-plan et de vérifier si ce point respecte la contrainte. Si c’est le cas, n’importe
quel point du demi-plan respecte la contrainte. Pour faciliter les calculs, on choisit
généralement l’origine (le point (0, 0) pour deux Variables de base).

Figure 2

3/11
La contrainte 2 représente un demi-plan dont la frontière est la droite
4 x1  2 x2  100 qui est représentée dans la figure 3.

Figure 3 -

L’intersection des deux contraintes permet de définir le DSR comme cela est montré
dans la figure 4.

Figure 4 -
Tous les points du DSR sont une solution possible au PL c'est-à-dire que pour les
points du DSR toutes les contraintes sont vérifiées. Il est par conséquent possible de
réaliser la valeur correspondante de la fonction objectif. En revanche, tous les autres
points du plan ne sont pas réalisables et ne peuvent être des solutions au PL.

4/11
 En conclusion, on peut souligner l’importance de définir le DSR car la solution
optimale ne peut être qu’un des points du DSR.

Exercice
Déterminez les demi-plans correspondant aux contraintes suivantes :
- 2 x1  3x2  12
- x1  x2  5
- x1  3 x2  6
- x1  3
- 3x2  9
3. Recherche de la solution optimale

La solution optimale dans ce PL est un point du DSR qui maximise la fonction objectif
ou fonction économique.

A titre d’exemple, considérons le point M tel que ( x1  12; x2  15 ). Nous vérifions

que le point M est une solution puisqu’il appartient au DSR.

La valeur de Z pour le point M est :

Z  6 *12  4*15  132 ; 6x1+4x2 = 132

Cette valeur de Z n’est pas optimale puisqu’il suffit de prendre par exemple le point
( x1  18; x2  17 ) qui est un point du DSR pour lequel la valeur de Z est supérieure à

132 (Z =176).

5/11
En revanche, si on considère un point qui n’appartient pas au DSR, la valeur de Z sera
supérieure mais non réalisable. Par exemple, pour le point ( x1  35; x2  5 ), Z =230

mais cette valeur ne pourra être atteinte pour ressources insuffisantes.

La fonction économique peut également être représentée par une droite pour une
valeur donnée de Z.

Dans notre exemple, l’intersection entre la droite 6 x1  4 x2  170 et l’ensemble des

solutions réalisables représente les solutions permettant d’attribuer une valeur de

170 à la fonction économique. Il s’agit du concept de droite d’indifférence. En effet,
toutes les solutions relatives à une droite d’indifférence permettent d’atteindre
exactement le même objectif.

Il est possible de définir une droite d’indifférence pour chaque valeur de la fonction
économique. Les droites d’indifférence sont toutes parallèles.

Résolution graphique du programme linéaire

60
X2

50
E

B
40

30
6x1+4x2 = 120

20
2x1+3x2 = 120

6x1+4x2 = 60
10
4x1+2x2 = 100

A D F
0
0 10 20 30 40 50 60 70
X1

Ainsi, optimiser Z consiste à faire évoluer la valeur de Z jusqu’à ce que la droite quitte
le DSR. La valeur de Z est optimale lorsque l’intersection entre le DSR et Z, est un seul
point qui représente la solution optimale.

Par conséquent la solution optimale ne peut se trouver que sur un des sommets
(appelés aussi points extrêmes) du polygone des solutions réalisables.

Pour retrouver cette solution optimale graphiquement, il suffit de calculer la valeur

de Z pour chaque sommet et de choisir le point qui optimise Z.

6/11
 Dans notre exemple, les sommets du DSR sont les points O, A, C et E.

Les coordonnées des points O, A et E se lisent directement sur la figure.

Le point C est l’intersection de deux droites correspondant aux contraintes 1 et 2.

Pour déterminer les coordonnées du point C, il suffit de résoudre le système suivant :

2 x1  3x2  120

4 x1  2 x2  100
15
Les coordonnées du point C sont : ( x1  ; x2  35 )
2

Points extrêmes x1 x2 Z

O 0 0 0

A 0 40 160

C 15/2 35 185

E 25 0 150

La solution optimale (le point C) s’écrit de la manière suivante :

15 *
Z *  185; x1*  ; x2  35
2
Exercices :

Résoudre graphiquement les PL suivants :

- PL 1

Max Z  16 x1  8 x2
 x2  1
x  x  4

S /C  1 2
  x1  4 x2  1
 x1 , x2  0

- PL 2

7/11
 Max Z  x1  2 x2
 x1  3 x2  21
 x  3 x  18
 1 2
S .C.  ,
 x1  x2  5
 x1  0, x2  0,

4. Cas particulier 1 : solutions multiples

Résoudre le PL suivant :

Min C  x1  x2
 x1  x2  4
x  3
 1
S .C. 
5 x1  4 x2  20
 x1  0, x2  0,

Points extrêmes Systèmes linéaires à résoudre X1 X2 Z

A : D1 axe x2 Lecture directe sur l’axe x2 0 4 4

 x1  x2  4
C : D1 D2  3 1 4
 x1  3

 x1  3
E: D2 D3  3 8.75 11.75
 5 x1  4 x2  20

F : Axe x2 D3 Lecture directe sur l’axe x2 0 5 5

La solution optimale est obtenue en deux points A et C.

8/11
 Z *  4; x1*  0; x2*  4 ou bien Z *  4; x1*  3; x2*  1

En réalité, il existe une infinité de solutions puisque lorsque la droite Z quitte le DSR,
elle sera en intersection avec tout le segment de droite AC. Tout point de ce segment
de droite est une solution optimale du PL.

5. Cas particulier 2 : Absence d’une solution optimale finie

Max Z  x1  x2
 1
  2 x1  x2  10

 x2  25

S .C.  x2  5
  x  6 x  100
 1 2

 x1  0, x2  0,


Points extrêmes Systèmes linéaires à résoudre X1 X2 Z

A : D1 axe x2 Lecture directe sur l’axe x2 0 10 10

 1
  x1  x2  10
C : D1 D4  2 20 20 40
  x1  6 x2  100

9/11
  x2  25
E: D2 D4  50 25 75
  x1  6 x2  100

G : Axe x2 D3 Lecture directe sur l’axe x2 0 5 5

On constate que le DSR est non borné. Cela implique qu’il existe d’autres points du
DSR pour lesquels la fonction économique sera supérieure à tous les points extrêmes.
Par exemple, si on prend le point X(90,10), on constate que ce point appratient aux
DSR puisque toutes les contraintes sont vérifiées et que Z = 100 pour le point X. Ainsi,
vu que le DSR est non borné, on va augmenter la valeur de Z à l’infini. On dit que le
PL n’admet pas de solution optimale finie. Ce problème est généralement du à une
mauvaise formulation du PL.

Question : Est-ce qu’un domaine non borné implique systématiquement l’inexistance

d’une solution optimale finie ?

Prenons le même PL mais en considérant la minimisation plutôt que la maximisation

du PL.

Min Z  x1  x2
 1
  2 x1  x2  10

 x2  25

S .C.  x2  5
  x  6 x  100
 1 2

 x1  0, x2  0,


On aura toujours le même DSR non borné. En revanche, on aura une solution optimale finie
Z* puisqu’il n’existe aucun point du DSR pour lequel Z< Z*. Il s’agit du point A qui permet

d’atteindre la solution optimale suivante : Z *  5; x1*  0; x2*  5 .

Généralement, lorsqu’un PL admet un DSR non borné, il n’existera pas de solution

optimale finie s’il s’agit d’une maximisation. Par contre, lorsqu’il s’agit d’une
minimisation, le PL admettra généralement une solution optimale finie unique ou
multiple.

6. Cas particulier 3 : PL sans solutions

10/11
 MaxZ  3 x1  2 x2
5
 4 x1  x2  5

S .C. 7 x1  10 x2  70
 x  0, x  0,
 1 2


Ce PL ne permet pas de définir un DSR. C'est-à-dire qu’il n’existe aucun point du plan qui
vérifie toutes les contraintes.

On dit que le PL n’admet aucune solution.

11/11