Notes de cours : Recherche Opérationnelles et

Optimisation

Faculté des Sciences Agadir

Département d’informatique
Licence Informatique : IA
Draft

Version 0.1

Prof. A. F El Ouafdi

Last updated : 5 mars 2025

Table des matières

1 Rappels mathématiques 3
Formulation mathématique (Modélisation) . . . . . . . . . . . . . . . . . . 3
1.1.1 Interprétation du gradient et du Hessien . . . . . . . . . . 5

2 Éléments sur la programmation linéaire 7

Formulation mathématique (Modélisation) . . . . . . . . . . . . . . . . . . 7
Résolution graphique du problème d’optimisation . . . . . . . . . . . . . . 15
2.2.1 Méthode graphique (cas de deux variables) . . . . . . . . . 15
2.2.2 Représentation graphique du domaine réalisable . . . . . 16
2.2.3 Représentation graphique de la fonction objectif . . . . . . 18
2.2.4 Résolution graphique du problème d’optimisation . . . . 19
2.2.5 Tracé initial des droites d’isoprofit . . . . . . . . . . . . . . 19
2.2.6 Translation parallèle des droites d’isoprofit . . . . . . . . . 21

3 Optimisation sans contraintes 52

Algorithme de Newton descente de gradient explicite . . . . . . . . . . . 57
Méthode de Descente Général . . . . . . . . . . . . . . . . . . . . . . . . . 61
Méthode de Recherche de Ligne Exacte . . . . . . . . . . . . . . . . . . . . 64
Exemple numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4.1 La descente de gradient stochastique (SGD) : . . . . . . . . 69

4 Recherche opérationnelle 79
Algorithmes sur les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.1.1 Recherche en Largeur (BFS) pour un Graph . . . . . . . . . 82
Fonctionnement de l’Algorithme BFS . . . . . . . . . . . . . . . . . . . . . . 83
Problème du flot maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3.1 Définition d’un réseau . . . . . . . . . . . . . . . . . . . . . 84
4.3.2 Flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

1
Short title of document Table des matières

Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4.1 Pseudo-code de l’algorithme de Ford-Fulkerson . . . . . . 85
4.4.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Problème du plus court chemin sur un graphe : algorithme de Dijkstra . . 89
4.5.1 Principe de l’algorithme de Dijkstra . . . . . . . . . . . . . 89
4.5.2 Exemple d’application de l’algorithme de Dijkstra :dis-
tance entre la ville A et la ville J . . . . . . . . . . . . . . . . 90
4.5.3 Présentation sous forme de tableau . . . . . . . . . . . . . . 94

5 ORDONNANCEMENT : La Méthode PERT et diagramme de GANTT

98
Représentation graphique des étapes et des tâches dans un réseau . . . . . 100
5.1.1 Types des Tâches : . . . . . . . . . . . . . . . . . . . . . . . 100
Tableau de niveaux : Détermination des niveaux des tâches pour la réali-
sation d’un réseau PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.2.1 Exemple de détermination des niveaux . . . . . . . . . . . 106
5.2.2 Construction du tableau de niveaux . . . . . . . . . . . . . 107
5.2.3 Interprétation du tableau de niveaux . . . . . . . . . . . . . 107
GESTION DE PROJET : Diagramme de Gantt . . . . . . . . . . . . . . . . 110
Exemple d’un diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . 112

2
Chapitre 1

Rappels mathématiques

L’optimisation est une discipline essentielle en ingénierie pour l’estimation de

paramètres, l’analyse économique et l’étude de systèmes chimiques. Ce chapitre
présente quelques rappels sur la continuité, la différentiabilité, la convexité, et
développe les conditions d’optimalité locale du premier et du second ordre, avec
des exemples et l’introduction aux algorithmes itératifs.

※ Formulation mathématique (Modélisation)

Définition 1.1.1. Une fonction 𝑓 (𝑥) : R𝑛 → R est continue dans R𝑛 si, pour
chaque point 𝑥¯ et pour tout 𝜀 > 0, il existe une valeur 𝛿 > 0 telle que

∥𝑥 − 𝑥∥
¯ < 𝛿 =⇒ ∥ 𝑓 (𝑥) − 𝑓 (𝑥)∥
¯ < 𝜀,

et donc, lim𝑥→𝑥¯ 𝑓 (𝑥) = 𝑓 (𝑥).

¯ Notez que le graphique en contours en bas à gauche
de la Figure 2.4 montre que 𝑓 (𝑥) est discontinue.
Définition 1.1.2. Une fonction continue 𝑓 (𝑥) : R → R𝑛 est Lipschitz continue
dans R𝑛 si, pour tous points 𝑥, 𝑦 ∈ R𝑛 , il existe un 𝐿 > 0 fini tel que

∥ 𝑓 (𝑥) − 𝑓 (𝑦)∥ ≤ 𝐿∥𝑥 − 𝑦∥.

Définition 1.1.3. Soit 𝛾(𝜉) une fonction scalaire d’une variable scalaire 𝜉. En
supposant que la limite existe, la première dérivée est définie par
𝑑𝛾 𝛾(𝜉 + 𝜀) − 𝛾(𝜉)
= 𝛾′(𝜉) := lim
𝑑𝜉 𝜀→0 𝜀
et la seconde dérivée est définie par
𝑑2 𝛾 ′′ 𝛾′(𝜉 + 𝜀) − 𝛾′(𝜉)
= 𝛾 (𝜉) := lim .
𝑑𝜉2 𝜀→0 𝜀
3
Short title of document Formulation mathématique (Modélisation)

Définition 1.1.4. Définissons le vecteur unitaire 𝑒 𝑖 = [0, 0, . . . , 1, . . . , 0] (c’est-

à-dire, un "1" à la 𝑖-ième position de 𝑒 𝑖 , les autres éléments étant nuls). En
supposant que les limites existent, la première dérivée partielle de la fonction
multivariable 𝑓 (𝑥) est définie par
𝜕𝑓 𝑓 (𝑥 + 𝜀𝑒 𝑖 ) − 𝑓 (𝑥)
:= lim
𝜕𝑥 𝑖 𝜀→0 𝜀
et la seconde dérivée partielle est définie par
𝜕 𝑓 (𝑥+𝜀𝑒 𝑖 ) 𝜕 𝑓 (𝑥)
𝜕2 𝑓 𝜕𝑥 𝑖
− 𝜕𝑥 𝑖
:= lim .
𝜕𝑥 2𝑖 𝜀→0 𝜀

Nous définissons 𝑓 (𝑥) comme étant (deux fois) différentiable si toutes les (se-
condes) dérivées partielles existent et
𝜕𝑓 𝜕𝑓
𝜕2 𝑓 𝜕𝑥 𝑗
(𝑥 + 𝜀𝑒 𝑖 ) − 𝜕𝑥 𝑗
(𝑥)
:= lim ,
𝜕𝑥 𝑖 𝜕𝑥 𝑗 𝜀→0 𝜀
et comme (deux fois) continûment différentiable si ces (secondes) dérivées par-
tielles sont continues. Les secondes dérivées qui sont continues ont la propriété
suivante :
𝜕2 𝑓 𝜕2 𝑓
= .
𝜕𝑥 𝑖 𝜕𝑥 𝑗 𝜕𝑥 𝑗 𝜕𝑥 𝑖
Notez que le graphique en contours en bas à droite de la Figure 2.4 montre que
𝑓 (𝑥) n’est pas différentiable.
En assemblant ces dérivées partielles, nous obtenons le vecteur gradient
 𝜕 𝑓 (𝑥) 
 𝜕𝑥1 
 . 
∇𝑥 𝑓 (𝑥) =  ..  . (1.1)
 𝜕 𝑓 (𝑥) 
 𝜕𝑥 
 𝑛 
En plus, la matrice Hessienne est définie par
 𝜕2 𝑓 (𝑥) 𝜕2 𝑓 (𝑥) 𝜕2 𝑓 (𝑥) 
 𝜕𝑥 2 𝜕𝑥 1 𝜕𝑥2
··· 𝜕𝑥 1 𝜕𝑥 𝑛 
 2 1 
 𝜕 𝑓 (𝑥) 𝜕2 𝑓 (𝑥) 𝜕2 𝑓 (𝑥) 
···
∇𝑥𝑥 𝑓 (𝑥) :=  𝜕𝑥2 𝜕𝑥1 𝜕𝑥22 𝜕𝑥 2 𝜕𝑥 𝑛 
 
. (1.2)
 ... ..
.
..
.
..
. 
 2 
 𝜕 𝑓 (𝑥) 𝜕2 𝑓 (𝑥) 𝜕2 𝑓 (𝑥) 
 𝜕𝑥 𝑛 𝜕𝑥1 𝜕𝑥 𝑛 𝜕𝑥2
··· 𝜕𝑥 𝑛2 


Lorsqu’une fonction n’a qu’un seul argument, nous omettons l’indice de
“∇” et écrivons simplement ∇ 𝑓 (𝑥) et ∇2 𝑓 (𝑥) pour le gradient et la Hessienne,
respectivement.

4
Short title of document Formulation mathématique (Modélisation)

Définition 1.1.5. Une fonction 𝑓 (𝑥), 𝑥 ∈ R𝑛 , est convexe si et seulement si

𝛼 𝑓 (𝑥 𝑎 ) + (1 − 𝛼) 𝑓 (𝑥 𝑏 ) ≥ 𝑓 (𝛼𝑥 𝑎 + (1 − 𝛼)𝑥 𝑏 )

pour tout 𝛼 ∈ (0, 1) et pour tous les points 𝑥 𝑎 , 𝑥 𝑏 ∈ R𝑛 . La convexité stricte

nécessite que l’inégalité (2.19) soit stricte. Pour les fonctions différentiables, cela
peut être étendu aux énoncés suivants :
— Une fonction continûment différentiable 𝑓 (𝑥) est convexe si et seulement si

𝑓 (𝑥 + 𝑝) ≥ 𝑓 (𝑥) + ∇ 𝑓 (𝑥)𝑇 𝑝

pour tout 𝑥, 𝑝 ∈ R𝑛 . La convexité stricte nécessite que l’inégalité (2.20) soit

stricte.
— Une fonction deux fois continûment différentiable 𝑓 (𝑥) est convexe si et seule-
ment si ∇2 𝑓 (𝑥) est semi-définie positive pour tout 𝑥 ∈ R𝑛 .
— Si ∇2 𝑓 (𝑥) est définie positive pour tout 𝑥 ∈ R𝑛 , alors la fonction 𝑓 (𝑥) est
définie comme fortement convexe. Une fonction fortement convexe est tou-
jours strictement convexe, mais la réciproque n’est pas vraie. Par exemple, la
fonction 𝑓 (𝑥) = 𝑥 4 est strictement convexe mais pas fortement convexe.

1.1.1 Interprétation du gradient et du Hessien

Le gradient ∇ 𝑓 (𝑥) indique la direction de la plus forte augmentation de 𝑓 (𝑥)

et est perpendiculaire aux courbes de niveau. Sa norme représente la pente
maximale locale.
Le Hessien ∇2 𝑓 (𝑥) décrit la courbure de 𝑓 (𝑥). S’il est défini positif, 𝑓 (𝑥)
est localement convexe ; s’il est défini négatif, 𝑓 (𝑥) est localement concave. Un
Hessien avec des valeurs propres de signes opposés indique un point-selle.
Ainsi, le gradient oriente l’optimisation, tandis que le Hessien en analyse la
stabilité.
La figure 1.2 illustre la fonction 𝑓 (𝑥) ainsi que ses zones de convexité et de
concavité. Les dérivées 𝑓 ′(𝑥) et 𝑓 ′′(𝑥) sont également représentées.
Comme le montre la figure 1.2, la fonction 𝑓 (𝑥) présente des zones de
convexité et de concavité, qui sont déterminées par le signe de la dérivée se-
conde 𝑓 ′′(𝑥).

5
Short title of document Formulation mathématique (Modélisation)

(a) Une fourmi se déplace sur une sphère (b) Représentation d’un champ vectoriel
avec une vitesse 𝑉 sur une sphère

Figure 1.1 – La figure 1.1(a) Illustre le champ vectoriel vitesse de la fourmi sur la sphère. La figure 1.1(b)
montre les vecteurs tangents de composantes locales 𝑉1 et 𝑉2 sont représentés sur le plan tangent au point
𝑃.

Figure 1.2 – Fonction et courbure : La fonction 𝑓 (𝑥) = 𝑥 3 − 6𝑥 2 + 4𝑥 + 12 est représentée avec ses
zones de convexité et de concavité. Dérivées de la fonction : Les dérivées 𝑓 ′(𝑥) = 3𝑥 2 − 12𝑥 + 4 et
𝑓 ′′(𝑥) = 6𝑥 − 12 sont également tracées.

6
Chapitre 2

Éléments sur la programmation

linéaire

La programmation linéaire est l’une des méthodes les plus classiques et

les plus utilisées dans la recherche opérationnelle. Le terme "programmation"
signifie essentiellement la planification de certaines activités soumises à des
contraintes en vue d’obtenir un rendement optimal.

※ Formulation mathématique (Modélisation)

Avant de définir rigoureusement ce qu’est la programmation linéaire, nous
allons partir d’une situation concrète. Construire un modèle mathématique
consiste à représenter en termes d’équations mathématiques les propriétés fon-
damentales du phénomène considéré. Pour définir un tel modèle mathématique,
trois entités doivent être identifiées :
— L’ensemble des actions dont dispose le décideur.
— L’objectif visé, qui sera exprimé sous forme d’une fonction linéaire.
— Les contraintes définissant le problème à étudier.
Dans ce cours, nous explorerons deux catégories de problèmes d’optimisation :
ceux visant à minimiser et ceux visant à maximiser une fonction objectif.

Exemple 1 : optimisation de chiffre d’affaire

Une société produit deux types de lingots d’acier de type LQ et HQ. La

production d’un lingot d’acier de type LQ nécessite 2 kg de matière première,
4 kWh de four électrique et 3 heures de laminage à chaud. En revanche, la

7
Short title of document Formulation mathématique (Modélisation)

Figure 2.1 – Données du problème d’optimisation du chiffre d’affaire.

production d’un lingot d’acier de type HQ nécessite 1 kg de matière première,

5 kWh de four électrique et 10 heures de laminage à chaud. L’entreprise dispose
des ressources suivantes : 8 kg de matière première, 2 kWh de four électrique
et 3 heures de laminage à chaud. Le prix de vente d’un lingot d’acier de type
LQ est de 3 dh et d’un lingot d’acier de type HQ est de 8 dh comme illustré
dans la figure 2.1. Le problème qui se pose est de déterminer combien de lots
de lingots de chaque type faut-il produire pour maximiser le chiffre d’affaires.
La modélisation de ce problème donne lieu au programme linéaire est comme
suit :
1. Variables de décision : Soient :
— 𝑥1 le nombre des lingots de type LQ
— 𝑥2 le nombre des lots de 1000 lingots de type HQ
2. Fonction objectif : Maximiser le chiffre d’affaire

max 𝑍 = 3𝑥1 + 8𝑥 2 (2.1)

La fonction-objectif est linéaire.

3. Contraintes :

Matière première : 2𝑥 1 + 𝑥2 ≤ 8 (2.2)

Énergie : 4𝑥1 + 5𝑥2 ≤ 20 (2.3)
Contraintes de laminage : 3𝑥1 + 10𝑥2 ≤ 30 (2.4)
Contraintes de positivité : 𝑥1 , 𝑥2 ≥ 0 (2.5)

8
Short title of document Formulation mathématique (Modélisation)

Une solution admissible est tout programme (𝑥 1 , 𝑥2 ) vérifiant l’ensemble des

contraintes :
 2𝑥1 + 𝑥2 ≤ 8





 4𝑥1 + 5𝑥2 ≤ 20




 3𝑥1 + 10𝑥 2 ≤ 30

 𝑥1 ≥ 0, 𝑥2 ≥ 0



étant des inéquations linéaires et la fonction-objectif est linéaire, on parle d’une
programmation linéaire.

Maximiser 3𝑥1 + 8𝑥2

sous contraintes 2𝑥1 + 𝑥2 ≤ 8
4𝑥1 + 5𝑥2 ≤ 20
3𝑥1 + 10𝑥2 ≤ 30
𝑥1 ≥ 0 𝑥2 ≥ 0

On appel solution optimal toute solution (𝑥1∗ , 𝑥2∗ ) optimisant la fonction ob-
jectif

∀(𝑥 1∗ , 𝑥2∗ ), 𝑍 = 3𝑥1 + 8𝑥 2 ≤ 𝑍 ∗ = 3𝑥1∗ + 8𝑥 2∗ (2.6)

Exemple 2 : optimisation de production

Une entreprise fabrique des chaises et des tables en bois. Pour fabriquer une
table, il faut : 0.5 m3 de bois, 10 h de main-d’œuvre et 2 h de machine. Pour
fabriquer une chaise, il faut : 0.1 m3 de bois, 6 h de main-d’œuvre et 1 h de
machine.
La capacité de la machine actuellement disponible est de 1200 heures par
trimestre. Il y a 7200 heures de main-d’œuvre par trimestre. Le fournisseur
actuel ne peut fournir que 300 m3 de bois par trimestre. Le bénéfice d’une table
vendue est de 50 DH et celui d’une chaise vendue est de 30 DH. La demande est
telle que l’entreprise ne pourra pas vendre plus de 500 tables par trimestre, et le
nombre de chaises vendues sera au maximum égal à 4 fois le nombre de tables
vendues.
Le problème décrit ci-dessous peut être résolu à l’aide de la programma-
tion linéaire. La formulation du problème en programmation linéaire consiste
à déterminer les variables de décision qui représentent le nombre de tables à

9
Short title of document Formulation mathématique (Modélisation)

produire et le nombre de chaises à produire. La fonction objectif vise à maximi-

ser le bénéfice total des ventes de tables et de chaises, tandis que les contraintes
imposent des limites sur les ressources disponibles, telles que la quantité de bois,
la main-d’œuvre et la capacité de la machine. De plus, elles garantissent que la
demande ne dépasse pas certaines quantités, comme la production maximale de
tables, et établissent une relation entre les tables et les chaises vendues.

1. Variables de décision :

Soit 𝑥1 le nombre de tables à produire.

Soit 𝑥2 le nombre de chaises à produire.

2. Fonction objectif : Maximiser le bénéfice total, qui peut être calculé en

vendant 𝑥1 tables à 50 dh et 𝑥 2 chaises à 30 dh :

Maximiser 𝑍 = 50𝑥1 + 30𝑥2 (2.7)

3. Contraintes :
3.1 Contraintes de matériaux. La quantité en m³ de bois disponible pour
fabriquer 𝑥1 tables et 𝑥2 chaises

0.5𝑥 1 + 0.1𝑥2 ≤ 300 (2.8)

3.2 Contraintes de main-d’œuvre. La capacité en heures de main-d’œuvre

disponible pour fabriquer 𝑥1 tables et 𝑥2 chaises :

10𝑥 1 + 6𝑥2 ≤ 7200 (2.9)

3.3 Contrainte de capacité de machine. La capacité en heures de machine

disponible pour fabriquer 𝑥1 tables et 𝑥2 chaises :

2𝑥 1 + 𝑥 2 ≤ 1200 (2.10)

3.4 Contrainte de demande de tables. L’entreprise ne pas vendre plus

de 500 tables par trimestre :

𝑥 1 ≤ 500 (2.11)

3.5 Contrainte de demande de chaises :

Le nombre de chaises vendues est au maximum égal à 4 fois le nombre
de tables :
𝑥2 ≤ 4𝑥1 (2.12)

10
Short title of document Formulation mathématique (Modélisation)

La modélisation du problèmes d’optimisation (2.7)-(2.12) peut être formulation

sous forme standard suivante :

Maximiser 𝑍 = 50𝑥1 + 30𝑥2

Sous les contraintes :


 0.5𝑥1 + 0.1𝑥2 ≤ 300 (Contraintes de matériaux)


10𝑥1 + 6𝑥2 ≤ 7200 (Contraintes de main-d’œuvre)




 (2.13)
 2𝑥1 + 𝑥2 ≤ 1200


 (Contrainte de capacité de machine)


 𝑥 1 ≤ 500 (Contrainte de demande de tables)

𝑥 2 ≤ 4𝑥 1




 (Contrainte de demande de chaises)

 𝑥1 ≥ 0, 𝑥2 ≥ 0

(Contraintes de positivité)


Il est à noter que la modélisation du problème d’optimisation (2.13) peut être

exprimée de manière plus concise sous une forme matricielle :

Maximiser 𝑍 = 𝐶 𝑇 𝑥
Sous contraintes :
𝐴𝑥 ≤ 𝑏 (2.14)

où
0.5 0.1  300 
   
 10 6  7200
   
   
" # " # 2 1 1200
50 𝑥1    
𝐶= , 𝑥= , 𝐴 =  1 0  et 𝑏 =  500 
30 𝑥2  −4 1   0 
   
 −1 0   0 
   
   
 0 −1   0 
   
La formulation (2.17) est la représentation matricielle du problème d’optimisa-
tion (2.13) .

Exemple 3 : problème de nutrition

En ce qui concerne la fourniture quotidienne de nutriments essentiels à

chaque individu d’une population, nous cherchons à atteindre un minimum
de 70 g de protéines, 3000 unités de calories, 800 mg de calcium et 12 mg de fer.
Les produits alimentaires disponibles sont le pain, le beurre, le fromage, les pois
et les épinards. Le prix par 100 g de ces produits est respectivement de 3, 7, 7,

11
Short title of document Formulation mathématique (Modélisation)

5, 5 unités monétaires. Les quantités de protéines en g, de calories en unités, de

calcium en mg et de fer en mg par 100 g de ces aliments sont données dans le
tableau suivant :

Table 2.1 – Tableau des informations nutritionnelles et des prix des produits alimentaires par 100 g

Produit Protéines Calories Calcium Fer Prix

Pain 10 300 v 50 4 3
Beurre 30 1800 400 0 7
Fromage 35 800 450 0 7
Pois 20 1500 750 4 5
Épinards 5 300 120 15 5

Le problème est de constituer au moindre frais les rations journalières en

respectant les exigences alimentaires. Le problème d’optimisation sous forme
standard peut être formuler comme suit :

1. 1. Variables de décision :
Soient 𝑥1 le nombre de grammes de pain à acheter, 𝑥2 le nombre de
grammes de beurre à acheter, 𝑥3 le nombre de grammes de fromage à
acheter, 𝑥4 le nombre de grammes de pois à acheter et 𝑥5 le nombre de
grammes d’épinards à acheter.
2. Fonction objectif : Minimiser le coût total des achats, qui peut être calculé
comme suit :
min 𝑍 = 3𝑥1 + 7𝑥2 + 7𝑥3 + 5𝑥 4 + 5𝑥5 (2.15)

3. Contraintes :
(a) Contraintes de protéines : 10𝑥1 + 30𝑥2 + 35𝑥3 + 20𝑥4 + 5𝑥 5 ≥ 70
(b) Contraintes de calories : 300𝑥 1 +1800𝑥2 +800𝑥 3 +1500𝑥4 +300𝑥 5 ≥ 3000
(c) Contraintes de calcium : 50𝑥1 + 400𝑥 2 + 450𝑥3 + 750𝑥4 + 120𝑥 5 ≥ 800
(d) Contraintes de fer : 4𝑥1 + 4𝑥4 + 15𝑥5 ≥ 12
(e) Contraintes de positivité : 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0

12
Short title of document Formulation mathématique (Modélisation)

Minimiser 𝑍 = 3𝑥1 + 7𝑥2 + 7𝑥3 + 5𝑥4 + 5𝑥5

Sous les contraintes :

10𝑥 1 + 30𝑥 2 + 35𝑥 3 + 20𝑥4 + 5𝑥5 ≥ 70 (Contraintes de protéines )







300𝑥1 + 1800𝑥2 + 800𝑥3 + 1500𝑥4 + 300𝑥5 ≥ 3000 (Contraintes de calories )






50𝑥 1 + 400𝑥2 + 450𝑥3 + 750𝑥 4 + 120𝑥5 ≥ 800 (Contraintes de calcium)


4𝑥1 + 4𝑥 4 + 15𝑥 5 ≥ 12 (Contraintes de fer)





 𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0, 𝑥4 ≥ 0, 𝑥5 ≥ 0



(2.16)
Sous forme matricielle, le problème (2.16) est formulé comme suit :

Minimiser 𝑍 = 𝐶 𝑇 𝑥
Sous contraintes :
𝐴𝑥 ≥ 𝑏 (2.17)

où
3 𝑥1 
     10 30 35 20 5   70 
7 𝑥    
   2 300 1800 800 1500 300 3000
𝐶 = 7 , 𝑥 = 𝑥3  , 𝐴 = et 𝑏 = 
       
  
 50 400 450 750 120  800 
𝑥4 
   
5    
     4 0 0 4 15   12 
5 𝑥5    
   

Exemple 4 : problème de transport

Une entreprise veut distribuer 4.5 tonnes (t) de marchandises à 4 clients :

𝐶1 , 𝐶2 , 𝐶3 et 𝐶4 . Ces marchandises sont stockés dans trois dépôt s 𝑃1 , 𝑃2 , 𝑃3 de
manière suivante : 10 𝑇 en 𝑃1 , 15 𝑇 en 𝑃2 et 20 𝑇 en 𝑃3 . Les demandes des clients
sont respectivement : 5 𝑇 pour 𝐶1 , 12 𝑇 pour 𝐶2 , 13 𝑇 pour 𝐶3 et 15 𝑇 pour 𝐶4 .
Les coûts de transport entre les dépôts et les clients sont données dans le tableau
suivant :

𝐶1 𝐶2 𝐶3 𝐶4
𝑃1 25 10 2 30
𝑃2 5 10 20 10
𝑃3 100 65 0 2

Soit 𝑥 𝑖𝑗 la quantité (en tonne) transporté du départ 𝑃𝑖 vers le client 𝐶 𝑗 , 𝑖 = 1, 2, 3

et 𝑗 = 1, 2, 3, 4.

13
Short title of document Formulation mathématique (Modélisation)

1. Variables de décision :

Soit 𝑥 𝑖𝑗 la quantité (en tonnes) transportée du dépôt 𝑃𝑖 vers le client 𝐶 𝑗 ,

pour 𝑖 = 1, 2, 3 et 𝑗 = 1, 2, 3, 4.

2. Fonction objectif : Minimiser le coût total du transport, qui peut être

calculé comme suit :

Minimiser 𝑍 = 25𝑥11 +10𝑥12 +2𝑥13 +30𝑥14 +5𝑥21 +10𝑥22 +20𝑥23 +10𝑥 24 +100𝑥 31 +65𝑥32 +2𝑥 34
(2.18)
3. Contraintes :
3.1 Contraintes d’offre des dépôts :

10𝑥 11 + 15𝑥12 + 20𝑥13 ≤ 10 (2.19)

10𝑥 21 + 15𝑥22 + 20𝑥23 ≤ 15 (2.20)
10𝑥 31 + 15𝑥32 + 20𝑥33 ≤ 20 (2.21)

3.2 Contraintes de demande des clients :

𝑥11 + 𝑥 21 + 𝑥31 ≥ 5 (2.22)

𝑥12 + 𝑥 22 + 𝑥32 ≥ 12 (2.23)
𝑥13 + 𝑥 23 + 𝑥33 ≥ 13 (2.24)
𝑥14 + 𝑥 24 + 𝑥34 ≥ 15 (2.25)

Figure 2.2 – Représentation graphique d’un problème de transport.

3.3 Contrainte de positivité des variables :

𝑥 𝑖𝑗 ≥ 0 pour 𝑖 = 1, 2, 3 et 𝑗 = 1, 2, 3, 4

14
Short title of document Résolution graphique du problème d’optimisation

Le problème de transport sous la forme standard est :

Minimiser 𝑍 = 25𝑥11 + 10𝑥 12 + 2𝑥 13 + 30𝑥14 + 5𝑥21

+ 10𝑥22 + 20𝑥23 + 10𝑥24 + 100𝑥31 + 65𝑥32 + 2𝑥34
Sous les contraintes :
10𝑥11 + 15𝑥12 + 20𝑥13 ≤ 10






 10𝑥21 + 15𝑥22 + 20𝑥23 ≤ 15




10𝑥31 + 15𝑥 32 + 20𝑥33 ≤ 20 (2.26)





 𝑥11 + 𝑥21 + 𝑥31 ≥ 5



 𝑥12 + 𝑥22 + 𝑥32 ≥ 12



𝑥13 + 𝑥23 + 𝑥33 ≥ 13






𝑥14 + 𝑥24 + 𝑥34 ≥ 15





 𝑥 𝑖𝑗 ≥ 0 pour 𝑖 = 1, 2, 3 et 𝑗 = 1, 2, 3, 4



Remarque : comme les commandes des clients coïncident avec les quantités dé-
posées dans les dépôts, alors toutes les contraintes sauf celles de la non négativité
sont des contraintes d’égalités.

※ Résolution graphique du problème d’optimisation

La méthode graphique est une approche visuelle de résolution des pro-
blèmes de programmation linéaire. Elle permet de représenter graphiquement
les contraintes et de trouver la solution optimale en identifiant le point d’inter-
section optimal sur le graphique.

2.2.1 Méthode graphique (cas de deux variables)

Nous examinerons d’abord les problèmes à deux variables 𝑥1 et 𝑥2 pour

lesquels la méthode graphique s’applique spécifiquement. Si les contraintes,
quel que soit leur nombre, ne comportent que deux variables, un problème de
PL peut s’écrire sous la forme :

Max 𝑧 = 𝑐1 𝑥1 + 𝑐 2 𝑥2
s.c. 𝛼1 𝑥1 + 𝛽1 𝑥2 ≤ 𝑏1
𝛼2 𝑥1 + 𝛽1 𝑥2 ≤ 𝑏2

15
Short title of document Résolution graphique du problème d’optimisation

..
.
𝛼 𝑖 𝑥1 + 𝛽 𝑖 𝑥2 ≤ 𝑏 𝑖
..
.
𝛼 𝑚 𝑥1 + 𝛽 𝑚 𝑥2 ≤ 𝑏 𝑚
𝑥1 , 𝑥2 ≥ 0

La résolution graphique d’un tel problème passe par trois étapes :

1. La représentation graphique du domaine réalisable,
2. La représentation graphie de la fonction objective,
3. La résolution graphique en déplaçant la fonction objective le long du do-
maine réalisable.

2.2.2 Représentation graphique du domaine réalisable

Figure 2.3 – Une droite sépare le plan en deux demi-plans

Comme c’est illustré dans la figure 2.3, chacune des équations 𝛼 𝑖 𝑥1 +𝛽 𝑖 𝑥2 = 𝑏 𝑖

définit une droite qui partage le plan en deux demi-plans 𝑃𝑖 et 𝑃𝑖′ d’équation :

(𝑃𝑖1 ) 𝛼 𝑖 𝑥1 + 𝛽 𝑖 𝑥2 ≤ 𝑏 𝑖
(𝑃𝑖2 ) 𝛼 𝑖 𝑥1 + 𝛽 𝑖 𝑥2 > 𝑏 𝑖

Chaque contrainte détermine l’un des deux demi-plans 𝑃𝑖1 ou 𝑃𝑖2 que l’on
trouvera en vérifiant si un point particulier (l’origine (0, 0) par exemple) est
contenu dedans ou non. L’intersection de tous les demi-plans correspondant
aux contraintes fournit un domaine plan, non nécessairement borné, appelé
domaine réalisable comme s’est illustré dans la figure 2.4. Le domaine réalisable
peut être soit borné, représentant un simplexe où toutes les contraintes sont

16
Short title of document Résolution graphique du problème d’optimisation

satisfaites comme c’est illustré dans la sous-figure 2.9(a), soit non borné illustré
dans la sous-figure 2.4(b), indiquant l’absence de limites sur certaines variables,
ce qui peut conduire à des solutions infinies.

(a) Domaine réalisable représenté par un (b) Domaine réalisable non borné
simplexe borné

Figure 2.4 – Représentation du domaine réalisable d’un problème d’optimisation par l’intersection des
demi-plans réalisables de chaque contrainte

Example 2.2.1. Reprenons la formulation du problème de productiondes lingos

métaliques vu dans le l’exemple 1.

Maximiser 3𝑥1 + 8𝑥2 (2.27)

sous contraintes 2𝑥1 + 𝑥 2 ≤ 8 Matière première (2.28)
4𝑥1 + 5𝑥2 ≤ 20 Énergie (2.29)
3𝑥1 + 10𝑥2 ≤ 30 Laminage (2.30)
𝑥1 ≥ 0 𝑥 2 ≥ 0 Positivité (2.31)

Une représentation bidimensionnelle des contraintes du problème d’optimisa-

tion de l’exemple 1 est illustrée dans la Figure 4.5. Les différentes contraintes sont
représentées comme suit : la contrainte de matière première (2.28) est montrée
dans la Figure 2.5(a), la contrainte d’énergie (2.29) est illustrée dans la Figure
2.5(b), la contrainte de laminage (2.30) apparaît dans la Figure 2.5(c), et enfin, la
contrainte de positivité (2.31) est présentée dans la Figure 2.5(d). Ces contraintes
délimitent le domaine réalisable du problème, qui prend la forme d’un simplexe
borné 𝑂, 𝐴, 𝐵, 𝐶, 𝐷 comme c’est rapporté dans la figure 2.5(d).

17
Short title of document Résolution graphique du problème d’optimisation

(a) Représentation en bleu de la contrainte (b) En vert la contrainte d’énergie

de matière première

(c) Représentation en bleu de la contrainte (d) En vert la contrainte de positivité

de laminage

Figure 2.5 – Représentation graphique des contraintes.

2.2.3 Représentation graphique de la fonction objectif

On s’intéresse à la famille des droites (𝐷𝑧 ) définies par l’équation

𝑧 = 𝑐1 𝑥1 + 𝑐2 𝑥2 (2.32)
où 𝑧 est une variable. La famille des droites (𝐷𝑧 ) partagent toutes le même
vecteur normal 𝑛® = (𝑐1 , 𝑐2 ). La direction du vecteur normal, ou gradient, indique
la direction d’augmentation de la valeur de 𝑧. En effet, le gradient 𝑛® pointe vers
les régions où 𝑧 augmente le plus rapidement comme s’est illustré dans la
figure . La droite (𝐷0 ) pour 𝑧 = 0 est déterminée par le point (0, 0) et le vecteur
normal 𝑛® = (3, 8), ce qui signifie qu’elles passent toutes par l’origine et que sont
inclinaison est dictée par la direction du vecteur normal, comme illustré dans la
figure 2.6.

18
Short title of document Résolution graphique du problème d’optimisation

Figure 2.6 – Illustration des droites parallèles et du vecteur normal (gradient) pour une fonction à deux
variables. Les droites représentent les niveaux de la fonction 𝑧, tandis que le vecteur normal indique la
direction de la plus forte augmentation.

Cela signifie que lorsque les droites (𝐷𝑧 ) se déplacent parallèlement dans la
direction du vecteur normal 𝑛® , la valeur de 𝑧 augmente, tandis que lorsque les
droites (𝐷𝑧 ) se déplacent parallèlement dans la direction opposée du vecteur
normal, la valeur de 𝑧 décroît, comme c’est illustré dans la figure 2.6.

2.2.4 Résolution graphique du problème d’optimisation

La méthode graphique permet de trouver la solution optimale d’un problème

de programmation linéaire en représentant les contraintes et les droites d’iso-
profit. Nous allons expliquer les étapes à suivre tout en se référant aux figures
4.5 illustrant la résolution du problème d’optimisation (2.27).

2.2.5 Tracé initial des droites d’isoprofit

On commence dans la figure 4.5(a) par le tracé de la droite de niveau 𝐷𝑧=0

correspondant à la fonction objectif :

𝑍 = 3𝑥 1 + 8𝑥2 = 0

19
Short title of document Résolution graphique du problème d’optimisation

(a) La droite de niveau 𝐷0 a fonction objec- (b) La droite de la fonction objectif 𝐷12 est
tif 3𝑥1 + 82𝑥2 = 0 passe par l’origine 𝑂(0, 0) ensuite obtenue en translatant parallemle-
et sont vecteur normal 𝑛® mentent 𝐷0 dans la direction du vecteur
normal 𝑛® jusu’au point extremal 𝐷.

(c) La droite de la fonction objectif 𝐷 62 est (d) La ligne de niveau de la fonction ob-
3
ensuite obtenue en translatant parallemle- jectif 𝐷24 est en fin obtenue en translatant
mentent 𝐷12 dans la direction du vecteur parallemlementent 𝐷 62 dans la direction du
3
normal 𝑛® jusu’au point extremal 𝐶. vecteur normal 𝑛® jusu’au point extremal 𝐵.

(e) La de la fonction objectif 𝐷25.2 est en fin (f) Il n’est plus possible de éplacer paralle-
obtenue en translatant parallemlementent lement les droite de niveau tout en restant
𝐷 62 dans la direction du vecteur normal 𝑛® à l’interieur du domaine réalisble.
3
jusu’au point extremal 𝐵.

Figure 2.7 – Représentation graphique des contraintes et des points d’intersection.

!
3
Cette droite passe par l’origine 𝑂(0, 0). Le vecteur normal 𝑛® = à la droite
2
𝐷0 donne la direction dans laquelle il faut déplacer pour maximiser la fonction
20
Short title of document Résolution graphique du problème d’optimisation

objectif 𝑍.

2.2.6 Translation parallèle des droites d’isoprofit

Pour maximiser la fonction objectif, on translate la droite parallèlement dans

la direction du vecteur normal 𝑛® . Ainsi

— Dans la Figure 4.5(b), la droite de la fonction objectif 𝐷0 est parallèlement

déplacée jusqu’à atteindre le point 𝐷 dont les coorodonnées sont une solution
du système : ( (
𝑥2 = 0 𝑥2 = 0
⇔
2𝑥1 + 𝑥2 = 8 𝑥1 = 4
La valeur correspondante de 𝑍 est alors :

𝑍 = 3 × 4 + 8 × 0 = 12.

À ce point, toute la matière première est utilisée, ce qui signifie que la

contrainte est « saturée », c’est-à-dire que la ressource est entièrement consom-
mée.
— Ensuite, dans la Figure 2.7(c), la droite de la fonction objectif 𝑍12 est déplacée
parallèlement dans la direction de 𝑛® jusqu’à atteindre le point 𝐶 solution du
système suivant :
10
 𝑥1 = 3
( 
2𝑥 1 + 𝑥 2 = 8



⇔
4𝑥1 + 5𝑥 2 = 20 4
 𝑥2 =


 3
La valeur correspondante de 𝑍 au point 𝐶 est :
10 4 62
𝑍 =3× +8× =
3 3 3
À ce point, les contraintes de Matière Première et Énergie sont saturées,
indiquant que les ressources associées sont entièrement utilisées.
— Figure 2.7(d) :La droite 𝐷 62 est ensuite déplacée continuellement et parallè-
3
lement jusqu’au point 𝐴, qui est la solution du système suivant :
( (
3𝑥1 + 10𝑥 2 = 30 𝑥2 = 3
⇔
𝑥1 = 0 𝑥1 = 0

La valeur de 𝑍 au point 𝐴 est :

𝑍 = 8 × 3 = 24.

21
Short title of document Résolution graphique du problème d’optimisation

À ce point, la contrainte de Laminage est saturée, indiquant que cette res-

source est pleinement utilisée.
— Figure 2.7(e) : La droite 𝐷24 est ensuite translatée parallèlement jusqu’à l’at-
teinte du point 𝐵, solution de :
( (
4𝑥1 + 5𝑥2 = 20 𝑥1 = 2
⇔ ⇒ 𝑍 = 25.20
3𝑥1 + 10𝑥2 = 30 𝑥2 = 2,4

Les contraintes Laminage et Énergie sont saturées.

— Figure 2.7(f) montre qu’il n’est plus possible de déplacer la droite d’isoprofit
parallèlement dans la direction du vecteur normal 𝑛® tout en restant à l’inté-
rieur du domaine réalisable. La solution optimale est donc atteinte au point
𝐵 avec 𝑍 = 25.20.

Limitations de la méthode graphique

La méthode graphique devient impraticable lorsque le nombre de variables

ou de contraintes augmente. En effet, au-delà de deux variables, la représentation
graphique devient complexe et difficile à visualiser. Par exemple, considérons
un problème de planification avec trois variables 𝑥 1 , 𝑥2 , et 𝑥3 et trois contraintes :

Maximiser 35𝑥1 + 38𝑥2 + 30𝑥3

sous contraintes 4𝑥 1 + 4𝑥2 + 2𝑥3 ≤ 80
4𝑥1 + 3𝑥2 + 2𝑥3 ≤ 50
𝑥1 + 2𝑥2 + 3𝑥3 ≤ 40
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Représenter graphiquement cet ensemble de contraintes dans un espace tri-

dimensionnel serait extrêmement difficile, voire impossible à visualiser. comme
c est illustré dans la figure 2.8. Étant donné la limitation de la méthode graphique
pour la résolution générale des problèmes d’optimisation, il est nécessaire de re-
courir à une approche algorithmique ou numérique. Dans la section suivante,
nous allons explorer la méthode du Simplexe, qui constitue une technique itératif
efficace pour la résolution d’un programme linéaire.

22
Short title of document Résolution graphique du problème d’optimisation

Figure 2.8 – Représentation graphique d’un problème d’optimisation.

Forme canonique et forme standard d’un programme linéaire

Pour résoudre un programme linéaire ()PL) avec l’algorithme du Simplexe,

on doit d’abord exprimer le PL sous form standard. Cependant, avant d’atteindre
la forme standard, le PL doit passer par la forme canonique.

Forme canonique d’un PL

En suivant les exemples de programmation linéaire présentés dans l’intro-

duction, les PLs suivent certaines règles lors de leur écriture. Ainsi, on remarque
qu’un PL de maximisation (ou de minimisation) par exemple est toujours ramené
à une forme dite canonique sous la forme :


 max 𝑧 = 𝐶1 𝑥 1 + 𝐶2 𝑥 2 + . . . + 𝐶 𝑛 𝑥 𝑛


sous contrainte





𝑎11 𝑥 1 + 𝑎 12 𝑥 2 + . . . + 𝑎 1𝑗 𝑥 𝑗 + . . . + 𝑎 1𝑛 𝑥 𝑛 ≤ 𝑏1



.

..





 𝑎 𝑖1 𝑥 1 + 𝑎 𝑖2 𝑥2 + . . . + 𝑎 𝑖𝑗 𝑥 𝑗 + . . . + 𝑎 𝑖𝑛 𝑥 𝑛 ≤ 𝑏𝑖
..


.





𝑎 𝑚1 𝑥 1 + 𝑎 𝑚2 𝑥 2 + . . . + 𝑎 𝑚 𝑗 𝑥 𝑗 + . . . + 𝑎 𝑚𝑛 𝑥 𝑛 ≤ 𝑏 𝑚






𝑥 𝑗 ≥ 0, 𝑗 = 1, . . . , 𝑛



S’écrit sous la forme matricielle du programme linéaire comme suit :

23
Short title of document Résolution graphique du problème d’optimisation

Fonction objectif :

 𝑥1 
 
𝑥 
 2
max 𝑧 = [𝐶1 , 𝐶2 , . . . , 𝐶 𝑛 ] ·  . 
| {z }  .. 
C𝑇 𝑥 
 𝑛
|{z}
x

Sous contraintes :
 𝑎11 𝑎12 . . . 𝑎1𝑛   𝑥1   𝑏1 
     
𝑎 𝑎 . . . 𝑎  𝑥  𝑏 
21 22 2𝑛 2  2
 .. . . . . ≤  .. 
   
 . .. .. ..   ..   . 
  
     
𝑎 𝑎 . . . 𝑎 𝑥 𝑏 
 𝑚1 𝑚2 𝑚𝑛   𝑛   𝑚
  
| {z } |{z} |{z}
A x b
𝑛
x∈R

Ou bien sous la forme matricielle contractée :



 max 𝑧 = C𝑇 x


 Sous contraintes :




 Ax ≤ b



 x≥0

Où

C = [𝐶1 , 𝐶2 , . . . , 𝐶 𝑛 ] est le vecteur des coefficients de la fonction objectif : de taille 𝑛,

A est la matrice des coefficients de la partie gauche des contraintes : de taille 𝑚 × 𝑛,
b = [𝑏1 , 𝑏2 , . . . , 𝑏 𝑚 ] est le vecteur des constantes de la partie droite des contraintes : de taille 𝑚,
x = [𝑥1 , 𝑥2 , . . . , 𝑥 𝑛 ] est le vecteur des variables : de décision de taille 𝑛.

Forme standard d’un programme linéaire

La forme standard nécessite que toutes les contraintes soient exprimées sous
forme d’égalités (=). Pour transformer des contraintes d’inégalité du problème
canonique aux contraintes d’égalité dans le problème de standard on introduit
𝑚 variables d’écart positives x𝑛+1 ≥ 0, . . . , x𝑛+𝑚 ≥ 0 mise exeptionnellement
dans des carrés :

24
Short title of document Résolution graphique du problème d’optimisation



 max 𝑧 = 𝐶1 𝑥1 + . . . + 𝐶 𝑛 𝑥 𝑛 + 0 𝑥 𝑛+1 + . . . + 0 𝑥 𝑛+𝑚





 sous contraintes

𝑎 11 𝑥1 + 𝑎 12 𝑥2 + . . . + 𝑎1𝑗 𝑥 𝑗 + . . . + 𝑎 1𝑛 𝑥 𝑛 + 𝑥 𝑛+1 = 𝑏1




𝑎 21 𝑥1 + 𝑎 22 𝑥2 + . . . + 𝑎2𝑗 𝑥 𝑗 + . . . + 𝑎 2𝑛 𝑥 𝑛 + 𝑥 𝑛+2 = 𝑏2




.. ..



. .
 (2.33)
𝑎 𝑖1 𝑥1 + 𝑎 𝑖2 𝑥2 + . . . + 𝑎 𝑖𝑗 𝑥 𝑗 + . . . + 𝑎 𝑖𝑛 𝑥 𝑛 + 𝑥 𝑛+𝑖 = 𝑏𝑖



..


.





𝑎 𝑚1 𝑥1 + 𝑎 𝑚2 𝑥2 + . . . + 𝑎 𝑚 𝑗 𝑥 𝑗 + . . . + 𝑎 𝑚𝑛 𝑥 𝑛 + 𝑥 𝑛+𝑚 = 𝑏𝑚





𝑥 𝑗 ≥ 0, 𝑗 = 1, . . . , 𝑛 + 𝑚




Ou sous la forme matricielle contractée :

max 𝑧 = C𝑇 x
Sous contraintes :
(2.34)
Ax = b
x≥0

Dans ce cas on a
 𝑎11 𝑎12 ··· 𝑎1𝑛 1 0 ··· 0

𝑎
 21 𝑎22 ··· 𝑎2𝑛 0 1 ··· 0
A=  . .. .. .. .. .. . . ..  (2.35)
 .. . . . . . . .
 
𝑎
 𝑚1 𝑎 𝑚2 · · · 𝑎 𝑚𝑛 0 0 · · · 1

C = [𝐶1 , . . . , 𝐶 𝑛 , 0, . . . , 0] est le vecteur des coefficients de la fonction objectif, de taille 𝑛 + 𝑚,

b = [𝑏 1 , 𝑏2 , . . . , 𝑏 𝑚 ] est le vecteur des constantes de la partie droite des contraintes, de taille 𝑚,
x = [x1 , x2 , . . . , x𝑛 , x𝑛+1 , . . . , x𝑛+𝑚 ] est le vecteur des variables de taille 𝑛 + 𝑚.

Définition 2.2.2. — Une solution réalisable de (𝑃) est tout 𝑥 ∈ R𝑛 vérifiant toutes
les contraintes de (𝑃).
— On appelle domaine réalisable l’ensemble de toutes les solutions réalisables.
— Une solution réalisable est dite optimale si elle minimise (ou maximise) la
fonction objectif.

Proposition 2.2.3. Tout programme linéaire peut s’écrire sous la forme standard.

25
Short title of document Résolution graphique du problème d’optimisation

Exemple :

Considérons le programme linéaire suivant :

Maximiser 𝑧 = 2𝑥1 + 3𝑥 2

sous les contraintes :

𝑥1 + 2𝑥2 ≤ 4,
2𝑥1 + 𝑥 2 ≥ 5,
𝑥1 − 𝑥 2 = 2,
𝑥 1 ≥ 0.

Transformation en forme standard :

1. Pour la contrainte de type ≤ :

La première contrainte 𝑥1 + 2𝑥2 ≤ 4 peut être transformée en :

𝑥1 + 2𝑥2 + 𝑠1 = 4, où 𝑠 1 ≥ 0 est une variable d’écart.

2. Pour la contrainte de type ≥ :

La deuxième contrainte 2𝑥1 + 𝑥2 ≥ 5 peut être transformée en :

2𝑥 1 + 𝑥 2 − 𝑠2 = 5, où 𝑠2 ≥ 0 est une variable de surplus.

3. Pour la contrainte d’égalité :

La troisième contrainte 𝑥 1 − 𝑥 2 = 2 reste inchangée, car elle est déjà sous
forme standard.
4. Pour la fonction objectif :
Le problème de maximisation peut être transformé en un problème de mini-
misation en changeant le signe de la fonction objectif :

Minimiser 𝑧 ′ = −2𝑥1 − 3𝑥 2

Programme linéaire sous forme standard :

Ainsi, le programme linéaire initial peut être réécrit sous la forme standard
suivante :

Minimiser 𝑧 ′ = −2𝑥1 − 3𝑥2

26
Short title of document Résolution graphique du problème d’optimisation

sous les contraintes :

𝑥1 + 2𝑥2 + 𝑠 1 = 4, 𝑠1 ≥ 0,
2𝑥1 + 𝑥2 − 𝑠 2 = 5, 𝑠2 ≥ 0,
𝑥1 − 𝑥 2 = 2,
𝑥 1 ≥ 0.

La solution de base réalisble du probleme de simplex

Pour résoudre un programme linéaire, il est essentiel de déterminer une so-

lution de base réalisable qui satisfait l’ensemble des contraintes du problème.
Une fois cette solution de base trouvée, l’objectif est de l’optimiser afin de parve-
nir à une solution optimale, c’est-à-dire une solution qui maximise ou minimise
la fonction objectif du programme linéaire tout en respectant les contraintes
imposées.

Hypothèse. Dans ce qui suit, nous faisons les hypothèses suivantes :

— La matrice 𝐴 (2.35) est de plein rang, c’est-à-dire rang(𝐴) = 𝑚, où 𝑚
représente le nombre de contraintes.
— De plus, on suppose que le vecteur b est non négatif, c’est-à-dire
b ≥ 0 pour tout 𝑖 = 1, . . . , 𝑚.

Définition :

On appelle base de 𝐴 toute sous-matrice carrée de 𝐴 d’ordre 𝑚 et qui est

non singulière.

Remarque :

Puisque le rang 𝐴 est supposé égal à 𝑚, une telle base existe. Pour fixer les
idées, on suppose que 𝐵 est constituée des 𝑚 premières colonnes de 𝐴, ainsi
nous pouvons décomposer la matrice A (2.35) de dimension 𝑚 × (𝑛 + 𝑚) en deux

27
Short title of document Résolution graphique du problème d’optimisation

matrices B et N comme suit :

 𝑎1 1 𝑎1 2 · · · 𝑎1 𝑚 𝑎 1 𝑚+1 ... 𝑎 1 𝑚+𝑛 

𝑎
 2 1 𝑎2 2 · · · 𝑎2 𝑚 𝑎 2 𝑚+1 ... 𝑎 2 𝑚+𝑛 
 . .. .. .. .. .. .. 
A =  .. . . . . . . 
𝑎
 𝑚 1 𝑎𝑚 2 · · · 𝑎𝑚 𝑚 𝑎 𝑚 𝑚+1 . . . 𝑎 𝑚 𝑚+𝑛 
| {z } | {z }

 B N 
sous une forme plus compacte

𝐴 = [B | N] (2.36)

où N est une matrice de taille 𝑚 × (𝑛 − 𝑚 − 1) et 𝐵 est une matrice inversible de

taille 𝑚 × 𝑚, données par :

 𝑎11 𝑎12 ··· 𝑎 1𝑚   𝑎1,𝑚+1 ··· 𝑎 1𝑛 

 
𝑎
 21 𝑎22 𝑎 2𝑚 
··· 𝑎 ··· 𝑎 2𝑛 
 2,𝑚+1
B=  . .. .. ..  et N =  . .. ..  (2.37)
 .. . . .  .. . .
   
𝑎
 𝑚1 𝑎 𝑚2 · · · 𝑎 𝑚𝑚  𝑎 · · · 𝑎 𝑚𝑛 
 𝑚,𝑚+1
Suivant la décomposition ( 2.36) de 𝐴 en deux sous matrices 𝐵 et 𝑁, on décom-
pose le vecteur 𝑥 en deux sous vecteurs :
 𝑥 
 1 
 𝑥2 
 
 .   𝑥1 
 ..  !    𝑥 𝑚+1 
𝑥𝐵
𝑥 
 .. 
   
 2
𝑥 =  𝑥𝑚  = où 𝑥 𝐵 =  .  et 𝑥 𝑁 =  .  (2.38)
 
𝑥𝑁  .. 
 𝑥 𝑚+1 
   
  𝑥 𝑚+𝑛 
𝑥 
 ..   𝑚
   
 . 
𝑥 𝑚+𝑛 
 
 

Exemple de décomposition de 𝐵 et 𝑁

Considérons le cas du programme sous forme standard (2.33), dans cet

exemple, la matrice 𝐴 est donnée par :

 𝑎11 𝑎12 ··· 𝑎 1𝑛 1 0 ··· 0


𝑎
 21 𝑎22 ··· 𝑎 2𝑛 0 1 ··· 0
A=  . .. .. .. .. .. . . .. 
 .. . . . . . . .
 
𝑎
 𝑚1 𝑎 𝑚2 · · · 𝑎 𝑚𝑛 0 0 · · · 1

28
Short title of document Résolution graphique du problème d’optimisation

La décomposition en 𝑁 et 𝐵 de la matrice A suivant le modèle ( 2.36) est

comme suit :

 𝑎11 𝑎12 ··· 𝑎1𝑛  1 0 ··· 0


   
𝑎
 21 𝑎22 ··· 𝑎2𝑛 1 ···
 0 0

𝑁= . .. ... .. et 𝐵 =  . .. . . .. (2.39)
  
 .. . .  .. . . .
 
 
   
𝑎
 𝑚1 𝑎 𝑚2 · · · 𝑎 𝑚𝑛 0 · · · 1 
 0
 
où 𝑁 est la matrice de taille 𝑚 × 𝑛 qui contient les coefficients des variables de
décision originales, et 𝐵 est une matrice identité de taille 𝑚 × 𝑚 représentant les
variables d’écart introduites pour convertir les inégalités en égalités.
Proposition 2.2.4. Le vecteur
" # " #
𝑥𝐵 B−1 𝑏
𝑥= =
𝑥𝑁 0
est solution réalisable du problème d’optimisation ( 2.34)

Démonstration

Suivant la décomposition ( 2.36) de 𝐴 en deux sous matrices 𝐵 et 𝑁, ainsi que

la décomposition (2.38) du vecteur 𝑥 en deux sous vecteurs 𝑥 𝐵 et 𝑥 𝑁 , alors 𝑥 est
une solution réalisable si seulement si
𝐴𝑥 = 𝑏 ⇐⇒ 𝐵𝑥 𝐵 + 𝑁 𝑥 𝑁 = 𝑏 (2.40)
Puisque 𝐵 est inversible, on peut écrire 𝑥 𝐵 en fonction de 𝑥 𝑁 sous la forme
𝑥 𝐵 = B−1 (𝑏 − N𝑥 𝑁 ) (2.41)
Cette relation montre comment les variables de base x𝐵 peuvent être exprimées
en fonction des variables hors base x𝑁 . Pour avoir une solution du système (2.41),
0
.
 
considérons que : 𝑥 𝑁 =  ..  Ainsi,
 
0
 
" # " #
𝑥𝐵 B−1 𝑏
𝑥= =
𝑥𝑁 0
est solution du système :
𝐴𝑥 = 𝑏
" #
𝑥¯ = B−1 𝑏
Définition 2.2.5 (Solution de base). La solution est une solution de
0
base du système 𝐴𝑥 = 𝑏 relativement à la base réalisable 𝐵 de 𝐴.

29
Short title of document Résolution graphique du problème d’optimisation

Exemple :

Reprenons l’exemple de la section 2 (le problème (𝑃prod )) et introduisons les

variables d’écart.
3𝑥1 + 4𝑥2 + 5𝑥3 ≤ 35 pour écrire le problème sous la forme standard :



 Max 50𝑥1 + 60𝑥2
sujet à




𝑥1 + 2𝑥2 + 𝑥3 = 8




(2.42)

 𝑥1 + 𝑥2 + 𝑥4 = 5

9𝑥1 + 4𝑥2 + 𝑥5 = 36




 𝑥1 ≥ 0, 𝑖 = 1, . . . , 5



La matrice 𝐴 vaut :
1 2 1 0 0 
 
𝐴 = 1 1 0 1 0 
 
 
9 4 0 0 1 
 
Il est facile de vérifier que les dix sous-matrices d’ordre 3 sont toutes régulières
et forment donc des bases.

𝐼 (indices de base) 𝐵𝑥 𝐵 = 𝑏 : système à résoudre Solution de base Réalisabilité

𝑥1 + 2𝑥 2 =8 𝑥1 = 2

 


 


 

𝐼 = {1, 2, 5} 𝑥1 + 𝑥2 =5 𝑥2 = 3 sommet b(2,3) : réalisabl
 
 9𝑥1 + 4𝑥2 + 𝑥5 = 36  𝑥5 = 6

 

 
𝑥1 =8 𝑥1 = 8

 


 


 

𝐼 = {1, 4, 5} 𝑥1 + 𝑥4 =5 𝑥4 = −3 sommet f(8,0) : non réalisa
 
 9𝑥1 + 𝑥5 = 36  𝑥5 = −36

 

 
𝑥3 = 8

 (
𝑥1 = 0




𝐼 = {3, 4, 5} 𝑥4 = 5 sommet o(0,0) : réalisabl
 𝑥2 = 0
 𝑥5 = 36



Table 2.2 – Sommets rapportés dans la figure 2.9 correspondant à chaque bases

30
Short title of document Résolution graphique du problème d’optimisation

Interpretation graphique de la solution de base réalisable du

problème linéaire

Théorème 2.2.6. Chaque sommet d’un polytope 𝑃 correspond à une et une seule
solution de base réalisble et inversemnt.

Exemple. Considérons le probleme 2.42 dont la representation graphique est

illustrée dans la figure 2.9. Le tableau 2.3 résume la nature des sommets dépend-
sments s’ils sont des sommets ou non.

(a) Domaine réalisable représenté par

un simplexe borné

Figure 2.9 – Représentation du domaine réalisable d’un problème d’optimisation par l’intersection des
demi-plans réalisables de chaque contrainte

La solution de base réalisable optimale du problème linéaire

Après avoir déterminé une solution de base réalisable pour le problème

linéaire (2.34), l’objectif maintenant est de chercher une solution de base réali-
sable optimale pour ce problème. Pour cela, nous partons de l’expression de la
variable de décision !
𝑥𝐵
𝑥= ,
𝑥𝑁

31
Short title of document Résolution graphique du problème d’optimisation

𝐼 = (indices de base) Variables de base point correspondant

𝐼 = {1, 2, 3} 𝑥 1 = 3.2, 𝑥 2 = 1.8, 𝑥 3 = 1.2 𝑐 : sommet
𝐼 = {1, 2, 4} 𝑥1 = 20
7 , 𝑥2 = 7 𝑥4 = − 7
18 3
𝑖 : n’est pas un sommet
𝐼 = {1, 2, 5} 𝑥1 = 2, 𝑥 3 = 3, 𝑥 5 = 6 𝑏 : sommet
𝐼 = {1, 3, 4} 𝑥1 = 4, 𝑥 3 = 4, 𝑥 4 = 1 𝑑 : sommet
𝐼 = {1, 3, 5} 𝑥1 = 5, 𝑥 3 = 3, 𝑥 5 = −9 𝑒 : n’est pas un sommet
𝐼 = {1, 4, 8} 𝑥1 = 8, 𝑥 4 = −3, 𝑥 8 = −36 𝑓 : n’est pas un sommet
𝐼 = {2, 3, 4} 𝑥2 = 9, 𝑥 3 = −10, 𝑥 4 = −4 ℎ : n’est pas un sommet
𝐼 = {2, 3, 5} 𝑥2 = 5, 𝑥 3 = −2, 𝑥 5 = 16 𝑔 : n’est pas un sommet
𝐼 = {2, 4, 8} 𝑥3 = 4, 𝑥 4 = 1, 𝑥 5 = 20 𝑎 : sommet
𝐼 = {3, 4, 5} 𝑥3 = 8, 𝑥 4 = 5, 𝑥 5 = 36 𝑜 : sommet

Table 2.3 – Classification des points correspondant à différentes sommets bases. Les sommets sont rapportés
dans la figure 2.9

où

x𝐵 = (𝑥1 , . . . , 𝑥 𝑚 ) représente les variables de base, (2.43)

x𝑁 = (𝑥 𝑚+1 , . . . , 𝑥 𝑚+𝑛 ) représente les variables hors base. (2.44)

En posant 𝑧 = 𝐶 𝑇 𝑥, où 𝑧 est la valeur de la fonction objectif, on peut réécrire 𝑧

en fonction des coefficients associés aux variables de base et hors base :

𝑍 = 𝐶 𝐵𝑇 𝑥 𝐵 + 𝐶 𝑁
𝑇
𝑥𝑁 .

où

𝐶 𝐵 = (𝐶1 , . . . , 𝐶 𝑚 ) sont les coûts associés aux variables de base, (2.45)

𝐶 𝑁 = (𝐶 𝑛+1 , . . . , 𝐶 𝑛+𝑚 ) sont les coûts associés aux variables hors base. (2.46)

Cette équation permet de reformuler le problème linéaire (2.34) comme suit :

(P) min 𝑧 (2.47)

s.t. 𝐵x𝐵 + 𝑁x𝑁 = b (2.48)
− 𝑍 + C𝑇𝐵 x𝐵 + C𝑇𝑁 x𝑁 = 0 (2.49)

En note que l’équation (2.48 ) représente les contraintes du problème, où 𝐵 et 𝑁

sont les matrices associées aux variables de base et hors base respectivement. La
seconde équation (2.49 ) est la fonction objectif exprimée en termes des variables
de base et hors base. Ensuite, en substituant l’expression de x𝐵 = B−1 (𝑏 − N𝑥 𝑁 )
dans la relation (2.49 ) , nous obtenons :

32
Short title of document Résolution graphique du problème d’optimisation

−𝑍 + C𝑇𝐵 (𝐵−1 b − 𝐵−1 𝑁x𝑁 ) + C𝑇𝑁 x𝑁 = 0.

Cela conduit à une nouvelle expression de la fonction objectif :

𝑍 = C𝑇𝐵 𝐵−1 b + (C𝑇𝑁 − C𝑇𝐵 𝐵−1 𝑁)x𝑁 (2.50)

Cette forme met en évidence la décomposition de la fonction objectif en une
partie constante C𝑇𝐵 𝐵−1 b et une partie variable (C𝑇𝑁 − C𝑇𝐵 𝐵−1 𝑁)x𝑁 liée aux va-
riables hors base x𝑁 . Le terme C𝑇𝐵 𝐵−1 b est constant dans l’expression de 𝑍, ce
qui signifie qu’il n’affecte pas le processus de minimisation. Par conséquent, on
peut l’ignorer dans la fonction objectif, puisque minimiser :

C𝑇𝐵 𝐵−1 b + (C𝑇𝑁 − C𝑇𝐵 𝐵−1 𝑁)x𝑁 revient à minimiser (C𝑇𝑁 − C𝑇𝐵 𝐵−1 𝑁)x𝑁

Ce qui nous permet de reformuler le problème linéaire (2.34) en termes des

variables de base x𝐵 et des variables hors base x𝑁 en un problème plus réduit
comme suit :

max C𝑇𝑁 − C𝑇𝐵 𝐵−1 𝑁 x𝑁

 
𝑥𝑁
sous contraintes 𝐵−1 𝑁x𝑁 + x𝐵 = 𝐵−1 b (2.51)
− 𝑍 + (C𝑇𝑁 − C𝑇𝐵 𝐵−1 𝑁)x𝑁 = −C𝑇𝐵 𝐵−1 b

Notons par
 𝐶¯ 1 
 
 𝐶¯ 
 2
C̄𝑇𝑁 = C𝑇𝑁 − C𝑇𝐵 B−1 N =  .  ,
 .. 
 
𝐶¯ 
 𝑛
qui représente le vecteur des coûts réduits associés aux variables hors base, où
𝐶¯ 𝑗 désigne le coût réduit de la 𝑗-ème variable hors base.

Remarque. Dans le problème réduit (2.51), si 𝐶¯ 𝑗 ≤ 0 pour tout 𝑗 = 1, . . . , 𝑛, cela

signifie que tous les coefficients associés aux variables hors base dans l’expres-
sion de la fonction objectif sont non négatifs. Dans ce cas, la solution (x𝐵 , x𝑁 )
avec x𝑁 = 0 est une solution réalisable optimale du problème initial n ( 2.34).

Dans le cas contraire, s’il existe un 𝑗 tel que 𝐶¯ 𝑗 > 0 : supposant sans perdre
de généralité que :
𝐶¯ 𝑗 = max 𝐶¯ 𝑖 pour 𝑖 = 1, . . . , 𝑛,
𝑖

33
Short title of document Résolution graphique du problème d’optimisation

alors il est possible de réduire davantage la fonction objectif en introduisant dans

la base la variable non basique 𝑥 𝑗 correspondante à cet indice 𝑗. Pour ce faire, on
effectue un pivotage sur la colonne correspondante à 𝑥 𝑗 dans la matrice B−1 N,
ce qui se réalise par des manipulations élémentaires de Gauss. Cette opération
permet d’introduire 𝑥 𝑗 dans la base et de retirer la variable basique associée à la
plus petite valeur positive dans B−1 b.
Le processus de pivotage se répète jusqu’à ce que tous les coefficients de C̄𝑇𝑁
soient non négatifs, indiquant que la solution de base obtenue est optimale.
Lorsque tous les coefficients de C̄𝑇𝑁 sont non négatifs, l’algorithme du sim-
plexe matriciel s’arrête, ayant trouvé la solution optimale au problème linéaire
𝑛 ( 2.34).
Le tableau du simplexe matriciel dans la définition qui suit est utilisé pour
effectuer les opérations de pivotage, permettant d’introduire les variables hors
base les plus prometteuses dans la base tout en assurant la réduction de la
fonction objectif jusqu’à atteindre une solution optimale.
Définition 2.2.7. On appelle tableau du simplexe matriciel la représentation
matricielle du problème linéaire sous forme réduite (2.51), qui permet de visua-
liser à la fois les coefficients des variables de base, des variables hors base, ainsi
que la fonction objectif. Ce tableau est construit à partir des matrices B, N, C𝐵 ,
et C𝑁 , ainsi que du vecteur des constantes b, comme suit :

x𝐵 x𝐻 −𝑍
x𝐵 𝐵 𝑁
−1 𝐼 𝐵−1 b
−𝑍 C𝑇𝑁 − C𝑇𝐵 𝐵−1 𝑁 0 −C𝑇𝐵 𝐵−1 b

Ce tableau résume les relations linéaires du problème, où :

— La matrice identité 𝐼 représente les coefficients des variables de base dans le
système d’équations,
— B−1 𝑁 contient les coefficients des variables hors base après transformation
par l’inverse de la matrice de base B,
— B−1 b est le vecteur des constantes transformées,
— C𝑇𝑁 − C𝑇𝐵 B−1 𝑁 est le vecteur des coûts réduits,
— −C𝑇𝐵 B−1 b est la valeur actuelle de la fonction objectif.

À chaque itération de l’algorithme du simplexe, nous mettons à jour les

colonnes de 𝐴 et le vecteur b en utilisant la matrice de base 𝐵. Les mises à jour
se font selon les règles explicités dans l’algorithme de simplex en utilisant la
méthode du tableau du simplex décrite dans section suivante.

34
Short title of document Résolution graphique du problème d’optimisation

Base 𝑥1 ... 𝑥𝑠 ... 𝑥𝑛 𝑥 𝑛+1 . . . 𝑥 𝑟 . . . 𝑥 𝑛+𝑚 b

𝑥 𝑛+1 𝑎1 1 ... 𝑎1 𝑠 ... 𝑎1 𝑛 1 ... 0 ... 0 𝑏1
.. .. ... .. ... .. .. . . . .. .. .. ..
. . . . . . . . .
𝑥𝑟 𝑎𝑟 1 ... 𝑎𝑟 𝑠 ... 𝑎𝑟 𝑛 0 ... 1 ... 0 𝑏𝑟
.. .. .. .. .. .. .. .. .. .. .. ..
. . . . . . . . . . . .
𝑥 𝑛+𝑚 𝑎 𝑚 1 . . . 𝑎𝑚 𝑠 . . . 𝑎𝑚 𝑛 0 ... 0 ... 1 𝑏𝑚
−𝑍 𝐶1 . . . 𝐶𝑠 . . . 𝐶𝑛 0 ... 0 ... 0 0

Table 2.4 – Tableau initial relative au probléme d’optimisation sous forme standard (2.52)

Algorithme de simplex :méthode de résolution par le tableau de

simplex

L’algorithme du simplexe converge interactivement vers la solution optimale

en se déplaçant de sommet en sommet de la région admissible jusqu’à atteindre
la solution optimale. Voici une explication détaillée de chaque étape de l’algo-
rithme :
Algorithme du simplexe
Étape 0 :
On part de la forme explicite un programme linéaire reduit 2.51) sous forme
canonique :



 max 𝑍




 sous contraintes


𝑎1 1 𝑥 1 + . . . + 𝑎 1 𝑛 𝑥 𝑛 + 𝑥 𝑛+1 + 0 𝑥 𝑛+2 + . . . + 0 𝑥 𝑛+𝑚 = 𝑏1




𝑎2 1 𝑥 1 + . . . + 𝑎 2 𝑛 𝑥 𝑛 + 0 𝑥 𝑛+1 + 𝑥 𝑛+2 + . . . + 0 𝑥 𝑛+𝑚 = 𝑏2




..



. (2.52)
𝑎 𝑚 1 𝑥 1 + . . . + 𝑎 𝑚 𝑛 𝑥 𝑛 + 0 𝑥 𝑛+1 + 0 𝑥 𝑛+2 + . . . + 𝑥 𝑛+𝑚 = 𝑏𝑚





𝐶1 𝑥1 + 𝐶2 𝑥2 + . . . + 𝐶 𝑛 𝑥 𝑛 + 0 𝑥 𝑚+1 + . . . + 0 𝑥 𝑛 − 𝑍



 =0


𝑥 𝑗 ≥ 0, 𝑗 = 1, . . . , 𝑚 : variables d’écart,





𝑥 𝑗 ≥ 0, 𝑗 = 𝑚 + 1, . . . , 𝑛 : variables de décision,





Étape 1 : ensuite On forme le tableau initial :

Étape 2 : Détermination de la variable d’entrée 𝑥 𝑠 :

35
Short title of document Résolution graphique du problème d’optimisation

— Pour un problème de maximisation :

Si 𝐶 𝑗 ≤ 0 pour tout 0 ≤ 𝑗 ≤ 𝑛, alors la solution est optimale et l’algorithme s’arrête.
Sinon, on choisit l’indice s tel que
𝐶 𝑠 = max{𝑐 𝑗 | 𝑐 𝑗 > 0}. (2.53)
— Pour un problème de minimisation :
Si 𝐶 𝑗 ≥ 0 pour tout 0 ≤ 𝑗 ≤ 𝑛, alors la solution est optimale et l’algorithme s’arrête.
Sinon, on choisit l’indice s tel que
𝐶 𝑠 = min{𝑐 𝑗 | 𝑐 𝑗 < 0}. (2.54)

La variable dont l’indice est 𝑠, c est à dire 𝑥 𝑠 est la variable d’entrée à la base.
Étape 3 : Détermination de la variable de sortie de la base 𝑥 𝑟
La variable d’entrée 𝑥 𝑠 déterminée dans l´ Étape 1 doit vérifier :
𝑥1 = 𝑏 1 − 𝑎 1𝑠 𝑥 𝑠 ≥ 0
𝑥2 = 𝑏 2 − 𝑎 2𝑠 𝑥 𝑠 ≥ 0
..
. (2.55)
𝑥 𝑚 = 𝑏 𝑚 − 𝑎 𝑚𝑠 𝑥 𝑠 ≥ 0

Si 𝑎 𝑖𝑠 ≤ 0, pour tout 𝑖 = 1, 2, . . . , 𝑚, alors 𝑥 𝑠 peut augmenter indéfiniment

sans qu’une variable de base s’annule. Dans ce cas, la valeur de 𝑧 décroît indéfi-
niment, le problème est dit non borné inférieurement et l’algorithme s’arrête.
Sinon , si 𝑎 𝑖𝑠 > 0 pour au moins un 𝑖, on choisit l’indice r en utilisant le
critère du quotient :
𝑏𝑟 𝑏𝑖
 
= min 𝑎 𝑖𝑠 > 0, 𝑖 = 1, 2, . . . , 𝑚 (2.56)
𝑎 𝑟𝑠 𝑎 𝑖𝑠
où 𝑠 est la colonne de pivot de l’étape 1. La variable de sortie est celle qui se
trouve sur la 𝑟-ième ligne, il s’agit donc ici de la variable 𝑥 𝑟 .
L’élement pivot 𝑎 𝑟𝑠 : L’intersection entre la ligne de la variable de sortie 𝑟 et
la colonne la variable de sortie 𝑠 détermine l’élément pivot 𝑎 𝑟𝑠 dans le tableau
formé dans l’étape 1.
Étape 4 : Pivotage et mise à jours du tableau de simplex
Le pivotage est le processus qui consiste à amener la colonne de la variable
sortante 𝑥 𝑟 en lieu et place de la variable entrante 𝑥 𝑠 . Le pivot nous permettra
de transformer le tableau actuel en un deuxième tableau correspondant à la
nouvelle base. Ceci peut se faire par trois types d’opérations :

36
Short title of document Résolution graphique du problème d’optimisation

— Transformation de la ligne pivot :

Pour obtenir la ligne du pivot transformée, il suffit de diviser tous ses éléments
par le pivot. Ainsi, en term de notation du tableau 2.4, on divise tous les
éléments de la ligne de la variable de sortie 𝑥 𝑟 (la ligne de pivot) par l’élément
pivot 𝑎 𝑟𝑠 pour le rendre égal à 1 :
𝑎𝑟 𝑗
𝐿𝑟 : 𝑎 𝑟 𝑗 ← , pour 𝑗 = 1, 2, . . . , 𝑛 + 𝑚. (2.57)
𝑎 𝑟𝑠

— Transformation de la colonne pivot :

Après avoir ramené le pivot à 1 par division, tous les éléments situés au-dessus
et au-dessous du pivot deviennent zéro.
— Transformation des autres cases du tableau :
Pour obtenir la transformée des autres éléments, on applique la règle du
rectangle :

Figure 2.10 – Représentation graphique d’un problème d’optimisation.

— Définition des éléments :

𝑎 : le nombre initial dont on cherche la transformée 𝑎 ′ ,

Soit : 𝑥 𝑟𝑠 : le pivot,
𝑏, 𝑑 : les nombres permettant de construire un rectangle à partir de 𝑎 et 𝑥 𝑟𝑠 .

— Transformation :

La transformée de 𝑎, notée 𝑎 ′ , est donnée par :

𝑏×𝑑
𝑎′ = 𝑎 − .
𝑎 𝑟𝑠
— Remarque :
— Toute ligne possédant un zéro dans la colonne du pivot reste inchangée.
— Toute colonne possédant un zéro dans la ligne du pivot reste inchangée.

37
Short title of document Résolution graphique du problème d’optimisation

Base 𝑥1 . . . 𝑥𝑠 ... 𝑥𝑛 𝑥 𝑛+1 . . . 𝑥 𝑟 . . . 𝑥 𝑛+𝑚 b

𝑎𝑟 1
𝑥 𝑛+1 𝑎1 1 − 𝑎1 𝑠 · 𝑎𝑟 𝑠 ... 0 ... 𝑎1 𝑛 − 𝑎1 𝑠 · 𝑎𝑟 𝑛
𝑎𝑟 𝑠 1 . . . − 𝑎𝑎1𝑟 𝑠𝑠 ... 0 𝑏 1 − 𝑎 1 𝑠 𝑎𝑏𝑟𝑟𝑠
.. .. .. . .. .. .. .. .. .. .. ..
. . . .. . . . . . . . .
𝑎𝑟 1 𝑎𝑟 𝑛 𝑏𝑟
𝑥𝑟 𝑎𝑟 𝑠 ... 1 ... 𝑎𝑟 𝑠 0 . . . 𝑎𝑟 𝑠
1
... 0 𝑎𝑟 𝑠
.. .. . . . .. ... .. .. .. .. .. .. ..
. . . . . . . . . .
𝑎𝑟 1 𝑎𝑟 𝑛
𝑥 𝑛+𝑚 𝑎𝑚 1 − 𝑎𝑚 𝑠 · 𝑎𝑟 𝑠 ... 0 . . . 𝑎𝑚 𝑛 − 𝑎𝑚 𝑠 · 𝑎𝑟 𝑠 0 . . . − 𝑎𝑎𝑚𝑟 𝑠𝑠 ... 1 𝑏 𝑚 − 𝑎 𝑚 𝑠 𝑎𝑏𝑟𝑟𝑠
−𝑍 𝐶1 − 𝐶 𝑠 𝑎𝑎𝑟𝑟 1𝑠 ... 0 ... 𝐶𝑛 − 𝐶 𝑠 𝑎𝑎𝑟𝑟 𝑛𝑠 0 ... − 𝑎𝐶𝑟𝑠𝑠 ... 0 0 − 𝐶 𝑠 𝑎𝑏𝑟𝑠𝑟

Table 2.5 – Mise a jours du tableau aprés les deux operations (2.57) et (2.58)

Ainsi, en term de notation du tableau 2.4, Pour chaque ligne 𝑖 ≠ 𝑟, la mise à

jour des éléments est comme suit :
𝑎 𝑖𝑠
𝐿 𝑖 : 𝑎 𝑖𝑗 ← 𝑎 𝑖𝑗 − · 𝑎𝑟 𝑗 , pour 𝑗 = 1, 2, . . . , 𝑛 + 𝑚. (2.58)
𝑎 𝑟𝑠
Le mis à jour donne lieu au nouveau tableau 2.5. Ces mises à jour garantissent
que la nouvelle base est correcte, avec la ligne de pivot normalisée et les autres
lignes ajustées pour maintenir la structure du tableau. On retourne ensuite à
l’étape 1 pour continuer l’algorithme. Le resumé de la méthode de simplex pour
un programme linéaire de maximisation est résumé dans l’algorithme 1.
Exemple de résolution du programme linéaire par la méthode du Simplexe
Nous avons le problème suivant sous forme canonique à résoudre :




 Maximiser 𝑧 = 𝑥1 + 2𝑥2 + 4𝑥3
sous les contraintes




𝑥1 + 3𝑥2 + 2𝑥3 ≤ 9





 𝑥1 + 2𝑥2 − 𝑥3 ≤ 2

−𝑥1 + 𝑥2 + 𝑥 3 ≤ 4




𝑥1 , 𝑥2 , 𝑥3 ≥ 0





Étape 0 : Mise sous forme standard

Pour résoudre ce problème à l’aide du simplexe, il faut d’abord mettre le

problème sous forme standard.On introduit donc les variables d’écart (𝑥4 , 𝑥5 , et
𝑥6 ) pour que les équations soient des égalités. La fonction à maximiser devient
donc :

38
Short title of document Résolution graphique du problème d’optimisation

Data: Initialisation
Result: Terminé pour la maximisation
while Il existe 𝑐 𝑗 > 0 do
Détermination de la variable de sortie :
Trouver la colonne pivot : 𝑠 = arg max 𝑗 {𝑐 𝑗 | 𝑐 𝑗 > 0};
Détermination de la variable d’entrée : ;
Trouver la ligne  pivot en utilisant
 le critère du quotient :
𝑏𝑖
𝑟 = arg min𝑖 𝑎 𝑖𝑠 𝑎 𝑖𝑠 > 0 ;

if 𝑎 𝑟𝑠 > 0 then
Effectuer l’élimination de Gauss-Jordan autour du pivot :
Pour chaque ligne 𝑖 ≠ 𝑟, faire :
𝐿 𝑖 ← 𝐿 𝑖 − 𝑎𝑎𝑟𝑠𝑖𝑠 𝐿𝑟 ;
Mettre à jour la ligne pivot en la divisant par le pivot pour la
rendre égale à 1 :
𝐿𝑟 ← 𝑎1𝑟𝑠 𝐿𝑟 ;
end
else
Le problème est non borné inférieurement : arrêtez l’algorithme.
end
end
Terminé pour la maximisation;
Algorithm 1: Algorithme de simplexd’un problème de maximisation




 Maximiser 𝑧 = 𝑥1 + 2𝑥2 + 4𝑥3
sous les contraintes




𝑥1 + 3𝑥2 + 2𝑥3 + 𝑥4 = 9





 𝑥1 + 2𝑥2 − 𝑥3 + 𝑥5 = 2

−𝑥1 + 𝑥2 + 2𝑥3 + 𝑥6 = 4




𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0





Étape 1 : Tableau initial du Simplexe

Nous construisons le tableau initial du simplexe. La dernière colonne corres-

pond à la valeur des termes constants des contraintes (le côté droit des équations).

39
Short title of document Résolution graphique du problème d’optimisation

— Il est évident que

𝑥1 = 𝑥2 = 𝑥3 = 0, 𝑥4 = 9, 𝑥5 = 2, 𝑥6 = 4

est une solution de base réalisable

— Puisque, dans la dernière ligne y a des coefficients des variables hors base
qui sont positifs (valeurs 1, 2, 4 ), cette solution de base réalisable n’est pas
optimale.

Étape 2 :Recherche d’une meilleure solution de base réalisable

— Détermination de la variable d’entrée : D’après les critères d’entrée présenté

en (2.53), la colonne correspondante à 𝑥3 a le coefficient le plus positif dans
la ligne de 𝑍. Puisque on a

𝐶3 = max{1, 2, 4}

nous allons donc choisir 𝑥3 comme colonne (variable) d’entrée à la base.

— Détermination de la variable de sortie :

— D’après les critères de sortie de la base présenté en (2.56), la colonne

correspondante à variable 𝑥6 en base sort de base, puisque c’est elle qui

40
Short title of document Résolution graphique du problème d’optimisation

correspond à la ligne pour laquelle le rapport 𝑎𝑏𝑖𝑟𝑖 est le plus petit avec
𝑎 𝑖𝑟 > 0, 𝑖 = 1, 3, 𝑟 = 3. En effet, 𝑎13 , 𝑎 33 sont positifs mais 𝑎 23 = −1 < 0.
𝑏1 9 𝑏3 4
= = 4.5, = =2
𝑎13 2 𝑎 33 2
Le plus faible ratio est 24 qui correspond à la ligne d’indice 3 et par conséquent
la variable 𝑥6 qui doit sortir de la base et la ligne pivot est celle de 𝑥6 .

Mise à jour du tableau

Construisons le nouveau tableau simplexe en appliquant les règles de mise

à jours dans les équations (2.57)- (2.58) et en utilisant la régle du carré illustrée
dans la figure 2.10 :

Base 𝑥1 𝑥 2 𝑥3 𝑥4 𝑥5 𝑥6 b
𝑥4 2 2 0 1 0 −1 5
𝑥5 1
2
5
2 0 0 1 1
2 4
𝑥3 − 2 2 1 0 0
1 1 1
2 2
−𝑍 3 0 0 0 0 −2 −8

Puisqu’il y a encore, la dernière ligne, un coéfficient positif (valant 3), nous

ne somme pas à solution optimale et nous devrons donc chercher une nouvelle
meilleure solution de base réalisable.

Étape 4 : Deuxième itération

Nous recherchons à nouveau la colonne pivot. Cette fois, c’est la colonne 𝑥1

avec un coefficient positif 3 dans la ligne de 𝑍.
Calculons les ratios :

5
Pour 𝑥4 : ≈ 2.5
2
4
Pour 𝑥5 : =8
1/2
Pour 𝑥3 : (non valide)
La ligne pivot est celle de 𝑥4 . Nous déduisons donc :
— 𝑥1 variable hors base entre dans la base
— 𝑥4 variable de base sort la base
Nous allons effectuer le pivot pour 𝑥 2 .

41
Short title of document Résolution graphique du problème d’optimisation

Mise à jour du tableau

Nous ajustons les lignes selon le pivot.

Base 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥 6 RHS
𝑥2 0 1 0 5
3 0 − 23 5
3
𝑥5 1 0 0 − 35 1 1
3
11
3
𝑥3 1 0 1 − 31 0 1 4
𝑍 0 0 0 −6 −4 −8 −20

Conclusion

Le tableau final indique que la solution optimale a été atteinte. Les valeurs
des variables sont :

𝑥1 = 0,
5
𝑥2 = ,
3
𝑥3 = 4,

et la valeur maximale de 𝑧 est 20.

Ainsi, le problème de programme linéaire est résolu avec succès en utilisant
la méthode du Simplexe.

Dualité

1. Exemple introductif

Exemple. Une entreprise E1 fabrique les produits P1 et P2. Elle utilise les ma-
tières premières M1, M2 et M3, à raison de :
— 2 tonnes de M1, 1 tonne de M2 et 3 tonnes de M3 par unité produite de P1,
— 1 tonne de M1, 3 tonnes de M2 et 4 tonnes de M3 par unité produite de P2.
Elle dispose de :
— 50 tonnes de M1, 25 tonnes de M2 et 60 tonnes de M3.
Le bénéfice net est de 5000 UM par unité de P1 et de 2000 UM par unité de
P2.

42
Short title of document Résolution graphique du problème d’optimisation

Le problème qui se pose à l’entreprise est le suivant : Quelle quantité de

chacun des deux produits P1 et P2 l’entreprise doit-elle fabriquer pour que le
bénéfice soit maximal ?

Produit P1 Produit P2 Disponibilité

Quantité de m.p M1 (tonnes) 2 1 50
Quantité de m.p M2 (tonnes) 1 3 25
Quantité de m.p M3 (tonnes) 3 4 60
Prix unitaire (UM) 5000 2000

Le problème de l’entreprise E1 se modélise par le programme linéaire :

Maximiser 𝑧 = 5000𝑥1 + 2000𝑥 2

sous contraintes 2𝑥1 + 𝑥 2 ≤ 50 Quantité de m.p M1
𝑥1 + 3𝑥 2 ≤ 25 Quantité de m.p M2
3𝑥1 + 4𝑥 2 ≤ 60 Quantité de m.p M3
𝑥 1 ≥ 0, 𝑥 2 ≥ 0
où
— 𝑥1 : quantité de produits P1 fabriqués,
— 𝑥2 : quantité de produits P2 fabriqués.
Supposons qu’une autre entreprise E2, en rupture de stock, désire racheter les
matières premières (M1, M2 et M3) de l’entreprise E1. Le problème qu’elle va se
poser est le suivant :
Quel doit être le prix unitaire minimum d’achat 𝑦1 , 𝑦2 et 𝑦3 de chaque
matière première, pour que :
— la valeur totale des m.p consommées par chaque produit P1 et P2 soit supé-
rieure ou égale à leurs prix unitaires respectifs, 𝑐1 = 5000 UM et 𝑐2 = 2000
UM (pour que cela reste intéressant pour l’entreprise E1),
— le prix total d’achat des matières premières disponibles soit minimum ?
Ce deuxième problème peut se mettre sous la forme :

min 𝑤 = 50𝑦1 + 25𝑦2 + 60𝑦3







sous contraintes :






(D) 2𝑦1 + 𝑦2 + 3𝑦3 ≥ 5000 (contrainte produit P1)

𝑦1 + 3𝑦2 + 4𝑦3 ≥ 2000

(contrainte produit P2)





 𝑦1 , 𝑦2 , 𝑦3 ≥ 0



43
Short title of document Résolution graphique du problème d’optimisation

𝑦 𝑖 : prix unitaire d’achat de la m.p Mi (𝑖 = 1, 2, 3)

Exemple. Un menuisier E1 dispose de 300 planches, 500 vis et 40 litres de colle.
Il peut fabriquer deux types de meubles : un meuble de type 1, qu’il peut vendre
avec 4000 DH l’unité, et dont la fabrication nécessite 12 planches, 60 vis et 4 litres
de colle ; et un meuble de type 2, qu’il peut vendre 1600 DH l’unité et dont la
fabrication nécessite 8 planches, 35 vis et 2 litres de colle.
Le problème du menuisier est alors de déterminer la quantité à fabriquer de
chaque type de meuble afin de maximiser les revenus.
Soient 𝑥 1 le nombre de meubles de type 1 à fabriquer, et 𝑥2 le nombre de
meubles de type 2 à fabriquer. le problème de maximisation du menuisier E1 est
le suivant :
max 𝑍 = 4000𝑥1 + 1600𝑥2





sous contraintes :






12𝑥 1 + 8𝑥2 ≤ 300 (contrainte 1)






(P) 60𝑥 1 + 35𝑥 2 ≤ 500 (contrainte 2)


4𝑥1 + 2𝑥2 ≤ 40 (contrainte 3)





𝑥1 ≥ 0





 𝑥2 ≥ 0



Supposons qu’une autre entreprise E2, en rupture de stock, désire racheter
les matières premières (M1, M2 et M3) de l’entreprise E2. Le problème qu’elle
va se poser est le suivant :
Quel doit être le prix unitaire minimum d’achat 𝑦1 , 𝑦2 et 𝑦3 de chaque
matière première, pour que :
— la valeur totale des m.p consommées par chaque produit P1 et P2 soit supé-
rieure ou égale à leurs prix unitaires respectifs, 𝑐1 = 5000 UM et 𝑐2 = 2000
UM (pour que cela reste intéressant pour l’entreprise E1),
— le prix total d’achat des matières premières disponibles soit minimum ?
Ce deuxième problème peut se mettre sous la forme :

min 𝑤 = 50𝑦1 + 25𝑦2 + 60𝑦3







sous contraintes :






(D) 2𝑦1 + 𝑦2 + 3𝑦3 ≥ 5000 (contrainte produit P1)

𝑦1 + 3𝑦2 + 4𝑦3 ≥ 2000

(contrainte produit P2)





 𝑦1 , 𝑦2 , 𝑦3 ≥ 0



44
Short title of document Résolution graphique du problème d’optimisation

𝑦 𝑖 : prix unitaire d’achat de la m.p Mi (𝑖 = 1, 2, 3)

Sous forme matricielle :

Pour le problème primal (P) :

" #
h i 𝑥
1
Max 𝑍 = 4000 1600
𝑥2

sous contraintes :

12 8  " # 300 " # " #

  𝑥   𝑥1 0
 1
60 35 ≤ 500 , ≥
  
 𝑥 𝑥2 0
4 2 2
  
 40 
   
Pour le problème dual (D) :

i  𝑦1 
 
h
Min 𝑊 = 300 500 40  𝑦2 
 
 𝑦3 
 
 
sous contraintes :

" #  𝑦1  " #  𝑦  0

15 60 4  
  4000
 1  
 𝑦2  ≥ ,  𝑦2  ≥ 0
   
8 36 2   1600
 𝑦3   𝑦3  0
   
     
Définition 2.2.8. Le problème (𝐷) est appelé problème dual de (𝑃).
Le problème (𝑃) est appelé problème primal.

Remarque

Comparons les deux problèmes, primal (𝑃) et dual (𝐷) :

(𝑃) (𝐷)
 max 𝑧 = 5000𝑥 1 + 2000𝑥2
min 𝑤 = 50𝑦1 + 25𝑦2 + 60𝑦3

 
2𝑥1 + 𝑥2 ≤ 50

 

 2𝑦1 + 𝑦2 + 3𝑦3 ≥ 5000

 


 
𝑥 1 + 3𝑥2 ≤ 25 ↔
  𝑦1 + 3𝑦2 + 4𝑦3 ≥ 2000
3𝑥1 + 4𝑥 2 ≤ 60

 


  𝑦1 , 𝑦2 , 𝑦3 ≥ 0

𝑥1 , 𝑥2 ≥ 0

 

45
Short title of document Résolution graphique du problème d’optimisation

— Les coefficients de la fonction objectif 𝑤 de (𝐷) correspondent aux coefficients

du second membre de (𝑃).

— De même, les coefficients de la fonction objectif 𝑧 de (𝑃) correspondent aux

coefficients du second membre de (𝐷).

Si nous désignons par :

— 𝐴, 𝑏 et 𝑐 respectivement la matrice des contraintes, le second membre et le

vecteur des coûts du problème (𝑃),
— 𝐴′ , 𝑏 ′ et 𝑐 ′ respectivement la matrice des contraintes, le second membre et le
vecteur des coûts du problème (𝐷),

alors on a :

2 1 50 !
© ª © ª 5000
𝐴 = ­­1 3®® ; 𝑏 = ­­25®® ; 𝑐=
2000
«3 4 ¬ «60¬
! ! 50
2 1 3 5000
′
= 𝐴𝑇 ; ′ ′
© ª
𝐴 = 𝑏 = = 𝑐; 𝑐 = ­­25®® = 𝑏
1 3 4 2000
«60¬
Le problème primal (𝑃) et son dual (𝐷) sont liés par les relations suivantes :

• Le problème (𝑃) contient 2 variables (𝑥1 et 𝑥2 ) et 3 contraintes.

• Le problème (𝐷) contient 3 variables (𝑦1 , 𝑦2 et 𝑦3 ) et 2 contraintes.
• On en conclut que le nombre de variables de (𝑃) est égal au nombre de
contraintes de (𝐷) et réciproquement, le nombre de variables de (𝐷) est égal
au nombre de contraintes de (𝑃).
• On peut vérifier facilement que le dual de (𝐷) est le problème (𝑃).
• Le problème (𝑃) est un problème de maximisation. Tandis que (𝐷) est un
problème de minimisation.
• Le minimum 𝑤min atteint par le problème (𝐷) est égal au maximum 𝑧 max du
problème (𝑃).
Cela signifie dans notre cas que le prix d’achat minimal des matières pre-
mières par l’entreprise E2 est égal au profit maximal que peut en tirer l’en-
treprise E1 en vendant ces matières premières.

46
Short title of document Résolution graphique du problème d’optimisation

2. Formulation générale du problème dual

Formulation algébrique :
Soit un programme linéaire sous forme canonique :



 max 𝑧 = 𝑐 1 𝑥1 + 𝑐2 𝑥2 + . . . + 𝑐 𝑛 𝑥 𝑛

𝑎 11 𝑥1 + 𝑎 12 𝑥2 + . . . + 𝑎 1𝑛 𝑥 𝑛 ≤ 𝑏 1






 𝑎21 𝑥1 + 𝑎22 𝑥2 + . . . + 𝑎2𝑛 𝑥 𝑛 ≤ 𝑏2



(𝑃) ..


 .

𝑎 𝑚1 𝑥1 + 𝑎 𝑚2 𝑥2 + . . . + 𝑎 𝑚𝑛 𝑥 𝑛 ≤ 𝑏 𝑚






 𝑥1 ≥ 0, . . . , 𝑥 𝑛 ≥ 0


𝑛 variables 𝑥 1 , 𝑥2 , . . . , 𝑥 𝑛 et 𝑚 contraintes.
Coefficients du second membre : 𝑏 1 , 𝑏2 , . . . , 𝑏 𝑚 .
Coefficients (coûts) de la fonction objectif : 𝑐1 , 𝑐2 , . . . , 𝑐 𝑛 .
Matrice des contraintes 𝐴 de type (𝑚, 𝑛) (m lignes et n colonnes).

Le problème dual de (P)

Le problème dual de (𝑃) est défini par :



 min 𝑤 = 𝑏 1 𝑦1 + 𝑏 2 𝑦2 + · · · + 𝑏 𝑚 𝑦𝑚




𝑎 11 𝑦1 + 𝑎 21 𝑦2 + · · · + 𝑎 𝑚1 𝑦𝑚 ≥ 𝑐 1







 𝑎12 𝑦1 + 𝑎22 𝑦2 + · · · + 𝑎 𝑚2 𝑦𝑚 ≥ 𝑐2



(𝐷)
..
.







𝑎 1𝑛 𝑦1 + 𝑎2𝑛 𝑦2 + · · · + 𝑎 𝑚𝑛 𝑦𝑚 ≥ 𝑐 𝑛







 𝑦1 ≥ 0, 𝑦2 ≥ 0, . . . , 𝑦𝑚 ≥ 0


m variables 𝑦1 , 𝑦2 , . . . , 𝑦𝑚 et n contraintes. Coefficients du second membre :
𝑐1 , 𝑐2 , . . . , 𝑐 𝑛 . Coefficients (coûts) de la fonction objectif : 𝑏 1 , 𝑏2 , . . . , 𝑏 𝑚 . Matrice
des contraintes : 𝐴′ = 𝐴𝑇 de type (𝑛, 𝑚) (n lignes et m colonnes).

47
Short title of document Résolution graphique du problème d’optimisation

Formulation matricielle :

Formulation matricielle :



 max 𝑧 = 𝑐 𝑇 𝑥 

 min 𝑤 = 𝑏 𝑇 𝑦

 

𝐴𝑇 𝑦 ≥ 𝑐

 

(𝑃) 𝐴𝑥 ≤ 𝑏 (𝐷)

 

 
𝑥 ≥ 0
 𝑦 ≥ 0

 
Exemple 1 :



 max 𝑧 = 𝑥1 + 3𝑥 2
min 𝑤 = 14𝑦1 + 12𝑦2 + 12𝑦3

 

 
𝑥1 + 𝑥2 ≤ 14

 

 
 𝑦1 − 2𝑦2 + 2𝑦3 ≥ 1

 



 

(𝑃1 ) −2𝑥1 + 3𝑥2 ≤ 12 (𝐷1 )
𝑦1 + 3𝑦2 − 𝑦3 ≥ 3

 

 
2𝑥1 − 𝑥 2 ≤ 12

 

 
 𝑦1 , 𝑦2 , 𝑦3 ≥ 0

 



 𝑥1 , 𝑥2 ≥ 0
 


Exemple 2 :




 min 𝑧 = −2𝑥 1 + 9𝑥2 


 min 𝑧 = −2𝑥1 + 9𝑥2

 

3𝑥1 + 𝑥2 ≥ 10 3𝑥 1 + 𝑥2 ≥ 10

 


 


 


 

(𝑃2 ) 4𝑥1 − 3𝑥2 ≤ 8 ⇐⇒ −4𝑥1 + 3𝑥2 ≥ −8

 

 
𝑥1 − 𝑥2 ≤ 6 −𝑥1 + 𝑥2 ≥ −6

 


 


 

 
 𝑥1 , 𝑥2 ≥ 0
  𝑥1 , 𝑥2 ≥ 0

 

Le dual de (𝑃2 ) est :

max 𝑤 = 10𝑦1 − 8𝑦2 − 6𝑦3







 3𝑦1 − 4𝑦2 − 𝑦3 ≤ −2




(𝐷2 )
𝑦1 + 3𝑦2 + 𝑦3 ≤ 9






 𝑦1 , 𝑦2 , 𝑦3 ≥ 0



Question : Dual de (𝐷2 ) ?

48
Short title of document Résolution graphique du problème d’optimisation




 min 𝑧 = −2𝑢1 + 9𝑢2


3𝑢1 + 𝑢2 ≥ 10






¯ 2)


(𝐷 −4𝑢1 + 3𝑢2 ≥ −8



−𝑢1 + 𝑢2 ≥ −6







 𝑢1 , 𝑢2 ≥ 0


Le dual du dual de (𝑃2 ) = (𝑃2 ).

3. Correspondances entre le primal et le dual

Problème Primal Problème Dual

maximisation minimisation
second membre des contraintes coefficient de la fonction objectif
coefficient de la fonction objectif second membre des contraintes
𝑚 contraintes 𝑚 variables de décision
𝑛 variables de décision 𝑛 contraintes
𝑖 ème contrainte de type ≤ 𝑖 ème variable ≥ 0
𝑗 ème variable ≥ 0 𝑗 ème contrainte de type ≥ 0

4. Théorème de dualité

Avec les notations du paragraphe précédent, on a les résultats suivants :

Théorème 2 (Dualité faible)

Soit 𝑥 une solution réalisable d’un problème (PL) sous forme canonique et
𝑦 une solution réalisable du problème dual (PLD). Alors :
1. 𝑧(𝑥) ≤ 𝑤(𝑦)
2. (Certificat d’optimalité) Si 𝑧(𝑥) = 𝑤(𝑦) alors 𝑥 et 𝑦 sont deux solutions
optimales de (PL) et (PLD) respectivement.

49
Short title of document Résolution graphique du problème d’optimisation

Théorème 1 (Dualité forte)

Le problème primal (P) admet une solution optimale 𝑥 ∗ si et seulement si

le problème dual (D) admet une solution optimale 𝑦 ∗ , et dans ce cas, on a :

𝑐𝑇 𝑥 ∗ = 𝑏𝑇 𝑦 ∗ autrement dit 𝑧∗ = 𝑤∗.

Théorème des écarts complémentaires

Théorème 3 (Caractérisation de l’optimalité

Soit 𝑥 ∗ une solution réalisable du problème primal. 𝑥 ∗ est optimal si et

seulement s’il existe une solution réalisable 𝑦 ∗ du problème dual telle que
 Í𝑛 
∀𝑖 ∈ {1, . . . , 𝑚}, 𝑦 ∗
𝑏 − 𝑎 𝑥 ∗
𝑗=1 𝑖𝑗 𝑗 = 0,

𝑖 𝑖




 ∀𝑗 ∈ {1, . . . , 𝑛}, 𝑥 ∗𝑗 𝑐 𝑗 − 𝑚 𝑦 ∗
𝑎
Í
𝑖=1 𝑖 𝑖𝑗 = 0.


On peut toujours considérer que 𝑦 ∗ est une solution réalisable optimale du
dual.

Le système est équivalent à

 ∀𝑖 ∈ {1, . . . , 𝑚}, 𝑏 𝑖 − 𝑛𝑗=1 𝑎 𝑖𝑗 𝑥 ∗𝑗 > 0 ⇒ 𝑦 𝑖∗ = 0,


 Í

 ∀𝑗 ∈ {1, . . . , 𝑛}, 𝑐 𝑗 − 𝑚𝑖=1 𝑦 𝑖 𝑎 𝑖𝑗 < 0 ⇒ 𝑥 𝑗 = 0.
∗ ∗
 Í

Ce théorème dit que SI 𝑦 𝑖∗ > 0 ALORS la 𝑖-ième contrainte du problème primal
est saturée : 𝑏 𝑖 = 𝑛𝑗=1 𝑎 𝑖𝑗 𝑥 ∗𝑗 . De même, SI 𝑥 ∗𝑗 > 0 ALORS la 𝑗-ième contrainte du
Í

problème dual est saturée : 𝑐 𝑗 = 𝑚 𝑖=1 𝑦 𝑖 𝑎 𝑖𝑗 .

∗
Í

Par exemple :

Maximiser 𝑧 = 6𝑥1 + 4𝑥2

sous les contraintes 3𝑥1 + 9𝑥2 ≤ 81
4𝑥1 + 5𝑥2 ≤ 55
2𝑥1 + 𝑥 2 ≤ 20
𝑥1 , 𝑥2 ≥ 0.

50
Short title of document Résolution graphique du problème d’optimisation

(PL)
Solution optimale de (PL) :
15
𝑥 1∗ =
2
∗
𝑥2 = 5

Programme dual :

Minimiser 𝑤 = 81𝑦1 + 55𝑦2 + 20𝑦3

sous les contraintes 3𝑦1 + 4𝑦2 + 2𝑦3 ≥ 6
9𝑦1 + 5𝑦2 + 𝑦3 ≥ 4
𝑦1 , 𝑦2 , 𝑦3 ≥ 0.

(PLD)

Solution optimale de (PL) :

15
𝑥1∗ = > 0 =⇒ 3𝑦1∗ + 4𝑦2∗ + 2𝑦3∗ = 6
2
𝑥2 = 5 > 0 =⇒ 9𝑦1∗ + 5𝑦2∗ + 𝑦3∗ = 4
∗

27
81 − (3𝑥 1∗ + 9𝑥2∗ ) = > 0 =⇒ 𝑦1∗ = 0
2
=⇒ Solution optimale du problème dual
1 7
𝑦1∗ = 0, 𝑦2∗ = , 𝑦3∗ = .
3 3

 max 𝑧 = 5000𝑥 1 + 2000𝑥2

min 𝑤 = 50𝑦1 + 25𝑦2 + 60𝑦3

 
2𝑥1 + 𝑥2 ≤ 50

 

 2𝑦1 + 𝑦2 + 3𝑦3 ≥ 5000

 


 
(𝑃) 𝑥 1 + 3𝑥2 ≤ 25 (𝐷)
  𝑦1 + 3𝑦2 + 4𝑦3 ≥ 2000
3𝑥1 + 4𝑥 2 ≤ 60

 


  𝑦1 , 𝑦2 , 𝑦3 ≥ 0

𝑥 1 ≥ 0, 𝑥 2 ≥ 0

 

Si 𝑥 = (𝑥1 , 𝑥2 ) réalisable pour 𝑃 et 𝑦 = (𝑦1 , 𝑦2 , 𝑦3 ) réalisable pour 𝐷, alors 𝑥
et 𝑦 sont solutions optimales ssi :

𝑦1 (50 − 2𝑥1 − 𝑥2 ) = 0 ; 𝑦2 (25 − 𝑥1 − 3𝑥 2 ) = 0 ; 𝑦3 (60 − 3𝑥1 − 4𝑥2 ) = 0

(2𝑦1 + 𝑦2 + 3𝑦3 − 5000)𝑥 1 = 0 ; (𝑦1 + 3𝑦2 + 4𝑦3 − 2000)𝑥 2 = 0

51
Chapitre 3

Optimisation sans contraintes

L’optimisation sans contraintes est essentielle en ingénierie pour l’estimation

de paramètres, l’analyse économique et l’étude de systèmes chimiques. Elle sert
de base à l’optimisation avec contraintes. Ce chapitre présente la formulation
des problèmes d’optimisation sans contraintes, aborde la continuité, la différen-
tiabilité, la convexité, et développe les conditions d’optimalité locale du premier
et du second ordre, avec des exemples et l’introduction aux algorithmes itératifs.

Définition 3.0.1. Une racine (ou zéro) d’une fonction continue 𝑓 : R → R est un
point 𝑥¯ ∈ R tel que :
𝑓 ( 𝑥)
¯ = 0.

Cela signifie que, pour une fonction 𝑓 continue, 𝑥¯ est une valeur où la fonction
𝑓 prend la valeur zéro.

Algorithme de Newton-Raphson pour la recherche des racine

d’une fonction continue

Pour approcher une solution de l’équation 𝑓 (𝑥) = 0, on utilise la méthode de

Newton, qui repose sur l’approximation de la fonction 𝑓 par son développement
de Taylor au premier ordre. À partir d’un point initial 𝑥 0 , choisi près du zéro
recherché, on approxime la fonction par la tangente en ce point :

𝑓 (𝑥) ≈ 𝑓 (𝑥 0 ) + 𝑓 ′(𝑥0 )(𝑥 − 𝑥 0 ).

Pour trouver un zéro de cette approximation, on résout l’équation linéaire

suivante pour l’intersection de la tangente avec l’axe des abscisses :

52
Short title of document

Figure 3.1 – Illustration de la racine (zéro) de la fonction continue 𝑓 (𝑥) = cos(𝑥) − 𝑥 3 . La courbe bleue
représente la fonction, et le marqueur rouge indique l’emplacement de la racine approximative 𝑥¯ ≈ 0.865,
où la fonction s’annule.

0 = 𝑓 (𝑥0 ) + 𝑓 ′(𝑥0 )(𝑥 − 𝑥0 ).

Cela donne un nouveau point 𝑥1 , qui devrait être plus proche du zéro de la
fonction que le point initial 𝑥0 . En répétant ce processus d’approximation par la
tangente aux points successifs (𝑥1 , 𝑥 2 , etc.), on peut améliorer progressivement
l’approximation du zéro de 𝑓 .
La figure 3.2 montre le processus itératif de la méthode de Newton-Raphson,
qui utilise la tangente à la courbe 𝑦 = 𝑓 (𝑥) pour obtenir une meilleure approxi-
mation de la racine de la fonction à chaque itération.
(a) Le principe général est illustré, avec l’utilisation de la tangente en un point
(𝑥 𝑛 , 𝑓 (𝑥 𝑛 )) pour estimer 𝑥 𝑛+1 . (b) à (f) montrent les itérations successives (𝑥1 à
𝑥5 ), où chaque nouvelle estimation affine la précision par rapport à la racine
recherchée. Ce processus démontre la rapidité de convergence de la méthode,
sous réserve que l’estimation initiale soit adéquate.

53
Short title of document

Figure 3.2 – Illustration de la racine (zéro) de la fonction continue 𝑓 (𝑥) = cos(𝑥) − 𝑥 3 . La courbe bleue
représente la fonction, et le marqueur rouge indique l’emplacement de la racine approximative 𝑥¯ ≈ 0.865,
où la fonction s’annule.

Data: Une fonction 𝑓 (𝑥), sa dérivée 𝑓 ′(𝑥), une estimation initiale 𝑥0 , une
tolérance 𝜖, un nombre maximal d’itérations 𝑁max .
Result: Une approximation de la racine 𝑥 ∗ .
begin
𝑛 ← 0;
while 𝑛 < 𝑁max do
Calculer 𝑓 (𝑥 𝑛 ) et 𝑓 ′(𝑥 𝑛 );
if | 𝑓 (𝑥 𝑛 )| < 𝜖 then
Retourner 𝑥 𝑛 (la racine est trouvée);
end
if 𝑓 ′(𝑥 𝑛 ) = 0 then
Erreur : la dérivée est nulle, la méthode échoue;
Arrêter;
end
𝑓 (𝑥 𝑛 )
Mettre à jour 𝑥 𝑛+1 ← 𝑥 𝑛 − 𝑓 ′ (𝑥 𝑛 )
;
𝑛 ← 𝑛 + 1;
end
Retourner 𝑥 𝑛 (approximation après 𝑁max itérations);
end
Algorithm 2: Méthode de Newton-Raphson pour trouver la racine d’une
fonction
54
Short title of document

Example 3.0.2. Pour illustrer la méthode, recherchons le nombre positif 𝑥 véri-

fiant cos(𝑥) = 𝑥 3 . Reformulons la question pour introduire une fonction devant
s’annuler : on recherche le zéro positif (la racine) de 𝑓 (𝑥) = cos(𝑥) − 𝑥 3 . La
dérivation donne 𝑓 ′(𝑥) = − sin(𝑥) − 3𝑥 2 .
Comme cos(𝑥) ≤ 1 pour tout 𝑥 et 𝑥 3 > 1 pour 𝑥 > 1, nous savons que
notre zéro ne peut être supérieur à 1. De plus, cos(0) = 1 > 0 = 03 et cos(1) <
cos(𝜋/4) < 1 = 13 , ce qui nous permet de conclure que notre zéro appartient à
l’intervalle [0, 1].
Nous prenons comme valeur de départ 𝑥0 = 0, 5 :
𝑓 (𝑥 𝑛−1 )
𝑥𝑛 𝑥 𝑛 = 𝑥 𝑛−1 − 𝑓 ′ (𝑥 𝑛−1 )
Approximation numérique
cos(0,5)−0,53
𝑥1 0, 5 − − sin(0,5)−3×0,52
≈ 1, 112 141 637 097 2
𝑥2 ··· ≈ 0, 909 672 693 736 8
𝑥3 ··· ≈ 0, 866 263 818 208 8
𝑥4 ··· ≈ 0, 865 477 135 298 2
𝑥5 ··· ≈ 0, 865 474 033 110 9
𝑥6 ··· ≈ 0, 865 474 033 101 6
𝑥7 ··· ≈ 0, 865 474 033 101 6
Ainsi, la méthode de Newton converge vers la solution 𝑥 ≃ 0, 865 474 033 101 6.

Problèmes de minimisation sans contraintes

Les problèmes d’optimisation les plus simples sont ceux qui consistent à
minimiser (ou maximiser) une fonction 𝑓 : 𝑊 ⊂ R → R. Le problème général
d’optimisation sans contrainte peut être formulé de la manière suivante :

min 𝑓 (𝑥) (3.1)

𝑥∈R

Il s’agit donc de déterminer un point 𝑥 ∗ de R tel que :

∀𝑥 ∈ R : 𝑓 (𝑥 ∗ ) < 𝑓 (𝑥) (3.2)

c’est-à-dire un minimum global de 𝑓 sur R. Lorsque l’inégalité stricte 𝑓 (𝑥 ∗ ) <
𝑓 (𝑥) est vérifiée pour tout 𝑥 ≠ 𝑥 ∗ , le minimum global est unique comme c’est
illustré par le point entouré par le carré vert dans la figure 3.3.
Pour beaucoup de problèmes d’optimisation sans contrainte, les principales
méthodes de résolution connues ne permettent pas la détermination d’un mi-
nimum global : il faut alors se contenter de minimums locaux, c’est-à-dire des

55
Short title of document

Figure 3.3 – Représentation de la fonction 𝑓 (𝑥) = 0.1𝑥 2 + sin(3𝑥) + sin(5𝑥) avec des minima locaux
(cercles rouges) et un minimum global (carré vert).

points qui vérifient (3.2) seulement dans un voisinage de 𝑥 ∗ comme c’est illus-
tré par des point entourés de cercles dans la figure 3.3. On verra maintenant
comment de tels points peuvent être caractérisés.

Conditions nécessaires d’optimalité locale

Dans ce qui va suivre, on supposera que la fonction 𝑓 est au moins de classe

𝐶 1 (𝑊 𝑙 ). En fait, on suppose que
𝑓 est suffisamment différentiable pour éviter les
difficultés dans l’analyse des algorithmes de solution. De plus, on se limite à une
version locale du problème de minimisation de la fonction 𝑓 , soit qu’il existe un
voisinage 𝑉(𝑥 ∗ ) de 𝑥 ∗ tel que

∀𝑥 ∈ 𝑉(𝑥 ∗ ) : 𝑓 (𝑥 ∗ ) < 𝑓 (𝑥) (3.3)

Théorème 3.0.3 (Conditions nécessaires d’optimalité locale). Soit une fonction

𝑓 : R𝑛 → R de classe 𝐶 2 ; si 𝑥 ∗ est un minimum local de 𝑓 , alors

(a) ∇ 𝑓 (𝑥 ∗ ) = 0
(b) ∇2 𝑓 (𝑥 ∗ ) est une matrice semi-définie positive

Théorème 3.0.4. ] [Conditions suffisantes d’optimalité locale]Soit une fonction

𝑓 : R𝑛 → R de classe 𝐶 2 ; Si les deux conditions suivante sont satisfaites :
(a) ∇ 𝑓 (𝑥 ∗ ) = 0
(b) ∇2 𝑓 (𝑥 ∗ ) est une matrice définie positive
alors 𝑥 ∗ est un minimum local de 𝑓 .

56
Short title of document Algorithme de Newton descente de gradient explicite

Définition 3.0.5. Un point 𝑥 ∗ qui vérifie la condition ∇ 𝑓 (𝑥 ∗ ) = 0 est appelé point

stationnaire.

※ Algorithme de Newton descente de gradient explicite

Pour obtenir un minimum local de 𝑓 , d’après le théorème 3.0.4 exprimant les
conditions suffisantes d’optimalité pour qu’un point 𝑥 ∗ est un minimum local
sont
∇ 𝑓 (𝑥 ∗ ) = 0 et ∇2 𝑓 (𝑥 ∗ ) est une matrice définie positive (3.4)
En posant
𝑔(𝑥) := ∇ 𝑓 (𝑥) (3.5)

On remarque que 𝑥 ∗ est un minimum local de 𝑓 alors 𝑥 ∗ est un point station-

naire de la fonction 𝑔(𝑥). Donc on peut appliquer l’algorithme 2 pour converger
vers un point stationnaire de la fonction 𝑔(𝑥 ∗ ) = ∇ 𝑓 (𝑥 ∗ ) = 0 toute en tenant
compte que la deuxième condition ∇2 𝑓 (𝑥 ∗ ) définie positive est satisfaite. ré-
sume les étapes de l’approche de Newton pour atteindre un minimum local.
Data: Approximation initiale 𝑥 0 , tolérance 𝜖, nombre maximal
d’itérations 𝑁max
Result: Approximation du minimum local 𝑥∗
𝑘 ← 0;
while 𝑘 < 𝑁max et ∇ 𝑓 (𝑥 𝑘 ) > 𝜖 do
Calculer la dérivée première (gradient) 𝑔 𝑘 = ∇ 𝑓 (𝑥 𝑘 );
Calculer la dérivée seconde (Hessien) 𝐻 𝑘 = ∇2 𝑓 (𝑥 𝑘 );
if 𝐻 𝑘 est définie positive then
𝑥 𝑘+1 ← 𝑥 𝑘 − 𝐻 𝑘−1 𝑔 𝑘 ;
end
else
Sortie : La matrice Hessienne n’est pas définie positive;
end
𝑘 ← 𝑘 + 1;
end
Algorithm 3: Méthode de Newton pour trouver le minimum d’une fonction
en 1D
L’algorithme 2 est appliqué à la fonction suivante :

1
𝑓 (𝑥) = 1 − (3.6)
5𝑥 2 − 6𝑥 + 5

57
Short title of document Algorithme de Newton descente de gradient explicite

rapportée dans la figure 3.4. Sa dérivée première est donnée par :

10𝑥 − 6
𝑓 ′(𝑥) = (3.7)
(5𝑥 2 − 6𝑥 + 5)2

et sa dérivée seconde par :

′′ 10(5𝑥 2 − 6𝑥 + 5) − (10𝑥 − 6)(20𝑥 − 12)

𝑓 (𝑥) = (3.8)
(5𝑥 2 − 6𝑥 + 5)3

Le tableau 3.1 présente les itérations de convergence de l’algorithme 2 vers

Figure 3.4 – Représentation de la fonction 1 − 1

5𝑥 2 −6𝑥+5
montrant un minimum local isolé en 𝑥 ∗ = 0.6.

le point stationnaire 𝑥 ∗ = 0.6. On observe que la convergence est très rapide,

atteignant le point souhaité en seulement trois itérations.

Itérations de l’algorithme de Newton

Itération 𝑥𝑘 𝑥 𝑘+1 𝑓 ′(𝑥 𝑘+1 ) 𝑓 ′′(𝑥 𝑘+1 )

0 0.5000000000 0.6065573770 -0.0946745562 0.8884842968
1 0.6065573770 0.5999982374 0.0064028281 0.9761688967
2 0.5999982374 0.6000000000 -0.0000017213 0.9765625000
1
Table 3.1 – Itérations de l’algorithme de Newton sur la fonction 1 − 5𝑥 2 −6𝑥+5
.

58
Short title of document Algorithme de Newton descente de gradient explicite

Algorithme de Newton par approximation du gradient

Lorsque les dérivées partielles d’une fonction 𝑓 : R𝑛 → R ne sont pas dispo-

nibles ou ne peuvent pas être calculées analytiquement, le gradient ∇ 𝑓 (𝑥) (1.1)
peut être approximé numériquement à l’aide de différences finies. L’approxima-
tion du gradient est donnée par :
 𝜕 𝑓 (𝑥)   𝑓 (𝑥 𝑘 +ℎ𝑒0 )− 𝑓 (𝑥 𝑘 −ℎ𝑒0 ) 
 𝜕𝑥1   2ℎ
 .   ..

 .
𝑔(𝑥) = ∇𝑥 𝑓 (𝑥) =  .  ≈   . .

(3.9)
 𝜕 𝑓 (𝑥)   𝑓 (𝑥 𝑘 +ℎ𝑒𝑛 )− 𝑓 (𝑥 𝑘 −ℎ𝑒𝑛 ) 
 𝜕𝑥   2ℎ
 𝑛  

où ℎ > 0 est un petit incrément, et 𝑒 𝑗 est le 𝑗-ième vecteur de la base canonique de

R𝑛 . De même, les composantes de la matrice Hessienne (1.2) sont approximées
par :

𝑓 (𝑥 𝑘 + ℎ𝑒 𝑖 + ℎ𝑒 𝑗 ) − 𝑓 (𝑥 𝑘 + ℎ𝑒 𝑖 ) − 𝑓 (𝑥 𝑘 + ℎ𝑒 𝑗 ) + 𝑓 (𝑥 𝑘 )
𝐻˜ 𝑘 (𝑖, 𝑗) ≈ (3.10)
ℎ2

59
Short title of document Algorithme de Newton descente de gradient explicite

Data: Approximation initiale 𝑥0 ∈ R𝑛 , tolérance 𝜖 > 0, nombre maximal

d’itérations 𝑁max , petit pas ℎ > 0 pour l’approximation des
dérivées
Result: Approximation du minimum local 𝑥∗
𝑘 ← 0;
while 𝑘 < 𝑁max et ∥∇ 𝑓 (𝑥 𝑘 )∥ > 𝜖 do
Approximer le gradient ∇ 𝑓 (𝑥 𝑘 ) par différences finies centrées :;
for 𝑗 = 1 to 𝑛 do
𝑓 (𝑥 +ℎ𝑒 𝑗 )− 𝑓 (𝑥 −ℎ𝑒 𝑗 )
𝑘 𝑘
𝑔˜ 𝑘 (𝑗) ← 2ℎ ;
end
Approximer la matrice Hessienne 𝐻 𝑘 par différences finies :;
for 𝑖 = 1 to 𝑛 do
for 𝑗 = 1 to 𝑛 do
𝑓 (𝑥 𝑘 +ℎ𝑒 𝑖 +ℎ𝑒 𝑗 )− 𝑓 (𝑥 𝑘 +ℎ𝑒 𝑖 )− 𝑓 (𝑥 𝑘 +ℎ𝑒 𝑗 )+ 𝑓 (𝑥 𝑘 )
𝐻˜ 𝑘 (𝑖, 𝑗) ← ℎ 2 ;
end
end
if 𝐻˜ est définie positive then
𝑥 𝑘+1 ← 𝑥 𝑘 − 𝐻˜ 𝑘−1 𝑔˜ 𝑘 ;
end
else
Sortie : La matrice Hessienne n’est pas définie positive;
Stop;
end
𝑘 ← 𝑘 + 1;
end
Algorithm 4: Algorithme de Newton avec approximations numériques pour
minimiser une fonction à valeur réelle 𝑓 (𝑥).
Dans l’algorithm utilise une approximation du gradient et du hessien pour
mettre à jour la valeur de 𝑥 jusqu’à ce que la norme du gradient soit suffisamment
petite, indiquant que nous avons atteint un minimum local.
Ce tableau montre les valeurs calculées pour chaque itération de l’algorithme,
avec une précision de 10 chiffres après la virgule pour chaque valeur de 𝑥 𝑘 , 𝑓 ′(𝑥 𝑘 ),
et 𝑓 ′′(𝑥 𝑘 ). On remarque dans cet exemple que la différence entre les résultats de
l’utilisation de l’expression exacte du gradient et de la matrice hessienne dans
le tableau 3.1 et les résultats de l’approximation du gradient et hessien dans le
tableau 3.2 se limite à une seule itération pour atteindre le minimum 𝑥 ∗ = 0.6.

60
Short title of document Méthode de Descente Général

Itération 𝑥𝑘 𝑓 ′(𝑥 𝑘 ) 𝑓 ′′(𝑥 𝑘 )

0 0.5000000000 -0.0946745562 0.8884837310
1 0.6065574449 0.0064028943 0.9761702557
2 0.5999982465 -0.0000017124 0.9765621645
3 0.6000000000 0.0000000000 0.9 765621645

Table 3.2 – Itérations de l’algorithme de Newton avec approximations numériques pour minimiser la
1
fonction 1 − 5𝑥 2 −6𝑥+5 .

※ Méthode de Descente Général

En général, l’analyse du problème de minimiser localement une fonction de
𝑛 variables ne peut pas se réduire à l’analyse de la minimisation locale d’une
fonction d’une seule variable. On pourrait réécrire le problème ainsi :

𝑓 (𝑥 ∗ ) ≤ 𝑓 (𝑥 ∗ + 𝛼𝑑), ∀𝑑 ∈ 𝑉(0),

où 𝑑 représente le déplacement de 𝑥 ∗ à un point voisin, ou encore, en séparant

la notion de direction et la notion de distance du déplacement,

𝑓 (𝑥 ∗ ) ≤ 𝑓 (𝑥 ∗ + 𝛼𝑑), ∀𝑑 ∈ R𝑛 , ∥𝑑∥ = 1, et ∀𝛼 < 𝜖,

où 𝜖 représente le diamètre d’une boule centrée en 𝑥 ∗ contenue dans 𝑉(𝑥 ∗ ).

Cependant, nous ne pouvons pas établir d’équivalence entre les restrictions
unidimensionnelles et les problèmes originaux.
En fait, si 𝑥 ∗ est un minimum local de 𝑓 , alors 0 est un minimum local d’une
def
seule variable ℎ 𝑥 ∗ ,𝑑 (𝛼) = 𝑓 (𝑥 ∗ + 𝛼𝑑), et ce quelle que soit la valeur de 𝑑 ∈ R𝑛
telle que ∥𝑑∥ = 1.

Théorème 3.2.1 (Approximation de Taylor Linéaire). Soit 𝑓 : R𝑛 → R une

fonction de classe 𝐶 1 au voisinage d’un point 𝑥 ∗ . On peut approcher la valeur
de la fonction en un point voisin 𝑥 ∗ + 𝑑 de 𝑥 ∗ par une fonction polynomiale de
degré 1.

𝑓 (𝑥 ∗ + 𝛼𝑑) ≈ 𝒫linéaire (𝑑) = 𝑓 (𝑥 ∗ ) + 𝛼∇ 𝑓 (𝑥 ∗ ) · 𝑑. (3.11)

Ici, 𝒫linéaire (𝑑) est l’approximation de Taylor linéaire de 𝑓 (𝑥) au point 𝑥 ∗ .

Les méthodes de descente sont fondamentales en optimisation pour mini-

miser des fonctions. Elles consistent à chercher une nouvelle solution à chaque

61
Short title of document Méthode de Descente Général

itération en se déplaçant dans une direction qui réduit la valeur de la fonction

objectif. En général, la solution à l’itération (𝑘 + 1)-ème est donnée par

𝑥 𝑘+1 = 𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 , 𝛼𝑘 > 0 (3.12)

où 𝑑 𝑘 est la direction de pas et 𝛼 𝑘 est la taille du pas le long de cette direction.

Le processus de recherche de 𝛼 𝑘 , appelé recherche de ligne, consiste à trouver la
taille de pas optimale qui minimise la fonction le long de 𝑑 𝑘 . Dans les méthodes
de descente, la fonction à minimiser diminue à chaque itération, c’est-à-dire que,
pour minimiser une fonction 𝑓 , on a :

𝑓 (𝑥 𝑘+1 ) < 𝑓 (𝑥 𝑘 )

sauf lorsque 𝑥 𝑘 est déjà optimal. Pour garantir une diminution de la fonction,
la direction de descente 𝑑 𝑘 doit satisfaire :

∇ 𝑓 (𝑥 𝑘 )𝑇 𝑑 𝑘 < 0 (3.13)

Cela signifie que la direction de recherche doit former un angle aigu avec le
négatif du gradient de la fonction. Une telle direction est connue sous le nom
de direction de descente. Un algorithme général pour une méthode de descente
d’optimisation est donné par l’Algorithme 5.
Input: Initialisation : 𝑥0 , tolérance 𝜖 0
Output: Solution optimale 𝑥 𝑘
for 𝑘 = 1, 2, . . . do
Trouver une direction de descente 𝑑 𝑘 ;
Recherche de ligne : Choisir une taille de pas 𝛼 𝑘 > 0tel que :;
𝛼 𝑘 ← arg min𝛼≥0 𝑓 (𝑥 + 𝛼𝑑)) ;
Mettre à jour la solution en utilisant l’équation : 𝑥 𝑘+1 = 𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 ;
if ∥∇ 𝑓 (𝑥 𝑘+1 )∥2 ≤ 𝜖0 then
Sortir;
end
end
Algorithm 5: Méthode Générale de Descente
Pour qu’on puisse appliquer l’algorithme de décente 5 pour converger vers
un minimum, à chaque itération, on doit absolument spécifier deux inconnus :
1. La direction de recherche de descente 𝑑 𝑘
2. La méthode de calcul du pas de déplacement 𝛼 𝑘

62
Short title of document Méthode de Descente Général

La direction de recherche de descente

Proposition 3.2.2. Si ∇ 𝑓 (𝑥) ≠ 0, la direction 𝑑 = −∇ 𝑓 (𝑥) est une direction de

descente pour 𝑓 au point 𝑥.
En effet, en substituant la direction 𝑑 = −∇ 𝑓 (𝑥) dans la relation (3.11 et pour
𝛼 = 1, on obtient :

𝑓 (𝑥 + 𝑑) ≈ 𝑓 (𝑥) + ∇ 𝑓 (𝑥) · (−∇ 𝑓 (𝑥)) = 𝑓 (𝑥) − ∥∇ 𝑓 (𝑥)∥2 . (3.14)

Le produit scalaire ⟨∇ 𝑓 (𝑥), −∇ 𝑓 (𝑥)⟩ = −∥∇ 𝑓 (𝑥)∥2 < 0 montre que, pour un
petit pas 𝛼 > 0, on a
𝑓 (𝑥 + 𝛼𝑑) < 𝑓 (𝑥).

Cela signifie que la fonction 𝑓 diminue le long de la direction opposée au

gradient.

Figure 3.5 – Illustration de la descente de gradient pour la fonction 𝑓 (𝑥) = 1 − 5𝑥 2 −6𝑥+5

1
. Les points rouges
montrent la progression de la descente de gradient à partir du point initial 𝑥0 = 0.9 jusqu’à l’optimum
𝑥 ∗ = 0.6. Le pas de déplacement est fixé à 𝛼 = 1.

Comme illustré à la figure 3.5, la descente de gradient (avec un pas de dépla-

cement fixe 𝛼 𝑘 = 1) permet dans cet exemple de se rapprocher progressivement
du point optimal 𝑥 ∗ . Les points rouges montrent les étapes successives de cette
descente à partir du point initial 𝑥 0 , jusqu’à atteindre le minimum de la fonction.

63
Short title of document Méthode de Recherche de Ligne Exacte

La méthode de calcul du pas de déplacement 𝛼 𝑘

※ Méthode de Recherche de Ligne Exacte

Pour affiner la recherche de la taille de pas 𝛼 𝑘 , la méthode de recherche de
ligne exacte résout un problème d’optimisation le long de la direction 𝑑 𝑘 . Cette
approche consiste à minimiser 𝑓 le long du rayon {𝑥 + 𝛼𝑑|𝛼 > 0} :

𝛼 𝑘 = arg min 𝑓 (𝑥 + 𝛼𝑑) (3.15)

𝑣≥0

Cependant, la recherche de ligne exacte peut être computationnellement

coûteuse pour les grands problèmes, ce qui limite son utilisation en pratique.

Définition 3.3.1 (Direction suffisamment descendante). Une direction 𝑑 est dite

**suffisamment descendante** s’il existe deux constantes positives 𝛾0 et 𝛾1 , in-
dépendantes de 𝑥, telles que 𝑑 vérifie les deux inégalités suivantes :

— ∇ 𝑓 (𝑥) · 𝑑 ≤ −𝛾0 ∥∇ 𝑓 (𝑥)∥2 ,

— ∥𝑑∥ ≤ 𝛾1 ∥∇ 𝑓 (𝑥)∥.

Une fois qu’une direction 𝑑 suffisamment descendante est déterminée, il

convient de spécifier une longueur de déplacement admissible, souvent appelée
pas de déplacement.

Définition 3.3.2 (Critères d’Armijo et de Wolfe). Un pas 𝛼 est dit admissible

pour une direction suffisamment descendante 𝑑 s’il satisfait aux deux conditions
suivantes :

— Critère d’Armijo :
 
1
𝑓 (𝑥 + 𝛼𝑑) − 𝑓 (𝑥) < 𝜏𝛼∇ 𝑓 (𝑥) · 𝑑, avec 𝜏 ∈ 0, ,
2

— Critère de Wolfe :

∇ 𝑓 (𝑥 + 𝛼𝑑) · 𝑑 ≥ 𝜎∇ 𝑓 (𝑥) · 𝑑, avec 𝜎 ∈ ]0, 1[ .

où 𝜏 et 𝜎 sont des paramètres fixés pour déterminer l’admissibilité du pas.

Théorème 3.3.3. Soit un algorithme de descente appliqué au problème

min𝑛 𝑓 (𝑥), 𝑓 ∈ 𝐶 1 (R𝑛 );

𝑥∈R

64
Short title of document Méthode de Recherche de Ligne Exacte

supposons qu’à chaque itération la direction utilisée 𝑑 𝑘 est une direction

suffisamment descendante, et que le pas 𝛼 𝑘 utilisé dans cette direction est un
pas admissible ; alors, tous les points d’accumulation de la suite {𝑥 𝑘 } engendrée
par l’algorithme sont des points stationnaires pour le problème min 𝑓 (𝑥).

Ce théorème garantit la convergence vers des points stationnaires lorsque la

direction est suffisamment descendante et que le pas est admissible. Le théorème
suivant précise le calcul de ce pas 𝛼 𝑘 en le choisissant comme la première valeur
d’une séquence géométrique satisfaisant au critère d’Armijo.

Théorème 3.3.4. Soit un algorithme de descente appliqué au problème

min𝑛 𝑓 (𝑥), 𝑓 ∈ 𝐶 1 (R𝑛 );

𝑥∈R

supposons qu’à chaque itération la direction utilisée 𝑑 𝑘 est une direction

suffisamment descendante, et que le pas 𝛼 𝑘 utilisé dans cette direction est la
première valeur de la suite
  𝑚 
1 1 1
1, , , . . . , ,... (3.16)
2 4 2
qui satisfasse au critère d’Armijo ; alors, tous les points d’accumulation de
la suite {𝑥 𝑘 } engendrée par l’algorithme sont des points stationnaires pour le
problème min 𝑓 (𝑥).

Avec ce choix de 𝛼 𝑘 selon la suite géométrique (3.16), on garantit que le pas

est suffisamment petit pour satisfaire au critère d’Armijo. Ce mécanisme permet
de maintenir la décroissance de la fonction 𝑓 , assurant ainsi la convergence vers
un point stationnaire, car l’algorithme ne prend jamais de pas trop grands et
ajuste progressivement la longueur du déplacement jusqu’à ce qu’il trouve une
direction qui respecte la condition de suffisance de descente. L’algorithme de
recul fonctionne en démarrant avec une longueur de pas initiale 𝛼0 , souvent
égale à 1 dans le cas de la méthode de Newton. Si la condition de décroissance
suffisante d’Armijo n’est pas satisfaite (c’est-à-dire si le pas est trop grand),
le pas est multiplié par un facteur de réduction 𝜌, généralement choisi dans
l’intervalle (0, 1), jusqu’à ce que la condition d’Armijo soit remplie. Cela garantit
une convergence progressive vers un point stationnaire tout en évitant des pas
trop petits ou inefficaces.

65
Short title of document Exemple numérique

Entrée: Point de départ 𝑥0

Entrée: Critère de convergence 𝜖 > 0
Entrée: Nombre maximal d’itérations 𝑁
Sortie : Point optimal 𝑥 𝑘 et valeur optimale 𝑓 (𝑥 𝑘 )
𝑘 ← 0;
while 𝑘 ≤ 𝑁 do
Calculer (ou approximer) le gradient ∇ 𝑓 (𝑥 𝑘 ) (3.9);
𝑑 𝑘 ← −∇ 𝑓 (𝑥 𝑘 );
if ∥𝑑 𝑘 ∥ ≤ 𝜖 then
Sortir;
end
𝛼 𝑘 ← 1;
1 first line while 𝑓 (𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 ) ≥ 𝑓 (𝑥 𝑘 ) + 𝑐𝛼 𝑘 ∇ 𝑓 (𝑥 𝑘 )⊤ 𝑑 𝑘 do
2 𝛼 𝑘 ← 𝛼2𝑘 ;
end
𝑥 𝑘+1 ← 𝑥 𝑘 + 𝛼 𝑘 𝑑 𝑘 ;
𝑘 ← 𝑘 + 1;
end
Retourner 𝑥 𝑘 , 𝑓 (𝑥 𝑘 );
Algorithm 6: Algorithme de la descente la plus raide avec calcul du pas selon
la suite géométrique

※ Exemple numérique
Pour illustrer l’algorithme de descente de gradient avec recherche linéaire,
nous allons résoudre le problème d’optimisation non contraint suivant :

min 𝑓 (𝑥) = 𝑥1 − 𝑥2 + 2𝑥 1 𝑥2 + 2𝑥 12 + 𝑥 22
𝑥1 ,𝑥 2

Première itération :

Le gradient de la fonction objectif est donné par :

" #
1 + 2𝑥 2 + 4𝑥1
∇ 𝑓 (𝑥) =
−1 + 2𝑥 1 + 2𝑥2

66
Short title of document Exemple numérique
" #
0
En partant de 𝑥 0 = , on a :
0
" #
1
∇ 𝑓 (𝑥 0 ) =
−1
" #
−1
La direction de descente est donc 𝑑0 = −∇ 𝑓 (𝑥0 ) = .
1
Nous appliquons la règle de recherche linéaire d’Armijo les lignes 1 et 2 de
l’algorithme est 𝛼0 =1. Ainsi, la mise à jour de 𝑥 donne :
" # " # " #
0 −1 −1
𝑥 1 = 𝑥 0 + 𝛼 0 𝑑0 = + 1.0 · =
0 1 1

Deuxième itération :
" #
−1
Étant donné 𝑥1 = , on calcule le gradient :
1
" # " #
1 + 2 · 1 + 4 · (−1) −1
∇ 𝑓 (𝑥1 ) = =
−1 + 2 · (−1) + 2 · 1 −1
" #
1
La direction de descente est 𝑑1 = −∇ 𝑓 (𝑥1 ) = .
1
En appliquant deux itération des lignes 1-2 d’Armijo, nous trouvons que
𝛼1 = 0.25. La nouvelle valeur de 𝑥 est donc :
" # " # " #
−1 1 −0.75
𝑥 2 = 𝑥 1 + 𝛼 1 𝑑1 = + 0.25 · =
1 1 1.25

Troisième itération :
" # " #
−0.75 0.5
À partir de 𝑥2 = , on calcule le gradient : ∇ 𝑓 (𝑥2 ) = La direction
1.25 0
" #
−0.5
de descente est 𝑑2 = −∇ 𝑓 (𝑥2 ) = . Avec deux iterations des lignes 1 et 2 du
0
critère d’Armijo, on trouve 𝛼2 = 0.25. La mise à jour de 𝑥 est donc :
" # " # " #
−0.75 −0.5 −0.875
𝑥 3 = 𝑥 2 + 𝛼 2 𝑑2 = + 0.25 · =
1.25 0 1.25

67
Short title of document Exemple numérique

Quatrième itération :
" # " #
−0.875 0.0
Avec 𝑥3 = , le gradient devient : ∇ 𝑓 (𝑥3 ) =
1.25 0.25
" #
0.0
La direction de descente est 𝑑3 = −∇ 𝑓 (𝑥3 ) = . Avec une itération du
−0.25
critère d’Armijo on obtient 𝛼3 = 0.5. Donc :
" # " # " #
−0.875 0.0 −0.875
𝑥 4 = 𝑥 3 + 𝛼 3 𝑑3 = + 0.5 · =
1.25 0.25 1.375

Terminaison :

Le gradient au point 𝑥31 est :

" #
7.62939453𝑒 − 06
∇ 𝑓 (𝑥5 ) =
0

La norme du gradient est :

||∇ 𝑓 (𝑥5 )|| ≈ 0.0001

Puisque cette valeur est suffisamment proche de zéro, l’algorithme converge. La

solution optimale est donc :
" #
−1.0
𝑥∗ = , 𝑓 (𝑥 ∗ ) ≈ −1.23
1.50

Nous appliquons l’algorithme de descente de gradient et les approches de re-

cherche de ligne présentées pour trouver la solution optimale. Les résultats sont
résumés dans le tableau 3.3.

68
Short title of document Exemple numérique

Itération xk dk ∥dk ∥ 𝛼𝑘
0 [0, 0] [-1, 1] 1.4142 1.0000
1 [-1, 1] [1, 1] 1.4142 0.2500
2 [-0.75, 1.25] [-0.5, -0] 0.5000 0.2500
3 [-0.875, 1.25] [-0, 0.25] 0.2500 0.5000
4 [-0.875, 1.375] [-0.25, -0] 0.2500 0.2500
5 [-0.9375, 1.375] [-0, 0.125] 0.1250 0.5000
.. .. .. ..
. . . .
24 [-0.99987793, 1.49987793] [-0.00024414, -0] 0.0002 0.2500
25 [-0.99993896, 1.49987793] [-0, 0.00012207] 0.0001 0.5000
26 [-0.99993896, 1.49993896] [-0.00012207, -0] 0.0001 0.2500
27 [-0.99996948, 1.49993896] [-0, 0.000061035] 0.0001 0.5000
28 [-0.99996948, 1.49996948] [-0.000061035, -0] 0.0001 0.2500
29 [-0.99998474, 1.49996948] [-0, 0.0000305176] 0.0000 0.5000
30 [-0.99998474, 1.49998474] [-0.0000305176, -0] 0.0000 0.2500
31 [-0.99999237, 1.49998474] [-0, 0.0000152588] 0.0000 0.5000

Table 3.3 – Résultats détaillés des itérations de l’algorithme de descente avec point de départ (0, 0) et le
paramètre 𝑐 = 0.1

3.4.1 La descente de gradient stochastique (SGD) :

Le descente de gradient stochastique (abrégée SGD) est une méthode itérative

souvent utilisée en apprentissage automatique pour optimiser la descente du
gradient lors de chaque recherche une fois qu’un vecteur de poids aléatoire est
choisi.
En apprentissage profond, la fonction objectif est généralement la moyenne
des fonctions de perte pour chaque exemple dans l’ensemble de données d’en-
traînement. Étant donné un ensemble de données d’entraînement de 𝑛 exemples,
nous supposons que 𝑓𝑖 (x) est la fonction de perte par rapport à l’exemple d’en-
traînement d’indice 𝑖, où x est le vecteur de paramètres. Nous obtenons alors la
fonction objectif

𝑛
1Õ
𝑓 (x) = 𝑓𝑖 (x).
𝑛
𝑖=1

Le gradient de la fonction objectif en x est calculé comme

69
Short title of document Exemple numérique

𝑛
1Õ
∇ 𝑓 (x) = ∇ 𝑓𝑖 (x).
𝑛
𝑖=1

Si la descente de gradient est utilisée, le coût computationnel pour chaque

itération de la variable indépendante est 𝑂(𝑛), ce qui croît linéairement avec 𝑛.
Par conséquent, lorsque l’ensemble de données d’entraînement est plus grand,
le coût de la descente de gradient pour chaque itération sera plus élevé.
La descente de gradient stochastique (SGD) réduit le coût computationnel
à chaque itération. À chaque itération de la descente de gradient stochastique,
nous échantillonnons uniformément un indice 𝑖 pour des exemples de données
au hasard, et calculons le gradient ∇ 𝑓𝑖 (x) pour mettre à jour x :

x ← x − 𝜂∇ 𝑓𝑖 (x),

où 𝜂 est le taux d’apprentissage. Nous pouvons voir que le coût computa-

tionnel pour chaque itération passe de 𝑂(𝑛) de la descente de gradient à la
constante 𝑂(1). De plus, nous voulons souligner que le gradient stochastique est
une estimation non biaisée du gradient complet car

E[∇ 𝑓𝑖 (x)] = ∇ 𝑓 (x).

Cela signifie que, en moyenne, le gradient stochastique est une bonne esti-
mation du gradient. Les étapes pour effectuer SGD sont les suivantes :
Input: Ensemble de données d’entraînement, taux d’apprentissage 𝜂,
nombre maximal d’itérations 𝑁
Output: Paramètres du modèle x
Initialiser x aléatoirement;
for 𝑡 = 1 to 𝑁 do
Choisir aléatoirement un exemple d’entraînement 𝑖;
Calculer le gradient stochastique ∇ 𝑓𝑖 (x);
Mettre à jour les paramètres du modèle : x ← x − 𝜂∇ 𝑓𝑖 (x);
end
Algorithm 7: Descente de gradient stochastique

70
Short title of document Exemple numérique

Exemple : Implémentation en Python de la Descente de Gradient Stochastique

Figure 3.6 – Régression linéaire avec l’algorithme de Descente de Gradient Stochastique (SGD). La figure
montre l’ajustement de la droite de régression aux données générées. Les points bleus représentent les
données réelles (𝑥 𝑖 , 𝑦 𝑖 ) et la ligne rouge est la prédiction de la régression calculée par SGD..

Soit un ensemble de données d’entraînement constitué de 𝑛 exemples notés

(𝑥 𝑖 , 𝑦 𝑖 ) pour 𝑖 = 1, 2, . . . , 𝑛, où 𝑥 𝑖 ∈ R𝑑 représente un vecteur de caractéristiques
et 𝑦 𝑖 ∈ R représente la valeur cible associée. L’objectif est de trouver un modèle
linéaire de la forme :

𝑦pred = 𝑥 · 𝑤 + 𝑏

où 𝑤 ∈ R𝑑 est le vecteur des poids et 𝑏 ∈ R est le biais. Où :

— 𝑋 est la matrice des caractéristiques d’entrée (taille 𝑛 × 𝑑),
— 𝑤 est le vecteur des poids,
— 𝑏 est le biais.
La fonction de coût utilisée est l’erreur quadratique moyenne (Mean Squared
Error, MSE) :

𝑛
1Õ
MSE(𝑤, 𝑏) = (𝑦 𝑖 − 𝑦ˆ 𝑖 )2
𝑛
𝑖=1

71
Short title of document Exemple numérique

Avec 𝑦ˆ 𝑖 = 𝑋𝑖 · 𝑤 + 𝑏.
La mise à jour des poids et du biais se fait selon les gradients de la fonction
de coût par rapport à 𝑤 et 𝑏 :

𝜕 2
MSE(𝑤, 𝑏) = 𝑋 𝑇 (𝑋 · 𝑤 + 𝑏 − 𝑦)
𝜕𝑤 𝑛
𝑛
𝜕 2Õ
MSE(𝑤, 𝑏) = (𝑋𝑖 · 𝑤 + 𝑏 − 𝑦 𝑖 )
𝜕𝑏 𝑛
𝑖=1

Les poids et le biais sont ensuite mis à jour à chaque itération de l’algorithme
SGD par :

𝜕
𝑤 := 𝑤 − 𝜂 · MSE(𝑤, 𝑏)
𝜕𝑤
𝜕
𝑏 := 𝑏 − 𝜂 · MSE(𝑤, 𝑏)
𝜕𝑏
Où 𝜂 est le taux d’apprentissage.
L’algorithme 7 basé sur la Descente de Gradient Stochastique (SGD) ajuste les
paramètres de la régression linéaire à partir d’un ensemble de données. La figure
3.6 montre les points de données (𝑥 𝑖 , 𝑦 𝑖 ) en bleu et la droite de régression prédite
en rouge. Le modèle est optimisé sur 1000 époques. Le tableau 3.4 résume les
résultats obtenus, montrant la diminution de la perte MSE à chaque époque, ce
qui indique la convergence du modèle. Les poids 𝑤 du modèle sont également
affichés après chaque époque.

1
Époque Perte (MSE) Poids (𝑤)
0 3.012 [1.23, -0.47, 2.06, 0.38, 0.52]
100 2.403 [0.89, -0.45, 1.89, 0.32, 0.45]
200 1.672 [0.72, -0.40, 1.50, 0.29, 0.40]
300 1.134 [0.65, -0.37, 1.31, 0.26, 0.36]
400 0.902 [0.61, -0.34, 1.19, 0.24, 0.33]
500 0.786 [0.58, -0.32, 1.13, 0.23, 0.31]
600 0.754 [0.57, -0.31, 1.09, 0.22, 0.30]
700 0.723 [0.56, -0.30, 1.05, 0.21, 0.29]
800 0.695 [0.55, -0.29, 1.02, 0.21, 0.28]
900 0.672 [0.54, -0.28, 0.99, 0.20, 0.27]

Table 3.4 – Résumé des résultats de l’entraînement du modèle avec SGD. Les poids sont mis à jour à
chaque époque et la perte (MSE) diminue à mesure que le modèle converge.

72
Short title of document Exemple numérique

Exemple d’Application : Réseaux de Neurones Convolutifs (CNN)2

Figure 3.7 – Un CNN est organisé en deux parties : l’extraction de l’information et l’analyse de cette
information (crédit : Lambert Rosique)

Les réseaux de neurones convolutifs (Convolutional Neural Networks, CNN)

sont couramment utilisés pour des tâches de vision par ordinateur comme la
classification d’images, la détection d’objets, etc. Pour comprendre comment
fonctionnent les CNN sans aucune "boîte noire", nous devons détailler chaque
étape mathématique. Voici les étapes principales avec leurs formules mathéma-
tiques :

1. Convolution

La convolution est l’opération fondamentale d’un CNN. Elle consiste à appli-

quer un filtre (ou noyau) sur l’entrée pour produire une carte de caractéristiques
(feature map).
Pour une entrée 2D (image) 𝐼 et un filtre 𝐾 de dimensions (ℎ, 𝑤), la sortie
(feature map) 𝑆 est calculée par :

ℎ−1 𝑤−1
Õ Õ
𝑆(𝑖, 𝑗) = (𝐼 ∗ 𝐾)(𝑖, 𝑗) = 𝐼(𝑖 + 𝑚, 𝑗 + 𝑛) · 𝐾(𝑚, 𝑛)
𝑚=0 𝑛=0

où 𝐼(𝑖, 𝑗) est le pixel de l’image d’entrée à la position (𝑖, 𝑗), et 𝐾(𝑚, 𝑛) est le
poids du filtre à la position (𝑚, 𝑛).

1. Une époque fait référence à un cycle complet où l’algorithme de machine learning utilise
l’ensemble du jeu de données pour mettre à jour les paramètres du modèle. Un modèle peut être
entraîné sur plusieurs époques, ce qui signifie que le jeu de données est vu plusieurs fois durant
l’entraînement.
2. Section facultatif.

73
Short title of document Exemple numérique

2. Ajout de Biais

Après la convolution, un biais est souvent ajouté à chaque valeur de la carte

de caractéristiques :

𝑆(𝑖, 𝑗) = (𝐼 ∗ 𝐾)(𝑖, 𝑗) + 𝑏

où 𝑏 est un biais appris pour chaque filtre.

3. Fonction d’Activation (ReLU)

Une fonction d’activation non linéaire, comme la fonction ReLU (Rectified

Linear Unit), est appliquée à chaque élément de la carte de caractéristiques pour
introduire la non-linéarité :

ReLU(𝑥) = max(0, 𝑥)

Ainsi, la carte de caractéristiques activée est donnée par :

𝐴(𝑖, 𝑗) = ReLU(𝑆(𝑖, 𝑗))

4. Pooling (Sous-échantillonnage)

Le pooling est utilisé pour réduire les dimensions spatiales de la carte de

caractéristiques, tout en conservant les informations les plus importantes. Le
pooling le plus courant est le Max Pooling, qui prend le maximum d’une région
de taille fixe (par exemple, 2 × 2) :

𝑃(𝑖, 𝑗) = max{𝐴(2𝑖, 2𝑗), 𝐴(2𝑖 + 1, 2𝑗), 𝐴(2𝑖, 2𝑗 + 1), 𝐴(2𝑖 + 1, 2𝑗 + 1)}

où 𝑃(𝑖, 𝑗) est la valeur de la carte de caractéristiques après le pooling à la

position (𝑖, 𝑗).

5. Aplatissage (Flattening)

Après plusieurs couches de convolution et de pooling, la sortie est aplatie en

un vecteur 1D pour être utilisé dans des couches entièrement connectées (dense

74
Short title of document Exemple numérique

layers). Si l’entrée après le pooling est de taille 𝑛 × 𝑛 × 𝑑, elle est transformée en

un vecteur de taille 𝑛 2 × 𝑑.

6. Couche Entièrement Connectée (Fully Connected Layer)

La couche entièrement connectée prend le vecteur aplati et applique une

transformation linéaire suivie d’une activation non linéaire. Pour un vecteur
d’entrée 𝑥 et des poids 𝑊 et biais 𝑏, la sortie est :

𝑦 = Activation(𝑊 · 𝑥 + 𝑏)

où l’activation peut être une fonction telle que la fonction sigmoïde, ReLU,
ou softmax pour la classification.

7. Fonction de Perte

Pour entraîner le CNN, une fonction de perte est définie pour mesurer la
différence entre la sortie prédite et la sortie réelle. Pour la classification, la cross-
entropy est couramment utilisée :

𝐶
Õ
𝐿=− 𝑦 𝑖 log( 𝑦ˆ 𝑖 )
𝑖=1

où 𝑦 𝑖 est la véritable étiquette (one-hot encodée) et 𝑦ˆ 𝑖 est la probabilité prédite

par le réseau pour la classe 𝑖. Différentes fonctions de perte sont rapportées dans
le tableau 3.5.
Table 3.5 – Tableau des différentes fonctions de perte et leurs applications courantes en apprentissage
machine.

Fonction de Perte Formule Mathématique Domaine d’Application

Perte d’Erreur Qua- Régression (réduit la dis-

dratique Moyenne 𝑁 tance quadratique entre
1 Õ
(Mean Squared 𝐿(𝑦, 𝑦)
ˆ = (𝑦 𝑖 − 𝑦ˆ 𝑖 )2 les valeurs prédites et les
𝑁
𝑖=1
Error, MSE) vraies valeurs)

75
Short title of document Exemple numérique

Fonction de Perte Formule Mathématique Domaine d’Application

Perte Logarithmique 𝑁 Classification binaire (mi-

1 Õ
ou Cross-Entropy 𝐿(𝑦, 𝑦)
ˆ =− (𝑦 𝑖 log( 𝑦ˆ 𝑖 ) nimise l’entropie croisée
𝑁
𝑖=1
(Log Loss / Cross- entre les vraies étiquettes et
Entropy Loss) +(1 − 𝑦 𝑖 ) log(1 − 𝑦ˆ 𝑖 )) les probabilités prédites)

Perte Entropie Croi-

𝐶
Classification multi-
sée Catégorique Õ
𝐿(𝑦, 𝑦)
ˆ =− 𝑦 𝑖 log( 𝑦ˆ 𝑖 ) classes (ex : classification
(Categorical Cross-
𝑖=1 d’images)
Entropy)

Perte Hinge (Hinge 𝑁

Õ Classification binaire (uti-
Loss) 𝐿(𝑦, 𝑦)
ˆ = max(0, 1 − 𝑦 𝑖 · 𝑦ˆ 𝑖 ) lisé dans les SVM)
𝑖=1

𝑁
1 Õ
𝐿(𝑦, 𝑦)
ˆ = 𝑙 𝑖 , où
𝑁
Perte Huber (Huber 𝑖=1 Régression robuste (moins
Loss) sensible aux outliers)
(
2 (𝑦 𝑖 − 𝑦ˆ 𝑖 ) si |𝑦 𝑖 − 𝑦ˆ 𝑖 | ≤ 𝛿
1 2
𝑙𝑖 =
𝛿(|𝑦 𝑖 − 𝑦ˆ 𝑖 | − 21 𝛿) sinon

𝑦 · 𝑦ˆ Apprentissage de simila-
Perte Cosine (Cosine
𝐿(𝑦, 𝑦)
ˆ =1− rité, modèles de recom-
Loss) ∥𝑦∥∥ 𝑦∥
ˆ
mandation

Classification des don-

Perte Focal (Focal nées déséquilibrées (par
ˆ = −𝛼(1 − 𝑦ˆ 𝑖 )𝛾 𝑦 𝑖 log( 𝑦ˆ 𝑖 )
𝐿(𝑦, 𝑦)
Loss) exemple, détection d’ob-
jets)

8. Propagation Rétrograde (Backpropagation)

Pour optimiser les poids et les biais, l’algorithme de rétropropagation est

utilisé. Il s’agit de calculer le gradient de la fonction de perte par rapport à

76
Short title of document Exemple numérique

chaque paramètre du réseau et de mettre à jour ces paramètres à l’aide de la

descente de gradient :

𝜕𝐿
𝑤new = 𝑤 old − 𝜂
𝜕𝑤
𝜕𝐿
où 𝜂 est le taux d’apprentissage et 𝜕𝑤
est le gradient de la perte par rapport
au poids 𝑤.

Table 3.6 – Tableau des différentes formules de mise à jours des poids et leurs application dans l’appren-
tissage automatique.

Algorithme d’Opti-
Mise à Jour des Poids Domaine d’Application
misation
Descente de Gra- Problèmes de grande
dient Stochastique 𝑤 𝑡+1 = 𝑤 𝑡 − 𝜂∇𝐿(𝑤 𝑡 ) échelle, apprentissage
(SGD) profond

Descente de Gra- 𝑣 𝑡+1 = 𝛽𝑣 𝑡 + 𝜂∇𝐿(𝑤 𝑡 ),

Accélère la convergence,
dient avec Momen-
𝑤 𝑡+1 = 𝑤 𝑡 − 𝑣 𝑡+1 réduit les oscillations
tum

Apprentissage adaptatif,
AdaGrad (Adaptive 𝜂
𝑤 𝑡+1 = 𝑤 𝑡 − √ ∇𝐿(𝑤 𝑡 ) rareté des données (NLP,
Gradient) 𝐺𝑡 + 𝜖
vision par ordinateur)

RMSprop (Root 𝐸[𝑔 2 ]𝑡 = 𝛽𝐸[𝑔 2 ]𝑡−1 + (1 − 𝛽)𝑔𝑡2 , Stabilise l’apprentissage,

Mean Square Propa- recommandé pour les
𝜂
gation) 𝑤 𝑡+1 = 𝑤 𝑡 − p ∇𝐿(𝑤 𝑡 ) réseaux récurrents
𝐸[𝑔 2 ]𝑡 + 𝜖

77
Short title of document Exemple numérique

Algorithme d’Opti-
Mise à Jour des Poids Domaine d’Application
misation

𝑚𝑡 = 𝛽1 𝑚𝑡−1 + (1 − 𝛽 1 )∇𝐿(𝑤 𝑡 ),

𝑣 𝑡 = 𝛽2 𝑣 𝑡−1 + (1 − 𝛽 2 )(∇𝐿(𝑤 𝑡 ))2 Méthode populaire pour

Adam (Adaptive Mo-
𝑚𝑡 𝑣𝑡 la plupart des réseaux de
ment Estimation) 𝑚ˆ𝑡 = 𝑡
, 𝑣ˆ 𝑡 =
1 − 𝛽1 1 − 𝛽 2𝑡 neurones profonds
𝜂𝑚
ˆ𝑡
𝑤 𝑡+1 = 𝑤 𝑡 − √
𝑣ˆ 𝑡 + 𝜖

𝑣 𝑡+1 = 𝛽𝑣 𝑡 + 𝜂∇𝐿(𝑤 𝑡 − 𝛽𝑣 𝑡 ), Améliore le taux de conver-

Nesterov Accelera-
gence par rapport à SGD
ted Gradient (NAG)
𝑤 𝑡+1 = 𝑤 𝑡 − 𝑣 𝑡+1 avec momentum

Utilise une approximation de

L-BFGS (Limited-
la matrice Hessienne pour une
memory Broyden- Régression logistique, pe-
mise à jour des poids plus pré-
Fletcher-Goldfarb- tits réseaux de neurones
cise sans stocker la matrice com-
Shanno)
plète

Les poids et biais des couches convolutives et entièrement connectées sont

mis à jour par gradient à chaque itération. Un CNN apprend des caractéristiques
hiérarchiques et fait des prédictions. Le tableau 3.6 présente les formules de mise
à jour des poids. Dans cet exemple, le taux d’apprentissage 𝜂 est constant et la
fonction 𝑙𝑟() retourne une valeur fixe.

78
Chapitre 4

Recherche opérationnelle

Éléments sur les graphes

Figure 4.1 – Exemple de graphe et d’arc

Un graphe orienté est un couple (𝑋 , 𝐸) où 𝑋 est un ensemble fini (sommets)

et 𝐸 est un sous-ensemble de 𝑋 × 𝑋 (arcs) :

— Un arc (𝑥, 𝑦) possède une extrémité initiale 𝑥 et une extrémité finale 𝑦.

— Une boucle est un arc dont les extrémités coïncident.
— Deux arcs ayant au moins une extrémité commune sont dits adjacents.
— On dit que 𝑦 ∈ 𝑋 est successeur de 𝑥 ∈ 𝑋 si (𝑥, 𝑦) ∈ 𝐸. L’ensemble des
successeurs de 𝑥 est noté Γ+ (𝑥), l’application 𝑥 ↦→ Γ+ (𝑥) est une applica-
tion multivoque qui associe à un élément de l’ensemble de départ plusieurs
éléments de l’ensemble d’arrivée.
— On dit que 𝑦 ∈ 𝑋 est prédécesseur de 𝑥 ∈ 𝑋 si (𝑦, 𝑥) ∈ 𝐸. L’ensemble des
prédécesseurs de 𝑥 est noté Γ− (𝑥), l’application 𝑥 ↦→ Γ− (𝑥) est une application
multivoque.
— Un sommet 𝑥 est adjacent (ou voisin) à 𝑦 s’il est le prédécesseur ou le succes-
seur de 𝑦.

79
Short title of document

— Soit 𝑥 ∈ 𝑋, on note Γ(𝑥) = Γ− (𝑥) ∪ Γ+ (𝑥) l’ensemble des voisins de 𝑥.

— Si Γ(𝑥) = ∅, 𝑥 est dit isolé.
— Soit 𝑒 = (𝑥, 𝑦) ∈ 𝐸, l’arc 𝑒 est incident à 𝑥 vers l’extérieur et incident à 𝑦 vers
l’intérieur.
— Le nombre d’arcs incidents à 𝑥 vers l’extérieur est noté 𝑑𝐺
+
(𝑥) et s’appelle le
demi-degré extérieur.
— Le nombre d’arcs incidents à 𝑥 vers l’intérieur est noté 𝑑𝐺
−
(𝑥) et s’appelle le
demi-degré intérieur.
— Le degré de 𝑥, noté 𝑑𝐺 (𝑥), est donné par :

− +
𝑑𝐺 (𝑥) = 𝑑𝐺 (𝑥) + 𝑑𝐺 (𝑥)

— Un 𝑝-graphe est un graphe dans lequel il y a au maximum 𝑝 arcs de la forme

(𝑥, 𝑦) entre deux sommets 𝑥 et 𝑦.

Figure 4.2 – Exemple de 𝑝-graphes

Un 1-graphe peut être représenté par le couple (𝑋 , 𝐸) ou par la donnée de 𝑋

et de l’application Γ+ (𝑥), ∀𝑥 ∈ 𝑋 ou Γ− (𝑥).

Terminaison

Un graphe peut être caractérisé par sa matrice d’adjacence 𝑀 = (𝑎 𝑖𝑗 ) de

dimension 𝑛 × 𝑛 avec 𝑛 = card(𝑋) où :
(
1 si (𝑥 𝑖 , 𝑥 𝑗 ) ∈ 𝐸
𝑎 𝑖𝑗 =
0 sinon

Le sous-graphe de (𝑋 , 𝐸) engendré par 𝑌 ⊂ 𝑋 est le graphe dont tous les

sommets sont dans 𝑌 et dont les arcs sont dans 𝐸 qui ont leurs extrémités dans
𝑌.

— Le graphe partiel d’un graphe engendré par 𝑉 ⊂ 𝐸 est le graphe (𝑋 , 𝑉).

— Un sous-graphe partiel est un sous-graphe d’un graphe partiel.

80
Short title of document

Figure 4.3 – Exemple de matrices d’adjacence pour un graphe orienté

— Un chemin dans (𝑋 , 𝐸) est une suite de sommets telle que si 𝑥 𝑘 , 𝑥 𝑙 sont deux
sommets consécutifs de cette suite alors (𝑥 𝑘 , 𝑥 𝑙 ) ∈ 𝐸.
— Un circuit dans (𝑋 , 𝐸) est un chemin dont le dernier sommet coïncide avec le
premier.
— Un chemin (resp. circuit) est dit élémentaire s’il contient une et une seule fois
chacun des sommets dans le graphe.
— Un chemin est dit Hamiltonien s’il passe une et une seule fois par chaque
sommet du graphe.
— Un chemin est dit Euclidien s’il passe une et une seule fois par chaque arc du
graphe.

Un graphe non orienté est un couple (𝑋 , 𝐸) où 𝑋 est un ensemble fini d’élé-

ments (sommets) et 𝐸 est un ensemble de paires de sommets affectés.

Figure 4.4 – Exemple de graphe non orienté

La matrice d’incidence d’un graphe symétrique (𝑋 , 𝐸) où 𝑋 = 𝑥1 , · · · , 𝑥 𝑛 et

𝐸 = 𝑒1 , · · · , 𝑒 𝑛 est la matrice 𝐵 = (𝑏 𝑖𝑗 ) de dimension 𝑛 × 𝑒 avec 𝑛 = card(𝑋) et
𝑒 = card(𝐸) où :

81
Short title of document Algorithmes sur les graphes

(a) Graphe non orienté (b) Matrice d’adjacence pour un

graphe non orienté

Figure 4.5 – Exemple de matrices d’adjacence pour un graphe non orienté

(
1, si (𝑥 𝑖 , 𝑥 𝑗 ) ∈ 𝐸
𝑏 𝑖𝑗 =
0, sinon
La matrice d’adjacence d’un graphe non orienté est symétrique. Les relations
entre arêtes et sommets, appelées les relations d’incidence, sonttoutes représen-
tées par la matrice d’incidence du graphe.

※ Algorithmes sur les graphes

4.1.1 Recherche en Largeur (BFS) pour un Graph

La recherche en largeur (BFS) est un algorithme fondamental de parcours de

graphes. Il consiste à visiter tous les noeuds connectés d’un graphe de manière
niveaux par niveaux. Cet algorithme est souvent utilisé dans les recherches de
chemins, les composantes connectées et les problèmes de chemin le plus court.
Cet algorithme garantit que tous les noeuds du graphe sont visités en largeur
d’abord.

82
Short title of document Fonctionnement de l’Algorithme BFS

(a) Étape 1 : initialement, la file d’at-

tente et les tableaux visités sont vides.

ß
(b) Étape 2 : poussez le noeud 0 dans (c) Étape 3 : Supprimez le noeud 0 du
la file d’attente et marquez-le comme début de la file d’attente, visitez les
visité. voisins non visités et placez-les dans
la file d’attente.

(d) Étape 4 : Supprimez le noeud 1 du (e) Étape 5 : Supprimez le noeud 2 du

début de la file d’attente, visitez les début de la file d’attente, visitez les
voisins non visités et placez-les dans voisins non visités et placez-les dans
la file d’attente. la file d’attente.

(f) Étape 6 : Supprimez le noeud 3 du (g) Étape 7 : Supprimez le noeud 4 du

début de la file d’attente, visitez les début de la file d’attente, visitez les
voisins non visités et placez-les dans voisins non visités et placez-les dans
la file d’attente. la file d’attente.

Figure 4.6 – Illustration des étapes de l’algorithme BFS.

※ Fonctionnement de l’Algorithme BFS

À partir de la racine, tous les noeuds d’un niveau particulier sont visités
en premier, puis les noeuds du niveau suivant sont parcourus jusqu’à ce que
tous les noeuds soient visités. Pour ce faire, une file est utilisée. Tous les noeuds
adjacents non visités du niveau actuel sont poussés dans la file et les noeuds du
niveau actuel sont marqués visités et retirés de la file.

83
Short title of document Problème du flot maximum

Data: Un graphe 𝐺 = (𝑉 , 𝐸), un nœud de départ 𝑠

Result: Ordre de visite des nœuds en largeur d’abord
Initialisation :
Créer une file 𝑄;
Créer un tableau 𝑣𝑖𝑠𝑖𝑡 initialisé à faux pour chaque nœud;
Marquer 𝑠 comme visité (visité[s] = vrai);
Enfiler 𝑠 dans 𝑄;
while 𝑄 n’est pas vide do
Défilaire le nœud 𝑢 de 𝑄;
Visiter 𝑢 (par exemple, imprimer 𝑢);
for chaque voisin 𝑣 de 𝑢 tel que visité[v] = faux do
Enfiler 𝑣 dans 𝑄;
Marquer 𝑣 comme visité (visité[v] = vrai);
end
end
Algorithm 8: Algorithme de recherche en largeur (BFS)

※ Problème du flot maximum

4.3.1 Définition d’un réseau

Un réseau est défini par :

— (𝑆, 𝐴) un graphe orienté ;
— une capacité 𝑐 : 𝐴 → N∗ , avec la convention suivante : si l’arc (𝑢, 𝑣) n’existe
pas, alors 𝑐(𝑢, 𝑣) = 0 ;
— un sommet source 𝑠 sans arcs entrants ;
— un sommet puits 𝑡 sans arcs sortants.

4.3.2 Flot

Le flot d’un réseau est une fonction 𝑓 : 𝑆2 → R+ qui vérifie :

— pour tous sommets (𝑢, 𝑣) ∈ 𝑆 × 𝑆, on a 0 ≤ 𝑓 (𝑢, 𝑣) ≤ 𝑐(𝑢, 𝑣) ;
— pour tout sommet 𝑢 ∈ 𝑆 tel que 𝑢 ≠ 𝑠 et 𝑢 ≠ 𝑡 :
Õ Õ
𝑓 (𝑣, 𝑢) = 𝑓 (𝑢, 𝑤) (propriété de conservation du flot).
𝑣∈𝑆 𝑤∈𝑆

84
Short title of document Algorithme de Ford-Fulkerson

La valeur du flot 𝑓 est donnée par :

Õ
|𝑓| = 𝑓 (𝑠, 𝑣).
𝑣∈𝑆

※ Algorithme de Ford-Fulkerson
L’algorithme de Ford-Fulkerson est un algorithme itératif. À chaque itération,
la solution courante est un flot qui satisfait les contraintes de capacité (c’est
donc un flot réalisable), et l’algorithme essaie d’augmenter la valeur de ce flot.
Cela peut nécessiter d’annuler certains choix. Pour ce faire, on définit le graphe
résiduel 𝐺 𝑓 de 𝐺 et de 𝑓 , qui indique les modifications possibles (ajout ou
annulation) : c’est un graphe pondéré 𝑅 𝑓 = (𝑆, 𝐴 𝑓 , 𝑟 𝑓 ), où :

𝑐(𝑢, 𝑣) − 𝑓 (𝑢, 𝑣) si (𝑢, 𝑣) ∈ 𝐴 (ajout)







𝑟 𝑓 (𝑢, 𝑣) = 𝑓 (𝑣, 𝑢) si (𝑣, 𝑢) ∈ 𝐴 (annulation)


0

sinon

et 𝐴 𝑓 = {(𝑢, 𝑣) ∈ 𝑆 × 𝑆 | 𝑟 𝑓 (𝑢, 𝑣) > 0}.

4.4.1 Pseudo-code de l’algorithme de Ford-Fulkerson

Data: 𝐺 = (𝑆, 𝐴, 𝑐, 𝑠, 𝑡), un réseau avec un graphe orienté et une capacité

Result: Un flot maximal 𝑓
Initialisation :
Initialiser 𝑓 comme un flot nul ;
while il existe un chemin simple 𝛾 de 𝑠 à 𝑡 dans le graphe résiduel 𝑅 𝑓 do
Δ ← min{𝑟 𝑓 (𝑢, 𝑣) : (𝑢, 𝑣) ∈ 𝛾} ;
foreach arête (𝑢, 𝑣) ∈ 𝛾 do
if (𝑢, 𝑣) ∈ 𝐴 then
𝑓 (𝑢, 𝑣) ← 𝑓 (𝑢, 𝑣) + Δ ;
end
else
𝑓 (𝑣, 𝑢) ← 𝑓 (𝑣, 𝑢) − Δ ;
end
end
end
Algorithm 9: Algorithme de Ford-Fulkerson

85
Short title of document Algorithme de Ford-Fulkerson

Graphe 𝐺 avec capacité 𝑐 Flot 𝑓 Graphe résiduel 𝐺 𝑓

résultant (avec les
nouvelles capacités
résiduelles 𝑟 𝑓 ).

𝑒∈𝐴 𝑓 (𝑒) 𝑒∈𝐴 𝑓 (𝑒) 𝑒∈𝐴 ( 𝑟 𝑓 (𝑒) 𝑟 𝑓 (←

𝑒−)𝐴
(𝑠, 𝑢) 4 (𝑠, 𝑢) 0 (𝑠, 𝑢) 4 0
(𝑢, 𝑡) 1 (𝑢, 𝑡) 0 (𝑢, 𝑡) 1 0
(𝑠, 𝑣) 2 (𝑠, 𝑣) 0 (𝑠, 𝑣) 2 0
(𝑣, 𝑡) 6 (𝑣, 𝑡) 0 (𝑣, 𝑡) 6 0
(𝑢, 𝑣) 3 (𝑢, 𝑣) 3 (𝑢, 𝑣) 3 0

Table 4.1 – Graphe initial avec capacités et flots

4.4.2 Exemple

Considérons le réseau de flot 𝐺 = (𝑆, 𝐴, 𝑐, 𝑠, 𝑡), consistant du graphe 𝐺 =

(𝑆, 𝐴) avec les sommets 𝑆 = {𝑠, 𝑡, 𝑢, 𝑣} et les arêtes 𝐴 = {(𝑠, 𝑢), (𝑢, 𝑡), (𝑠, 𝑣), (𝑣, 𝑡), (𝑢, 𝑣)},
ainsi que la fonction de capacité 𝑐 : 𝐴 → R≥0 ., comme c est illustré dans la table
4.1
Étape 0 : On commence dans la table 4.1 avec le flot vide 𝑓 qui attribue
la valeur 0 à chaque arête. Initialement, le graphe résiduel 𝐺 𝑓 et les capacités
résiduelles 𝑟 𝑓 correspondent alors exactement au réseau 𝐺 avec les capacités 𝑐.
Étape 1 : Supposons que l’algorithme choisisse d’abord le chemin 𝛾 =
((𝑠, 𝑢), (𝑢, 𝑣), (𝑣, 𝑡)) (bleu) voir la table 4.2. Le long de ce chemin, on peut aug-
menter le débit au maximum de 3 puisque l’arête (𝑢, 𝑣) est limitante :

𝑟 𝑓 ((𝑢, 𝑣)) = 3.

Il en résulte un nouveau flot (qu’on appellera toujours 𝑓 ) avec :

𝑓 ((𝑠, 𝑢)) = 𝑓 ((𝑢, 𝑣)) = 𝑓 ((𝑣, 𝑡)) = 3.

L’arête (𝑠, 𝑢) a une capacité de 𝑐((𝑠, 𝑢)) = 4. Elle est utilisée dans le flot :

86
Short title of document Algorithme de Ford-Fulkerson

Graphe 𝐺 avec capacité 𝑐 Flot 𝑓 Graphe résiduel 𝐺 𝑓

résultant (avec les
nouvelles capacités
résiduelles 𝑟 𝑓 ).

𝑒∈𝐴 𝑓 (𝑒) 𝑒∈𝐴 ( 𝑟 𝑓 (𝑒) 𝑟 𝑓 (←

𝑒−)𝐴
(𝑠, 𝑢) 3 (𝑠, 𝑢) 1 3
(𝑢, 𝑡) 0 (𝑢, 𝑡) 1 0
(𝑠, 𝑣) 0 (𝑠, 𝑣) 2 0
(𝑣, 𝑡) 3 (𝑣, 𝑡) 3 3
(𝑢, 𝑣) 3 (𝑢, 𝑣) 0 3

Table 4.2

𝑓 ((𝑠, 𝑢)) = 3.

Dans le graphe résiduel, sa capacité résiduelle sera donc :

𝑟 𝑓 ((𝑠, 𝑢)) = 𝑐((𝑠, 𝑢)) − 𝑓 ((𝑠, 𝑢)) = 1.

De même :

𝑟 𝑓 ((𝑢, 𝑣)) = 𝑐((𝑢, 𝑣)) − 𝑓 ((𝑢, 𝑣)) = 3 − 3 = 0,

𝑟 𝑓 ((𝑣, 𝑡)) = 𝑐((𝑣, 𝑡)) − 𝑓 ((𝑣, 𝑡)) = 6 − 3 = 3.

Les trois arêtes (𝑠, 𝑢), (𝑢, 𝑣), (𝑣, 𝑡) sont strictement positives dans le flot. Ces
poids dans le flot ne sont peut-être pas les plus optimaux.
Les nouvelles arêtes arrières (𝑡, 𝑣), (𝑣, 𝑢), (𝑢, 𝑠) (en rouge) dans le graphe
résiduel marquent alors le fait que l’on pourra toujours diminuer le flot sur ces
arêtes.
Étape 2 : Supposons que l’algorithme sélectionne le chemin améliorant 𝛾 =
((𝑠, 𝑣), (𝑣, 𝑢), (𝑢, 𝑡)) dans la table 4.3. L’augmentation maximale du débit est li-
mitée par la capacité résiduelle :

87
Short title of document Algorithme de Ford-Fulkerson

Graphe 𝐺 avec capacité 𝑐 Flot 𝑓 Graphe résiduel 𝐺 𝑓

résultant (avec les
nouvelles capacités
résiduelles 𝑟 𝑓 ).

𝑒∈𝐴 𝑓 (𝑒) 𝑒∈𝐴 ( 𝑟 𝑓 (𝑒) 𝑟 𝑓 (←

𝑒−)𝐴
(𝑠, 𝑢) 3 (𝑠, 𝑢) 1 3
(𝑢, 𝑡) 1 (𝑢, 𝑡) 0 1
(𝑠, 𝑣) 1 (𝑠, 𝑣) 1 1
(𝑣, 𝑡) 3 (𝑣, 𝑡) 3 3
(𝑢, 𝑣) 2 (𝑢, 𝑣) 1 2

Table 4.3

𝑟 𝑓 ((𝑢, 𝑡)) = 𝑐((𝑢, 𝑡)) − 𝑓 ((𝑢, 𝑡)) = 1 − 0 = 1.

Pour la première fois, on passe par une arête arrière (𝑣, 𝑢). Alors que le flot 𝑓
augmente de 1 le long des arêtes (𝑠, 𝑣) et (𝑢, 𝑡), il diminue de 1 le long de (𝑢, 𝑣).
On peut remarquer que les capacités résiduelles des arêtes arrières sont
toujours égales aux poids dans le flot.
Étape 3 : Supposons que l’algorithme choisisse à nouveau le chemin 𝛾 =
((𝑠, 𝑢), (𝑢, 𝑣), (𝑣, 𝑡)) comme c’est illustré dans le tableau 4.4. Cette fois, le débit le
long du chemin ne peut être augmenté que de 1. Cela correspond justement au
montant par lequel on a diminué (𝑢, 𝑣) à l’étape précédente. En effet, l’algorithme
peut faire beaucoup de va-et-vient.
Étape 4 : Dans le tableau 4.5, seul le chemin 𝛾 = ((𝑠, 𝑣), (𝑣, 𝑡)) est possible.
Cela augmente alors le débit de 1. Le flot a alors une valeur de :

𝑓 ((𝑠, 𝑢)) + 𝑓 ((𝑠, 𝑣)) = 6

Les arêtes sortantes de la source sont pleinement utilisées, donc ce flot est un
flot maximal.

88
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

Graphe 𝐺 avec capacité 𝑐 Flot 𝑓 Graphe résiduel 𝐺 𝑓

résultant (avec les
nouvelles capacités
résiduelles 𝑟 𝑓 ).

𝑒∈𝐴 𝑓 (𝑒) 𝑒∈𝐴 ( 𝑟 𝑓 (𝑒) 𝑟 𝑓 (←

𝑒−)𝐴
(𝑠, 𝑢) 4 (𝑠, 𝑢) 0 4
(𝑢, 𝑡) 1 (𝑢, 𝑡) 0 1
(𝑠, 𝑣) 1 (𝑠, 𝑣) 1 1
(𝑣, 𝑡) 4 (𝑣, 𝑡) 2 4
(𝑢, 𝑣) 3 (𝑢, 𝑣) 0 3

Table 4.4

※ Problème du plus court chemin sur un graphe : algorithme

de Dijkstra

L’algorithme de Dijkstra, créé par Edsger Dijkstra en 1959, résout efficacement

le problème du plus court chemin dans les graphes connexes avec des poids
positifs ou nuls. Fondamental en théorie des graphes, il trouve des applications
pratiques, notamment pour déterminer les trajets optimaux dans des réseaux
comme les réseaux routiers. Sa démonstration en tant qu’algorithme polynomial
le rend efficace pour des problèmes de taille raisonnable.

4.5.1 Principe de l’algorithme de Dijkstra

L’algorithme de Dijkstra peut être décrit comme suit :

— Entrée : Un graphe orienté pondéré par des réels positifs et un sommet

source.
— Initialisation :
— Les distances de chaque sommet au sommet de départ sont infinies, sauf
pour le sommet de départ pour lequel la distance est nulle.
— Le sous-graphe de départ est l’ensemble vide.

89
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

Graphe 𝐺 avec capacité 𝑐 Flot 𝑓 Graphe résiduel 𝐺 𝑓

résultant (avec les
nouvelles capacités
résiduelles 𝑟 𝑓 ).

𝑒∈𝐴 𝑓 (𝑒) 𝑒∈𝐴 ( 𝑟 𝑓 (𝑒) 𝑟 𝑓 (←

𝑒−)𝐴
(𝑠, 𝑢) 4 (𝑠, 𝑢) 0 4
(𝑢, 𝑡) 1 (𝑢, 𝑡) 0 1
(𝑠, 𝑣) 2 (𝑠, 𝑣) 0 2
(𝑣, 𝑡) 5 (𝑣, 𝑡) 1 5
(𝑢, 𝑣) 3 (𝑢, 𝑣) 0 3

Table 4.5

— Itération : À chaque étape, procéder comme suit :

— Choisir un sommet en dehors du sous-graphe ayant la distance minimale
et l’ajouter au sous-graphe.
— Mettre à jour les distances des sommets voisins de celui qui vient d’être
ajouté :
— La nouvelle distance du sommet voisin est le minimum entre la distance
existante et celle obtenue en ajoutant le poids de l’arc entre le sommet
voisin et le sommet ajouté à la distance du sommet ajouté.
— Terminaison : Continuer jusqu’à épuisement des sommets ou jusqu’à la
sélection du sommet d’arrivée.

La description détaillée de la détermination du plus court chemin sur un graphe

est résumée dans l’algorithme 1.

4.5.2 Exemple d’application de l’algorithme de Dijkstra :distance entre la

ville A et la ville J

L’exemple suivant montre les étapes successives dans la résolution du chemin

le plus court dans un graphe. Les nœuds symbolisent des villes identifiées

90
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

Data: Un graphe 𝐺 = (𝑉 , 𝐸) avec des poids positifs sur les arêtes

Result: Un sous-graphe 𝑠𝑢𝑏𝐺 connecté couvrant tous les sommets de 𝐺
avec des distances minimales
Initialisation :
𝑠𝑢𝑏𝐺 ← ∅ ; // Sous-graphe initial vide
𝑑𝑖𝑠𝑡[𝑣] ← ∞ pour tout 𝑣 ∈ 𝑉 ; // Distances initialisées à l’infini
Choisir un sommet source 𝑠 et poser 𝑑𝑖𝑠𝑡[𝑠] ← 0;
while 𝑠𝑢𝑏𝐺 n’inclut pas tous les sommets de 𝐺 do
Choisir le sommet 𝑣 en dehors de 𝑠𝑢𝑏𝐺 avec la distance minimale;
Ajouter 𝑣 à 𝑠𝑢𝑏𝐺;
foreach voisin 𝑢 de 𝑣 do
Mettre à jour la distance de 𝑢 :
𝑑𝑖𝑠𝑡[𝑢] ← min(𝑑𝑖𝑠𝑡[𝑢], 𝑑𝑖𝑠𝑡[𝑣] + 𝑝𝑜𝑖𝑑𝑠(𝑣, 𝑢));
end
end
Algorithm 10: Algorithme de mise à jour des distances

par une lettre et les arêtes indiquent la distance entre ces villes. On cherche à
déterminer le plus court trajet pour aller de la ville A à la ville J.

Étape 1 : à partir de la ville A, 3 villes sont accessibles, B, C, et E qui se voient

donc affectées des poids respectifs de 85, 217, 173, tandis que les autres villes
sont affectées d’une distance infinie.
Étape 2 : la distance la plus courte est celle menant à la ville B. Le passage

91
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

par la ville B ouvre la voie à la ville F (85+80 = 165).

Étape 3 : La distance la plus courte suivante est celle menant à la ville F. Le

passage par la ville F ouvre une voie vers la ville I (415).
Étape 4 : La distance la plus courte suivante est alors celle menant à la ville
E. Le passage par la ville E ouvre une voie vers la ville J (675).

Étape 5 : la distance la plus courte suivante mène alors à la ville C. Le passage

par la ville C ouvre une voie vers la ville G (403) et la ville H (320).

92
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

Étape 6 : la distance la plus courte suivante mène à ville H(320). Le passage

par la ville H ouvre une voie vers la ville D et un raccourci vers la ville J (487<
675).

Étape 7 : la distance la plus courte suivante mène à la ville G et ne change

aucune autre distance.
Étape 8 : la distance la plus courte suivante mène à la ville I. Le passage par
la ville I ouvre un chemin vers la ville J qui n’est pas intéressant (415+ 84 > 487).

Étape 9 : la distance la plus courte suivante mène à la ville J (487).

93
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

On connait ainsi le chemin le plus court menant de A à J, il passe par C et H et

mesure 487 km. De nos jours, l’algorithme de Dijkstra est utilisé dans plusieurs
applications informatiques telles que les GPS. En outre, Google par exemple a pu
introduire cet algorithme pour améliorer plusieurs fonctionnalités sur Google
Maps ainsi que Google Earth..

4.5.3 Présentation sous forme de tableau

L’illustration par une série de graphes peut se révéler un peu longue. Il est
d’autre part un peu plus difficile de repérer le chemin le plus court à l’issue
du dessin. Ainsi l’algorithme de Dijsktra est souvent réalisé à l’aide d’un ta-
bleau dans lequel chaque étape correspond à une ligne. À partir de la matrice
des arcs orientés reliant les diverses villes : On construit un tableau dans le-

àA àB àC àD àE àF àG àH àI àJ
De A 0 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
De B 85 0 ∞ ∞ ∞ 80 ∞ ∞ ∞ ∞
De C 217 ∞ 0 ∞ ∞ ∞ 186 103 ∞ ∞
De D ∞ ∞ ∞ 0 ∞ ∞ ∞ 183 ∞ ∞
De E 173 ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ 502
De F ∞ 80 ∞ ∞ ∞ 0 ∞ ∞ 250 ∞
De G ∞ ∞ 186 ∞ ∞ ∞ 0 ∞ ∞ ∞
De H ∞ ∞ 103 183 ∞ ∞ ∞ 0 ∞ 167
De I ∞ ∞ ∞ ∞ ∞ 250 ∞ ∞ 0 84
De J ∞ ∞ ∞ ∞ 502 ∞ ∞ 167 84 0

Table 4.6 – Matrices des arcs orientés

quel les distances d’un sommet au sommet de départ sont regroupées dans
une même colonne. Les sommets sélectionnés sont soulignés. Les distances des
voies ouvertes par la sélection d’un nouveau sommet sont barrées si elles sont
supérieures à des distances déjà calculées. Quand un sommet est sélectionné,
c’est que l’on a découvert sa distance minimale au sommet, il est alors inutile de
chercher d’autres distances de ce sommet au point de départ.
La construction de ce tableau donne non seulement la distance minimale de
la ville A à la ville J mais aussi le chemin à suivre (J - H - C - A) ainsi que toutes les
distances minimales de la ville A aux autres villes rangées par ordre croissant.

94
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

Table 4.7 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞

Table 4.8 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞

Table 4.9 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞
F(165𝐵 ) - 217 ∞ 173 - ∞ ∞ 415 ∞

Table 4.10 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞
F(165𝐵 ) - 217 ∞ 173 - ∞ ∞ 415 ∞
E(173𝐴 ) - 217 ∞ - - ∞ ∞ 415 675

Table 4.11 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞
F(165𝐵 ) - 217 ∞ 173 - ∞ ∞ 415 ∞
E(173𝐴 ) - 217 ∞ - - ∞ ∞ 415 675
C(217𝐴 ) - - ∞ - - 403 320 415 675

95
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

Table 4.12 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞
F(165𝐵 ) - 217 ∞ 173 - ∞ ∞ 415 ∞
E(173𝐴 ) - 217 ∞ - - ∞ ∞ 415 675
C(217𝐴 ) - - ∞ - - 403 320 415 675
H(320𝐶 ) - - 503 - - 403 - 415 675 487

Table 4.13 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞
F(165𝐵 ) - 217 ∞ 173 - ∞ ∞ 415 ∞
E(173𝐴 ) - 217 ∞ - - ∞ ∞ 415 675
C(217𝐴 ) - - ∞ - - 403 320 415 675
H(320𝐶 ) - - 503 - - 403 - 415 675 487
G(403𝐶 ) - - 503 - - - - 415 487

Table 4.14 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞
F(165𝐵 ) - 217 ∞ 173 - ∞ ∞ 415 ∞
E(173𝐴 ) - 217 ∞ - - ∞ ∞ 415 675
C(217𝐴 ) - - ∞ - - 403 320 415 675
H(320𝐶 ) - - 503 - - 403 - 415 675 487
G(403𝐶 ) - - 503 - - - - 415 487
I(415𝐹 ) - - 503 - - - - - 487

96
Short title of documentProblème du plus court chemin sur un graphe : algorithme de Dijkstra

Table 4.15 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞
F(165𝐵 ) - 217 ∞ 173 - ∞ ∞ 415 ∞
E(173𝐴 ) - 217 ∞ - - ∞ ∞ 415 675
C(217𝐴 ) - - ∞ - - 403 320 415 675
H(320𝐶 ) - - 503 - - 403 - 415 675 487
G(403𝐶 ) - - 503 - - - - 415 487
I(415𝐹 ) - - 503 - - - - - 487
J(487𝐻 ) - - 503 - - - - - -

Table 4.16 – Algorithme de Dijkstra

A B C D E F G H I J
Étape initiale 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
A(0) 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞
B(85𝐴 ) - 217 ∞ 173 165 ∞ ∞ ∞ ∞
F(165𝐵 ) - 217 ∞ 173 - ∞ ∞ 415 ∞
E(173𝐴 ) - 217 ∞ - - ∞ ∞ 415 675
C(217𝐴 ) - - ∞ - - 403 320 415 675
H(320𝐶 ) - - 503 - - 403 - 415 675 487
G(403𝐶 ) - - 503 - - - - 415 487
I(415𝐹 ) - - 503 - - - - - 487
J(487𝐻 ) - - 503 - - - - - -
D(503𝐻 ) - - - - - - - - -

97
Chapitre 5

ORDONNANCEMENT : La
Méthode PERT et diagramme de
GANTT

Les méthodes d’ordonnancement de tâches permettent de visualiser graphi-

quement la séquence des opérations. Cette représentation facilite le positionne-
ment relatif des opérations dans le temps.

I - La Méthode PERT (Program Evaluation and Review Tech-

nique)

La méthode PERT permet d’optimiser l’ordonnancement des tâches afin de

minimiser la durée totale d’un projet.

A - Principe de la méthode

La méthode consiste à réduire la durée totale d’un projet en analysant en

détail les tâches ou activités élémentaires et leur enchaînement chronologique.

B - Notions de base

La méthode s’appuie sur une représentation graphique, appelée réseau PERT,

constituée de nœuds et de tâches. Un réseau PERT est composé d’étapes (ou
nœuds) et de tâches.

98
Short title of document

(a) Représentation graphique d’une tâche (b) Représentation d’une

étape

Figure 5.1 – Représentation des éléments constituant le réseau PERT

Tâche

Une tâche représente le déroulement d’une opération dans le temps. Contrai-

rement à une étape, une tâche a une durée, nécessite des ressources et engendre
un coût. Elle est symbolisée par un vecteur ou une flèche. Par exemple, la figure
5.1(a) illustre une tâche symbolisée par A et la durée est 8. (Exp : 8 jours ou mois
ou heures ou ......)

Remarque. La longueur des arcs n’est pas proportionnelle au temps d’exécution.

Et pour alléger la représentation, on ne note pas le nom complet de la tâche mais
juste une lettre ou un code.

Étape (ou Nœud ou Sommet ou Événement)

Une étape illustrée dans la figure 5.3(b), marque le début ou la fin d’une tâche.
Elle n’a pas de durée et est représentée par un cercle divisé en trois parties :
— Partie supérieure : Numéro unique permettant d’identifier l’étape dans le
diagramme.
— Partie gauche : Date la plus tôt à laquelle la réalisation de tâche peut com-
mencée.
— Partie droite : Date la plus tardive possible à laquelle la réalisation de tâche
peut commencée sans retarder la fin du projet.

99
Short title of document Représentation graphique des étapes et des tâches dans un réseau

※ Représentation graphique des étapes et des tâches dans un

réseau

5.1.1 Types des Tâches :

— Tâches successives : C’est-à-dire que la tâche B ne peut commencer que si A

est terminée. A précède B ou A est une antériorité de BC ne peut commencer

que si A et B sont terminées.A et B précèdent C , ou A et B sont antériorité de
C.
— Tâches simultanées Elles peuvent commencer en même temps en partant

d’une même étape. A et B sont deux tâches simultanées. Elles commencent

en même temps. D ne peut commencer que si C est terminée.
— Tâches convergentes C’est-à-dire plusieurs tâches peuvent se terminer sur le

même noeud . A et B sont deux tâches convergentes vers le nœud 4. Donc on

ne peut pas commencer C sans terminer A et B
— Tâche fictif : Parfois, il est nécessaire d’introduire des tâches fictives. Une tâche
fictive a une durée nulle. Elle ne modifie pas le délai final. Par exemple, dans

(d) Représentation d’une étape successives (e) Représentation d’une étape

la représentation dans la figure 5.2(d), A et B sont deux tâches simultanées-

100
Short title of document Représentation graphique des étapes et des tâches dans un réseau

A et C sont deux tâches successives ( la même chose pour C et D ; B et E )Pour

commencer D il faut terminer C ,Si l’on souhaite que D ne commence que si
C et B sont terminées c à d on souhaite que C et B se terminent dans le nœud
4 ( se convergent ). qu’est ce qu’il faut faire ? On a déjà la tâche B se termine
dans le nœud 3 , et C se termine dans le nœud 4 et on veut les converger vers
le nœud 4. Donc on va créer une tâche fictive qui sert à représenter ce type
de contrainte de liaison.La tâche fictive et une tâche dont la durée et le coût
sont nuls. on l’a représente par des pointillés et on la note par X ( 0 ) comme
c est illustré dans la figure 5.2(e).

Les étapes pour créer un réseau PERT

1- Préparez les tâches

— Commencez par lister les tâches - Soyez exhaustif en restant sur un niveau
de détail gérable.
— Vous pouvez utiliser la méthode du brainstorming pour ne rien oublier et
découper le projet avec le WBS (Work Breakdown Structure).
— Estimez leur durée et leur(s) antécédent(s) : pour chaque tâche, évaluer le
temps nécessaire pour leur traitement. Pour estimer la durée des tâches, vous
pouvez recourir à l’estimation à 3 points :
𝑎 + 4𝑚 + 𝑝
Estimation durée de tâche =
6
Cette formule vous donne une durée moyenne en fonction d’une estimation
que vous jugez la plus probable, une seconde optimiste et une dernière,
pessimiste, où :
— a = estimation optimiste
— m = probable (le "m" vient de "Most likely")
— b = pessimiste

Exemple de tableau d’antériorités

2- Construisez le réseau en reliant les tâches entre elles, via des

étapes

Reprenez le tableau avec la liste de tâches et montez le réseau en utilisant les

liens de dépendance (les antécédents). Indiquez sur le graphique la désignation

101
Short title of document Représentation graphique des étapes et des tâches dans un réseau

Tâche Durée Antécédent(s)

A 2 -
B 8 -
C 5 A
D 2 B
E 6 B
F 5 E
G 3 A,D

Table 5.1 – Tableau des marges des tâches

des tâches et leur durée comme défini précédemment. Ainsi, pour représenter
les tâches dans un graphe PERT, il faut procéder par niveau :
— Le niveau 0 contient les tâches qui n’ont pas de précédent
— Le niveau 1 contient les tâches dont les tâches précédentes sont de niveau 0
— Le niveau 2 contient les tâches dont les tâches précédentes sont de niveau 1
— Le niveau 3 contient les tâches dont les tâches précédentes sont de niveau 2
— Le niveau K contient les tâches dont les tâches précédentes sont de niveau
K-1

La tâche en pointillés est qualifiée de fictive.

102
Short title of document Représentation graphique des étapes et des tâches dans un réseau

3-Indiquez les dates au plus tôt

— Prenez la première étape (ici "1"), ajoutez la date au plus tôt de l’étape précé-
dente à la durée de la tâche qui la concerne : 0 + 2 (tâche A) = 2
— Faites de même pour l’ensemble des tâches. Par exemple pour l’étape 4 : 8 +
6 (tâche E) = 14.

4-Renseignez les dates au plus tard

— Parcourez le chemin inverse pour calculer les dates au plus tard. Partez de la
dernière étape et indiquez la date au plus tard égale à la date au plus tôt, ici
19 jours. Puis remontez le graphe en retranchant cette fois à la date au plus
tard de l’étape en question, la durée de la tâche qui la précède pour trouver
la date au plus tard de l’étape positionnée en amont.
— Exemple pour l’étape 1 : 19 jours (nœud final) - 5 jours (tâche C) = 14 jours

103
Short title of document Représentation graphique des étapes et des tâches dans un réseau

5- Calculez les marges des tâches

Les marges de tâches sont des degrés de liberté qui permettent d’absorber
des retards. Elles assurent la flexibilité du projet.

Définition 5.1.1 (Marge totale). La marge totale représente le retard que peut
prendre la réalisation d’une tâche sans impacter la date de fin du projet (à
condition qu’elle ait commencé à sa date la plus tôt).

Définition 5.1.2 (Marge Libre). La marge libre correspond au retard que peut
prendre la réalisation d’une tâche sans impact sur la date au plus tôt des tâches
suivantes (à condition qu’elle ait débuté à sa date le plus tôt

Formule de la marge totale et la marge libre d’une tâche Prenez les 2 étapes
qui l’entourent et appliquez le calcul suivant :
Marge totale = Date au plus tard de l’étape suivante - Durée de la tâche - Date au
plus tôt de l’étape précédente
Exemple : pour la tâche D, la marge totale est de 6 jours (16-2-8).
Marge libre = Date au plus tôt de l’étape suivante - Durée de la tâche - Date au
plus tôt de l’étape précédente
Exemple : pour la tâche C, la marge libre est de 12 jours (19-5-2).

Remarque. La marge libre ne peut pas être supérieure à la marge totale

Exemple 1 (Calculez les marges totales et libres des tâches dans le tableau 5.2 ).

104
Short title of document Représentation graphique des étapes et des tâches dans un réseau

5- Calculez les marges des tâches

Calcul des marges dans l’exemple

Tâche Marge libre Marge totale

A 0 12
C 12 12
B 0 0
D 0 6
G 6 6
E 0 0
F 0 0

Table 5.2 – Tableau des marges des tâches

6- Définition du chemin critique

— Il s’agit du chemin passant par les tâches dont la marge totale est nulle. Ce
tracé indique le délai incompressible pour réaliser le projet.

— Une fois le PERT terminé, il est conseillé de construire un planning Gantt

pour faciliter la visualisation et la gestion au quotidien.

105
 Tableau de niveaux : Détermination des niveaux des tâches pour la réalisation d’un réseau
Short title of document PERT
※ Tableau de niveaux : Détermination des niveaux des tâches
pour la réalisation d’un réseau PERT

Lorsque le nombre de tâches à planifier est important, le recours à un ta-

bleau de niveaux devient indispensable pour déterminer l’ordre d’exécution
des tâches et construire un réseau PERT efficace. Cette méthode permet d’orga-
niser les tâches en niveaux successifs en tenant compte de leurs dépendances
(antécédents), facilitant ainsi la visualisation et la gestion du projet.
Dans cette section, nous illustrons, à travers un exemple concret, la démarche
de détermination des niveaux des tâches en utilisant un tableau de niveaux.
Nous expliquerons chaque étape de la construction du tableau et montrerons
comment en déduire l’ordonnancement des tâches pour la réalisation du réseau
PERT.

5.2.1 Exemple de détermination des niveaux

Considérons un projet composé de plusieurs tâches, chacune ayant une durée

et des antécédents spécifiques. Le tableau 5.3 présente la liste des tâches, leurs
antécédents et leurs durées respectives.

Tâches Antécédents Durée

A / 3
B A 1
C A 5
D B 6
E B 4
G E, F 9
H / 5
I H 8
J H 2
K I 3

Table 5.3 – Tableau des tâches avec leurs antécédents et durées.

106
 Tableau de niveaux : Détermination des niveaux des tâches pour la réalisation d’un réseau
Short title of document PERT
5.2.2 Construction du tableau de niveaux

Pour déterminer les niveaux des tâches, nous construisons un tableau de

niveaux (5.4) qui indique les dépendances entre les tâches. Chaque ligne et
colonne du tableau représente une tâche, et une croix (X) est placée dans les
cases correspondant aux antécédents d’une tâche.

Tâche A B C D E F G H I J K L n1 n2 n3 n4 n5
A 0
B X 1 0
C X 1 0
D X 1 1 0
E X 1 1 0
F X 3 3 1 0
G X 2 2 2 1 0
H 0
I X 1 0
J X 1 0
K X X 1 1 0
L X 3

Table 5.4 – Tableau des niveaux : Dépendances entre les tâches.

5.2.3 Interprétation du tableau de niveaux

Le tableau de niveaux permet de déterminer l’ordre d’exécution des tâches

en suivant les étapes suivantes :
1. Niveau 1 (n1) : Les tâches sans antécédents (valeur « 0 » dans la colonne
n1) sont identifiées. Dans notre exemple, les tâches A et H n’ont pas d’an-
técédents.
2. Niveaux suivants : À chaque niveau, les tâches dont les antécédents ont
été réalisés (valeur « 0 » dans la colonne précédente) sont retirées des
dépendances des autres tâches. Par exemple, une fois les tâches A et H
réalisées, les tâches B, C, I et J perdent ces antécédents et passent au niveau
suivant (n2).
3. Tâches commençantes et finissantes : Les tâches commençantes sont celles
sans antécédents (niveau 0), tandis que les tâches finissantes sont celles sans
successeurs (dernier niveau).

107
 Tableau de niveaux : Détermination des niveaux des tâches pour la réalisation d’un réseau
Short title of document PERT
Le tableau 5.5 résume les niveaux des tâches ce qui permet de bâtir un réseau
PERT efficacement.

n1 n2 n3 n4 n5
A B D F G
H C E L
I K
J

Table 5.5 – Tableau des niveaux des tâches.

Exemple 2. Exercice d’application

Soit le projet à analyser :

Tâches Antérieur Durée

A ———- 6
B ———- 5
C A 4
D B 6
E C 5
F A, D 6
G E, F 4

Niveau 0 : A et B (n’ont pas d’antérieur)

Niveau 1 : C et D
Niveau 2 : E et F

108
 Tableau de niveaux : Détermination des niveaux des tâches pour la réalisation d’un réseau
Short title of document PERT
Niveau 3 : G

Graphe partiel Calcul des dates :

Figure 5.2 – La tâche A est nécessaire pour C , mais on remarque que A aussi est nécessaire pour F, donc
on doit relier A par F par une tâche fictive.

Nœud Dates au plus tôt (hâtives) Nœud Dates au plus tard (tardives)
1 𝑡1 = 0 7 𝑇7 = 𝑡7 = 21
2 𝑡2 = max(0 + 6) = 6 6 𝑇6 = min(21 − 4) = 17
3 𝑡3 = max(0 + 5) = 5 5 𝑇5 = min(17 − 6) = 11
4 𝑡4 = max(6 + 4) = 10 4 𝑇4 = min(17 − 5) = 12
5 𝑡5 = max(6 + 0, 5 + 6) = 11 3 𝑇3 = min(11 − 6) = 5
6 𝑡6 = max(10 + 5, 11 + 6) = 17 2 𝑇2 = min(12 − 4, 11 − 0) = 8
7 𝑡7 = max(17 + 4) = 21 1 𝑇1 = min(8 − 6, 5 − 5) = 0

Graphe PERT Complet Marges libres et Marges totales

Tâches Marge libre (ML) Tâches Marge totale (MT)

A ML(A) = 6 - 0 - 6 = 0 A MT(A) = 8 - 0 - 6 = 2
B ML(B) = 5 - 0 - 5 = 0 B MT(B) = 5 - 0 - 5 = 0
C ML(C) = 10 - 6 - 4 = 0 C MT(C) = 12 - 6 - 4 = 2
D ML(D) = 11 - 5 - 6 = 0 D MT(D) = 11 - 5 - 6 = 0
E ML(E) = 17 - 10 - 5 = 2 E MT(E) = 17 - 10 - 5 = 2
F ML(F) = 17 - 11 - 6 = 0 F MT(F) = 17 - 11 - 6 = 0
G ML(G) = 21 - 17 - 4 = 0 G MT(G) = 21 - 17 - 4 = 0

109
Short title of document GESTION DE PROJET : Diagramme de Gantt

Les tâches critiques sont les tâches dont la marge totale est nulle.
Dans ce cas : B, D, F et G sont des tâches critiques
Alors le chemin critique (BDFG).

Remarques :

— La durée du projet est 21.

— Par exemple, si on augmente la durée de la tâche F de 3, (la durée de F devient
9 au lieu de 6), alors la durée du projet devient 24. (21 + 3 = 24), F est une
tâche critique qui n’a pas de marge totale. [le retard de F = le retard du projet]
— Par exemple, si on augmente la durée de E de 7 (la durée de E devient 12 au
lieu de 5), on retarde E de 7 et comme E a une marge totale de 2 donc on va
retarder le projet de (7 - 2 = 5) alors la durée du projet devient (21 + 5 = 26).
— ***** MT(E) = 2 càd on a un retard acceptable de 2 sans retarder le projet *****

※ GESTION DE PROJET : Diagramme de Gantt

Le diagramme de Gantt, couramment utilisé en gestion de projet, est l’un des
outils les plus efficaces pour représenter visuellement l’état d’avancement des
différentes activités (tâches) qui constituent un projet. Cet outil répond à deux
objectifs : planifier de façon optimale ainsi que communiquer sur le planning
établi et les choix qu’il impose. Le diagramme permet :

□ de déterminer les dates de réalisation d’un projet ;

□ d’identifier les marges existantes sur certaines tâches ;
□ de visualiser d’un seul coup d’œil le retard ou l’avancement des travaux.

Éléments essentiels du diagramme de Gantt

110
Short title of document GESTION DE PROJET : Diagramme de Gantt

Figure 5.3 – Représentation de base du diagramme de Gantt : les abscisses représentent le temps, tandis
que les tâches représentent les ordonnées.

— Temps : la durée de chaque tâche est souvent affichée en jours/semaines/-

mois, mais on peut également la représenter en minutes/heures. Le jour/la
période en cours sont généralement mis en évidence.
— Tâches : chaque étape de la réalisation d’un projet est composée d’activités
(ou tâches). Chaque tâche est indépendante, mais elle peut également faire
partie d’un groupe de tâches (ensembles et sous-ensembles).
— Propriétaire : c’est la personne responsable de la tâche. Remarque : il peut
s’agir de plusieurs personnes voire de toute une équipe.
— Statut : la réalisation de chaque tâche passe par différentes étapes. Le statut
représente l’étape à laquelle se trouve chaque tâche à un moment donné. Les
statuts les plus fréquents sont « à suivre », « planifié », « bloqué », « étapes
suivantes », « jalon », etc.
— Jalons : il s’agit de la date à laquelle le projet doit être terminé (ou date de
fin). Chaque étape peut elle-même comporter des « mini-jalons ».
— Dépendances : certaines tâches ne peuvent pas commencer tant qu’une autre
n’est pas terminée.

Les étapes à suivre pour la construction du Diagramme Gantt

— Étape 1 : Définir les tâches du projet et les jalons :

✓ Partez des grandes étapes en les décomposant en petites tâches.
✓ Choisissez les jalons : en fonction des livrables en fin d’étape et des évé-
nements validant la continuation ou l’arrêt du projet.
— Étape 2 : Estimer la durée des tâches
— Utiliser une méthode d’estimation de tâche.

111
Short title of document Exemple d’un diagramme de Gantt

— Le temps prévu pour chaque intervention est une donnée importante pour
la planification.
— Choisissez l’unité du temps la plus pertinente : heure, jour, semaine... sui-
vant le projet et conservez la même référence pour l’ensemble du tableau.
— Étape 3 : Identifier les interactions entre chaque activité Certaines tâches
ne peuvent être menées qu’après la fin ou le début d’une autre (on parle de
"tâches séquentielles"). Par ailleurs, d’autres sont traitables en parallèle. Il
convient donc d’identifier les dépendances, il s’agit de la phase d’ordonnan-
cement.
4 types de dépendance :

✓ Fin à fin (FF) : les 2 tâches doivent se terminer en même temps.

✓ Fin à début (FD) : une tâche ne peut débuter que lorsque la précédente
sera terminée. Il s’agit du mode d’enchaînement standard.
✓ Début à fin (DF) : une tâche ne peut pas se terminer tant que la précédente
n’a pas démarré.
✓ Début à début (DD) : une tâche ne peut débuter que si la précédente a
démarré.

— Étape 4 : Affecter les ressources

Définir les ressources aussi bien humaines que matérielles affectées à chaque
tâche. Cette donnée est utile lorsqu’il est nécessaire d’effectuer un suivi précis
de l’allocation des ressources. Ou bien simplement afin de savoir qui fait quoi.

Pour des projets plus complexes, l’utilisation en amont de la méthode PERT

s’impose pour lister les tâches, définir les dépendances, prendre en compte
les contraintes...

※ Exemple d’un diagramme de Gantt

Pour illustrer la méthode, voici la planification des différentes étapes pour
créer un site internet. Nous avons volontairement réduit le processus et pas
mentionné les ressources, les jalons, l’objectif étant de rester simple.

112
Short title of document Exemple d’un diagramme de Gantt

L’activité "Saisir le contenu du site" dépend de deux tâches (type FD). En effet, la
saisie ne peut se faire que lorsque le site est validé et que le contenu est rédigé.
L’étape "Réaliser l’intégration graphique", quant à elle, débute en même
temps que "Développer les fonctions". Les intégrateurs doivent, à l’évidence,
se coordonner avec les développeurs. Il s’agit d’une dépendance de type DD.

113
Short title of document Exemple d’un diagramme de Gantt

Le Graphique avec les ressources : les barres en rouge représentent le chemin

critique Déterminé par exemple par la méthode PERT .Il s’agit des étapes clés
pour lesquelles un dérapage a pour conséquence de retarder le projet.
Les logiciels pour créer votre diagramme de Gantt
Il existe des applications dédiées (souvent gratuites), plus accessibles, comme
Gantter for Google Drive, qui permettent de créer rapidement un planning basé
su la diagramme de GANTT. Des solutions complètes en ligne, plus évoluées,
intègrent la création d’un diagramme de Gantt parmi d’autres fonctionnalités
dédiées au travail collaboratif.

— Smartsheet, par exemple, est une solution en ligne performante.

— En local, sur votre ordinateur, vous pouvez vous tourner vers des logiciels
libres comme GanttProject.
— Ces logiciels sont très pratiques, voire indispensables, pour définir les dé-
pendances entre les tâches, réaliser des simulations, mesurer les impacts
d’un retard, etc., et ce, en quelques clics.

114