Cours de la

Recherche opérationnelle
Filière Economie et Gestion

Semestre 6

Pr. Anass TAHA Année universitaire 2021-2022

 Plan

1. Introduction à la RO

2. Programme linéaire et terminologie de base

3. Résolution graphique

4. La méthode du simplexe

5. La dualité et analyse de la sensibilité

Pr. Anass TAHA – 2022 2

3 – Résolution graphique d’un PL
 Introduction (1/1)

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 de résoudre le problème mathématique.

Pour résoudre un PL :

• Plusieurs algorithmes existent, dont le simplexe (prochaine partie)

• Pour des problèmes avec deux variables, on peut le résoudre graphiquement (aide à comprendre la
structure du problème)

Dans cette partie du cours, on examinera seulement les programmes linéaires à deux variables de décision.

Pr. Anass TAHA – 2022 4

 Résolution graphique (1/)
Problème linéaire à 2 variables

La formulation canonique d’un programme linéaire à 2 variables, peut prendre les deux formes suivantes :

Problème de maximisation Problème de minimisation

Pr. Anass TAHA – 2022 5

 Résolution graphique (2/)
Construction de la région réalisable

Chaque équation : 𝑎𝑖 𝑥1 + 𝑏𝑖 𝑥2 = 𝑐𝑖 (𝐷) définit une droite qui partage le plan en deux demi-plans P1 et P2
d’équation :
𝑃1 𝑎𝑖 𝑥1 + 𝑏𝑖 𝑥2 ≥ 𝑐𝑖
𝑃2 𝑎𝑖 𝑥1 + 𝑏𝑖 𝑥2 ≤ 𝑐𝑖

Pr. Anass TAHA – 2022 6

 Résolution graphique (3/)
Construction de la région réalisable

Chaque contrainte détermine l’un des deux demi-plans (P1) ou (P2) que l’on trouvera en vérifiant si un point
particulier (l’origine (0, 0) par exemple) est contenu dedans ou non.

Pr. Anass TAHA – 2022 7

 Résolution graphique (4/)
Construction de la région réalisable

L’intersection de tous les demi-plans correspondant aux contraintes constitue l’ensemble des points réalisables
(𝒟) ou la région réalisable : ce sont les solutions communes à toutes les contraintes.

Pr. Anass TAHA – 2022 8

 Résolution graphique (5/)
Construction de la région réalisable

Cette région (𝒟) est parfois vide ou non borné.

Région vide Région non bornée

Pr. Anass TAHA – 2022 9

 Résolution graphique (6/)
Recherche de la solution optimale

Nous venons de construire la région réalisable d’un programme linéaire à deux variable. Cet ensemble contient
un nombre infini de solutions réalisables.

 Il reste à repérer, parmi ces solutions réalisables celle(s) qui donne(nt) à la fonction objectif 𝑧 la meilleure
valeur.

Pr. Anass TAHA – 2022 10

 Résolution graphique (7/)
Recherche de la solution optimale

Définition : En fixant 𝑧 à une valeur 𝑝 choisie arbitrairement, on obtient la droite :

𝐷𝑝 𝑎0 𝑥1 + 𝑏0 𝑥2 = 𝑝
Cette droite est appelé droite d’iso-valeur de fonction 𝑧. Elle représente les points du plan qui donnent à 𝑧 la
valeur 𝑝.

On s’intéresse à la famille des droites (𝐷𝑝 ) (𝑝 paramètre). Ce sont toutes des droites parallèles de pente : −𝑎/𝑏,
que l’on peut écrire :

𝑎0 𝑝
𝑥2 = − 𝑥1 + (𝑠𝑖 𝑏0 ≠ 0)
𝑏0 𝑏0

, l’ordonné à l’origine de la droite (𝐷𝑝 ).

𝑝
Soit 𝑦 =
𝑏0

Pr. Anass TAHA – 2022 11

 Résolution graphique (8/)
Recherche de la solution optimale

Si 𝑏0 > 0, maximiser 𝑧 revient à maximiser 𝑝 et donc 𝑦𝑝 . Donc le maximum de 𝑧 est obtenu pour la droite ayant au
moins un point commun avec la région réalisable et ayant une ordonnée à l’origine la plus élevée possible.

Pr. Anass TAHA – 2022 12

 Résolution graphique (9/)
Recherche de la solution optimale

Si 𝑏0 < 0, maximiser 𝑧 revient à maximiser 𝑝 et donc à minimiser 𝑦𝑝 . Donc le maximum de 𝑧 est obtenu pour la
droite ayant au moins un point commun avec la région réalisable et ayant une ordonnée à l’origine la plus basse
possible.

Pr. Anass TAHA – 2022 13

 Application de la méthode graphique (1/8)
Exemple du problème de maximisation :

Un agriculteur souhaite produire le maximum (en poids) de légumes, sachant que le rendement est de 4𝑘𝑔/𝑚2 pour les
courgettes et 5𝑘𝑔/𝑚2 pour les navets. Le tableau résume les données su problème

Courgettes Navets Qte (𝑙)

engrais A 2 1 8
engrais B 1 2 7
antiparasites 0 1 3
Rendement (𝑘𝑔/𝑚2 ) 4 5

Pr. Anass TAHA – 2022 14

 Application de la méthode graphique (2/8)
Système d’axes

Une des conditions de la réussite d’une 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
cadran positif.

• Cette région s’appelle la région des solutions possibles du problème. Quadrant positif

Pr. Anass TAHA – 2022 15

 Application de la méthode graphique (3/8)

Représentation graphique des contraintes :

𝑥𝑛
Une des contraintes de ce problème est celle relative à l’engrais A : 2𝑥𝑐 + 𝑥𝑛 ≤ 8
2𝑥𝑐 + 𝑥𝑛 ≤ 8

• L’ensemble des solutions qui vérifient cette inégalité est le même

que celui qui vérifie 2𝑥𝑐 + 𝑥𝑛 = 8 et 2𝑥𝑐 + 𝑥𝑛 < 8.

• L’ensemble des solutions qui correspond à l’équation est

l’ensemble des points de la droite définie par 𝑥𝑛 = −2𝑥𝑐 + 8.

• Cette droite admet une valeur de la pente égale à –2 et intercepte

l’axe des ordonnées en 8 (voir figure).
𝑥𝑐

Pr. Anass TAHA – 2022 16

 Application de la méthode graphique (4/8)
Représentation graphique des contraintes :
𝑥𝑛
2𝑥𝑐 + 𝑥𝑛 ≤ 8

La 2è𝑚𝑒 contraintes de ce problème est celle relative à l’engrais B :

𝑥𝑐 + 2𝑥𝑛 ≤ 7

𝑥𝑐 + 2𝑥𝑛 ≤ 7

𝑥𝑐

Pr. Anass TAHA – 2022 17

 Application de la méthode graphique (5/8)
Représentation graphique des contraintes :
𝑥𝑛
2𝑥𝑐 + 𝑥𝑛 ≤ 8

𝑥𝑐 ≤ 3
La 3è𝑚𝑒
contraintes de ce problème est celle relative à l’engrais B :
𝑥𝑐 ≤ 3
𝑥𝑐 + 2𝑥𝑛 ≤ 7

𝑥𝑐

Pr. Anass TAHA – 2022 18

 Application de la méthode graphique (6/8)
Représentation graphique des contraintes :
𝑥𝑛

2𝑥𝑐 + 𝑥𝑛 ≤ 8

𝑥𝑐 ≤ 3

Le point 𝑥 = (1, 1) représente une solution réalisable du problème,

𝑥𝑐 + 2𝑥𝑛 ≤ 7
car il appartient à la région réalisable ( le polyèdre en vert). 𝑥 = (1, 1)

En d’autre terme 𝑥 = (1, 1) satisfait l’ensemble des contraintes du

problème
𝑥𝑐

Pr. Anass TAHA – 2022 19

 Application de la méthode graphique (7/8)
Optimiser l’objectif (max 𝑧)

𝑥𝑛
Les lignes de niveau {4𝑥𝑐 + 5𝑥𝑛 = 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒} sont des droites
parallèles

Interprétation économique :
Pour 𝑧 = 10, l’agriculteur produit 10𝑘𝑔/𝑚2 de légumes (courgette et
𝑥𝑐
navet confondus)

Pr. Anass TAHA – 2022 20

 Application de la méthode graphique (8/8)

la solution optimale correspond à la solution réalisable qui intercepte la

𝑥𝑛
droite à la plus grande valeur de z.
2𝑥𝑐 + 𝑥𝑛 ≤ 8

Elle est l’intersection des deux contraintes 2𝑥𝑐 + 𝑥𝑛 ≤ 8 et 𝑥𝑐 + 2𝑥𝑛 ≤ 7.

Une évaluation des coordonnées de ce point revient à résoudre le système
𝑥𝑐 ≤ 3
linéaire suivant :
𝑥∗
2𝑥 + 𝑥𝑛 ≤ 8 2
ቊ 𝑐 𝑥𝑐 + 2𝑥𝑛 ≤ 7
𝑥𝑐 + 2𝑥𝑛 ≤ 7

Elle correspond d’après le graphique au point 𝐱 ∗ = (𝟑, 𝟐).

3 𝑥𝑐
Donc la production optimale est de 6𝑘𝑔/𝑚2 de courgettes et 4𝑘𝑔/𝑚2 de
navets. Le poids total (la valeur de la fonction objectif) est égale à
z = 22𝑘𝑔/𝑚2 .

Pr. Anass TAHA – 2022 21

Polyèdre et points extrêmes (1/2)

Définition : Un polyèdre est un ensemble qui peut être décrit comme 𝑃 = {𝑥 ∈ ℝ𝑛 | 𝐴𝑥 ≥ 𝑏}, où 𝐴 est une
matrice 𝑚 × 𝑛 et 𝑏 un vecteur de ℝ𝑚
Note : l’ensemble admissible d’un programme linéaire est un polyèdre.

Définition : Un ensemble 𝑆 ⊂ ℝ𝑛 est convexe si pour tout 𝑥, 𝑦 ∈ 𝑆, et tout

𝜆 ∈ [0,1], on a 𝜆𝑥 + (1 − 𝜆)𝑦 ∈ 𝑆

Convexe Non
Convexe

Pr. Anass TAHA – 2022 22

 Polyèdre et points extrêmes (2/2)

Définition : Un point 𝑥 d’un ensemble convexe 𝑆 est un point extrême de 𝑆, s’il n’existe pas deux points
𝑦, 𝑧 ∈ 𝑆 t.q. 𝑥 = 𝜆𝑦 + (1 − 𝜆𝑧).

Soit 𝑃 un polyèdre, et soit 𝑥 ∗ ∈ 𝑃. Alors,

𝑥 ∗ est un point extrême ssi
𝑥 ∗ est un sommet ssi
𝑥 ∗ est une solution de base admissible

Pr. Anass TAHA – 2022 23

 Résolution par énumération (1/2)

On remarque que la solution optimale du problème

d’agriculture est un point extrême qui se trouve sur le bord
de l’ensemble des solutions (polyèdre convexe). Une telle
solution est dite solution réalisable de base.

Proposition : S’il en existe, il y a toujours une solution

optimale sur un sommet (point extrême) de la région des
solutions réalisable.

Corollaire : Pour trouver l’optimum, il ”suffit” d’examiner les

solutions réalisables de base (points extrêmes) de la région
réalisable et à calculer pour chaque point la valeur de la
fonction objectif.

Pr. Anass TAHA – 2022 24

 Résolution par énumération (2/2)

NOTE:
• En vert, la solution optimale.
• En rouge, les points qui ne satisfont pas les contraintes.

Pr. Anass TAHA – 2022 25

 Résolution graphique : cas spéciaux (1/4)

Problème avec solution non bornée

On peut augmenter la valeur de la fonction objectif dans la direction des flèches indéfiniment donc la solution
est non bornée.

Pr. Anass TAHA – 2022 26

 Résolution graphique : cas spéciaux (2/4)

Problème avec ensemble de solution réalisable vide

L’espace des solutions réalisables est vide, il est l’intersection des deux zones grises de la figure ci-dessus.

Pr. Anass TAHA – 2022 27

 Résolution graphique : cas spéciaux (3/4)

Problème avec solutions multiples

L’ensemble des points décrit par le segment [AB] représente les solutions optimales du problème linéaire.

Pr. Anass TAHA – 2022 28

 Résolution graphique : cas spéciaux (4/4)

Problème de dégénérescence

La solution optimale B(10,5) est dite dégénérée si trois contraintes concourent en ce point.

Pr. Anass TAHA – 2022 29

 Algorithme géométrique

1. Partir d’un point extrême x de la région réalisable

2. Déterminer une arête le long de laquelle l’objectif

augmente. S’il n’en existe pas, 𝑥 est optimal, STOP

3. Se déplacer le long de l’arête jusqu’au point

extrême 𝑦 suivant.

S’il n’existe pas, le problème est non borné, STOP,

Sinon, poser 𝑥 ← 𝑦 et revenir à l’étape 2

Pr. Anass TAHA – 2022 30

Fin de la partie 03