EC Recherche opérationnelle Credit: 1,5 BGF

Cours: 5H BMEP
TD/ 10H BGC

Objectif général: L'objectif de cet enseignement est de donner les bases de la recherche
opérationnelle :

Objectifs spécifiques : A l'issue de ce c de cet enseignement, l'étudiant doit être capable de:

• construire des modèles mathématiques de programmation linéaire;

• d’appliquer les principaux algorithmes de résolution ;
• maitriser les bases de la méthode PERT

Contenu pédagogique :
Chapitre 1 : Programmation linéaire
I. Généralités sur la programmation linéaire
• Définitions de la programmation linéaire
• Historique de la Programmation linéaire
II. Modélisation
III. Résolution d’un programme linéaire par la méthode graphique
• Délimitation de la région des solutions admissibles.

• Recherche de la solution optimale.

IV. Résolution d’un programme linéaire par la méthode du simplexe
• Mise sous forme standard du programme linéaire
• Solution initiale et tableau initial
• Amélioration de la solution

Chapitre 2 : METHODE PERT

I. Généralités sur la méthode PERT
II. Méthodologie de construction d'un graphe P.E.R.T.
III. Calcul des dates et détermination du chemin critique

1
BIBLIOGRAPHIE

Bair, J., Crama, Y., Henry, V., & Justens, D. (2011). Modèles mathématiques en gestion. Dijon : Cassini.

Bonnans, F., & Gaubert, S. (2016). Recherche opérationnelle Aspects mathématiques et applications.
Paris : Lavoisier.

Di Lorio, R., Sebbar, B., & Stösser, A. (2000). Outils de gestion commerciale. Première et deuxième année.
Paris : Bréal.

Guéret, C. P. (2002). Programmation linéaire : 65 problèmes d’optimisation modélisés et résolus avec

Visual Xpress. (2ème tirage). Paris.: Eyrolles.

Guéret, C., Prins, C., & Sevaux, M. (2011). Programmation linéaire avec Excel. 55 problèmes
d'optimisation modélisés pas à pas et résolus avec Excel. Paris: Eyrolles.

Maurel, E., Roux, D., & Dupont, D. (1977 ). Techniques opérationnelles d'ordonnancement . Paris:
Eyrolles.

Umbhauer, G. (2002). Théorie des aooliquée à la gestion. Colombelles: EMS.

2
INTRODUCTION

La Recherche opérationnelle (RO) est un ensemble de techniques mathématiques permettant de

chercher des solutions optimales à des problèmes complexes de prise de décision.

La recherche opérationnelle apparaît en 1940 en Angleterre puis aux États-Unis à des fins de
recherche militaire : il s'agissait pour le Royaume Uni de traiter des questions, telles que :
l’implantation optimale de radars de surveillance, la protection des convois de navires. Après la
guerre, la recherche opérationnelle s'introduit dans le monde des affaires, l'objectif étant
d'organiser, produire, stocker et vendre de façon optimale. L'arrivée de l'ordinateur allait accélérer
l'essor de cette nouvelle science laquelle utilise quatre branches mathématiques fondamentales :

La recherche opérationnelle joue un rôle important dans nos sociétés. Son champ d'application est
particulièrement vaste couvrant des problèmes de logistique, de planification, d'organisation des
services, de réseaux de télécommunication, d'environnement…
Elle sert notamment à l’élaboration d’horaires, l’établissement d’itinéraires optimaux pour des
camions, planifier la production, définir le trajet du ramassage des poubelles, etc.
La Recherche opérationnelle (RO) englobe un large éventail de Techniques. On peut citer :
• La Programmation linéaire
• La Programmation non linéaire
• La Programmation dynamique
• Méthode PERT
• La théorie des jeux
• La simulation
• La théorie des files d’attente

CHAPITRE 1 : PROGRAMMATION LINÉAIRE

I. Généralités sur la programmation linéaire

3
 1.1.Définitions de la programmation linéaire

Il existe de nombreuses définitions de la programmation linéaire :

La programmation est un processus de planification qui alloue des ressources (travail, matériaux,
machines, et capital) de la meilleure manière (optimale) possible de façon à minimiser les coûts ou
à maximiser les profits.

La programmation linéaire est une méthode de résolution d’une fonction linéaire. Elle permet de
déterminer l’optimum d’une fonction économique en tenant compte des contraintes.
Autrement dit, elle permet de répondre à la question suivante :
« Compte tenu des différentes contraintes et des objectifs à atteindre, quelle combinaison de
produits P1, P2, etc., faut-il produire pour atteindre l’optimum ? »

Un programme linéaire (PL) est un problème d’optimisation consistant à maximiser (ou

minimiser) une fonction objectif linéaire de n variables de décision soumises à un ensemble
de contraintes exprimées sous forme d’équations ou d’inéquations linéaires.

A l’origine, le terme programme a le sens de planification opérationnelle mais il est aujourd’hui

employé comme synonyme de problème (d’optimisation). La terminologie est due à G. B. Dantzig,
inventeur de l’algorithme du simplexe (1947).

1.2. Historique de la Programmation linéaire

• les premiers mathématiciens qui se sont occupés de problèmes, que l'on ne nommait pas encore
à l'époque « programmes linéaires » (P.L.), sont : LAPLACE (1749-1827) et le baron FOURIER.
• le russe KANTOROVITCH en 1939 a imaginé une methode inspirée des multiplicateurs de
LAGRANGE, classiques en mécanique, pour résoudre des « programmes de transport »
• la contribution décisive a été l'invention de l'algorithme du SIMPLEXE, développé à partir de
1947 notamment par G.B. DANTZIG.
Koopmans proposa pour la première fois le nom de « programmation linéaire » lors d'une
discussion avec Dantzig en 1948.

4
Kantorovich et Koopmans ont partagé le prix Nobel d'économie 1975 « pour leurs contributions à
la théorie d'allocation optimale des ressources ».
• Au milieu des années 80, l'indien KARMARKAR a proposé une nouvelle méthode créée aux Bell
Laboratories qui permettait de résoudre de très gros problèmes linéaires, par une démarche «
intérieure » au polyèdre des solutions admissibles.

1.3. Étapes de l’application de la programmation linéaire

Le processus d’optimisation mathématique à l’aide de la programmation linéaire se scinde en trois
grandes étapes :
• La première consiste à modéliser le problème, c’est-à-dire le traduire sous forme sous la
forme d’un programme mathématique (appelé programme linéaire), ensemble d’équations
constitué d’un objectif à minimiser ou maximiser et de contraintes à satisfaire.
• La seconde étape du processus est la résolution de ce programme mathématique. Il s’agit
de déterminer une solution respectant les contraintes et pour laquelle la valeur de l’objectif
est la meilleure possible.
• Enfin, la dernière étape, interprétation et analyse de sensibilité :
• Un programme linéaire est résolu à partir de données précises concernant les coefficients
de la fonction économique et des contraintes. On peut se demander ce que serait la solution
si l'un des coefficients variait. Le programme de fabrication changerait-il si le nombre
d'heures disponibles sur la machine augmentait ou diminuait ?

1.4.Hypothèses de base d’un programme linéaire

• On se place dans le cadre déterministe, c’est à dire toutes les données numériques sont
utilisées dans le programme linéaire (fonction objectif et contraintes) sont supposées
connues et constantes durant la période d’étude.
• On suppose le principe de proportionnalité dans la fonction économique et les
contraintes. Exemple : si la production d’une unité d’un produit nécessite 3 heures d’une
ressource, alors produire 10 unités de ce produit utiliseront 30 heures de cette ressource.
• La troisième hypothèse est l’additivité.
• L’hypothèse de divisibilité qui exprime que les variables du problème sont réelles et pas
forcément des entiers naturels.

5
 II. Modélisation
La Modélisation (formulation) consiste à traduire le problème du monde réel dans un format
d’équations mathématiques.

2.1.Les étapes de formulation d’un PL :

Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme
linéaire :
Identifier les variables du problème à valeur non connues (variable de décision) et les
représenter sous forme symbolique (exp. x, y).
Identifier les restrictions (les contraintes) du problème. Les contraintes sont présentées sous formes
d'inéquations linéaires, exprimant des ressources rares. En plus de ces inéquations, le système de
contraintes contient des conditions de non-négativité stipulant que les variables ne peuvent pas
prendre de valeurs négatives. Cela signifie qu’il n'est pas possible d'avoir des productions
négatives.
Identifier la fonction objectif : Le terme “objectif” vient du fait que l’objectif est d’optimiser cette
fonction. Elle doit etre représentée sous une forme linéaire
en fonction des variables de décision. Il faut ensuite
s p é c i f i e r s i l e c r i t è r e d e s é l e c t i o n e s t à maximiser ou à minimiser.

2.2.Forme générale d’un programme linéaire

Un Programme Linéaire (PL) est un problème d’optimisation consistant à maximiser (ou
minimiser) une fonction objectif linéaire de variables soumises à un ensemble de contraintes
exprimées sous forme d’équations ou d’inéquations linéaires.

La fonction objectif (ou fonction économique) est une fonction linéaire dépendante de variables à
déterminer appelées variables de décision ou variables
d’activité. Son expression mathématique :
Z=c1x1+ c2x2+ c3x3+....+ cnxn
x1, x2,….., xn : sont les variables de décision.
La fonction précédente est soit à maximiser ou à minimiser, selon la nature de problème.

6
Les contraintes de problème s’expriment sous la forme d’équations ou d’inéquations ou des deux
ensemble.
a11x1+ a12x2+....+ a1nxn (≤ , = , ≥) b1
a21x1+ a22x2+....+ a2nxn (≤ , = , ≥) b2
……………………………..
am1x1+ am2x2+....+ amnxn (≤ , = , ≥) bm
x1 ≥0; x2≥0; …xn ≥0

aij (i=1,2,...m, j=1,2,...n) et bi (i=1,2,…m) sont des constantes

bi : valeurs des seconds membres.
aij : généralement sont les coefficients technologiques de chaque activité (j) par rapport à la
ressource (i).

Exemples
Exemple 1 : problème d’allocation de ressources
Un fabricant de meubles produit des tables et des chaises en bois. Le bénéfice unitaire pour les
tables est de 6 mille francs et le profit unitaire des chaises est de 8 mille francs. Supposons que les
deux seules ressources que l'entreprise utilise pour produire les tables et les chaises sont le bois et
le travail (heures). Il prend 30 unités de bois et 5 heures pour faire une table, et 20 unités de bois et
10 heures pour fabriquer une chaise. Il y a 300 unités de bois disponibles et 110 heures de travail
disponibles. L'entreprise souhaite maximiser son profit, donc profit la maximisation et cherche à
déterminer le nombre de tables et de chaises à fabriquer compte tenu des ressources disponibles.

Le tableau suivant contient les informations relatives au problème de PL.

Tableau : Informations pour le PL des tables et chaises en bois.

7
 Ressources Table (X) Chaise (Y) Rressources
Disponibles
Bois (unités) 30 20 300
Travail (h) 5 10 110
Bénéfice unitaire (milles francs) 6 8

Formulation du PL.
Variables de décision :
Les inconnues du problème sont les quantités(nombres) de tables et de chaises que le fabricant
doit produire. Notons X le nombre de tables et Y le nombre de chaises.

Contraintes :
Dans ce problème les contraintes représentent la disponibilité des facteurs de production :
Bois : le fabricant dispose de 300 unités de bois. Sachant qu’une table demande 30 unités de bois
et une chaise 20 unités de bois, alors la contrainte liée à la limitation de la quantité de bois est 30X
+ 20Y ≤ 300
De même la contrainte qui exprime la limitation de la ressource travail est : 5X + 10Y ≤110

Fonction objectif :
La fonction objectif consiste à maximiser le profit apporté par fabrication des tables et des
chaises. Les contributions respectives 6 et 8, des deux variables de décision X et Y sont
proportionnelles à leur valeur. La fonction objectif est donc Maximiser: F = 6X + 8Y

Le programme linéaire qui modélise le problème de fabrication des tables et des chaises est
Maximiser: F = 6X + 8Y
Sous les contraintes :
30X + 20Y ≤ 300
5X1 + 10Y ≤ 110
X, Y ≥ 0 (conditions de non-négativité)

Exemple 2 : Problème de minimisation

8
La société DINDINO est spécialisée dans l’élevage de la volaille en particulier la dinde et le dindon.
Pour les nourrir elle utilise un mélange deux types d’aliments A et B.
Chaque type d’aliments contient, dans des proportions variées, une partie ou la totalité des trois
ingrédients (protéines, vitamines, fer) nécessaires à l’engraissement des dindes.
Chaque kg de type A contient 5 unités de protéines, 4 unités de vitamines et ½ unité de fer.
Chaque kg de type B contient 10 unités de protéines, 3 unités de vitamines et pas de fer.
Un kg de type A revient à 2 F et un kg de type B à 3 F.

Le tableau suivant résume l’ensemble des données de la société DINDINO.

Composition de chaque kg de nourriture Besoin mensuel

Ingrédient Type A Type B minimum par dindon
Protéine 5 10 90
Vitamine 4 3 48
Fer 1/2 0 1,5

Le propriétaire de la société souhaite un programme d’alimentation de coût minimal.

Formulation du PL.
Variables de décision :
Les inconnues du problème sont le nombre de kg de nourriture de type A et le nombres de kg de
nourriture de type B à acheter. Notons les X et Y respectivement.

Contraintes :
Dans ce problème les contraintes représentent les besoins mensuels minimum :
Protéine : il faut au minimum 90 unités. Sachant qu’un aliment type A fournit 5 unités de protéine
et un aliment type B fournit 10 unités de protéine, alors la contrainte correspondante est 5X + 10Y
≥ 90
Le même raisonnement donne les contraintes relatives à la vitamine et au fer :
vitamine : 4X + 3Y ≥ 48
fer : 0,5X ≥ 1,5

9
Fonction objectif :
La fonction objectif consiste à minimiser le coût de l’alimentation des dindes. Le coût d’un kg du
type A est 2F et celui de du type B 3F, alors la fonction objectif est : minimiser Z= 2X +3Y

Le programme linéaire qui modélise le problème d’agriculture est

Minimiser: Z = 2X + 3Y
Sous les contraintes :
5X + 10Y ≥ 90
0,5X ≥ 1,5
X, Y ≥ 0 (conditions de non-négativité)

III. Résolution d’un programme linéaire par la méthode graphique

La méthode graphique ne s’applique qu’aux programmes linéaires qui ne comportent que deux
variables.

La solution graphique comporte deux étapes :

• la délimitation de la région des solutions admissibles

• la recherche de la solution optimale

3.1. Délimitation de la région des solutions admissibles.

La délimitation de la région des solutions admissibles consiste à représenter l’ensemble des

contraintes sur un repère cartésien. Chaque contrainte de la forme 𝑎𝑥+𝑏𝑦+𝑐⩽0 définit une région
de demi-plan sur le plan 𝑥𝑦 où la frontière de la région est donnée par la droite 𝑎𝑥+𝑏𝑦+𝑐=0.

Cette droite divise le plan 𝑥𝑦 en deux régions. Pour déterminer quelle région satisfait la contrainte
donnée, on peut sélectionner n’importe quel point en dehors de la droite pour tester si le point
satisfait la contrainte donnée. Il est conseillé de sélectionner le point le plus simple possible pour
cela. Si l’origine (0;0) n'est pas sur la frontière, alors c’est toujours le choix le plus simple.

10
La région des solutions réalisables représente l'ensemble de toutes les solutions possibles à un
problème de PL. La région des solutions réalisables est l'ensemble des points du plan dont les
coordonnées x et y vérifient toutes les contraintes du programme linéaire, qu'elles soient évidentes
ou spécifiques au problème étudié.

Exemple :

Résoudre graphiquement le problème de programmation linéaire suivant :

Maximiser : Z = 50x + 15y

sous les contraintes:

5x + y ≤ 100,
x + y ≤ 50,
x ≥ 0, y ≥ 0

Région des solutions admissibles

On peut aussi écrire comme

5x + y = 100 …(i)
x + y = 50 ….(ii)

Étape 2 : Tracez maintenant ces points dans le graphique et trouvez la région réalisable.

11
 3.2. Recherche de la solution optimale.

Après avoir identifié la région de faisabilité, nous cherchons maintenant la solution, qui sera le
point de la région réalisable qui maximise la fonction objectif.

Il s'agit donc de chercher à l'intérieur de la région des solutions admissibles, le couple (x , y)

maximisant la fonction objectif.

12
Théorème : Théorème fondamental de la programmation linéaire

Si un problème de programmation linéaire a une solution optimale, alors la solution se situe sur la
frontière (c’est-à-dire sur les arrêtes et les sommets). De plus, si une frontière contenant une
solution optimale a un sommet (ou des sommets), alors la solution se situe sur l’un des sommets.

Représentons l’équation F0 (la fonction objectif passant par l’origine). Cette la droite passe par
l'origine et donne une valeur nulle à la fonction économique.
Pour augmenter la valeur de F0 et donc la fonction économique, il suffit d'éloigner F0 de l'origine.
Pour respecter les contraintes, cette droite sera déplacée jusqu'à l'extrême limite où il n'y aura plus
qu'un point d'intersection (éventuellement un segment) avec la région des solutions admissibles.

13
Maximiser la fonction F, tout en satisfaisant aux contraintes du problème, revient à chercher la
droite parallèle à la ligne de la fonction objectif et la plus éloignée de l’origine et qui n’a qu’un
seul point commun avec la région réalisable.

14
La solution de trouve au point d’intersection des deux droites. 5x + y = 100 et x + y = 50. Les
coordonnées de ce point sont obtenues en résolvant le système d’equations :

5x + y = 100 …(i)

x + y = 50 ….(ii)

Ainsi, on peut conclure que le point (12.5, 37,5) est la seule solution optimale. La valeur maximale
de la fonction d'objectif égale à

F = 50x + 15y

15
F = 50(12,5) + 15(37,5)

F = 625 + 562,5

F = 1187

IV. Résolution d’un programme linéaire par la méthode du simplexe

Initialement conçu par Dantzig ,l'algorithme du simplexe et ses variantes sont largement utilisés
pour résoudre les problèmes de LP. Fondamentalement, à partir d'une solution initiale réalisable,
l'algorithme du simplexe tente, à chaque itération, de construire une solution améliorée tout en
préservant la faisabilité jusqu'à ce que l'optimalité soit atteinte.

Partons de l’exemple suivant :

3x + 4y ≤ 160
6x+ 3y ≤ 180
Max z = 1200 x + 1000 y
X≥0; Y≥0

4.1.Mise sous forme standard du programme linéaire

Avant que l’algorithme du simplexe puisse être utilisé pour résoudre un programme linéaire, ce
programme doit être mis sous la forme standard, c'est-à-dire converti en un programme équivalent
où toutes les contraintes sont des équations et toutes les variables sont non négatives. Pour cela, on
introduit une variable supplémentaire appelée d’écart dans chacune des contraintes de la forme ≤,
pour la transformer en égalité :
La forme standard s'ecrit donc :
3x + 4y ≤ 160 3x + 4y + t1 = 160
6x+ 3y ≤ 180 6x + 3y + t2 = 180
Max F = 1200 x + 1000Y Max F = 1200 x + 1000Y
x≥0; Y≥0 x ≥ 0 ; y ≥ 0 ; t1 ≥ 0 ; t2 ≥ 0

16
 4.2.Solution initiale et tableau initial
La méthode de simplexe commence par l'identification d'une solution réalisable de base et ensuite,
elle essaye de trouver d'autres solutions réalisables de base jusqu’à atteindre à la solution optimale.
Ainsi, il est nécessaire d'avoir une solution initiale. Dans le cas simple, l'origine est solution, c.à.d.
que la première solution est x = 0 ; y = 0 ce qui sous-entend que t1 =160 ; t2 =180.

On peut formuler le tableau simplexe correspondant.

Tableau 0

Base X Y t1 t1 VVB1
t1 3 4 1 0 160
t2 6 3 0 1 180
-F 1200 1000 0 0 0

4.3.Amélioration de la solution
L’amélioration de la solution est synonyme d’un changement de base qui se déroule en deux étapes
:
• Choix de la variable entrante, de la variable sortante et du pivot
• Reformulation de la solution en fonction de la nouvelle base

4.3.1. Variable entrante, sortante et pivot

Détermination de la variable entrante
Selon le premier critère de Dantzig, on sélectionne dans la fonction objectif F la variable affectée
du coefficient positif le plus élevé.
Donc la variable entrante est x (coefficient 1200 dans F).

Détermination de la variable sortante

1
VVB signifie Valeurs des Variables de Base

17
Selon le second critère de Dantzig, il faut établir les rapports des seconds membres des contraintes
aux coefficients correspondants de la variable entrante (colonne x) et sélectionner la variable du
plus petit rapport positif.
On divise donc successivement 160 par 3 (53,33), 180 par 6 (30) et nous sélectionnons la variable
t2 (ligne correspondant à 30, plus petit rapport positif).

Le pivot est à l’intersection de la colonne de la variable entrante et de la ligne de la variable sortante.

Il va va nous permettre de transformer le tableau en un nouveau tableau correspondant à une
solution améliorée.

4.3.2. Reformulation de la solution en fonction de la nouvelle base

La variable entrante entre dans la première colonne à la place de la variable sortante.
si le nombre pivot est différent de un, on divise toute la ligne par ce nombre ;
On calcule le reste des valeurs du tableau en opérant des combinaisons linéaires dans le tableau de
simplexe précèdent en utilisant la règle du rectangle :

Terme à remplacer X
dans le tableau n° N

Y Pivot

Nouvelle valeur du terme = Terme à remplacer dans le - 𝑋. 𝑌

dans le tableau n° N+1 tableau n° N 𝑃𝑖𝑣𝑜𝑡

Cette formule peut être réécrite de la façon suivante si on raisonne en termes de lignes du tableau :

Nouvelle ligne i dans le tableau n° N+1 = ancienne ligne i – élément de la ligne i sur la colonne
du pivot X ligne résultante de la transformation de la ligne du pivot.

18
Ainsi on normalise l'élément pivot et sa valeur devient 1, alors que le reste des éléments de la
colonne pivot s'annulent.

4.4.Critère d'arrêt des itérations :

Lorsque les coefficients de la fonction objectif exprimée en fonction des seules variables hors base
sont négatifs ou nuls, l’algorithme s’arrête. La solution optimale est trouvée.

Ce n’est pas encore le cas pour notre exemple, d’autres solutions doivent être trouvées.
Le tableau suivant donne la deuxième solution admissible :
Base X Y t1 t1 VVB
t1 0 5/2 1 - 1/2 70
y 1 1/2 0 1/6 30
-F 0 400 0 -200 -36000

Tableau 2
Le tableau suivant donne la troisième solution admissible :
Base X Y t1 t1 VVB
t1 0 1 2/5 - 1/5 28
t2 1 0 - 1/5 1/4 16
-F 0 0 -160 -120 -47200

Ce tableau nous donne la troisième solution admissible. Celle-ci est optimale:

• Les valeurs des variables dans la Base sont X = 28 et Y =16. Cela signifie qu'on fabrique
16 pièces P1 et 28 pièces P2.
• La dernière cellule donne la valeur de -F : -F = - 47200 donc F = 47200. Cela signifie que
la marge est égale à 47200 F.

19
CHAPITRE 2 : METHODE PERT

L’abréviation P.E.R.T. signifie « Program Evaluation and Review Technique » ce que l’on peut
traduire « Technique d’Evaluation de et révision des Programmes. Le PERT est une méthode
d’ordonnancement basée sur la théorie des graphes, et visant à optimiser la planification des tâches
d'un projet.

I. Généralités sur la méthode PERT

1.1.Définition et buts de la méthode PERT
Le PERT peut se définir comme une méthode consistant à ordonnancer sous forme de graphe (ou
réseau) un ensemble de tâches qui grâce à leur dépendance et à leur chronologie concourent à
l’atteinte d’un objectif.
Il a pour buts de :
Définir le délai total d'accomplissement de l'œuvre et éventuellement proposer des moyens pour le
réduire.
Connaitre les conséquences du changement de la durée d'une tâche partielle.
Evaluer les moyens à mettre en œuvre.
Etablir une relation entre les délais et les coûts.

1.2.Historique
La méthode PERT a été conçue pour la marine américaine afin de permettre de coordonner les
travaux du projet Polaris (création d’une force d'attaque nucléaire comprenant sous-marins lance
missile et la fusée adaptée). Ce projet était soumis à de nombreux problèmes techniques,
notamment la coordination de 250 fournisseurs et 9000 sous-traitants. On estime que l’utilisation
du PERT a permis de ramener la durée globale de réalisation du projet de 7 à 4 ans. Cette méthode
s’est ensuite étendue dans l’industrie américaine, puis l’industrie occidentale.

II. Méthodologie de construction d'un graphe P.E.R.T.

2.1.Notions de base
La méthode PERT s'appuie sur une représentation graphique appelée graphe ou réseau PERT.
Un réseau PERT est constitué par des tâches et des étapes :

20
 • Les tâches (ou opérations) : ce sont les actions à réaliser pour atteindre un but. Une tâche
est caractérisée par sa durée et les moyens qu'elle met en œuvre. Elle consomme du temps
et des ressources. Les tâches sont représentées par des flèches orientées de la gauche vers
la droite. Elles portent l’indication de leur durée.
• Les événements (ou étapes) : c'est le jalon qui sépare deux tâches. C'est le commencement
ou la fin d'une tâche. Les étapes sont en règle générale numérotées et représentées par des
cercles. Certaines autres formes peuvent parfois être utilisées (carré, rectangle, ovale, etc.).
Une tâche se situe entre deux étapes.
• Les taches fictives : ce sont des tâches supplémentaires de durée nulle et ne consommant
aucune ressource, introduite pour respecter certaines contraintes d’antériorité. Une tâche
fictive est représentée par une flèche en pointillés

2.2.Conditions préalables à l’application de la méthode PERT

Le recours à la méthode PERT suppose qu'aient préalablement été identifiées les différentes tâches
nécessaires à la réalisation d'un projet, leur durée et leurs relations d'antériorité

2.2.1. La liste des tâches

Cette étape consiste à donner une liste exhaustive des tâches, c’est entreprendre l’inventaire de
l’ensemble des actions et évènements à réaliser pour exécuter le projet jusqu'à son terme.
Le Work Breakdown Structure (WBS) ou Organigramme des Tâches (OT) est la procédure
généralement utilisée pour le découpage des projets. Le WBS est une décomposition hiérarchique
des tâches à réaliser au sein d'un projet pour aboutir à des livrables spécifiques. L'organigramme
des tâches permet de partir d'un problème complexe (le projet, ou un lot du projet) et de le
décomposer en sous-problèmes, eux-mêmes décomposés en sous-sous-problèmes, pour aboutir à
des problèmes simples (tâches dont les entrées et sorties sont parfaitement identifiés et dont la
qualité du résultat est mesurable).

2.2.2. Le tableau de dépendances

Pour chacune des tâches décrites pendant l’inventaire, il s’agit de définir :
• quelle(s) autre(s) tâche(s) soit-elle immédiatement ? D’où vient-elle ?
• quelle(s) autre(s) tâche(s) précède-t-elle immédiatement ? Où va-t-elle ?

21
Généralement ces informations sont synthétisées dans un tableau :

Exemple : Projet « préparer un gâteau »

Les tâches suivantes sont à effectuer pour préparer un gâteau aux pommes :
▪ A : acheter les pommes, la farine, le lait, le beurre, la levure (25 min) ;
▪ B : éplucher et couper les pommes en rondelles (5 min) ;
▪ C : mélanger ensemble farine, lait, beurre, levure pour faire la pâte (5 min) ;
▪ D : demander à notre frère de préchauffer le four (2 min) ;
▪ E : étaler la pâte et la poser dans un plat allant au four (5 min) ;
▪ F : ajouter les pommes sur la pâte et placer le plat au four (5 min) ;
▪ G : attendre la fin de la cuisson pour sortir le plat du four et démouler le gâteau (5 min).

Tâche Durée Tâche précédente

A 25
B 5 A
C 5 A
D 2
E 5 C,D
F 5 B,C,D,E
G 5 F

2.3.Règles de représentation graphique PERT

Pour représenter un réseau PERT, il existe des règles :

Règle 1 : Un graphe possède toujours une et une seule étape de début ainsi qu’une étape de fin.
Chaque tâche est représentée par une seule flèche et chaque événement par un seul cercle.
Les flèches sont orientées de la gauche vers la droite.
Règle 2 : Deux tâches qui se succèdent immédiatement sont représentées par des flèches qui se
suivent.
A B
1 2 3
22
Règle 3 : Deux tâches A et B qui précédent une même tâche C sont dites convergentes et se
terminent par un événement commun. Elles sont représentées de la manière suivante :

Règle 4 : Deux tâches B et C qui succèdent à une même tâche A sont dites divergentes et
commencent par un événement commun, celui qui symbolise la fin de la tâche A.

Règle 5 : Parfois, il est nécessaire d’introduire des tâches fictives.

Exemple 1
B et C succèdent à A ; D succède à B et C

Exemple 2 :
D succède à B et C succède à A et B
La représentation ci-dessous, qui nous vient la première à l'esprit est la suivante :

23
Cette représentation n'est pas juste car elle indique aussi que D succède à A. La représentation
correcte est la suivante :

La tâche en pointillé est appelée tâche fictive. Les tâches fictives permettent d'éviter la création par
le graphe de nouvelles contraintes de succession des tâches non indiquées par l'analyse du projet.

Construction d'un graphe PERT

Sur la base des conventions précédentes, la construisons le graphe du projet suivant :

Taches Antécedents Durées (semaines)

A - 6
B - 5
C A 4
D B 6
E C 5
F A, D 6
G E, F 4

Les taches A et B sont sans antécédent et sont donc les taches de début.

C vient après A et D vient après B.

24
E vient après C et F vient après A et D

Enfin, G vient apres E et F. E et F convergent donc vers un événement commun d’où commence
la tache G

III. Calcul des dates et détermination du chemin critique

3.1. Détermination des dates au plus tôt
La date au plus tôt d'un événement correspond à la date à laquelle cet événement peut être atteint
au plus tôt en tenant compte du temps nécessaire à l’exécution des tâches précédentes. La date au
plus tôt d'un événement, c'est le temps minimum qu'il faut pour que toutes les tâches antérieures
soient effectuées.

25
Pour déterminer la date au plus tôt d'un événement, il faut parcourir le graphe de gauche à droite et
calculer le temps du plus long des chemins menant du début du projet à cet événement. S'il y a
plusieurs sous-chemins, on effectue le même calcul pour chacun et on choisit la durée du chemin
le plus long.

3.2. Détermination des dates au plus tard

La date au plus tard d'un événement correspond à la date limite à laquelle cet événement doit être
atteint pour que l’ensemble du projet ne prenne aucun retard.
Partant de l'hypothèse que le délai de réalisation du projet obtenu par le calcul des dates au plus tôt
est acceptable, nous allons déterminer à quelles dates au plus tard doivent être exécutées les tâches
sans remettre en cause cette date de fin du projet.
Nous déterminons pour chaque événement la durée dif du plus long des chemins menant de cet
événement à la fin projet ;
La date au plus tard de l’événement est ensuite obtenue en retranchant la durée dif de la durée
globale du projet (date au plus tôt de l’événement final).

Date au plus tard de l’événement i" = Date plus tot ef - Durée dif

26
3.3. Identification du chemin critique
Une fois la date au plus tôt et la date au plus tard de chaque événement trouvé, on peut analyser la
situation. On peut remarquer que certains événements présentent des dates au plus tôt différentes
des dates au plus tard, cela traduit un flottement qui autorise une certaine souplesse dans la
réalisation des tâches.
Quand la date au plus tôt est identique à la date au plus tard, le flottement est nul et on dit que
l’événement est critique.
Le chemin critique est donc le chemin formé par les événements de flottement nul.
Pour un même projet, il peut y avoir plusieurs chemins critiques.

Le chemin critique passe par les tâches B, D, F et G

27