Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Un programme linéaire (PL), selon sa nature, peut être résolu des
manières diffé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 :
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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 différents cas de PL, suivant la nature de l’objectif
(max ou min) et des contraintes (inégalités, égalités ou mixtes).
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
1. Premier exemple : cas de maximisation
Reprenons l’exemple 4:
Produit 1 Produit 2 Capacité
(châssis aluminium) (châssis bois) disponible
(heures/produit) (heures/produit) (heures/sema
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 profit net?
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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
(P1 ) 2x2 ≤ 12
3x + 2x2 ≤ 18
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.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Représentation de la région admissible:
La première étape de la résolution consiste à représenter
graphiquement la région admissible.
Dans notre cas, c’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.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Lorsque l’on fait l’intersection des cinq demi-plans correspondant
aux cinq inégalités:
x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18 (5)
x≥ 0
x2 ≥ 0
on obtient le polyèdre de la figure 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 :
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
3x1 + 5x2 = k
Les points d’une de ces droites sont donc le lieu de tous les points
donnant la même valeur du profit, d’où le nom de droites
d’isovaleur (ou droites d’isoprofit) de la fonction objectif.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
On a 3x1 + 5x2 = k ⇒ x2 = −3 k
5 x1 + 5 .
Donc les droites ∆k ont la même pente (coefficient directeur)
p = − 35 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.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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 profit le plus grand, donc la
droite d’isoprofit la plus élevée.
- II 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.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Le point optimal x ∗ = (x1∗ , x2∗ ) se trouve à l’intersection des deux
droites D2 : x2 = 6 et D3 : 3x1 + 2x2 = 18. x ∗ vérifie 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.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
1.2 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 profit 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 profit 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).
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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?
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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érifient la contrainte de
positivité : x1 ≥ 0 et x2 ≥ 0.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
- 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
x1 + 4x2 ≥ 120
6x + 3x2 ≥ 180
1
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 figure ci-dessous) :
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
(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 .
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
La fonction objectif étant z = 1000x1 + 1000x2 , les droites
d’isovaleur ont la même pente égale à -1 . On remarque sur la
figure que celle qui réalise le coût minimal est la droite passant par
le sommet B. Ce dernier étant I’intersection des droites D1 et D3 ,
ses coordonnées vérifient 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
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
3. Cas particuliers 3.1 Région admissible bornée - une infinité de
solutions optimales:
Dans l’exemple 1, là solution optimale est uniqué 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 effet, supposons que l’on aie, sous les mêmes
contraintes, un objectif de la forme
max z ′ = 3x1 + 2x2
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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 figure 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).
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Région admissible bornée - Infinité de solutions
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
3.2 Région admissible non bornée - infinité 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 ′ = 2x1 + 4x2 avec les mêmes contraintes. Nous
aurons alors le nouveau PL
min z ′ = 2x1 + 4x2
x1 + 2x2 ≥ 90
x1 + 4x2 ≥ 120
6x + 3x2 ≥ 180
1
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 infinité de
solutions représentées par le segment joignant les points B(10; 40)
et C (60; 15).
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
3.3 Région admissible non bornée - solution optimale infinie :
Considérons le programme linéaire suivant:
max z = x1 + x2
2x1 + 3x2 ≥ 6
2x + x2 ≥ 4
1
x1 ≥ 0; x2 ≥ 0
En donnant à x1 et x2 des valeurs assez grandes les contraintes
seront toujours vérifiées. La valeur de la fonction objectif z peut
être augmentée indéfiniment. Par conséquent, z = +∞.
Graphiquement, on remarque sur la figure ci-dessous que la région
admissible n’est pas bornée et que les droites d’isovaleur peuvent
être déplacées à l’infinie en conservant toujours une intersection
avec la région admissible : le programme linéaire possède une
solution optimale infinie (aucune solution optimale finie).
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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 figure 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.
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
Recherche opérationnelle
Programmation Linéaire
Résolution des programmes linéaires: Méthode graphique
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
- solution optimale unique −→ sommet optimal unique du
polyèdre
- infinité 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
- solution optimale unique −→ sommet optimal unique
- infinité de solutions optimales −→ côté optimal du polyèdre
- aucune solution optimale finie (z = ∞)
