Chapitre III : La méthode graphique
Avant toute chose indiquons que la méthode de résolution graphique s’applique plus
particulièrement aux problèmes comportant seulement deux variables et .
I. Position du problème :
Le problème est (Max ou Min) = + ; ≠ 0 et ≠ 0 sous les contraintes :
+ ≤=≥
+ ≤=≥
…. . ……… …….
Et ≥0 ; : = 1,2, … …
II. Les étapes de la résolution graphique :
1. Le plan et le domaine plan :
a. Le plan :
Chaque équation, + = , définit une droite qui partage le plan en
deux demi-plans : et
:
+ ≥
:
+ ≤
b. Le domaine des solutions réalisables
L’intersection de tous les demi-plans, correspondant aux contraintes, fournie un domaine
plan appelé le domaine des solutions réalisables ou domaine admissible que l’on note D .
1
2. Famille des droites parallèles et tableau des solutions :
a. La famille des droites parallèles :
On a = + , pour cela on s’intéresse aux familles des droites ( ) tel
que : + = (k variable).
Ce sont des droites de pente qui peuvent s’écrire comme : = + ; ≠0
b. Le tableau des solutions :
Parmi les solutions réalisables, on cherche celle qui nous donne le point optimum de la
fonction objectif. Voir le tableau suivant :
Point extrême ou sommet Valeur de la fonction objectif
A( . ; . ) Z=
B( . ; . ) ∗
=…
C( . ; . ) Z=
.
.
III. Exemples d’application :
1/ Exemple N°1 (l’exemple du restaurateur) :
Un restaurateur a constaté que sa clientèle préfère les assortiments de coquillages et qu’il
peut offrir indifféremment.
Les assiettes à 8 dh contenant 5oursins, 3 praires et 1 huître.
Les assiettes à 6 dh contenant 3 oursins, 3 praires et 3 huîtres.
Il dispose de 30 oursins, 24 praires et 18 huîtres.
Comment doit-il les disposer pour réaliser la recette maximale ?
2
Solution : Visualisons le problème à partir du tableau suivant :
Oursins Praires Huîtres
Assiettes à 8 dh 5 3 1
Assiettes à 6 dh 3 3 3
Quantités disponibles 30 24 18
Soient : : à ;
: ′ à .
Max = +
+ ≤ ( )
S/c : + ≤ ( )
+ ≤ ( )
≥0 ≥0
(0,10)
( : ≤) =− +
(6,0)
( : ≤) =− + (0,8)
(8,0)
( : ≤) =− + (0,6)
(3,5)
3
Points extrêmes (sommets) La valeur de la fonction objectif
A (0,6) Z = 36
B(3,5) ∗
=
C(6,0) Z = 48
2/ Exemple N°2 :
Supposons qu’une entreprise produise les biens x et y, chaque unité de bien x nécessite 1L (L :
travail), 3K (K : capital) et 1R (R : ressources) pour être produite.
Chaque unité de bien y nécessite 0,5L, 3K et 3R pour être produite.
L’entreprise ne peut pas utiliser plus de 8L, 30K et 24R. Sa marge de profit (la recette nette) est
de 4 Dhs par unité de x et de 3 Dhs par unité de y.
1- Exprimez ces données sous forme d’un programme linéaire (PL) (forme canonique)
2- Donnez la forme standard de ce PL.
3- Montrez sur un graphique le domaine D des solutions réalisables.
4- Donner la solution optimale
Solution :
Soient : : é ;
: é .
Visualisons le problème à partir du tableau suivant :
L K R
1 3 1
0,5 3 3
Capacité maximale 8 30 24
4
2.1 La forme canonique d’un PL :
Max =4 +3
Sous contraintes :
+ , ≤ ( )
S/c : + ≤ ( )
+ ≤ ( )
≥0 ≥0
2.2 La forme standard d’un PL
Max =4 +3 +0 +0 +0
+ , + +0 +0 =8
S/c : + + 0 + 1 + 0 = 30
+ + +0 + 0 + 1 = 24
≥ 0, ≥ 0, ≥ 0, ≥ 0 et ≥0
2.3 Le graphique du domaine D des solutions réalisables :
(0,16)
( : ≤) =− +
(8,0)
(0,10)
( : ≤) =− +
(10,0)
( : ≤) =− + (0,8)
(3,7)
5
Tableau des solutions
Points extrêmes (sommets) La valeur de la fonction objectif
A (0,8) Z=24
B(3,7) Z=33
C(6,4) ∗
=
D(8,0) Z=32
IV. Exercices :
Exercice 1 : Soit à résoudre le programme linéaire suivant :
Min Z= +
4 + 3 ≥ 9000
⎧ + 2 ≥ 4000
⎪
≤ 6400
S/c :
⎨ ≤ 4400
⎪ ≥0
⎩ ≥0
Solution :
Min Z= +
4 + 3 ≥ 9000 ( )
⎧ + 2 ≥ 4000 ( )
⎪
≤ 6400 ( )
S/c :
⎨ ≤ 4400 ( )
⎪ ≥0
⎩ ≥0
6
Le graphique du domaine des solutions réalisables :
(0,3000)
( : ≥) =− + ; (300,2500)
(0,2000)
( : ≥) =− + ; (2000,6000)
( : ≤) =
( : ≤) = .
Points extrêmes Valeur de la fonction objectif
A(0 , 3000) Z = 2 400 000
∗
B(1200,1600) =
C(4000 , 0) Z = 4 000 000
D(6400 , 0) Z = 6 400 000
E(6400 , 4400) Z = 9 920 000
F(0 , 4400) Z = 3 520 000
7
Exercice 2 : Soit à résoudre le programme linéaire suivant :
Max Z=3 +2
− ≤
S/c : + ≥
≥ ≥
Solution:
Max Z=3 +2
− ≤ ( )
S/c : + ≥ ( )
≥ ≥
(2,1)
( : ≥) = −
(1,0)
( : ≥) =− + (0,3)
(3,0)
Il nous apparait clairement à partir du graphique qu’aussi loin que l’on déplace l’hyperplan
(Z=3 + 2 ) dans le sens des Z croissantes, il n’y’a pas de programme optimal fini.
8
Exercice 3 : Trouver la solution optimale du PL suivant
Max = +
− + ≤
S/c : + ≤
≤
≥ ≥
Solution:
Max = +
− + ≤ ( )
S/c : + ≤ ( )
≤ ( )
≥ ≥
(0,1)
( : ≤) = +
(1,3)
(0,3)
( : ≤) + = = −
(3,0)
9
(0,0)
Z=0 3 +2 = 0 =−
(2, −3)
Tableau des solutions
Points extremes La valeur de la fonction objectif
A(0 , 1) Z=2
2 7
B , Z = 6,66
3 3
∗
C(2 , 1) =
D(2 , 0) Z=6
Exercice 4 : Soit à optimiser :
Max Z= +
− + , ≤
S/c : + ≤
≤
≥ ≥
Solution :
Max Z= +
− + , ≤ ( )
S/c : + ≤ ( )
≤ ( )
≥ ≥
10
( : ≤): = +
( : ≤): = −
Tableau des solutions
Points extremes Valeur de la fonction économique
A(0 , 1) Z=1
B , Z* = 3
C(2 , 1) Z=3
D(2 , 0) Z=2
11
On trouve ici qu’ il n’y’a pas un sommet comme solution optimale, mais l’ensemble de points
du segment [B,C]. Les deux points B et C sont deux programmes optimaux extrémaux et toute
combinaison linéaire convexe de ces points est aussi un programme optimal (non extrémal).
Une fonction est dite convexe si et seulement si :
( +[ − ] )≤ ( )+( − ) ( ) ; Avec ]0,1[.
Exemple :
Soit : 0 < < 1.
∗
On a: = . + (1 − ).
= (2 , 1) + (1 − ) ,
= 2 + (1 − ) + + (1 − ))
∗
Si = alors = , Z=3
Exercice 5 :
Min = −
⎧ + ≥ 8
⎪− +8 ≤ 40
S/c : ≥8
⎨
⎪ ≤8
⎩ ≥0 ≥0
Solution :
Min = −
⎧ + ≥ 8 ( )
⎪− + 8 ≤ 40 ( )
S/c : ≥8 ( )
⎨
⎪ ≤8 ( )
⎩ ≥0 ≥0
12
(0,8)
( ≥): + =8 =8− (2,7)
(0,5)
( ≥):− + 8 =40 =5+ (8,6)
Tableau des solutions
Points extrêmes Valeur de la fonction objectif
A(16 , 0) Z = 16
B(8 , 4) Z=4
C(8 , 6) Z* = 2
D(24 , 8 ) Z = 16
13
Exercice 6 :
Max = +
6≥ 0 −
⎧ ≤ 12
⎪
S/c : 2 + ≤ 60
⎨ 4 − ≤ 24
⎪
⎩ ≥0 ≥0
Solution :
Max = +
6 − ≥ 0 ( )
⎧ ≤ 12
⎪ ( )
S/c : 2 + ≤ 60 ( )
⎨4 − ≤ 24 ( )
⎪
⎩ ≥0 ≥0
(0,0)
( :≤ ) =6 (1,6)
(6,12)
( :≤ ) = 60 − 8
(7,4)
( :≥ ) =4 − 24 (6,0)
(7,4)
14
Tableau des solutions
Points extrêmes Valeur de la fonction objectif
A(0 , 0) Z=0
B(2 , 12) Z = 56
C(6 , 12) Z* = 120
D(7 , 4 ) Z = 120
D(6 , 0 ) Z = 96
15
