Chapitre 2

Méthode graphique

Université Hassan II de Casablanca

FSJES Ain Sebaa
LF MASS - S4
Pr. Abderrahim KADIRI

2020-2021
Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 1 / 32
 Méthode graphique Motivation

Un programme linéaire (PL), selon sa nature, peut être résolu des manières
diérentes :

1 Méthode graphique :
C'est une représentation géométrique plane dans le cas de deux
variables.

2 Algorithme du Simplexe :
Cet algorithme est recommandé lorsque le nombre de variables est
quelconque et il est très utilisé dans la pratique.

3 Recensement des sommets de la région admissible :

Cette méthode est possible tant que le nombre des sommets n'est pas
assez grand, c'est-à-dire, le nombre des variables et des contraintes
reste très limité. On prend le sommet qui optimise la fonction objectif.

Dans ce chapitre, nous allons présenter la méthode graphique en étudiant

les diérents cas de PL, suivant la nature de l'objectif (max ou min) et des
contraintes (inégalités, égalités ou mixtes).

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 2 / 32

 Méthode graphique Premier exemple : cas de maximisation

1. Premier exemple : cas de maximisation

Reprenons l'exemple 1 du chapitre 1 :

Produit 1 Produit 2 Capacité

(châssis aluminium) (châssis bois) disponible
(heures/produit) (heures/produit) (heures/semaine)
Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
Marge 3 UM 5 UM
La question qui se pose est la suivante : combien faut-il produire de chassis
de chaque type par semaine pour maximiser le prot net ?

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 3 / 32

 Méthode graphique Premier exemple : cas de maximisation

1.1 Modélisation du problème :

On a déjà montré que ce problème se ramène à résoudre le PL suivant :


 max z = 3x1 + 5x2
 x1 ≤ 4 Contrainte capacité dans l'atelier 1


(P1 ) 2x2 ≤ 12 Contrainte capacité dans l'atelier 2
3x + 2x2 ≤ 18

Contrainte capacité dans l'atelier 3
 1



x1 ≥ 0 ; x2 ≥ 0

où x1 est le nombre de châssis en aluminium et x2 est le nombre de châssis

en bois.

1.2 Résolution graphique :

Représentation de la région admissible :
Dans notre cas, la région admissible est l'ensemble des points (x1 , x2 )
satisfaisant les inégalités de (P1 ) .
Graphiquement une inégalité telle que 3x1 + 2x2 ≤ 18 correspond à un
demi-plan limité par la droite d'équation : 3x1 + 2x2 = 18.
Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 4 / 32
 Méthode graphique Premier exemple : cas de maximisation

Lorsque l'on fait l'intersection des cinq demi-plans correspondant aux cinq
inégalités :
4 (1)

 x1 ≤
2 x2 12 (2)

≤



3x1 + 2x2 ≤ 18 (3)


 x 1 ≥ 0 (4)
0 (5)

 x2 ≥
on obtient le polyèdre de la gure ci-dessous.

Représentation de l'objectif :
On va considérer des valeurs successives de l'objectif : z = k.
Ce qui correspond graphiquement à des droites parallèles ∆k d'équation :

3x1 + 5x2 = k

Les points d'une de ces droites sont donc le lieu de tous les points donnant
la même valeur du prot, d'où le nom de droites d'isovaleur (ou droites
d'isoprot) de la fonction objectif.
Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 5 / 32
 Méthode graphique Premier exemple : cas de maximisation

Représentation graphique de la région admissible

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 6 / 32

 Méthode graphique Premier exemple : cas de maximisation

−3 k
On a 3x1 + 5x2 = k ⇒ x2 = x1 + .
5 5
3
Donc les droites ∆k ont la même pente (coecient directeur) p=−
5

Prenons par exemple les valeurs k = 0 , k = 15 et k = 30 .

La droite ∆0 d'isovaleur k = 0, c-à-d : 3x1 + 5x2 = 0 , passe par les
points (0, 0) et (5, −3).
La droite ∆15 , c-à-d : 3x1 + 5x2 = 15 , passe par les points (5, 0) et
(0, 3).
Tandis que La droite ∆30 , c-à-d : 3x1 + 5x2 = 30 , passe par les points
(10, 0) et (0, 6).
On obtient donc des droites parallèles qui montent vers le haut si k
augmente.

Ainsi, on conclut que pour maximiser z, il faut prendre la droite d'isovaleur

la plus élevée.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 7 / 32

 Méthode graphique Premier exemple : cas de maximisation

Détermination du point optimal :

On cherche le point de la région admissible qui maximise la fonction
objectif z = 3x1 + 5x2 .
Ce point sera déterminé graphiquement en tenant compte des deux
conditions suivantes :

Il sera situé sur la droite qui donne le prot le plus grand, donc la
droite d'isoprot la plus élevée.

Il faut se restreindre à la région admissible.

Conclusion :
Pour maximiser l'objectif, il faut prendre la droite d'isovaleur la plus élevée
(qui donne la plus grande valeur à l'objectif ) et qui touche encore la région
admissible. Le point de contact est un point optimal.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 8 / 32

 Méthode graphique Premier exemple : cas de maximisation

Détermination algébrique du point optimal :

Le point optimal x ∗ = (x1∗ , x2∗ ) se trouve à l'intersection des deux droites
D2 : x 2 = 6 et D3 : 3x1 + 2x2 = 18.
x∗ vérie donc : 
x2 = 6
3x1 + 2x2 = 18

D'où
x ∗ = (2 , 6)
et la valeur maximale de la fonction objectif est : z ∗ = 3x1∗ + 5x2∗ = 36
Remarque :
Pour un calcul exact de la solution optimale, il faut commencer tout
d'abord par déterminer les droites (contraintes) qui se rencontrent au point
optimal, et ensuite résoudre le système d'équations relatives à ces droites.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 9 / 32

 Méthode graphique Premier exemple : cas de maximisation

Représentation graphique de la solution optimale

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 10 / 32

 Méthode graphique Premier exemple : cas de maximisation

Méthode pratique pour déterminer le point optimal :

1 Calculer la pente des droites d'isovaleur ∆k :

−3 k 3
3x1 + 5x2 = k =⇒ x2 = x1 + =⇒ p = −
5 5 5
2 Tracer la droite d'isovaleur ∆0 :

−3
Si k =0 alors ∆0 a pour équation 3x1 + 5x2 = 0 ⇐⇒ x2 = x1
5
x1 = 0 =⇒ x2 = 0 ; x1 = 5 =⇒ x2 = −3 ; x1 = 50 =⇒ −30.
Ainsi de suite, on obtient au moins 2 points permettant de tracer ∆0 .
3 Tracer ensuite manuellement et susamment des droites parallèles à
∆0 (droites d'isovaleur ∆k ), dirigées vers le haut.

4 Localiser la droite d'isovaleur la plus élevée, de telle sorte à ne pas

sortir de la région admissible. Le point d'intersection de cette dernière
droite et la région admissible est le point optimal.

5 Déterminer algébriquement les coordonnées du point optimal.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 11 / 32
 Méthode graphique Premier exemple : cas de maximisation

1.3 Interprétation économique :

La solution optimale est x ∗ = (2 ; 6), donc il faut produire 2 châssis en
aluminium et 6 châssis en bois pour réaliser un prot net maximal égal à
36 UM.

A l'optimum, la deuxième contrainte et la troisième contrainte sont

saturées mais la première contrainte ne l'est pas, car :

 ∗
 x1 = 2 < 4
∗
2x = 2 × 6 = 12
 2∗ ∗
3x1 + 2x2 = (3 × 2) + (2 × 6) = 18

Donc, pour réaliser le prot net maximal, il faut utiliser toute la capacité
disponible dans l'atelier 2 et l'atelier 3 (plein emploi), et il restera une
capacité dans l'atelier 1 (sous- emploi) égale à :

4 − x1∗ = 2 (heures par semaine).

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 12 / 32

 Méthode graphique Deuxième exemple : cas de minimisation

2. Deuxième exemple : cas de minimisation

Considérons maintenant un exemple où la fonction objectif doit être

minimisée :

Une compagnie possède deux mines de charbon A et B. La mine A produit

quotidiennement 1 tonne de charbon de qualité supérieure, 1 tonne de
qualité moyenne et 6 tonnes de qualité inférieure. La mine B produit par
jour 2, 4 et 3 tonnes de chacune des trois qualités. La compagnie doit
produire au moins 90 tonnes de charbon de qualité supérieure, 120 tonnes
de qualité moyenne et 180 tonnes de qualité inférieure.

Sachant que le coût de production journalier est le même dans chaque

mine, soit 1000 UM, quel est le nombre de jours de production dans la mine
A et dans la mine B qui minimisent le coût de production de la compagnie ?

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 13 / 32

 Méthode graphique Deuxième exemple : cas de minimisation

2.1 Modélisation du problème

variables de décision :

x1 : nombre de jours de travail dans la mine A

x2 : nombre de jours de travail dans la mine B

Mise en équations des contraintes :

La mine A produit par jour 1 tonne de charbon de qualité supérieure,

tandis que la mine B en produit 2 tonnes. Comme la compagnie doit
satisfaire à la demande de 90 tonnes de charbon de qualité supérieure,
la première contrainte s'écrit :

x1 + 2x2 ≥ 90
De même, pour les deux autres qualités de charbon, on obtient :

x1 + 4x2 ≥ 120
6x1 + 3x2 ≥ 180
En plus, x1 et x2 , étant des nombres, vérient la contrainte de
positivité : x1 ≥ 0 et x2 ≥ 0.
Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 14 / 32
 Méthode graphique Deuxième exemple : cas de minimisation

Fonction objectif :

Pour minimiser le coût de production de la compagnie, on doit

minimiser la fonction objectif : z = 1000x1 + 1000x2

Le programme linéaire qui modélise ce problème s'écrit donc :



 min z = 1000x1 + 1000x2


 x1 + 2x2 ≥ 90 Qté de charbon de qualité supérieure


x1 + 4x2 ≥ 120 Qté de charbon de qualité moyenne
 6x1 + 3x2 ≥ 180


 Qté de charbon de qualité inférieure


x1 ≥ 0 ; x2 ≥ 0


2.2 Résolution graphique

La région admissible est un polyèdre non borné qui a pour sommets les
points (voir gure ci-dessous) :

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 15 / 32

 Méthode graphique Deuxième exemple : cas de minimisation

1 A (0 ; 60) : intersection de la droite

D3 d'équation 6x1 + 3x2 = 180
avec l'axe x2 ;
2 B (10 ; 40) : intersection des deux droites D3 et (D1 : x1 + 2x2 = 90) ;
3 C (60 ; 15) : intersection des deux droites D1 et (D2 : x1 + 4x2 = 120) ;
4 D (120 ; 0) : intersection de la droite D2 avec l'axe x1 .
La fonction objectif étant z = 1000x1 + 1000x2 , les droites d'isovaleur ont
la même pente égale à −1. On remarque sur la gure que celle qui réalise
le coût minimal est la droite passant par le sommet B. Ce dernier étant
l'intersection des droites D1 et D3 , ses coordonnées vérient le système :

x1 + 2x2 = 90
6x1 + 3x2 = 180

D'où
x ∗ = (10 ; 40)

et la valeur minimale de la fonction objectif est :

z ∗ = 1000x1∗ + 1000x2∗ = 50000

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 16 / 32
 Méthode graphique Deuxième exemple : cas de minimisation

Graphique exemple 2

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 17 / 32

 Méthode graphique Deuxième exemple : cas de minimisation

2.3 Interprétation économique

On a x ∗ = (10 ; 40) et z ∗ = 50000, donc il faut 10 jours de travail dans la
mine A et 40 jours de travail dans la mine B à la compagnie pour un coût
de production minimal de 50000 UM.

A l'optimum, la première contrainte et la troisième contrainte sont saturées

mais la deuxième contrainte ne l'est pas :

 ∗
 x1 + 2x2∗ = 10 + (2 × 40) = 90
x ∗ + 4x2∗ = 10 + (4 × 40) = 170 > 120
 1∗ ∗
6x1 + 3x2 = (6 × 10) + (3 × 40) = 180

Pour minimiser le coût de production, la compagnie devra utiliser toutes les

quantités de charbon de qualités supérieure et inférieure, et il lui restera un
stock de charbon de qualité moyenne égal à 170 − 120 = 50 tonnes.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 18 / 32

 Méthode graphique Cas particuliers

3. Cas particuliers

3.1 Région admissible bornée - une innité de solutions optimales :

Dans l'exemple 1, la solution optimale est unique et correspond à un
sommet (optimal) de la région admissible (bornée).

En général, il existe des cas où tout un côté (segment) de la région

admissible est optimal. En eet, supposons que l'on aie, sous les mêmes
contraintes, un objectif de la forme :

max z 0 = 3x1 + 2x2

Il est facile, dans ce cas, de voir que les droites d'isovaleur de l'objectif
seraient toutes parallèles à la droite D3 d'équation :

3x1 + 2x2 = 18
On en déduit (voir gure ci-dessous) que tout le segment joignant le
sommet (2, 6) au sommet (4, 3) est optimal. Dans ce cas, on pourra choisir
comme solution optimale celle qui correspond au sommet (2, 6) ou (4, 3).
Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 19 / 32
 Méthode graphique Cas particuliers

Région admissible bornée - innité de solutions

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 20 / 32

 Méthode graphique Cas particuliers

3.2 Région admissible non bornée - innité de solutions :

Dans l'exemple 2, la région admissible est un polyèdre non bornée et la
solution optimale est unique et atteinte en un sommet du polyèdre.

Supposons maintenant que l'on aie à minimiser la fonction objectif

z 0 = 2x1 + 4x2 avec les mêmes contraintes.
Nous aurons alors le nouveau PL :

min z 0 = 2x1 + 4x2




 x1 + 2x2 ≥ 90


x1 + 4x2 ≥ 120
 6x1 + 3x2 ≥ 180



x1 ≥ 0 ; x2 ≥ 0


Les droites d'isovaleur seront toutes parallèles à la droite D1 d'équation

x1 + 2x2 = 90. Par suite, nous aurons une innité de solutions représentées
par le segment joignant les points B (10 ; 40) et C (60 ; 15).

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 21 / 32

 Méthode graphique Cas particuliers

Problème non borné - innité de solutions

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 22 / 32

 Méthode graphique Cas particuliers

3.3 Région admissible non bornée - solution optimale innie :

Considérons le programme linéaire suivant :



 max z = x1 + x2
2x1 + 3x2 ≥ 6

 2x1 + x2 ≥ 4

x1 ≥ 0 ; x2 ≥ 0


En donnant à x1 et x2 des valeurs assez grandes les contraintes seront

toujours vériées. La valeur de la fonction objectif z peut être augmentée
indéniment. Par conséquent, z = +∞.
Graphiquement, on remarque sur la gure ci-dessous que la région
admissible n'est pas bornée et que les droites d'isovaleur peuvent être
déplacées à l'innie en conservant toujours une intersection avec la région
admissible : le programme linéaire possède une solution optimale innie
(aucune solution optimale nie) .

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 23 / 32

 Méthode graphique Cas particuliers

Région admissible non bornée - solution innie

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 24 / 32

 Méthode graphique Cas particuliers

3.4 Région admissible vide - aucune solution :

Considérons maintenant le programme linéaire :



 max z = 2x1 + 3x2
x1 + x2 ≤ 1

x − x2 ≥ 2
 1


x1 ≥ 0 ; x2 ≥ 0

Sur la gure ci-dessous, nous remarquons que la région admissible est vide
et par suite le programme linéaire n'admet aucune solution optimale.

Algébriquement, d'après le système des contraintes, on a :

 
 x1 + x2 ≤ 1  x1 + x2 ≤ 1
x1 − x2 ≥ 2 ⇐⇒ −x1 + x2 ≤ −2 =⇒ 2x2 ≤ −1
x1 ≥ 0 ; x2 ≥ 0 x1 ≥ 0 ; x2 ≥ 0
 

ce qui contredit la contrainte x2 ≥ 0. Et par conséquent, l'ensemble des

solutions réalisables est vide.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 25 / 32

 Méthode graphique Cas particuliers

Région admissible vide (pas de solution)

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 26 / 32

 Méthode graphique Cas particuliers

En résumé :

L'ensemble réalisable (ou région admissible) d'un programme linéaire est

toujours un polyèdre de Rn (intersection de demi-espaces) qui peut être :

vide −→ pas de solution

non vide et bornée

I solution optimale unique −→ sommet optimal unique du polyèdre

I innité de solutions optimales −→ côté optimal du polyèdre, tous les
points de ce côté sont des solutions optimales
non vide et non bornée

I solution optimale unique −→ sommet optimal unique

I innité de solutions optimales −→ côté optimal du polyèdre
I aucune solution optimale nie (z = ∞)

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 27 / 32

 Méthode graphique Ensembles convexes

4. Ensembles convexes

Dénition
Un ensemble E est convexe si et seulement si pour toute paire de points A
et B de cet ensemble, le segment de droite joignant ces deux points est
entièrement inclus dans l'ensemble E. Autrement dit :

∀x, y ∈ E , ∀α ∈ [0 , 1] αx + (1 − α)y ∈ E

Un point extrême d'un ensemble convexe est un point qui ne peut jamais
être entre deux points de cet ensemble.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 28 / 32

 Méthode graphique Ensembles convexes

Propriétés
L'intersection de plusieurs ensembles convexes est un ensemble
convexe.

L'ensemble des solutions d'un système d'inéquations linéaires est un

ensemble convexe. Plus exactement, c'est l'intersection de
demi-espaces de Rn et correspond à un polyèdre convexe
(voir gure ci-dessous).

Lorsque les demi-espaces sont des demi-plans de R2 , l'intersection est

un polygone convexe.

En particulier, l'ensemble réalisable (région admissible) non vide d'un

programme linéaire est un ensemble convexe dont les côtés
représentent les contraintes linéaires du problème. Il est :
I soit un ensemble polyédrique convexe non borné,
I soit un polyèdre convexe borné (polygone dans le cas R2 ).

Si le PL admet des solutions optimales, alors au moins une solution

optimale est située sur un sommet (point extrême) du polyèdre.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 29 / 32

 Méthode graphique Ensembles convexes

Exemples de polyèdres

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 30 / 32

 Méthode graphique Exercices d'application

Exercice 1 :
Une usine fabrique deux modèles de bureaux M1 et M2 . Les marges
unitaires, les temps de fabrication de chacun des produits dans chacun des
ateliers ainsi que les capacités disponibles de ces ateliers sont donnés au
tableau suivant :

M1 M2 Capacité disponible
Atelier 1 (sciage) 1 2 20
Atelier 2 (assemblage) 2 1 22
Atelier 3 (sablage) 1 1 12
Marge 300 UM 200 UM

La question que se pose la direction de l'usine est la suivante : combien

faut-il produire de bureaux de chaque modèle pour maximiser son prot ?

1 Modéliser le problème sous forme d'un programme linéaire.

2 Résoudre graphiquement ce programme linéaire.

3 Donner une interprétation économique des résultats obtenus.

Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 31 / 32

 Méthode graphique Exercices d'application

Exercice 2 :
Un groupe d'étudiants organise un petit déjeuner pendant la pause de 10
heures. Pour pouvoir satisfaire la demande, ils doivent disposer au
minimum de 90 croissants, de 60 beignets et de 120 pains au chocolat.
Un supermarché propose 2 lots :

le lot A coûte 10 UM et il est composé de : 3 croissants, 1 beignet et

1 pain au chocolat,
le lot B coûte 20 UM et contient : 1 croissant, 1 beignet et 4 pains
au chocolat.

La question qui se pose est la suivante : combien de lots A et de lots B

doivent être achetés pour satisfaire la demande avec un coût minimum ?
1 Écrire le programme linéaire (P) modélisant ce problème.
2 Résoudre graphiquement (P).
3 Donner une interprétation économique des résultats trouvés en 2.
4 Combien de lots A et de lots B devraient être achetés s'ils avaient le
même prix 10 UM ? Justier votre réponse.
Pr. KADIRI - FSJES-AS Modélisation et optimisation MASS - S4 2020-2021 32 / 32