Les cahiers du formateur

UCAO/UUZ 2009-2010
Module de Recherche Opérationnelle de Gestion Prof : M Abdoulaye GAYE
[email protected]

Chapitre1 : Programmation linéaire

Section 1 : Généralités

Section 2 : Méthodes des tableaux

1. Méthode du simplexe

2. Méthode des deux phases et Méthode M

3. Dualité

Chapitre2 : Graphes

Section1 : Définitions et vocabulaires

Section2 : Chemin de valeur optimale

Section 3 : Problème d’ordonnancement

M Gaye RO : Lic Pro 1

 Les cahiers du formateur

Introduction

La recherche opérationnelle est une méthode d'analyse scientifique d'un problème. Elle consiste
aider le décideur lorsque celui-ci est confronté :
✓ à un problème combinatoire : Le problème comprend un grand nombre de solutions
admissibles parmi lesquelles on cherche une solution optimale ou proche de l'optimum.
Exemple: déterminer où installer 5 centres de distribution parmi 30 sites d'implantation
possibles, de sorte que les coûts de transport entre ces centres et les clients soient minimum
✓ à un problème aléatoire : il consiste à trouver une solution optimale face à un problème
qui se pose en termes incertains.
Exemple: connaissant la distribution aléatoire du nombre de personnes entrant dans une
administration communale en une minute et la distribution aléatoire de la durée de traitement
du cas d'une personne, déterminer le nombre minimum de guichets à ouvrir pour qu'une
personne ait moins de 5% de chances de devoir attendre plus de 15 minutes.
Etc….
Applications pratiques :

La RO intervient dans les domaines suivants :

✓ dans a gestion de projets : ex Logistique (tournées de véhicules optimisant les

transports),la planification(gestion des différentes tâches du projet)
✓ dans le domaine de la finance, les problèmes d'investissement sont des problèmes
classiques de recherche opérationnelle. Ils consistent en général à maximiser le profit
obtenu à partir d'un montant donné en combinant au mieux les différentes possibilités
offertes à l'investisseur.
✓ dans le domaine de l’industrie pétrolière Elle est couramment utilisée dans l'industrie
pétrolière, principalement dans l'établissement des plans de production à long terme, à
moyen terme, annuel, trimestriel et mensuel. Les résultats permettent aux décideurs
d'avoir un guide pour faire les meilleurs choix dans les investissements, dans
l'approvisionnement des bruts, dans l'utilisation des unités de raffinage, dans les
canaux de distribution les plus rentables
✓ dans le domaine de l’informatique (routage des paquets et choix du plus court chemin
que empruntés par les paquets dans les réseaux internet..)

Chapitre1: Programmation linéaire

M Gaye RO : Lic Pro 2

 Les cahiers du formateur

Section1 : Généralités

1. Introduction

Un programme linéaire est un programme consistant à trouver un extremum (maximum ou

minimum) d’une fonction à plusieurs variables, vérifiant en outre un système d’équations ou
d’inéquations, ces fonctions étant linéaires.
La méthode graphique devient difficile à réaliser lorsqu’il y a 3 variables, et impossible s’il y
a plus de 3 variables. Il faut donc trouver une autre méthode : celle du simplexe.

2. Exemple

Une usine fabrique deux produits A et B à partir de trois ressources R1, R2 et R3 avec les
caractéristiques suivantes:

A B Stocks
R1 2 1 8
R2 1 2 7
R3 0 1 3
gains 4 5

Mise en équations avec x1 le nombre de "A" et x2 le nombre de "B" sachant que x1et x2  0
Bilan de R1: 2 x1 + x2  8
Bilan de R2: x1 + 2 x2  7
Bilan de R3: x2  3
Le critère étant un max z = 4 x1 + 5 x2
3. Forme canonique

Tout programme linéaire peut être mis sous forme canonique, c'est à dire un système avec un
ensemble d'inéquations et une fonction à optimiser.
n
max z =  c j .x j
j=1
Fonction économique
n
 a ij .x j  b i , pour 1  i  m m: contraintes
j=1
x j  0, pour 1  j  n n: nbre de variables x1,…,xn

Il y a m contraintes propres et n contraintes impropres (de positivité), et n variables naturelles.

Remarque

Une solution admissible est un n-uplet qui vérifie toutes les contraintes ; parmi ces solutions
admissibles celle(s) pour la(les)quelle(s) la fonction économique est maximale, s’appelle(nt)
solution(s) optimale(s).

Exemple :

M Gaye RO : Lic Pro 3

 Les cahiers du formateur

Le programme linéaire suivant est sous forme canonique :

Max Z=3x1-2x2+8x3
5x1-2x2+4x3≤8
x1+ 3x2+8x3≤25
9x1+6x2-3x3≤17
x1, x2, x3≥0

4. Transformations

Tout programme linéaire quelconque peut être ramené à une fonction canonique .Voici
quelques exemples de transformations possibles :

➢ Si une variable x est négative, on la remplace par une variable positive x’=-x

Exemple

Max Z=3x1-2x2+8x3 Max Z=3x1-2x2-8x3’

Sous Sous
5x1-2x2+4x3≤8 ↔ 5x1-2x2-4x3’≤8
x1+3x2+8x3≤25 x1+3x2-8x3’≤25
9x1+6x2-3x3≤17 9x1+6x2+3x3’≤17
x1,x2≥0 et x3≤0 x1,x2,x3’≥0

➢ Si une variable x n’a pas de contrainte de signe, on la remplace par deux variables
positives x’ et x’’ telles que x=x’-x’’

Exemple

Max Z= 3x1+2x2 Max Z=3x1’-3x1’’+2x2

Sous Sous
5x1-2x2≤8 ↔ 5x1’-5x1’’-2x2≤0
9x1+x2≤5 9x1’-9x1’’+x2≤0
x1,x2≥0 x1’,x1’’,x2≥0

➢ Si le programme linéaire a une contrainte de supériorité,on la remplace par une

contrainte d’infériorité en inversant le signe des constantes
Exemple

Max Z= 3x1-2x2+8x3 Max Z=3x1-2x2+8x3

Sous Sous
5x1-2x2+4x3≤8 ↔ 5x1-2x2+4x3≤8
x1+3x2+8x3≤25 x1+3x2+8x3≤25
9x1+6x2-3x3≥17 -9x1-6x2+3x3≤-17
x1,x2,x3≥0 x1,x2,x3≥0

➢ Si le programme linéaire a une contrainte d’égalité, on la remplace par deux contraintes

équivalentes, l’une d’infériorité, l’autre de supériorité. Les variables du programme
doivent satisfaire ces deux contraintes, ce qui revient alors à l’égalité de départ.

M Gaye RO : Lic Pro 4

 Les cahiers du formateur

Exemple

Max Z= 3x1-2x2+8x3 Max Z=3x1-2x2+8x3

Sous Sous
5x1-2x2+4x3≤8 ↔ 5x1-2x2+4x3≤8
x1+3x2+8x3≤25 x1+3x2+8x3≤25
9x1+6x2-3x3=17 9x1+6x2-3x3≤17
x1,x2,x3 ≥0 9x1+6x2-3x3≥17
x1,x2,x3≥0
↔ Max Z=3x1-2x2+8x3
Sous
5x1-2x2+4x3≤8
x1+3x2+8x3≤25
9x1+6x2-3x3≤17
-9x1-6x2+3x3≤-17
x1,x2,x3≥0

5. Interprétation géométrique
Soit le système:
-2x1 + x2  1
x1 + 3x2  10
x1  4
max z = -x1 + x2

D1 2 1 D3
D1 -2x1 + x2 = 1
x2 = 2x1 + 1
0
D2 3x2 = 10 – x1
x2 = 10/3 – (1/3)x1 -1
A
D3 x1  4 D2
x2 = 2x1 + 1

k x2 – x1 = k
x2 = x1 + k

z a pour maximum 2 atteint en x1 = 1, x2 = 3

6. Forme standard

M Gaye RO : Lic Pro 5

 Les cahiers du formateur

Exemple :
Soit le système:

max z = -x1 + x2

-2x1 + x2  1
x1 + 3x2  10
x1  4
x1,x2≥0

Ce problème peut être écrit sous la forme standard suivante :

max z = -x1 + x2

-2x1 + x2 +t1=1
x1 + 3x2 +t2=10
x1 +t3=4
x1,x2,t1,t2,t3≥0

Les variables t1, t2 et t3 sont appelées variables d’écart

Théorème

Tout programme linéaire peut être écrit sous forme canonique ou sous forme standard.

n
max z =  c j .x j
j=1
n
 a ij .x j + x n +i = b i , pour 1  i  m
j=1
x j  0, pour 1  j  n
x n +i  0, pour 1  i  m

Section2 : Méthode des Tableaux

M Gaye RO : Lic Pro 6

 Les cahiers du formateur

1. Méthode du Simplexe
Exemple1

Soit le système S1:

max z = -x1 + x2

-2x1 + x2 ≤1
x1 + 3x2 ≤ 10
x1 ≤4
x1 , x2  0

Tout d’abord le point (0,0) est une solution admissible du problème S1

Mettons S1 sous la forme standard en introduisant les variables d’écart
max z = -x1 + x2

-2x1 + x2 + t1 =1
x1 + 3x2 + t2 = 10
x1 + t3 = 4
x1 , x2 , t1, t2 , t3  0

Sous forme de tableau :

coef bi x1 x2 t1 t2 t3
1 1 –2 1 1 0 0
10/3 10 1 3 0 1 0
 4 1 0 0 0 1
Z –1 1 0 0 0

La solution admissible de base (solution initiale) est:

x1=x2=0 (donc ce sont les variables Hors Base)

et t1 =1, t2= 10, t3= 4 (en base) avec z = 0.

Comme le coefficient de x2 est le plus petit positif, on va faire entrer x2 en base puis annuler
tous les coefficients de la colonne x2 sauf le pivot=1, en utilisant le pivot de Gauss ( L2-3L1)

coef bi x1 x2 t1 t2 t3
-1/2 1 –2 1 1 0 0 x2
1 7 7 0 -3 1 0 t2 L2 – 3L1
4 4 1 0 0 0 1 t3
Z-1 1 0 -1 0 0 L4 – L1

M Gaye RO : Lic Pro 7

 Les cahiers du formateur

on va faire entrer x1 en base et en sortir t2 puis utiliser la méthode du pivot de gauss pour annuler
tous les coefficients de la colonne x1 sauf le pivot=1.( L2/7 ; L1-L2)

bi x1 x2 t1 t2 t3
3 0 1 1/7 2/7 0 x2
1 1 0 -3/7 1/7 0 x1
3 0 0 3/7 -1/7 1 t3
Z–2 0 0 -4/7 -1/7 0

Condition d’arrêt : tous les coefficients de la dernière ligne Z sont négatifs ou nuls.

On a obtenu la solution optimale, puisque les coefficients de la fonction économique sont

tous négatifs ou nuls, une augmentation de t2 ou de t1, variables hors base entraînerait une
diminution de la valeur de Z.
Conclusion : solution optimale : x1=1, x2=3, z =2

Exemple2
Soit le programme linéaire S2 suivant sous sa forme canonique:
Soit le programme linéaire suivant sous sa forme canonique:
max z = x1 + 3x2

x1 + x2  14
-2x1 + 3x2  12
2x1 - x2  12
x1, x2  0

1. Résolvons S2 par la méthode simplexe

Tout d’abord le point (0,0) est une solution admissible du problème S1
Mettons S1 sous la forme standard en introduisant les variables d’écart :
max z = x1 + 3x2

x1 + x2 +t1=14
-2x1 + 3x2 +t2=12
2x1 - x2 +t3=12
x1, x2 ,t1,t2,t3 0

coef(bi/ai1) bi x1 x2 t1 t2 t3 définit
14 14 1 1 1 0 0 t1
4 12 -2 3 0 1 0 t2
-2 2 2 -1 0 0 1 t3
Z 1 3 0 0 0

Solution de base admissible: x1 = x2 = 0 t1 = 14

t2 = 12
t3 = 2
On prend celui qui fait augmenter le plus Z donc ici on choisit de faire rentrer x 2 en base car
son coeff sur Z est de 3.

M Gaye RO : Lic Pro 8

 Les cahiers du formateur

coef bi x1 x2 t1 t2 t3 définit
10*3/5 6 10 5/3 0 1 -1/3 0 t1 L1 - L2
4*(-3/2) -6 4 -2/3 1 0 1/3 0 x2 L2/3
16*3/4 12 16 4/3 0 0 1/3 1 t3 L3 + L2
Z-12 3 0 0 -1 0 LZ - 3L2

z=30 ; x1 = 6 ; x2=8 ; t1=t2=0 ; t3=8

2. Résolvons S2 par la méthode graphique

D2 D3
D1 x1 + x2 = 14 30
x2 = 14 – x1

12
D2 x2 = 2/3 x1 + 4

D3 x2 = 2 x1 - 12
D1
si x1 = 0 et k = 0 alors x2 = 0
car x2 = (k – x1) / 3
donc 0 x2 = -(1/3) x1 0
12 x2 = 4 = (1/3) k
30 x2 = 8 x1 = 6

Z = 30 pour x1 = 6 et x2 = 8

Exemple3

Soit le programme linéaire S3 suivant sous sa forme canonique:

x1 - x2  3
-x1 + 2x2  4 avec x1, x2  0
2x1 + x2  8
max z = x1 + ½ x2
On introduit donc les variables d'écart t1 et t2:
x1 - x2 + t1 = 3
-x1 + 2x2 + t2 = 4 avec xi, ti  0
2x1 + x2 + t3 = 8
max z = x1 + ½ x2
Trouvons une solution optimale par la méthode simplexe.

coef (bi/ai1) bi x1 x2 t1 t2 t3 définit

3 3 1 -1 1 0 0 t1
-4 4 -1 2 0 1 0 t2
4 8 2 1 0 0 1 t3
Z 1 1/2 0 0 0

M Gaye RO : Lic Pro 9

 Les cahiers du formateur

Solution de base admissible: x1 = x2 = Z = 0 t1 = 3

t2 = 4
t3 = 8

On fait rentrer x1 en base et sortir t1:

coef (bi/ai1) bi x1 x2 t1 t2 t3 définit

-3 3 1 -1 1 0 0 x1
7 7 0 1 1 1 0 t2
2/3 2 0 3 -2 0 1 t3
Z-3 0 3/2 -1 0 0

On fait rentrer x2 en base et sortir t3:

bi x1 x2 t1 t2 t3 définit
11/3 1 0 1/3 0 1/3 x1 L1+L'3
19/3 0 0 5/3 1 -1/3 t2 L2-L'3 B
2/3 0 1 -2/3 0 1/3 x2 L'3
Z-4 0 0 0 0 -1/2

Mais on voit que ce n'est pas la seule solution (notamment grâce au graphique) et on peut donc
continuer en faisant rentrer t1 et sortir t2.

bi x1 x2 t1 t2 t3 définit
12/5 1 0 0 -5 2 x1
19/5 0 0 1 3/5 -1/5 t1 A
16/5 0 1 0 2/5 1/5 x2
Z-4 0 0 0 0 -1/2

En fait, il y a une infinité de solutions optimales sur le segment [AB].

Section2 : Méthode des deux phases et Méthode M

Ces méthodes sont à utiliser si les seconds membres ne sont pas tous positifs.

1. Méthode des 2 phases

max z = 2 x 1 + 3x 2
x 1 + x 2  6

Soit le Programme Linéaire dont la forme canonique est la suivante : − 2 x 1 − x 2  −4
− 2 x + x  −2
 1 2
x1 , x 2  0

M Gaye RO : Lic Pro 10

 Les cahiers du formateur

max z = 2 x1 + 3 x2
 x1 + x2 + t1 = 6

En le mettant sous la forme standard : − 2 x1 − x2 + t 2 = −4
− 2 x + x + t 3 = −2
 1 2

x1 , x2 , t1, t 2, t 3  0

La difficulté de cette étude provient du fait que l’on n’a pas une solution admissible initiale, en
fixant x1=x2=0 (variables hors-base) car on aurait alors t1=6  0 (valable), mais t2=–4  0 (non
valable) et t3= –2  0 (non valable). Il faut donc commencer par chercher une première solution
admissible. On pourrait essayer se ramener au simplexe.
Ou alors, on introduit des variables artificielles : v1 et v2, associées à un coefficient de la
fonction économique négatif, (pour que la solution optimale du PL avec ces deux variables
artificielles soit obtenue avec x6 et x7 nulles, c’est-à-dire la solution optimale du nouveau PL est
la même que celle du PL sans ces deux variables artificielles).
Le Programme Linéaire devient :
max z = 2 x1 + 3x2 − Mv1 − Mv 2
 x1 + x2 + t1 = 6

− 2 x1 − x2 + t 2 − v1 = −4
− 2 x + x + t 3 − v 2 = −2
 1 2

x1 , x2 , t1, t 2, t 3, v1, v 2  0

ou

max z = 2 x1 + 3x2 − Mx6 − Mx7

 x1 + x2 + t1 = 6

2 x1 + x2 − t 2 + v1 = 4
2 x − x − t 3 + v 2 = 2
 1 2
x1 , x2 , t1, t 2, t 3, v1, v 2  0

1ère phase:
Cherchons dans le système à maximiser une nouvelle fonction économique z' = -V1 – V2
V1 = 4 – 2x1 – x2 + t2
V2 = 2 – 2x1 + x2 + t3
z' = -4 + 2x1 + x2 - t2 - 2 + 2x1 – x2 - t3 = -6 + 4x1 - t2 - t3

coef (bi/ai1) bi x1 x2 t1 t2 t3 V1 V2 définit

6 6 1 1 1 0 0 0 0 t1
2 4 2 1 0 -1 0 1 0 V1
1 2 2 -1 0 0 -1 0 1 V2
Z'+6 4 0 0 -1 -1 0 0
Z 2 3 0 0 0 0 0

M Gaye RO : Lic Pro 11

 Les cahiers du formateur

Ici, L1  L1 - L3

coef (bi/ai1) bi x1 x2 t1 t2 t3 V1 V2 définit

10/3 5 0 3/2 1 0 ½ 0 -1/2 t1
1 2 0 2 0 -1 1 1 -1 V1
-2 1 1 -1/2 0 0 -1/2 0 ½ x2
Z'+2 0 2 0 -1 1 0 -2
Z-2 0 4 0 0 1 0 -1

V2 étant devenu nul, on élimine sa colonne du tableau.

coef (bi/ai1) bi x1 x2 t1 t2 t3 V1 définit

14/3 7/2 0 0 1 ¾ -¼ -¾ t1
-2 1 0 1 0 -½ ½ ½ x2
-6 3/2 1 0 0 -¼ -¼ ¼ x1
Z' 0 0 0 0 0 -1
Z-6 0 0 0 2 -1 -2

Fin de la première phase: solution initiale de (S): x1 = 3/2 , x2 = 1 , t1 = 7/2 , z = 6

2ième phase: simplexe classique sur (S)

On a hors base: t2 et t3 , et en base: x1 , x2 et t1.

bi x1 x2 t1 t2 t3 définit
14/3 0 0 4/3 1 -1/3 t2
10/3 0 1 2/3 0 1/3 x2
8/3 1 0 1/3 0 -1/3 x1
Z –46/3 0 0 -8/3 0 -1/3

La solution optimale est donc pour x1 = 8/3 , x2 = 10/3 , t2 = 14/3 , et z = 46/3

2. Méthode M

max z = 2 x1 + 3x2 − Mx6 − Mx7

 x1 + x2 + t1 = 6

2 x1 + x2 − t 2 + v1 = 4
2 x − x − t 3 + v 2 = 2
 1 2
x1 , x2 , t1, t 2, t 3, v1, v 2  0
bi x1 x2 t1 t2 t3 V1 V2 définit
6 1 1 1 0 0 0 0 t1
4 2 1 0 -1 0 1 0 V1
2 2 -1 0 0 -1 0 1 V2
Z 2 3 0 0 0 -M -M

M Gaye RO : Lic Pro 12

 Les cahiers du formateur

Le premier tableau n'est pas un tableau du simplexe, il aurait donc fallu commencer par le
ramener à une forme de vrai tableau du simplexe. C'est-à-dire les coefficients des variables de
base sont nuls sur Z)

bi x1 x2 t1 t2 t3 V1 V2 définit
6 1 1 1 0 0 0 0 t1
Le tableau
4 2 1 0 -1 0 1 0 V1
initial du
2 2 -1 0 0 -1 0 1 V2
simplexe
Z+4M 2+2M 3+M 0 -M 0 0 -M L'4  L4 + ML2 est donc:
Z+6M 2+4M 3 0 -M -M 0 0 L'4  L4 + ML3

coef (bi/ai1) bi x1 x2 t1 t2 t3 V1 V2 définit

6 6 1 1 1 0 0 0 0 t1
2 4 2 1 0 -1 0 1 0 V1
1 2 2 -1 0 0 -1 0 1 V2
Z+6M 2+4M 3 0 -M -M 0 0

On fait rentrer x1 dans la base et sortir V2.

coef (bi/ai1) bi x1 x2 t1 t2 t3 V1 V2 définit

10/3 5 0 3/2 1 0 ½ 0 -½ t1
1 2 0 2 0 -1 1 1 -1 V1
-2 1 1 -½ 0 0 -½ 0 ½ x1
Z+2M-2 0 4+2M 0 -M 1+M 0 -1-2M

On fait rentrer x2 dans la base et sortir V1.

bi x1 x2 t1 t2 t3 V1 définit
7/2 0 0 1 ¾ -¼ -3/4 t1
1 0 1 0 -½ ½ ½ x2
3/2 1 0 0 -¼ -¼ ¼ x1
Z-6 0 0 0 2 -1 -2-M

3. Dualité

Il s’agit de transformer un problème de minimisation en son dual de maximisation. La

résolution de ce dernier permet de trouver les solutions du problème de minimisation en prenant
les coefficients des variables d’écarts( à un signe près) à la fin de l’algorithme du simplexe.

max z = 14x1 + 17 x 2 + 12x 3

x1 + x 2 + x 3  40

10x1 + 12x 2 + 7 x 3  420
6x + 9x + 5x  280
 1 2 3
x1 , x 2 , x 3  0
Le dual du 1er PL est obtenu à partir du tableau suivant :

M Gaye RO : Lic Pro 13

 Les cahiers du formateur

X1 X2 X3 Min
Y1 1 1 1 40
Y2 10 12 7 420
Y3 6 9 5 280
max 14 17 12

Les coefficients contraintes deviennent les coefficients de la fonction économique Z’. la matrice
de production est transposée( lignes deviennent colonnes et vice-versa), les coefficients de Z
deviennent les contraintes du programme dual.

min z' = 40 y1 + 420 y 2 + 280 y 3

 y1 + 10 y 2 + 6 y 3  14

C’est-à-dire :  y1 + 12 y 2 + 17 y 3  17
 y + 7 y + 5y  12
 1 2 3
y1 , y 2 , y 3  0

M Gaye RO : Lic Pro 14

 Les cahiers du formateur

Chapitre 2 : Les Graphes

Section1 : Définitions et vocabulaires
1.1) Graphe
Définition : Soit X un ensemble fini et dénombrable : X = {x1, …, xn}. Soit  une application
de X dans lui-même ( est l'ensemble des arcs ou trajets existants = {(x1,x2), (x1,x3), (x1,x6),
(x2,x3), (x2,x4), (x3,x4), (x3,x5), (x4,x5), (x6,x5), (x6,x5)}.
On appelle l’ensemble (X, ) un graphe d’ordre n (n est le nombre de sommets = card X). Un
graphe est donc un ensemble de liaisons entre des points.
Représentation sagittale :

x1 x2

x6 x3

x5 x4

On peut noter + l’application « successeur » : + : X → P(X) (ensemble des parties de X). Par
exemple, +(x1) = {x2, x4, x6}. De même, on peut définir -, l’application « prédécesseur », : X
→ P(X). Ex. :  -(x2)={x1}

Précédents Suivants
x1 x2, x4, x6
x2 x1 x3, x4
x3 x2 x4, x5
x4 x1, x2, x3, x6 x5
x5 x3, x4, x6
x6 x1 x4, x5

Deux sommets reliés s’appellent sommets adjacents.

1.2) Chemins
Un graphe peut être orienté ou non orienté.
Ex. :
x2 x2 arête
cycle
x1 x3 x1 x3
x4 x4

Graphe orienté graphe non orienté

Dans un graphe orienté, on parle d’arcs reliant deux sommets.

On appelle chemin une suite ordonnée d’arcs dans lesquels l’extrémité terminale d’un arc
coïncide avec l’extrémité initiale du suivant : [x1x2], [x2 x3] = x1 x2 x3 (chaîne si non orienté).

M Gaye RO : Lic Pro 15

 Les cahiers du formateur

Un chemin pour lequel u1 = uP s’appelle circuit.

x2
x1 x2
x1
x3
x5 x3
x4 x5
x4
Chemin circuit

Longueur d’un chemin = nombre d’arcs du chemin

Boucle = chemin de longueur 1

Un chemin est simple lorsqu’il ne passe qu’une seule fois par chacun de ses arcs
Un chemin est élémentaire s’il ne rencontre pas plus d’une seule fois chaque sommet.

(abcd) = chemin élémentaire

a b (abbcd) = chemin non élémentaire
(bb) = boucle et circuit élémentaire
(abca) =circuit élémentaire
c d (abcabc) = circuit non élémentaire
Un chemin qui passe une fois exactement par chaque sommet est hamiltonien

Ex. : (a,b,c,d) est un chemin hamiltonien. Mais il n’y a pas de circuit hamiltonien : il faudrait
que d  a
NB : dans un graphe d’ordre n, un circuit hamiltonien est de longueur n, un chemin est de
longueur n – 1.

Dans un graphe non orienté :

On appelle un arc non orienté une arête. Le chemin devient chaîne, le circuit cycle.

2 : Matrices associées à un graphe

On écrit tous les chemins possibles d'un graphe pour trouver les chemins hamiltoniens.

2.1) Matrice latine

A B C D E
B A AB AC AE
B BB BC
A C C CD
D DA DE
E EA EC
E D
Pour trouver les chemins de longueur 2, on calcule M² ; pour les chemins de longueur 3, on
calcule M3 et ainsi de suite.

M Gaye RO : Lic Pro 16

 Les cahiers du formateur

ABC
AEA ABB ACD
M² = AEC
BBB BBC BCD
CDA CDE
DAC
DEA DAB DAE
DEC
EAB EAC ECD EAE

Recherche des chemins élémentaires : avec la multiplication latine, il suffit de ne considérer

que les chemins de Mn-1 qui n’ont pas de répétition de lettres ; dans l’exemple, matrice des
chemins élémentaires de longueur 4, ici chemins hamiltoniens.

0 1 1 0 1 1 1 2 1 0
M2 = 0 1 1 0 0 0 1 1 1 0
0 0 0 1 0 1 0 0 0 1
1 0 0 0 1 1 1 2 0 1
1 0 1 0 0 0 1 1 1 1

2.2) Matrices booléenne et arithmétique

a) Matrice arithmétique :

A C
M= M² =

E D
Si M est symétrique, le graphe est symétrique.
Si dans M², il y a un 1 (ex. : (A,B)) alors: il y a
un chemin de longueur AEAEA AEABB AEABC AEAEC ABCDE
1 de A à B, s’il y a un 2
(ex. : (A,C)), il y a un ABCDA AEACD
ABBBB ABBBC AECDE chemin de longueur 2,
AECDA ABBCD
etc. ACDAB ACDAC ACDAE
ACDEA
On peut connaître ACDEC l'existence et le nombre
de chemin d'une BBCDA BBBBB BBBBC BBCDE longueur donnée mais
on ne peut pas préciser BCDEA BCDAB BCDAC BBBCD
BCDAE s'il est hamiltonien,
BCDEC
simple ou autre… CDABC
CDABB CDACD
CDAEA CDAEC CDEAE
CDEAB CDECD
Rappel: CDEAC
DEABC 25
DEAEA DEABB DEACD 8 DACDE
7
B= 1x2 + 3x8 =
26 DEAEC
DACDA DABBB DABCD DAEAE
DABBC
DECDA DAEAB DAECD DECDE
DAEAC
EABBC
M Gaye RO : Lic Pro EABBB EACDE
EACDA ECDAC EABCD 17
ECDAB ECDAE
ECDEA ECDEC EAECD
EAEAB EAEAE
EAEAC
 Les cahiers du formateur

1x5 + 3x7 = 26
13 25 26 26 13
24 . 87 = 36 38 A= 24 26 26 2x2 + 4x8 = 36
36 38 2x5 + 4x7 = 38

N'oublions pas que BA  AB ! 13

A= 2 4
25
B= 87 12 26
22 52

b) Matrice booléenne :

0 1 1 1 1 1 1 1 1 1 1 1
A B      
0 1 1 0 0 1 1 1 1 1 1 1
M= M² =  M =
3
0 0 0 1 1 1 1 0 0 1 1 1
     
D C 1 0  0 1  1 1
 1 1  1 1  1 1

Ici, la présence d'un 1 représente l'existence d'un chemin. Dans M², s’il y a un 1 cela signifie
qu’il existe un chemin de longueur au plus 2 entre les deux sommets.
Les matrices booléennes permettent d’aider lors de la recherche des composantes connexes.

Remarque : si le graphe a une entrée (point de début, c'est à dire que les arcs partent de ce
sommet mais aucun n'y arrive), il y a une colonne de 0 associée à ce sommet ; et si le graphe a
une sortie, il a une ligne de 0.

3 Connexité et forte connexité

3.1) Connexité
Un graphe est dit connexe s’il existe au moins un chemin entre toute paire de sommets.

Exemple :
Ce graphe est non connexe, mais il a 3
A B composantes connexes.
C D E G

Déf. de composante connexe :

On définit une relation d’équivalence  par xi  xj si xi et xj (confondus ou non) sont reliés par
une chaîne (On a évidemment : xi  xi)

Ex : A B C X= {A, B, C, D, E, F}
E
Ce graphe contient deux composantes connexes :
D F {E} et {A, B, C, D, F}

M Gaye RO : Lic Pro 18

 Les cahiers du formateur

Démo : Cette relation est bien une relation d’équivalence :

A  A donc la relation est réflexive.
A  B et B  A : car il existe une chaîne de A vers B ou de B vers A (l’ordre ne compte pas),
donc la relation est symétrique
A  B et B  C  A  C, donc la relation est transitive
On parle alors des classes d’équivalence de cette relation : la classe de x est l’ensemble des
sommets équivalents à x, on l’appelle composante connexe de x.
Remarque: un sommet est toujours lié à lui-même.

3.2) Forte connexité

Un graphe est dit fortement connexe si entre toute paire de sommets, il existe un chemin de A
vers B et un chemin de B vers A.
Soit G =(X, U) un graphe. Si quels que soient A, B  X, il existe un chemin de A vers B et un
chemin de B vers A, alors le graphe est fortement connexe. Sinon on définit des composantes
fortement connexes.
Exemple : dans l’exemple précédent, il y a quatre composantes fortement connexes qui sont :
{A}, {B, C, D}, {F} et {E}. Dans la suite, on a une composante fortement connexe.
A B C B -> C B -> D
C -> B D -> C -> B
D F

Remarque : on définit là encore une relation d’équivalence (en admettant que A est en relation
avec lui-même).

3.3) Fermeture transitive

Fermeture transitive d’un sommet x : {ensemble des sommets reliés à x par un chemin de
longueur  n – 1} = {x}  {t(x)}…  {tn-1(x)}, où tk(x) = t(tk-1(x)).

A partir d’un graphe G, on définit une matrice booléenne M, puis on calcule les puissances M k.
Entre xI et xj, il existe au moins un chemin de longueur k si le terme (i,j) de la matrice M k vaut
1. Alors dans M+M[2] +…+M[k-1], on trouvera 1 en place (i,j) s’il existe un chemin de longueur
 k-1 entre xi et xj

La fermeture transitive de l’ensemble X des sommets du graphe G est obtenue en calculant

I+M+…+M[n-1] = (I+M)[n-1]

Exemple :
2
1 3
4
5

M Gaye RO : Lic Pro 19

 Les cahiers du formateur

0 1 1 0 1 1 1 1 0 1 1 1 1 1 1
     
0 0 1 0 0 0 1 1 0 0 0 1 1 1 1
M =0 0 0 1 1  , I+M=A= 0 0 1 1 1  , A²= 0 0 1 1 1 ,
     
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
0  0 0 0  0 0 0 1 
 0 0 1 0  1 1  1
A3= A²=Ak pour k  2

La fermeture transitive du graphe est donc obtenue en permutant lignes et colonnes :

1 1 1 1 1
 
0 1 1 1 1
0 0 1 1 1 1 2 3 5 4
 
0 0 0 1 1
0 1
 0 0 0

et le graphe a cinq composantes fortement connexes.

Remarque : on n’est pas toujours obligé de calculer jusqu’à (I+M)(n-1), on peut s’arrêter dès
que (I+M)(k-1) = (I+M)(k)

3.4) Recherche des classes fortement connexes,

des circuits hamiltoniens
Soit le graphe d’ordre 7 suivant :
A B G C

F E D
0 1 0 0 0 0 0 1 1 1 1 1 1 1
   
0 0 0 0 0 1 1 1 1 1 1 1 1 1
M= 0 0 0 1 0 0 0 (I+M)6 = 0 0 1 1 1 0 1
   
0 0 0 0 1 0 0 0 0 1 1 1 0 1
0 0 0 0 0 0 1  0 0 1 1 1 0 1
 
1 0 0 0 1 0 0 1 1 1 1 1 1 1
   
0 0 1 0 0 0 0 0 0 1 1 1 0 1
Après réorganisation des lignes et des colonnes, on détermine les classes fortement connexes :
c 1 c2 c6 c3 c4 c5 c7
A 1 1 1 1 1 1 1 A B G C
 
B 1 1 1 1 1 1 1
I II
F 1 1 1 1 1 1 1
  F E D
C 0 0 0 1 1 1 1
D  0 0 0 1 1 1 1
II
E 0 0 0 1 1 1 1
 
G 0 0 0 1 1 1 1

M Gaye RO : Lic Pro 20

 Les cahiers du formateur

Recherche des chemins hamiltoniens :

La classe II n’a que des arcs incidents intérieurement. Donc s’il existe un ou plusieurs chemins
hamiltoniens, leur origine doit se trouver dans la classe I et leur extrémité dans la classe II.
FABGCDE ; ABFEGCD sont les deux chemins hamiltoniens de ce graphe.

Section 2 : Chemin de valeur optimale

Algorithme de Ford

On a un graphe quelconque, valué par des grandeurs positives.

Problème du voyageur de commerce : aller de A à B en passant par un certain nombre d’autres
villes, en effectuant un minimum de km.

3
C D
2 2
8 2
6
A
5 E 2 F 1 B
8
3 3
G
Algorithme :
1. On numérote les sommets dans un ordre quelconque (sauf le x1 et xn)
2. i = +  sauf 1 = 0
3. pour tout sommet xj pour lequel j - i > V(xi, xj), V représentant la valuation de l’arc,
remplacer j par i + V(xi, xj)
4. s’arrêter lorsque aucun i ne peut plus être modifié.

C =2 D =5
3 D
C 2
2 2
8
A = 0 6
F = 6
BB =7
A
5 2 F 1
E
E=5 8
3 3
G
G =3
Le but est de trouver un chemin de A vers B associé à la valuation totale la plus faible.
ACDB = 2+3+2=7
AEDB = 5+8+2=15
AEFB = 5+2+1=8
…

M Gaye RO : Lic Pro 21

 Les cahiers du formateur

Chemins de valeur minimale : ACDB, ou AGFB, coût : 7

M Gaye RO : Lic Pro 22

 Les cahiers du formateur

Algorithme de Ford-Fulkerson

2.1) flot à travers un réseau

Trois châteaux d’eau A, B, C alimentent quatre villages D, E, F, G.
Le château d’eau A dispose d’un débit de 45 litres/sec
Le château d’eau B dispose d’un débit de 25 litres/sec
Le château d’eau C dispose d’un débit de 20 litres/sec
Le village D aurait besoin d’un débit de 30 litres/sec
Le village E aurait besoin d’un débit de 10 litres/sec
Le village F aurait besoin d’un débit de 20 litres/sec
Le village G aurait besoin d’un débit de 30 litres/sec
Dans la canalisation entre le château A et le village D, le débit maximum est : 10 litres/sec
Dans la canalisation entre le château A et le village E, le débit maximum est : 15 litres/sec
Dans la canalisation entre le château A et le village G, le débit maximum est : 20 litres/sec
Dans la canalisation entre le château B et le village D, le débit maximum est : 15 litres/sec
Dans la canalisation entre le château B et le village E, le débit maximum est : 5 litres/sec
Dans la canalisation entre le château B et le village F, le débit maximum est : 15 litres/sec
Dans la canalisation entre le château C et le village F, le débit maximum est : 10 litres/sec
Dans la canalisation entre le château C et le village G, le débit maximum est : 10 litres/sec.

[10] D
A [15] [30]
[15]
[45]
E [10]
O [25] [5] S
B
[15] [20]
[20] F
[10]
C
[20] [30]
[10]
G

On appelle réseau de transport tout graphe fini, sans boucle, avec une source (ou point de
départ) et un puits (ou point d’arrivée), où tout arc est valué par un entier positif c(u), nommé
capacité de l’arc.
Source = entrée, sommet sans prédécesseur (ou ajouté)
Puits = sortie, sommet sans successeur (ou ajouté)
On appelle flux de l’arc u la quantité (u) (entier naturel) telle que 0   (u)  c(u)

Loi de Kirchoff :   (u ) =   (u ) pour tout sommet x différent de l’entrée et de la sortie

uU x − uU x +
Où Ux- est l’ensemble des arcs incidents intérieurement à x et U x+ est l’ensemble des arcs
incidents extérieurement à x.
On appelle flot : flux émis par la source =   (u )
uU x 0 +

= flux recueillis par le puits =   (u )

uU x n −

M Gaye RO : Lic Pro 23

 Les cahiers du formateur

2.2) Procédure
1. Trouver un flot complet : flot dont tous les chemins menant de x0 à xn ont au moins un arc
saturé.

Exemple : 10 D
A 10 20
5
35
E 10
O 25 5 S
B
10 20
20 F
10
C
20 30
10
G

OCGXn : O  C  G  Xn CG = 10 saturé
20 10 30 OC = GXn =10

OCFXn : CF saturé puis OC saturé (CF=10, donc OC = 10+10=20)

OBFXn : O  B  F  Xn FXn = 10 saturé
25 15 10 OB = BF = 10
OBEXn : O  B  E  Xn BE = 5
15  5 10 OB = (10+)5=15, EXn = 5
OBDXn : O  B  D  Xn OB = (25+)10
 10 15  30 BD=DXn= 10
OAGXn : O  A  G  Xn AG = GXn = 20
45 20 (30-10)=20 OA = 20
OAEXn : O  A  E  Xn EXn= 5
25 15 10-5 OA = AE = 5
OADXn : O  A  D  Xn AD = 10
 20  10  20 OA = DXn = 10

(Selon la principe du bas vers le haut)

On a déterminé un flot complet dont la valeur est V() = 80 (mais n'est pas maximale).

2. Marquage : on va chercher si ce flot est maximal ou non.

▪ Marquer l’entrée du réseau : +O
▪ Marquer toute extrémité terminale J d’un arc non saturé (I, J) dont l’extrémité initiale I est
marquée. On écrira +I à côté de J.
▪ Marquer l’extrémité initiale K de tout arc (K, L) transportant un flot non nul dont l’extrémité
finale L est marquée. On écrira –L à côté de K

Si on n’arrive pas à marquer la sortie du réseau, le flot est maximal. Si on arrive à marquer la
sortie du réseau, le flot n’est pas maximal. Dans ce cas, il faut considérer une suite de sommets
marquées, formant une chaîne entre l’entrée et la sortie et améliorer le flot en augmentant le
flux des arcs joignant les sommets de la suite, en respectant la loi de Kirchoff.
▪ Recommencer tant qu’il sera nécessaire pour qu’on ne puisse plus marquer la sortie.

M Gaye RO : Lic Pro 24

 Les cahiers du formateur

Exemple :
+B
+O 10 D
A 10 20
5
35 +A +D
E 10
O 25 -E 5 S
B
+B
10 20
20 F
-F 10
C
20 30
10
G

On fait partir de O: 80 et sortir de S: 80. Comme le sommet S est marqué, le flot n’est pas
maximal. Isolons une chaîne de sommets marqués pour essayer d’augmenter le flot allant de O
à S.
+B
+O 10 D
A 10 20
5
35 +A +D
E 10
O 25 -E 5 S
B

En augmentant l’arc BD de 10 à 15, on augmentera DS de 20 à 25, mais il faut annuler le flot

entre B et E et donc pour équilibrer E, augmenter AE puis OA.
D’où voilà une meilleure solution :

+O D
A 15 25
+A
40 10
25 E 10
O S
B
10 20
20 F
10
C
20 30
10
G
Les antécédents par un arc nul ne peuvent pas être marqués. Les sommets marqués sont reliés
aux autres par des arcs saturés ou nuls.

M Gaye RO : Lic Pro 25

 Les cahiers du formateur

Section 3:Problème d’ordonnancement

Ordonnancement
Il s'agit de l'utilisation des graphes pour optimiser les enchaînements (le chemin critique dans
l'organisation des tâches).

Introduction
Un décideur a un projet à réaliser, il le décompose en macro-tâches, puis chacune de ces
tâches est décomposée en tâches élémentaires. Ces dernières sont articulées entre elles par des
contraintes :

Contraintes potentielles :
➢ Contraintes de succession : telle chose doit se faire complètement ou
partiellement avant une autre.
✓ la tâche i précède la tâche j = succession totale ;
✓ la tâche i doit être aux 2/3 commencée avant que j commence =
succession partielle
➢ Localisation temporelle : disponibilité dans le temps. Si par exemple, un
équipement n’est disponible qu’entre les instants t1 et t2
Formalisation :
Soit di : la durée de la tâche i données
dj : la durée de la tâche j
ti : la date de début de la tâche i inconnues
tj : la date de début de la tâche j
Contraintes : si i précède j, ti + di  tj  di  tj - ti
si 2/3 i précède j, ti + 2/3 di  tj  2/3 di  tj -ti
d’une manière générale,  ij di  tj – ti càd ij  tj - ti (où ij est une donnée)
▪ contraintes disjonctives : exclusion mutuelle car les tâhces ne peuvent pas se
faire en même temps (exemple : les tâches i et j utilisent une même ressource : une
seule machine, …). [ti, ti + di]  [tj, tj + dj] = 
▪ contraintes cumulatives : les moyens sont limités, en main d’œuvre, en
équipement, en budget

Pour illustrer une solution, on peut utiliser un diagramme de GANT :

charpentiers

couvreurs

plombiers

maçon

0 10 20 30 40 50

M Gaye RO : Lic Pro 26

 Les cahiers du formateur

Méthodes d’ordonnancement

Deux méthodes sont principalement utilisées pour résoudre les problèmes

d’ordonnancement à contraintes potentielles : les méthodes MPM (française) et PERT
(américaine). Leurs buts sont :
1. d’établir un ordonnancement, i.e. un calendrier si les contraintes sont compatibles en
déterminant pour chaque tâche la date ti de début de la tâche i
2. de minimiser la durée totale du projet.
3. d’énumérer les tâches critiques, (ce sont celles qui, si elles subissent un retard, décalent la
fin prévue du projet) et d’évaluer les marges des tâches non critiques.

2.1) Méthode MPM

MPM = méthode des Potentiels Métra, du Professeur B. Roy
On la représente grâce à un graphe G=(X,U) où les sommets représentent les tâches
(auxquelles on a ajouté une tâche de début  et une tâche de fin ) et les arcs traduisent les
contraintes.
Si deux sommets sont liés par un arc, cela signifie que l’opération associée à l’extrémité
initiale de l’arc doit être commencée pour que puisse débuter l’opération liée à l’extrémité
terminale de l’arc.
Succession de deux opérations : a de durée 4, b de durée inconnue, b
a
4
b ne pouvant débuter qu’une fois a achevée.

Si b ne peut débuter que deux unités de temps après le début de a, on représentera les deux
tâches ainsi :
a b
2

Ainsi, sur un graphe MPM, la valeur numérique associée à l’arc (i,j) est le délai minimum
après le début de la tâche i au bout duquel peut démarrer la tâche j.
Le sommet du graphe représente le début de la tâche a dans un graphe MPM.

a) Exemple des tâches du bâtiment

La construction d'un bâtiment nécessite les interventions des personnes suivantes:

Maçons-platriers: 1 mois 1m 2m
Couvreur: 1 mois 1m couvreur
Départ maçon 1m Fin
Electricien: 15 jours 15j 3 sem
Carreleur: 3 semaines électric. 1,5 m carrel. 2 m 1s

b) Exemple: travail de graphe

Dans cette organisation, certaines tâches ont de la marge, d'autres non. Le chemin critique
–C-F-G- ne doit pas connaître de retard car c'est lui qui impose sa durée. Cette méthode peut
être complétée par des tableaux (qui marcherait aussi avec la méthode PERT).

M Gaye RO : Lic Pro 27

 Les cahiers du formateur

Tâches Contraintes Durée

A Peut débuter 5 jours après l’origine 16 j
B Peut débuter dès l’origine 14 j
C Peut débuter 3 jours après l’origine 20 j
D Ne peut débuter que quand A et B sont finis 8j
E Quand B est fini 18 j
F Quand B et C sont finis 25 j
G Quand D, E, F sont finis 15 j
H Quand E est fini et que la moitié de C est réalisée 17 j
I Quand D, E, F sont finis 10 j

A 16 D 8 G
5 5 8 15
14 18

0 B 14 E 18 I 10 
3 14 25 17
25
C 20 18
F H
10

De plus en , t = 0, tA = 5, tB = 0, tC =3, tD = max (16+5, 14+0)=21, tE= max(14+0)=14,

tF= max(14+0, 20+3)=23, tG= max (tD+8, tE+18, tF+25)=max(21+8, 14+18, 23+25)=48,
tI= max (tD+8, tE+18, tF+25)=max(21+8, 14+18, 25+23)=48
tH= max (tE+18, tC+10) = 32
t = max(tG+15, tI+10, tH+17)= max(48+15, 48+10, 32+17)=63

Alors le chemin critique est  C F G , il y a trois tâches critiques, le projet durera au

minimum 63 jours.
t *= t,
tH* = max( 32, 63-17)= 46, la tâche H doit et peut commencer entre le 32ème jour et le 45ème j.
tI*= max (48, 63-10)=53
tG* = tG = 48, tF* = tF= 23 (ce sont des tâches critiques), tC* = tC
tE* = min (tG*-18, tI* - 18, tH* -18)=28
tD*= min (tG* - 8, tI*-8)= 40
tB* = min (tD* -14, tE* -14, tF* -14) = 9
tA* = min (tD* -16)= 26

On peut également calculer les dates au plus tôt et les dates au plus tard par les tableaux
suivants :
Dates au plus tôt :

0  5 A 0 B 3 C 21 D 14 E 23 F 48 G 32 H 48 I 63 
5 :0 0  :0 3  :0 16 A :5 14 B : 0 14 B:0 8 D : 21 10 C:3 8 D : 21 15 G : 48
14 B :0 20 C:3 18 E : 14 18 E : 14 18 E : 14 17 H : 32
25 F : 23 25 F : 23 10 I : 48
Chemin critique
Chaque colonne de ce tableau est constituée :
Date au plus tôt de Xi Nom du sommet : Xi
Durée de la tâche XjXi Prédécesseur Xj: date au plus tôt de Xj
On retrouve le chemin critique en repartant de  et en déterminant le chemin qui a permis
de trouver la date au plus tôt de ce sommet final.(en gras et souligné dans le tableau)

M Gaye RO : Lic Pro 28

 Les cahiers du formateur

Dates au plus tard :

 0 A 24 B 9 C 3 D 40 E 28 F 23 G 48 H 46 I 53  63
A: 5 D :40 16 D :40 14 F :23 20 G :48 8 G: 48 18 G: 48 25  :63 15  :63 17 : 63 10
B: 0 E :28 14 H :46 10 I :53 8 H: 46 18 I: 53 25
C :3 3 F :23 14 I: 53 18

On remplit ce tableau après le précédent en partant du sommet final  et de la date minimale

de fin du projet : 63, puis en remontant les calculs. Pour cela, dans chaque colonne de ce tableau,
on a inscrit :

Nom du sommet : Xi Date au plus tard de Xi

Successeur Xj: date au plus tard de Xj Durée de la tâche XiXj

2.2) Méthode PERT

PERT= Program Evaluation Research of Tascks

Dans cette méthode, on représente aussi les tâches et les contraintes qu’elles subissent à
travers un graphe G = (X, U), mais les sommets représentent des étapes de la réalisation du
projet et les arcs les tâches.

Notation : Numéro de l’étape k

Date au plus tard de l’étape k

Date au plus tôt de l’étape k

L’opération est donc représentée par un arc auquel on associe une valeur numérique, durée
de l’opération.
Les sommets sont les aboutissements des opérations, ou représentent la réalisation de
certaines étapes ou objectifs partiels du programme (opérations fictives parfois).
Si on veut représenter la succession de deux opérations a et b, a durant 4 unités de temps et
b 6, on tracera :
a(4) b(6) b ne peut débuter que quand a est achevé, mais il n’est pas obligé
1 2 3 de commencer immédiatement après. Le moment 1 est le
démarrage de a, l’instant 2 est l’achèvement de a et le moment
où b peut commencer, l’instant 3 est l’achèvement de b.

En revanche, si b peut commencer dès que deux unités de temps ont été consacrées à a, il
faut introduire un autre sommet :
a(2) a(4)
1 2 3

b(6)

M Gaye RO : Lic Pro 29

 Les cahiers du formateur

Pour le même exemple que plus haut, on obtient le graphe suivant :

A 8 D 9 G 10
21 40 8 48 48 15
5 24 16 63 63 8
1 3 5 0
5 I
0 0
10
B 3 E 7 12
0 0 14 14 23 32 46 63 63
18
2 4 6
0
3 0 H
4 C1 5 C2 6 F 17
3 3 10 13 13 10 23 23 25

7 11
0 32 46
Chemin critique

On retrouve que les tâches critiques sont C, F et G.

Marges pour l’étape 10 par exemple : il y a quatorze jours de marge entre la fin de l’opération
qui mène à 11 et le début de l’opération H pour ne pas retarder l’achèvement des travaux

2.3) Comparaison des deux méthodes

a) Opérations parallèles
Soient deux opérations b et c devant satisfaire aux conditions suivantes : s’effectuer en même
temps, succéder à une même opération a, précéder une opération d.
Les durées respectives de a, b, c,d sont : 3, 2, 5, 7.

PERT : MPM : b
2
a(3) c(5) d(7) 3
1 2 3 4
b(2) a d
b’(0) : opération
virtuelle
3 5
3’
On peut interchanger le rôle de b et c par c
symétrie.

Remarque : on ne peut pas tracer ce style de

graphe, car il ne serait pas simple :
a(3) c(5) d(7)
1 2 3 4

b(2)

M Gaye RO : Lic Pro 30

 Les cahiers du formateur

b) Opérations dépendantes et indépendantes

Soient a et b deux opérations de durée respectives 5 et 2 indépendantes, et c et d de durées
respectives 3 et 1 indépendantes, telles que c succède à a sans succéder à b et d succède à la fois
à a et à b.

PERT : MPM :
a(5) c(3)
1 3’ 4 a c
a’(0)
b(2) d(1)
2 3 5
2
b d
Attention : cette fois, c et d n’ont pas des
rôles symétriques

M Gaye RO : Lic Pro 31

 Les cahiers du formateur

c) Opérations composées (successions avec recouvrement)

Situation : certaines opérations peuvent débuter avant l’achèvement complet d’une opération :
Exemple : a dure 2 jours ; b, qui dure 7 jours, succède à a ; e, qui dure 2 jours, succède à b ; c,
qui dure 3 jours, peut débuter 1 jour après le début de b ; d ; qui dure 4 jours, peut débuter 3
jours après le début de b.

PERT :

Il faut fractionner l’opération en plusieurs sous-opérations successives :

a(2) b1(1) b2(2) b3(4) e(2)

1 2 3 5 7 8
c(3) d(4)

4 6

MPM :
deux solutions, l’une en fractionnant, l’autre non.
2 2 4
1 b2 b3 e
a b1
1 2

c d

M Gaye RO : Lic Pro 32