ÉCOLE SUPÉRIEURE DE GESTION

ET D’ADMINISTRATION DES ENTREPRISES

Agrément définitif par Arrêté n°4677/MES/CAB du 05 Juillet 2017
Accréditée par le Conseil Africain et Malgache pour l’Enseignement Supérieur (CAMES)
BP : 2339 – Brazzaville – CONGO
E-mail : [email protected] Site web : www.esgae.org

Formation continue

RECHERCHE OPERATIONNELLE

Parcours
Certificat d’Etudes Supérieures en
Administration des Entreprises ( CESAE)

Enseignant
Equipe pédagogique
Recherche opérationnelle CEASE
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

1
CHAPITRE 1 : PROGRAMMATION LINÉAIRE

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

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écisions 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.

2
Koopmans proposa pour la première fois le nom de « programmation linéaire » lors d'une
discussion avec Dantzig en 1948.
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 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é.

3
 • L’hypothèse de divisibilité qui exprime que les variables du problème sont réelles et pas
forcément des entiers naturels.

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 connue (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 objective : Le terme “objectif” vient du fait que l’objectif est d’optimiser
cette fonction. Elle doit être représentée sous une forme linéaire
en fonction des variables de décision. Il faut ensuite spécifier si le critère de sélection est à
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

4
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.
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.

5
Tableau : Informations pour le PL des tables et chaises en bois.
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 objective 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é)

6
Exemple 2 : Problème de minimisation
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

7
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 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

3.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'écrit donc :

8
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

3.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

3.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

3.3.1. Variable entrante, sortante et pivot

Détermination de la variable entrante

1
VVB signifie Valeurs des Variables de Base

9
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

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 nous permettre de transformer le tableau en un nouveau tableau correspondant à
une solution améliorée.

3.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 dans = Terme à remplacer dans le tableau - 𝑋. 𝑌

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

10
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.

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.

3.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.

11
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 :

12
 • 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-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 ?

13
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

14
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 :

15
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.

16
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.

17
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

18
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

19