3 Méthode graphique

1. Introduction
Après avoir illustrer par des exemples, comment un problème pratique peut être modélisé par
un programme linéaire, l’étape qui va suivre sera certainement celle de la résolution de ce
problème mathématique. La méthode graphique est l’une des premières méthodes utilisées à
ce sujet. Si on parle de résolution graphique alors on doit se limiter à une représentation à deux
variables et au plus à trois variables.
La méthode graphique n’est pas celle habituellement utilisée pour résoudre les programmes
linéaires ; par contre, elle permet une meilleure compréhension de certaines propriétés et
situations qui peuvent se présenter lors de l’étude de la méthode du simplexe.

2. Quelques rappels de géométrie

Les programmes linéaires à deux variables peuvent être représentés dans le plan R2 rapporté
à deux axes. On va examiner des problèmes de la forme : optimiser (maximiser ou minimiser)
z = ax1 + bx2 sous les contraintes : ai x1 + bi x2 (>, 6) ci i = 1, . . . , m et x1 > 0, x2 > 0.

2.1. Système d’axes

Une des conditions de la réussite de notre représentation graphique est le choix d’un système
d’axes. Un mauvais choix peut rendre notre représentation non claire et imprécise.
A cause des contraintes de non-négativité des variables de décision, nous nous intéressons
seulement au quadrant positif.
x2

Quadrant
positif

O x1

2.2. La construction de la région réalisable

Pour une inéquation linéaire de la forme ai x1 + bi x2 6 ci ou de la forme ai x1 + bi x2 > ci ,
correspond la droite d’équation :
ai x 1 + b i x 2 = c i
Cette droite partage alors le plan en deux demi-plans. Chaque inéquation linéaire peut être
représentée graphiquement en commençant par dessiner l’équation correspondante. Pour

© Hachimi 2020 • Recherche Opérationnelle

3 Méthode graphique 2

vérifier de quel demi-plan il s’agit, il suffit d’introduire un point (par exemple l’origine O)
dans l’inéquation et de vérifier si celle-ci est satisfaite.
x2

O x1

L’intersection de tous les demi-plans correspondant aux contraintes constitue l’ensemble des
solutions réalisables : ce sont les solutions communes à toutes les contraintes. Cet ensemble
correspond à une région D du plan et est souvent appelée région réalisable. Cette région
souvent bornée mais il y a des cas où elle est soit non borné soit vide.
x2 x2 x2

O x1 O x1 O x1

2.3. La recherche d’une solution optimale

La région réalisable contient souvent un nombre infini de solutions réalisables. Il reste à
repérer, parmi ces solutions réalisables celle(s) qui donne(nt) à z la meilleur valeur.
Comme l’expression de la fonction objectif fait intervenir trois variables, elle ne peut donc être
représentée que dans l’espace R3 . Pour se ramener dans le plan (x1 ; x2 ), on va considérer la
variable z comme un paramètre. Ce qui définit une famille de droites d’isovaleur parallèles,
chacune d’elles correspondant à une valeur de z :

(Dz ) ax1 + bx2 = z

x2

O x1

© Hachimi 2020 • Recherche Opérationnelle

3 Méthode graphique 3

Toutes ces droites ont le même vecteur normal → −

u (a, b) ; et il est intéressant de savoir que ce
vecteur indique toujours le sens des z croissants.
La recherche de la valeur optimale se fait selon une démarche commune, celle-ci peut être
résumée en quatre directives :
— Tracer une droite de référence (Dr ), où r est une valeur fixe de z. Habituellement, on trace
la droite (D0 ), relative à z = 0.
— Tracer une flèche (ou le vecteur normal) afin d’indiquer le sens de déplacement parallèle
de (Dz ) qui fait augmenter z.
— Balayer la région réalisable par des droites parallèles à la droite particulière.
— Si le programme linéaire est de type maximisation (resp. minimisation), déterminer la
droite ayant une valeur de z la plus élevée (resp. basse) possible et ayant aussi une
intersection non vide avec la région réalisable.

3. Exemples de base
3.1. Problème de maximisation
Considérons le problème de l’entreprise UVW qui fabrique deux nouveaux modèles chassis.
Ce problème a été traduit par le modèle linéaire suivant :


 max z = 300x1 + 500x2


 x1 6 4 (1)


(P1 ) 2x2 6 12 (2)
3x1 + 2x2 6 18 (3)






x1 > 0, x2 > 0 (4)


Tracé des contraintes

Ici, on va indiquer comment tracer les contraintes associées au programme linéaire. D’abord,
les contraintes de non-négativité (4) nous restreignent au quadrant positif. Ensuite, on doit
faire un bon choix du système d’axes en se basant sur une lecture des différents paramètres du
programme linéaire.
Dans notre cas, on ne peut que qualifier de bon le choix de 10 unités dans chacun des deux
axes :
x2
10

O 2 4 6 8 x1

© Hachimi 2020 • Recherche Opérationnelle

3 Méthode graphique 4

Transformons les inéquations des contraintes technologiques en équations de droites :

x1 = 4 (D1)
2x2 = 12 (D2)
3x1 + 2x2 = 18 (D3)

Pour les deux premiers droites (D1) et (D2), il suffit de tracer les parallèles aux axes passant
par les point (4, 0) et (0, 6) respectivement.
x2
10 (D1)

8
(D2)
6

O 2 4 6 8 x1

Pour tracer une droite oblique, on cherche d’abord deux points de cette droite. Le plus simple
est de chercher ses points d’intersection avec les axes du repère. Par exemple, pour tracer la
droite (D3) d’équation 3x1 + 2x2 = 18, on cherche quel est le point dont l’abscisse x1 vaut 0 : on
trouve x2 = 18/2 = 9. Le point (0, 9) est un point de cette droite. Ensuite, on cherche quel est
le point dont l’ordonnée x2 vaut 0 : on trouve x1 = 18/3 = 6. Le point (6, 0) est un autre point
de cette droite.
x2
10

2
(D3)

O 2 4 6 8 x1

Pour chaque contrainte technologique, on détermine de quel côté de la droite associée se

trouvent les points pour lesquels la contrainte est satisfaite. Dans notre cas, l’origine O vérifie
chacune des trois contrainte. Ainsi, chaque contrainte est satisfaite dans le demi-plan limité
par la droite associée et contenant l’origine O.
L’intersection commune de toutes les contraintes (technologiques et de non-négativité)
constitue la région réalisable D. Sur la figure suivante, la région réalisable est colorée en gris.

© Hachimi 2020 • Recherche Opérationnelle

3 Méthode graphique 5

x2
10 (D1)

8
(D2)
6

4
D
2
(D3)

O 2 4 6 8 x1

A chaque couple de valeurs des variables de décision x1 et x2 on associe un point (x1 , x2 ) du

plan R2 : le point (x1 , x2 ) s’interprète comme la proposition d’un plan de production indiquant
le nombre de chassis à fabriquer par semaine. Généralement, on parle indifféremment du point
(x1 , x2 ) ou du plan de production (x1 , x2 ) ou encore de la solution (x1 , x2 ).

Localisation de la solution optimale

Il s’agit ici de chercher, parmi les points appartenant à la région réalisable D, le point (x1 , x2 )
maximisant la fonction objectif z. On trace l’une des droites parallèles représentant les courbes
de niveau de la fonction objectif z. En particulier, la droite d’équation :

300x1 + 500x2 = 0

est tracée ; elle passe par l’origine et donne une valeur nulle à la fonction objectif. On lui ajoute
une flèche qui indique le sens des z croissants. Cette droite sera déplacée dans le sens de la
flèche jusqu’à l’extrême limite de la région réalisable.
x2
10 (D1)

8
(D2)
6

4
D
2
(D3)

O 2 4 6 8 x1

Noter que plus on s’éloigne de l’origine O, plus la valeur de z augmente. Autrement dit, plus
on s’éloigne de l’origine, plus on se rapproche de la solution optimale. Ainsi, on voit à la figure
ci-dessus que la solution optimale est le point

(x1 , x2 ) = (2, 6).

© Hachimi 2020 • Recherche Opérationnelle

3 Méthode graphique 6

Calcul de la solution optimale

Graphiquement, on a localisé la solution optimale. Parfois, pour avoir une certaine précision,
il est utile de calculer les coordonnées de celle-ci. Dans cet exemple, la solution optimale
correspond au point d’intersection des deux droites (D2) et (D3) d’équations respectives :

2x2 = 12 (D2)
3x1 + 2x2 = 18 (D3)

Donc : x1 = 2, x2 = 6, et la valeur optimale est z = 3 600

3.2. Problème de minimisation

Considérons le problème de l’agriculteur qui cherche un régime alimentaire pour son troupeau
qui soit le moins cher possible, tout en garantissant un apport suffisant en éléments nutritifs.
Ce problème a été traduit par le modèle linéaire suivant :


 min z = 20x1 + 40x2


 2x1 + x2 > 16 (1)


(P2 ) x1 + x2 > 12 (2)
x1 + 3x2 6 18 (3)






x1 > 0, x2 > 0 (4)


Cet exemple diffère du premier sous trois aspects : la fonction objectif c’est à minimiser ; les
contraintes technologiques sont de type « > » ; l’origine O du repère n’est pas une solution
réalisable ; et la région réalisable n’est pas bornée.

Tracé des contraintes

La technique de tracé des contraintes reste la même que celle employée dans l’exemple
précédent. Compte tenu des différents paramètres du programme linéaire, le choix de 20 unités
dans chacun des deux axes du repère nous paraît judicieux.
Transformons les inéquations des contraintes technologiques en équations de droites :

2x1 + x2 = 16 (D1)
x1 + x2 = 12 (D2)
x1 + 3x2 = 18 (D3)

Les trois droites sont obliques. Il s’agira, pour chaque droite de :

— déterminer deux points de cette droite pour la tracer. Les points d’intersection avec les
axes sont convenables dans le cas de cet exemple.
— déterminer de quel côté de la droite se trouvent les points pour lesquels la contrainte
concernée est satisfaite. Les contraintes technologiques de cet exemple correspondent tous
aux demi-plans ne contenant pas l’origine O.

Lorsqu’on prend en considération toutes les contraintes, on doit alors prendre l’intersection
des demi-plans qui y sont associés. Sur la figure suivante, la région réalisable est la partie non
borné colorée en gris.

© Hachimi 2020 • Recherche Opérationnelle

3 Méthode graphique 7

x2

16
(D1)
D
12

8 (D2)
4
(D3)

O 4 8 12 16 x1

Recherche de la solution optimale

Pour trouver la solution optimale, la droite isovaleur z = 0 de la fonction objectif a été tracée et
munie d’une flèche indiquant le sens des z croissants. Aussi, une série de droites d’isovaleur
(en pointillé), telles que les valeurs de z soient de plus en plus importantes, ont été tracées (voir
la figure ci-dessus).
Comme l’objectif est de minimiser z, l’optimum s’atteint en cherchant la droite d’isovaleur la
plus basse possible (au sens de la flèche) qui touche la région réalisable D. Dans cet exemple,
cette droite est celle la plus proche de l’origine et elle touche la région réalisable au point :
(x1 , x2 ) = (9, 3).
alors la valeur optimale z = 20 × 9 + 40 × 3 = 300.

Calcul de la solution optimale

Dans cet exemple, la solution optimale correspond au point d’intersection des deux droites
(D2) et (D3) d’équations respectives :
x1 + x2 = 12 (D2)
x1 + 3x2 = 18 (D3)
Après résolution de ce système d’équation, on obtient : x1 = 9, x2 = 9.

4. Autres exemples
Dans cette section on donne quelques exemples de résolution graphique de problèmes linéaires
relatifs au différents cas possibles.

4.1. Problème à solutions multiples

Reprenons le programme linéaire (P1 ) qui modélise le problème de l’entreprise UVW. On va
remplacer la fonction objectif z = 300 x1 + 500 x2 par z = 300 x1 + 200 x2 :


 max z = 300x1 + 200x2


 x1 6 4 (1)


(P3 ) 2x2 6 12 (2)
3x1 + 2x2 6 18 (3)






x1 > 0, x2 > 0 (4)


© Hachimi 2020 • Recherche Opérationnelle

3 Méthode graphique 8

La région réalisable est la même que celle du problème (P1 ). On trace la droite isovaleur z = 0
de la nouvelle fonction objectif. En déplaçant cette droite parallèlement, nous constatons que la
droite d’isoprofit correspondant au profit maximum touche la région réalisable en un segment.
x2
10 (D1)

8
(D2)
6

4
D
2
(D3)

O 2 4 6 8 x1

4.2. Problème impossible

On veut résoudre graphiquement le programme linéaire suivant :


 max z = 2x1 + x2


 −2x1 + x2 6 2 (1)


(P4 ) −x1 + 2x2 > 5 (2)
x1 + x2 6 5 (3)






x1 > 0, x2 > 0 (4)


La région réalisable associée à ce problème est vide L’intersection des demi-plans représentant
les contraintes est vide. Cela signifie qu’il y a incompatibilité entre les contraintes.
x2
10 (D1)

8
(D2)
6

2
(D3)

O 2 4 6 8 x1

© Hachimi 2020 • Recherche Opérationnelle

3 Méthode graphique 9

4.3. Problème avec solution non bornée

On veut résoudre graphiquement le programme linéaire suivant :


 max z = −x1 + 2x2


 x 65 (1)
1
(P4 )

 x1 − x 2 6 3 (2)


x1 > 0, x2 > 0 (4)


Sur la figure suivante, la région réalisable est la partie non borné colorée en gris.
x2
10 (D1)

8 (D2)

6 D
4

O 2 4 6 8 x1

On peut augmenter la valeur de la fonction objectif dans la direction de la flèche indéfiniment.

La valeur maximale de z est donc infinie. Par conséquent, le problème n’admet aucune solution
optimale.

© Hachimi 2020 • Recherche Opérationnelle