Institut Supérieur de Gestion et de Planification ISGP

Support de Cours du Module :

Méthodes Quantitatives de Gestion

Réalisé par : Djouadi Mohamed

Mai 2014

1
Introduction :

La Recherche opérationnelle est une science dont les fondements de bases et les premières
applications datent de la deuxième guerre mondiale. Elle englobe des problèmes résolus
mathématiquement à l’époque afin de répondre à certaines exigences des responsables
militaires. A la fin de la guerre, les scientifiques se sont retrouvé avec une armada de méthodes
qui permettent de résoudre beaucoup problèmes, c’est à partir de là qu’ils ont pensé à
développer cet acquis mais cette fois ci pour l’exploiter dans la vie quotidienne, en économie,
en industrie et la recherche scientifique.

La recherche opérationnelle en tant que science se partage en plusieurs filières suivant le type
d’applications, ainsi elle est composée de : la Théorie des graphes, l’optimisation dans les
réseaux, la programmation linéaire, la programmation non linéaire, l’optimisation combinatoire,
la modélisation, la Simulation et l’aide à la décision monocritère et le multicritère etc...

Dans ce cours nous allons essayer de présenter quelques domaines de la recherche

opérationnelle, nous commencerons dans un premier temps par la présentation des définitions de
bases de la théorie des graphes, afin de vous familiariser avec le Jargon de ce domaine, ensuite
nous entamerons la partie optimisation dans les réseaux dans laquelle on verra en détail les
problèmes de cheminements leurs applications et leurs résolutions. Ensuite on passera aux
principes de bases de la résolution des problèmes de flots, ces problèmes sont présentés par des
exemples avec lesquels nous avons simplifié leurs complexités. Et en fin on terminera ce cours
par les problèmes d’ordonnancement de projets, que nous avons étoffé avec beaucoup
d’exemples afin de rendre palpable les définitions théoriques présentées dans ce cours.

2
 Chapitre 1
Définitions de base de la théorie des graphes
Introduction :

La théorie des graphes permet de transcrire concrètement des faits en les modélisant à l'aide
d'objets mathématiques, afin de résoudre des problèmes tels :

- Les problèmes d’ordonnancement, qui ont pour but la recherche d’un ordre optimal des tâches
pour une réalisation complexe : il s’agit de trouver un ordre de réalisation des travaux, en
minimisant le temps total et le coût total ;

- Les emplois du temps et la répartition des salles ;

- Les problèmes d’affectations (organiser des équipes de travail pour qu’elles soient le plus
efficaces possibles) ;

- Les problèmes de maintenance (minimiser les stocks de pièces de rechange, ou les coûts dus à
l’arrêt des machines) ;

- Les problèmes de compétition et de concurrence ;

- Les problèmes de classification de produits, ou d’individus.

Le premier problème connu d’utilisation d’un graphe pour résoudre un problème est celui des «
7 ponts de Königsberg », résolu en 1735 par le mathématicien suisse Leonhard Euler :

La ville de Königsberg (Prusse orientale) comptait 7 ponts, disposés selon la figure ci-contre.

3
L’histoire veut que Léonard Euler, en visite dans cette ville, ait eu à résoudre le problème qui
préoccupait fortement ses habitants : Est-il possible de trouver un chemin qui emprunte une fois
et une seule chacun des sept ponts de la ville et revenir au point de départ? Pour cela, l’idée est
de commencer par traduire l’énoncé du problème par un schéma :

Chaque lieu de la ville est repéré par sa position géographique : N pour le nord de la ville ; S
pour le sud de la ville, O pour l’ouest et I pour île. Chaque pont sera alors représenté par un «
trait » reliant ces lieux entre eux.

Cette modélisation s’appelle un graphe : Qu’est-ce qu’un graphe ? C’est un ensemble de

sommets et de liens entre 2 sommets que l’on appelle arêtes.

La traduction du problème de départ en termes de propriétés du graphe est alors : «Peut-on

circuler sur le graphe à partir d’un sommet en empruntant une fois et une seule chaque arête ? ».
Mais la théorie des graphes a réellement pris son départ pendant la seconde guerre mondiale,
plus précisément en Angleterre en 1940, sous le nom d’ « Operation Research ». L’État Major
allié, qui devait accroître l’efficacité de ses opérations, en confia le travail au physicien Blackett.
Il s’agissait de rechercher la meilleure rotation des équipages dans les avions1, l’implantation
optimale des radars, plus tard l’organisation des convois transatlantiques…

Définitions de base.

1) Généralités sur les graphes

Définition1: Un Graphe est un ensemble de points (appelés Sommets du graphe)

éventuellement reliés par un ou plusieurs segment(s) appelés Arêtes.

Définition2: Un modèle mathématique est une traduction de la réalité pour pouvoir lui appliquer
les outils, les techniques et les théories mathématiques, puis généralement, en sens inverse, la
traduction des résultats mathématiques obtenus en prédictions ou opérations dans le monde réel.

Ainsi la théorie des graphes s’intéresse aux modèles mathématiques définit par des graphes
selon la définition1.

Sommet : Un sommet est un 'noeud' du graphe. C'est l'extrémité d'une arête.

Arrête : On désigne une arête par la pair de sommets qu’elle relie : {x,y} ou [x y], et on parle
de l’arête d’extrémités x et y; les sommets x et y sont alors dit adjacents, et l’arête et dite
incidente aux sommets x et y.

4
Graphe : Un graphe G est définit par un couple d’ensembles, le premier représente l’ensemble
des sommets X et le second représente l’ensemble des arêtes E. Et on écrit alors G=(X,E), Le
cardinal de X =n et s’appel l’ordre du graphe G.

Exemple : On s’intéresse à un tournoi de football. Supposant que nous voulons organiser un

tournoi de football avec 05 équipes. Nous cherchons à voir quel est le nombre de matchs de
football à programmer ?

Dans un premier temps en commence par la modélisation mathématiques et la on suppose que

les sommets représentent les différentes équipes et les arêtes représentent les rencontres de
football. Donc il existe un arête relient deux sommets (x,y)∈X2.

X={E1, E2, E3, E4, E5}

E={(E1,E2), (E1,E3), (E1,E4), (E1,E5), (E2,E3), (E2,E4), (E2,E5), (E3,E4), (E3,E5)}

Le graphe correspondant est :

E1

E5 E2

E4 E3

G=(X,E)

Degré d’un sommet : On appel degré d’un sommet x, dans un graphe, G noté d(x), le nombre
d’arêtes de G ayant x comme extrémité. Ou bien on dit que c’est le nombre d’arêtes incidentes
au sommet x.

Dans le graphe précédant tous les sommets ont le même degré est égal à 4.

Remarque : Pour un graphe G d’ordre n ; le degré d’un sommet est un entier compris entre 0 et
n-1.

Graphe régulier : Un graphe G est dit régulier de degré r si tous les sommets sont de degré r. Le
graphe précédant est régulier de degré 5.

5
Théorème1 : Dans un graphe quelconque on à toujours la somme des degrés est égale à deux
fois le nombre d’arêtes m : Σd(x)=2×m ∀x∈X.

Proposition1 : Dans un graphe le nombre de sommets de degré impair est toujours pair.

Proposition 2 : Soit G=(X,E) un graphe d’ordre n >=2. Alors ∃ au moins deux sommets
différents qui ont le même degré.

Graphe complet : Un graphe G est dit complet si et seulement si tous les sommets sont reliés
deux à deux.

Une boucle : est une arête dont les deux extrémités coïncident.

Arêtes parallèles : Soit G un graphe. On appel arêtes parallèle des arêtes différentes de G ayant
les mêmes extrémités.

Multi graphe : est un graphe admettant des arêtes parallèles.

Graphe simple : Soit G=(X,E) un graphe. G est simple s’il n’admet pas de boucles et d’arcs
parallèles.

E1
E1

E5 E2
E5 E2

E4 E3
E4 E3

Exemple de graphe non Simple Exemple de graphe Simple

Chaine: Une chaine est une suite fini de sommets et d’arêtes Ch=[X0,e0,X1,e1X2,….., Xm-1,em-
1,Xm].

Tel que : X0 et Xm représentent les extrémités de la chaine Ch, et m sa longueur l(ch)=m.

Une chaine simple est une chaine dont toutes les arêtes sont distinctes.

Une chaine élémentaire est une chaine dont tous les sommets sont distincts.

6
Définition: une chaîne eulérienne est une chaîne passant une et une seule fois par toutes les
arêtes du graphe. Si le sommet initial et le sommet final sont confondus, on parle alors de cycle
eulérien.

Définition : Un graphe est dit eulérien s’il admet un chemin ou un cycle eulérien.

Théorème d’Euler : Un graphe simple connexe est eulérien si et seulement si pour tout sommet
x, d(x) est pair.

Exemple :

x1
e4 e1

x5 x2

e3
e2

x4 x3

G=(X,E)
C1=[x1e1x2e2x3e3x5] est une chaine de longueur 3 avec x1 et x5 comme extrémités.

Par contre : C2=[x1e1x2e2x3e3x5e4x1] est appelé un cycle.

Cycle : Un cycle est une chaine fermée, dont toutes les arêtes sont distinctes.

Graphe connexe : Un graphe G est dit connexe, ssi, ∀(x1,x2)∈X, ∃ une chaine reliant x1 à x2.

Sous Graphe : Soit G = (X, E) un graphe, pour un sous-ensemble de sommets A inclus dans X,
le sous-graphe de G induit par A est le graphe G = (A, E(A)) dont l'ensemble des sommets est A
et l'ensemble des arêtes E(A) est formé de toutes les arêtes de G ayant leurs deux extrémités
dans A. Autrement dit, on obtient G' en enlevant un ou plusieurs sommets au graphe G, ainsi
que toutes les arêtes incidentes à ces sommets.

Graphe Partiel : Soit G = (X, E) un graphe. Le graphe G' = (X, E') est un graphe partiel de G,
si E' est inclus dans E. Autrement dit, on obtient G' en enlevant une ou plusieurs arêtes au
graphe G tout en gardant le même ensemble de sommet X.

Remarques : Un graphe partiel d'un sous-graphe est un sous-graphe partiel de G.

Une clique : Une clique un sous-graphe complet de G.

Stable : Un stable un sous-graphe de G sans arêtes.

7
Exemples :

Sous-graphe partiel de
Graphe partiel de G Sous-graphe de G
G

X'=X X'={x1, x3, x4, x5}

X'={x1, x2, x3, x4}
E'={e1, e4, e5} E'={e3, e4, e5}
E'={e1, e4}
Le graphe G

Soit G=(X, E)
X={x1, x2, x3, x4,
x5}
E={e1=(x1,x2),
e2=(x2,x3),
e3=(x1,x3),
e4=(x3,x4),
e5=(x3,x5)}
Une clique de G Un stable de G

X'={x1,x2,x3} X'={x1,x4,x5}
E'={e1, e2, e3} E'={}

Graphe orienté : En donnant un sens aux arêtes d'un graphe, on obtient un graphe orienté. Dans
ce cas l’ensemble des sommets X reste le même, mais l’ensemble des arêtes E sera appelé
l’ensemble des arcs U qui est défini par des paires ordonnées de sommets, car l’orientation des
arcs est importante. Ainsi dans le cas non orienté l’arête e1=[x1 x2] est la même que l’arête
e1=[x2 x1], par contre, dans le cas orienté l’arc u1=(x1,x2) est différent de l’arc u2=(x2,x1).
x1
Exemple : u5 u1

G=(X,U) est graphe orienté x5 x2

u3
u2

x4 x3

G=(X,U)

8
Chemin : Dans un graphe orienté, un chemin d'origine x et d'extrémité y est défini par une suite
finie d'arcs consécutifs empruntés dans le bon sens, reliant x à y. La notion correspondante dans
les graphes non orientés est celle de chaîne.

Un chemin élémentaire est un chemin ne passant pas deux fois par un même sommet, c'est-à-
dire dont tous les sommets sont distincts.

Un chemin simple est un chemin ne passant pas deux fois par un même arc, c'est-à-dire dont
tous les arcs sont distincts.

La longueur d'un chemin est le nombre d'arcs le constituant, ou bien, dans le cas d'un graphe
pondéré, la somme des poids des arêtes.

Circuit : Un circuit est un chemin dont les deux extrémités sont identiques. Si le chemin est
élémentaire, c'est-à-dire ne passe pas deux fois par un même sommet, on parle de circuit
élémentaire. Dans un circuit élémentaire, le degré des sommets est deux. Dans les graphes
pondérés, le poids d'un circuit est la somme des poids des arcs qu'il contient. Si cette somme est
négative, on parle de circuit absorbant.

Définition : Un graphe orienté est dit fortement connexe ssi il réalise la relation R suivante :
pour tout couple de sommets (xi,xj)∈X2 , ∃ un chemin permettant de joindre xi à xj et un autre
chemin permettant de joindre xj à xi dans G.

Nous pouvons démontrer facilement que la relation R est une relation d’équivalence, ainsi elle
admet des classes d’équivalences. Ces classes sont appelées des composantes fortement
connexes.

Remarque :

1/On ne parle pas de forte connexité dans le cas non orienté.

2/ il existe des algorithmes permettant de vérifier si un graphe est fortement connexe ou pas.

3/ Un graphe G est fortement connexe s’il admet une seule composante fortement connexe. En
d’autres termes un graphe est fortement connexe si il admet un circuit passant par tous les
sommets de G.

9
Exemple :

G1 n’est pas fortement connexe car il existe un chemin entre x4 et x3 par contre il n’existe pas de
chemin reliant x3 et x4.

La composante {x1, x2, x3, x5} est une composante fortement connexe.

x1

x5 x2

x4 x3

G1=(X,U)
Graphe réduit :

G : graphe orienté admettant p composantes fortement connexes : C1, C2, …, Cp

On définit le graphe réduit de G (noté GR) par :

GR=(XR,UR) avec : XR={C1,C2,…,Cp} et (Ci ,Cj) ∈ UR si Il existe au moins un arc dans G

ayant son extrémité initiale dans la composante fortement connexe Ci et son extrémité terminale
dans la composante fortement connexe Cj.

10
Représentation des graphes sur machines

Matrice d’adjacence sommets-sommets :

Soit G = (X,E) un graphe ayant n sommets. On défini la matrice d’adjacence M associée, dont
les lignes et les colonnes représentent les sommets de G, par :

M = mij i,j = 1,…, n tel que : mij = Nombre d’arêtes reliant xi à xj. Cette matrice est appelée
Matrice d’adjacence sommet-sommet.

Exemple : La matrice d’adjacence de l’exemple suivant est:

X1 X2 X3 X 4 X5

X1 1 1 0 1 0 x1

X2 1 0 1 0 0
x5 x2
X3 0 1 0 1 0
M=
X4 1 0 1 0 2

X5 0 0 0 2 0
x4 x3

Exemple de graphe non Simple

Remarque : Une boucle est toujours comptabilisée deux fois.

Matrice d’incidence sommets-arêtes (sommets-arcs) :

Soit G = (X,E) un graphe ayant n sommets. On défini la matrice d’incidence B associée, dont
les lignes et les colonnes représentent les sommets et les arêtes de G respectivement, par :

B = bij i= 1,…,n, j= 1,…,m tel que :

Cette matrice est appelée Matrice d’incidence sommet-arête.

Remarque : Une boucle est représentée automatiquement par le chiffre 2.

11
Dictionnaire des successeurs: Dans cette représentation, on définit le graphe par le détail des
successeurs de chaque sommet.

Dictionnaire des prédécesseurs: Dans cette représentation, on définit le graphe par le détail des
prédécesseurs de chaque sommet.

12
13
 Chapitre 2
Cheminement dans les graphes
Graphe pondéré : On appelle graphe pondéré un graphe tel que, à chaque arête e est associé un
poids Pe. Les applications des graphes pondérés sont nombreuses : cartes routières avec des
indications de durées, de tarifs ou de distances portées sur des routes entre deux lieux, par
exemple.
Réseau : On appel réseau un graphe pondéré ayant un seul sommet S avec d-g(S)=0 appelé
source et un seul sommet P avec d+g(P)=0 appelé puit.
Remarque : Dans le cas ou on a un graphe pondéré avec plusieurs sommets sources xi et
plusieurs sommets puits yi, alors il suffit d’ajouter deux sommets fictifs S et P tels que : S sera
relié à tous les sommets xi et tous les sommets yi seront reliés à P. les pondérations des arcs
fictifs ajoutés seront égales à 0 où l’infini ( ) suivant le sens des pondérations du graphe initial.
Chemin: Un chemin Ch est une suite d’arcs adjacents parcouru dans le même sens. La longueur
de ce chemin l(Ch) peut être définit de deux manières différentes:
1/ La longueur en termes d’arcs, et la on donne le nombre d’arcs constituants ce chemin.
l(Ch)=nombre d’arcs de ch.
2/ La longueur en termes de pondérations, et la on donne la somme des pondérations des
arcs constituants ce chemin.l(Ch)= .
Circuit : Un circuit est un chemin simple dont les deux extrémités coïncident. Ainsi on défini
la longueur d’un circuit de la même manière, par la longueur en terme d’arcs et la longueur en
termes de pondérations.
Circuit absorbant : Un circuit C est dit absorbant ssi, .
Plus court chemin : On appel plus court chemin dans un réseau R, le chemin reliant S à P dans
R, ayant la somme des pondérations minimales de tous les chemins reliant S à P dans R.
Le Problème du plus court chemin : Le problème du plus court chemin est un problème ancien,
présent dans de nombreux domaines (trafics autoroutiers, ferroviaires, maritimes, investissement
et gestion des stocks, optimisation d’un réseau, intelligence artificielle, etc…).
Le problème est simple : Comment, en partant d’un point, arriver à un autre point en faisant le
moins de chemin possible ?
Pour vous aider, prenons un exemple : Une voiture partant de Paris souhaite se rendre à
Toulouse. Mais l’autoroute entre Paris et Toulouse est bouchée. Le conducteur aimerait savoir
si, en passant par Bordeaux, il mettra plus ou moins de temps que pour aller à Toulouse par

14
l’autoroute. Sachant que le conducteur mettra 7 heures en passant par l’autoroute, et qu’il mettra
5 heures pour aller à Bordeaux, et 3 heures pour relier Bordeaux à Toulouse. Le graphe ci-
dessous résume le problème.

Chaque arc possède une pondération représentant le temps nécessaire de déplacement d’un
sommet vers un autre. On dit que ce graphe est un graphe « orienté », car les arcs ont un sens.
Pour déterminer le plus court chemin entre Paris et Toulouse, il suffit d’additionner les
longueurs d’arcs des différents passages pour aller de Paris à Toulouse, et de les comparer. Ici,
on a l (P => T) = 7 et l (P => B) + l (B => T) = 5 + 3 = 8
On peut donc voir que l’automobiliste ferait mieux de passer par l’autoroute Paris-Toulouse,
plutôt que de faire un détour par Bordeaux, où il perdrait une heure !
Existence un plus court chemin : Soit R=(X,U,d) un réseau, on dit que R admet un plus court
chemin, si et seulement si, R n’admet pas de circuit absorbant.
Exemple :
Dans le graphe ci-dessous, le plus court chemin n’existe pas, car ce graphe admet un circuit
absorbant (3,4,5,6,3). La somme des pondérations de ce circuit est égale à (-3), à chaque fois
quand fait un passage sur ce circuit absorbant la valeur du plus court chemin diminue jusqu’a -
∞. 1
5 7 9
7
2 3

4 3

6 4

‐8 ‐2
5
Propriétés des plus courts chemins
Propriété1 : Tout sous-chemin d’un plus court chemin est un plus court chemin.

15
Propriété2 : S’il existe un plus court chemin entre deux sommets x et y, alors il existe un plus
court chemin élémentaire entre x et y.
Il existe plusieurs algorithmes de recherche de plus cours chemin, on peut citer à titre
d’exemple : l’algorithme de Bellmann, l’algorithme de Disjktra, l’algorithme de Bellmann-
Ford…etc.
Algorithmes de recherche de plus court chemin :
1/ Algorithme de Bellman :
L’algorithme de Bellman s’applique sur les graphes (réseaux) sans circuits, avec des
pondérations quelconques. Ainsi nous devons assurer l’inexistence de circuits dans le graphe en
question, pour cela nous décrivons dans ce qui suit un algorithme simple permettant de vérifier
si un graphe G est sans circuits ou non. L’algorithme s’appel algorithme de mise à niveau.
1.1. Algorithme de mise à niveau :
Le principe de cette algorithme est simple, il s’agit de classer les sommets du graphe G par
niveau ou par rang, si on arrive à le faire alors le graphe est sans circuit, sinon on sera
bloquer au niveau du circuit. L’algorithme commence par chercher tous les sommets x de G
ayant les dg-(x)=0 (càd, les sommets sans successeurs) et les mettres dans le même niveau k,
ensuite il faut supprimer tous les arcs sortants des sommets x du niveau k; et refaire la même
chose càd, chercher les nouveaux sommets ayant les dg-(x)=0, cette fois-ci on va les mettre
au niveau k+1 et ainsi de suite, si on arrive à classé tous les sommets de G donc le graphe est
sans circuit, par contre, si on bloque quelque part dans G, cela veut dire que le graphe
contient un circuit.
Algorithme mise à niveau
1- Soit un graphe quelconque G=(X,U), et k=1. V=X.
2- Choisir tous les sommets x n’ayant aucun prédécesseurs (c à d dg-(x)=0).
Si ses sommets existent alors les mettre
dans le niveau k, N(k)=N(k)∪{x} et V=V−{x}.
Si non Si V=∅ alors le graphe est sans circuit
Si non le graphe contient un circuit.
3- Supprimer tous les arcs sortants de tous les sommets du niveau k. Mettre k=k+1 et aller à
(2).
Exemple1:
Soit le graphe suivant, contient il un circuit ?

16
 1 6 3 7

2 4
8

Appliquons l’algorithme, nous remarquons que les deux sommets 1 et 8 n’ont pas de
prédécesseurs, car dg-(1)=0 et dg-(8)=0. Ainsi : N(1)={1,8}.
On va supprimer tous les arcs sortant de 1 et 8, ont aura ainsi le graphe suivant :

1 6 3 7

2 4
8

A cette étape nous constatons qu’il n’ya que les sommets 4,5 et 6 ayants dg-(4)=0, dg-
(5)=0 et dg-(6)=0. Ainsi on aura : N(2)={4,5,6}, de la même manière on va supprimer les
arcs sortant de 4,5 et 6, on aura le graphe suivant :

1 6 3 7

2 4
8

A cette étape c’est le sommet 2 qui n’a pas de prédécesseurs, donc : N(3)={2}. De la même
manière on aura le graphe suivant :

1 6 3 7

2 4
8

5
De la même manière on aura N(4)=3 et N(5)=7. Puis que nous avons réussi à classer tous
les sommets de G, alors G n’admet pas de circuit. Et le graphe mis à niveau aura l’allure
suivante:

17
 4

1
2 3 7

Niveau 1 Niveau 2 Niveau 3 Niveau 4 Niveau 5

Exemple2 :
Soit le graphe suivant, admet il un circuit ?

1 6 3 7

2 4
8

Appliquons l’algorithme : V=X={1,2,3,4,5,6,7,8}

Dans ce graphe nous remarquons que : dg-(1)=0 et dg-(8)=0 ce qui veut dire que, le niveau 1
est égale à : N(1)={1,8}, d’où le nouveau V=V-{1,8}={2,3,4,5,6,7}. Ensuite d’après
l’algorithme de mis à niveau, en supprimant les arcs sortant de N(1), on aura le graphe
suivant:
1 6 3 7

2 4
8

Et le V={2,3,4,5,6,7} et non vide et il n’existe aucun sommet x avec les dg-(x)=0, donc ce
graphe contient un circuit.

18
1.2 Algorithme de Bellman :
L'algorithme de Bellman est un algorithme de programmation dynamique qui permet de trouver
des plus courts chemins, dans un graphe G orienté pondéré (accepte même les valeurs négatives)
sans circuit, depuis un sommet source donné. Contrairement à l'algorithme de Dijkstra, qui ne
peut être utilisé dans un graphe avec circuit et tous les arcs ont des poids positifs ou nuls.
Définition : On appel π(x), le plus court chemin du sommet S source du graphe G, jusqu’à x.
Le principe de cet algorithme est simple, premièrement on initialise π(S) à 0, et les autres
sommets de G à +∞, ie. π(x)= +∞ ∀x∈X. Ensuite on prend les sommets dans l’ordre
topologique, cet ordre peut être déduit à partir de l’algorithme de mise à niveau présenté ci-
dessus. Ce choix nous permettra de ne choisir que les sommets x ayant yi comme prédécesseurs
tel que π(yi)≠+∞, ie. Que les plus cours chemins jusqu’à yi sont déjà calculés.
Soit x un sommet pour lequel on va calculer π(x), et soit Y={ yi, i=1..p} l’ensemble des
prédécesseurs direct de x. Une seule condition doit être respectée c’est que π(yi) sont déjà
calculé ∀i, i=1..p. De la nous calculons π(x) par la formule suivante :
π(x)=min(π(yi)+d(yi,x)) ∀i, i=1..p
Tel que : d(yi,x) représente la pondération de l’arc (yi,x).
Algorithme
Soit R un réseau ayant une source S et un puit P.
1. Initialiser π(S)=0 et π(x)= +∞ ∀ x∈X. T=∅.
2. Choisir les sommets x ayant seulement S pour prédécesseurs, et calculer π(x)=
π(S)+d(S,x). T=T∪{x}.
3. Tantque (X≠T)
Faire
Choisir un sommet Z de X ayant pour Wi prédécesseurs, tel que π(Wi) sont déjà calculé.
π(Z)=min(π(Wi)+d(Wi,Z) pour tous Wi prédécesseurs de Z.
T=T∪{Z}.
Fait.
Fin de l’algorithme

Exemple :
On considère le graphe orienté G = (X, U) ci-dessous pondéré par des longueurs d’arcs.
On cherche à déterminer les plus courts chemins de a à tout autre sommet.

19
On peut appliquer l’algorithme de Bellman parce que le graphe est sans circuit, ce qu’on peut
vérifier en effectuant la numérotation topologique (la mise à niveau du graphe) qui a été fait ci-
dessous. Les numéros topologiques sont encadrés.
Après avoir posé distance(a) = 0, on calcule les distances par numéros topologiques croissants
en appliquant la formule :
distance(x) = MIN prédécesseurs de x (distance(y)+ longueur(y,x)) .
2. Algorithme de Dijsktra :
L’algorithme de Dijkstra est un autre algorithme de recherche de distance et de plus court
chemin. Il est plus efficace que Bellman, mais ne fonctionne que dans le cas où toutes les
pondérations des arcs sont positives.
Principe :
On construit petit à petit, à partir de {S}, un ensemble M de sommets marqués. Pour tout
sommet marqué x, l’estimation d(x) est égale à la distance d(S,x).
A chaque étape, on sélectionne un sommet non marqué y dont la distance estimé d(y) est la plus
petite parmi tous les sommets non marqué. On marque alors y (on rajoute y à M), puis on met à
jour à partir de y les distances estimées des successeurs non marqués de y.
On recommence, jusqu’à épuisement des sommets non marqués. L’algorithme de Dijkstra
permet de trouver une chaîne de longueur minimale entre deux sommets d’un graphe pondéré
orienté ou non.

20
Algorithme de Disjktra :
Initialisation de l'algorithme :
Étape 1 : On affecte le poids 0 au sommet origine (S) et on attribue provisoirement un poids ∞
aux autres sommets. Répéter les opérations suivantes tant que le sommet de sortie (P) n'est pas
affecté d'un poids définitif.
Étape 2 : Parmi les sommets dont le poids n'est pas définitivement fixé, choisir le sommet x de
poids p minimal. Marquer définitivement ce sommet x affecté du poids p(x).
Étape 3 : Pour tous les sommets y qui ne sont pas définitivement marqués, adjacents au dernier
sommet fixé x :
3.1 Calculer la somme som du poids de x et du poids de l'arête reliant x à y.
3.2 Si la somme som est inférieure au poids provisoirement affecté au sommet y, affecter
provisoirement à y le nouveau poids som et indiquer entre parenthèses le sommet x pour
se souvenir de sa provenance.
Quand le sommet P est définitivement marqué, le plus court chemin de S à P s'obtient en
écrivant de gauche à droite le parcours en partant de la fin P.

Exemple :
Dans le graphe orienté, pondéré G = (X,U) ci-dessous par des longueurs d’arcs, utiliser
l’algorithme de Dijkstra pour déterminer une arborescence de plus cours chemins depuis le
sommet a jusqu’à tous les autres sommets.
On pourra utiliser un tableau pour indiquer les valeurs initiales des champs d (ou distance) et
père (ou antérieur) puis, pour chaque étape, les actualisations de ces valeurs effectuées par
l’algorithme; on indiquera aussi les pivots successifs.
Par manque de temps, on peut aussi indiquer la succession des pivots et ajouter, à côté de
chaque sommet, les valeurs successives obtenues pour les champs d (ou dist) et père (ou
ant); le graphe de cet exercice est un peu gros pour permettre cela. On surlignera les arcs d’une
arborescence de plus courts chemins.

21
On applique l’algorithme de Dijkstra en initialisant puis en actualisant à chaque étape les valeurs
de d (ou distance) et père (ou antérieur) décrites dans l’algorithme. Une arborescence de plus
courts chemins à partir de a est indiquée ci-dessous.

22
3. Algorithme de Ford-Bellamn
L'algorithme de Bellman-Ford (Bell-End-Ford) (Richard Bellman, Samuel End et Lester Ford)
est un algorithme de programmation dynamique qui permet de trouver des plus courts chemins,
depuis un sommet source donné, dans un graphe orienté pondéré. Contrairement à l'algorithme
de Dijkstra, qui ne peut être utilisé que lorsque tous les arcs ont des poids positifs ou nuls,
l'algorithme de Bellman-Ford autorise la présence de certains arcs de poids négatif et permet de
détecter l'existence d'un circuit absorbant, s’il n’en existe pas, l’algorithme donne les plus courts
chemins ainsi que leurs poids.
Les notations sont les suivantes : π(v) contient le prédécesseur de v sur le chemin (NIL s’il n’y
en a pas), δ(u,v) est le poids du plus court chemin de u vers v (∞ s’il n’existe pas), d[v] est une
variable qui est une borne supérieure du poids du plus court chemin de s vers v.
Algorthme Ford-Bellman
Step1: pour tout sommet x∈X faire
Step 2: d[x]=∞ et π[x]=NIL.
Step 3: d[S]=0
Step 4: pour i=1 à |X|-1 faire
Step 5: pour tout arc (x,y)∈U faire

23
Step 6: si d[y]>d[x]+ w(x,y) alors
Step 7: d[y]=d[x] + w(x,y) ; π[y]=x.
Step 8: pour tout arc (x,y)∈U faire // détection des circuits négatifs
Step 9: si d[y] > d[x] + w(x,y) alors retourner Faux
Step 10: retourner Vrai
Fin algorithme

24
 Chapitre 3
Arbres et Arborescences
Définition : Un arbre est un graphe connexe sans cycle.

Théorème : Le nombre d’arêtes dans un arbre est toujours égal au nombre de sommets moins 1.
m = n-1.

Soit A un graphe à n sommets.

Théorème : Les propriétés suivantes sont équivalentes.

(a) A est un arbre.
(b) A ne contient aucun cycle et possède n-1 arêtes.
(c) A est connexe et possède n-1 arêtes.
(d) A est connexe, et chaque arête est un isthme.
(e) Deux sommets quelconques de A sont reliés par un unique chemin.
(f) A est acyclique mais l'addition d'une quelconque nouvelle arête crée exactement un cycle.

Arbres couvrant de poids minimum :

Introduction : Un réseau comporte des machines A, B, C, D, et E qui doivent pouvoir
communiquer entre elles. Les liaisons envisagées sont représentées par le graphe suivant (les
arêtes sont étiquetées par la distance entre les machines):

Question : Comment câbler le réseau à moindre coût ?

Réponse : Il s'agit d'enlever des arêtes au graphe de façon qu'il reste connexe, et que la somme
des pondérations des arêtes soit la plus petite possible. Remarquons que le graphe partiel
recherché est sans cycle (pourquoi ?)

Ce problème se pose, par exemple, lorsqu'on désire relier n villes par un réseau routier de coût
minimum. Les sommets du graphe représentent les villes, les arêtes, les tronçons qu'il est
possible de construire et les poids des arêtes correspondent aux coûts de construction du tronçon
correspondant.

Le problème est ramené au problème suivant :

25
Définition : Le problème de l'arbre recouvrant de poids minimal est celui qui consiste à
déterminer un arbre qui soit un graphe partiel d’un graphe G simple connexe et dont le poids
total est minimal

Exemple de solutions sur le graphe ci-dessus

Algorithme de Kruskal

La stratégie de cet algorithme consiste à construire l’arbre en question comme suit : on part
d’une solution vide. On choisit, à chaque fois, une arête de G de poids minimum et qui ne crée
pas de cycle. Soit E l'ensemble des sommets de G. On utilisera un ensemble d'arêtes T qui sera
en sortie l'arbre couvrant minimal et un ensemble d'arêtes F qui représentera les arêtes qui
peuvent être choisies.

Exemple 1:

Les différentes étapes pour construire l’arbre T

Exemple 2 : Reprenons le graphe ci-dessus, et construisons l’arbre recouvrant de poids

minimum à l’aide de l’algorithme de Kruskal.

Poids Arêtes
2 B-C
2 D-E
3 C-D
4 B-D éliminée
4 A-E
5 A-B éliminée
6 B-E éliminée
Complexité : Si les arêtes sont classées par ordre de coût croissant, ce qui peut se faire en
O (e log e) ; e étant le nombre d’arêtes dans le graphe, il reste à évaluer la complexité de test
d’acyclicité. Si les composantes connexes du graphe T sont connues, ce test se réduit à vérifier
que les extrémités de l’arête choisie sont dans eux composantes connexes distinctes. Il reste
alors à gérer ces composantes connexes de manière à fusionner deux composantes connexes
reliées par l’arête choisie. Cela peut se faire par la technique de fusion rapide en O (e log n) -
comment? – L’algorithme de Kruskal a une complexité de l’ordre O (e × max(log n, log e))

26
Algorithme de Prim

L’algorithme de Kruskal veille à maintenir la propriété d’acyclicité d’un arbre alors que
l’algorithme Prim se base sur la connexité d’un arbre. L’algorithme Prim fait pousser un arbre
couvrant minimal en ajoutant au sous-arbre T déjà construit une nouvelle branche parmi les
arêtes de poids minimal joignant un sommet de T à un sommet qui n’est pas dans ce dernier.
L’algorithme s’arrête lorsque tous les sommets du graphe sont dans T.
Soit X l’ensemble de sommets du graphe de départ G. On utilisera un ensemble d’arêtes qui
sera l’arbre recouvrant en question, et S un ensemble qui contiendra les sommets de T.

Les différentes étapes pour construire l’arbre T

Codage de Prüfer :
Le codage de Prüfer permet de représenter un arbre T d’ordre n avec un code qui est une suite de
nombre de taille égale à n-2.
Algorithme Codage de Prüfer
Soit T un arbre d’ordre n.
Soit S le codage de T. S=∅.
Tant que (n>2)
Faire
1/ Choisir dans T la feuille v ayant le plus petit indice.
2/ Ajouter dans S le seul sommet x adjacent à v. S=S∪{x}.
3/ Supprimer de T le sommet v ainsi que l’arête correspondante. n=n-1.
Fait.
Exemple :
Donner le codage de Prüfer pour l’arbre suivant :

S={5,5,2,1,4,1}

Arbre T
Algorithme Décodage de Prüfer
Soient S un codage de Prüfer de taille n-2 et I={1,2,…,n}.

27
Tant que (S≠∅) et (|I|>2)
Faire
1/ Trouver k le petit élément de I qui n’appartient pas à S.
2/ Relier k au premier élément j dans S.
3/ I=I−{k} et S=S−{j}.
Fait
Il faut relier par une arête les deux derniers sommets restant dans I.

28
 Chapitre 4
Programmation Linéaire
1. Introduction
Un programme linéaire est un problème dans lequel on est amené à maximiser (ou minimiser)
une application linéaire, appelée fonction d'objectif ou fonction économique, sur un ensemble
d'équations et/ou d'inéquations linéaires, dites contraintes. Autrement dit, la programmation
linéaire est une branche des mathématiques qui a pour but de résoudre des problèmes
d'optimisation linéaire de type

Les coefficients et bi sont des réels fixés et les xj sont des variables réelles. Les
contraintes d'inégalités éventuelles sont toutes larges et non strictes. Il se peut qu'une contrainte
d'inégalité soit de type '' ''. En multipliant chaque inégalité de type '' '' par (-1), on peut
supposer que toutes les contraintes d'inégalité sont de type '' ''.
2. Méthode graphique
Nous allons décrire la méthode graphique à travers trois exemples représentatifs, ayant chacun
deux variables structurelles. Le premier admet une et une seule solution optimale. Le deuxième
admet une infinité de solutions optimales. Par contre, le troisième exemple n'admet aucune
solution optimale.
La résolution d'un (PL) par la méthode graphique se fait selon une démarche commune, celle-ci
peut être résumée en quatre directives :
1. Schématiser le domaine réalisable dans un repère orthonormé.
2. Dans le même repère, représenter l'hyperplan . Noter que tout
hyperplan d'équation Z(x) = r, , est parallèle à .
3. Si le (PL) considéré est de type maximisation ( resp. minimisation), indiquer, par une
flèche, le sens de déplacement parallèle de qui fait augmenter ( resp. diminuer) r.
4. Déterminer la droite la plus éloignée (dans le sens de la flèche) de et qui
coupe le domaine réalisable . Tout point de est une solution optimale. Si
une telle droite n'existe pas, cela veut dire que l'optimum est infini.
Appliquons ce principe général sur l'exemple 1 défini dans le paragraphe précédent……

29
 3. Exemple
Une usine fabrique deux produits (A) et (B) à l'aide des matières premières I, II et III. Le
fonctionnement de l'usine est comme suit :
• 1 unité du produit (A) nécessite 2 unités de I et 1 unité de II.
• 1 unité du produit (B) nécessite 1 unité de I, 2 unités de II et 1 unité de III.
On suppose que l'usine dispose des matières premières I, II et III en quantités respectives 8, 7 et
3. Le profit dû à la fabrication d'une unité du produit (A) (resp. (B)) est égal à 4 (resp. 5) Dinars
L'objectif étant de maximiser le profit tout en respectant les contraintes sur la matière première.
4. Méthodes des sommets
Si on désigne respectivement par x1 et x2 les quantités vendues du produit (A) et (B), le gain
total vaut
Z(x1,x2) = 4x1 +5x2
D'autre part, la disponibilité en matières premières revient à exiger des quantités, utilisées pour
la fabrication de x1 et x2, qui soient inférieures aux quantités disponibles. Ces contraintes
s'expriment par les inégalités suivantes :

Bien entendu, les variables x1 et x2 doivent être positives. En conclusion, le problème de

maximisation du profit se traduit mathématiquement par un programme linéaire qui s'écrit sous
la forme :

Reprenons l'exemple

5. Représentation graphique
Exemple 1
Le domaine réalisable est schématisé en gris sur la Figure. Toute droite d'équation Z(x1, x2)
= r, où r est un réel fixé, est parallèle à la droite : Z(x1, x2) = 0. On constate aussi que tout

30
déplacement parallèle de dans le sens de la flèche (voir dessin ci-après) fait augmenter r.
Donc maximiser la fonction Z, tout en satisfaisant aux contraintes du problème, revient à
chercher la droite la plus éloignée (dans le sens de la flèche) de et qui coupe le domaine
réalisable. Du point de vue graphique, il s'agit de la droite passant par le point (3, 2) et
parallèle à . Ainsi, on peut conclure que le point (3, 2) est la seule solution optimale qui
donne une valeur maximale de la fonction d'objectif égale à Z(3, 2) = 22. Autrement dit, le
meilleur profit vaut 22DT obtenu en fabriquant 3 unités du produit (A) et 2 unités du produit
(B).

On considère le (PL) suivant :

Exemple 2
En considère maintenant le (PL) suivant :

Exemple 3
Le domaine réalisable est la partie non bornée représentée partiellement en gris sur la Figure.
Tout déplacement parallèle de dans le sens de la flèche (voir dessin ci-
après) fait augmenter r. Donc tout point de la demi-droite est optimal et la valeur
maximale de Z vaut Z(A) = Z(3,2) = 12 (voir dessin ci-après).

31
Le domaine réalisable associé à ce (PL) est la partie non bornée représentée partiellement en gris
dans la Figure. Dans le graphique, on observe que toute droite d'équation Z(x1, x2) = r,
avec , coupe le domaine réalisable. Donc, et par conséquent, le problème
n'admet aucune solution optimale (voir dessin ci-dessous).

6. Principe de l’algorithme du simplexe

La méthode des sommets est simple, elle se base sur la résolution des systèmes linéaires de
Cramer. Cependant, elle est dans la pratique inexploitable car le nombre de systèmes à résoudre
est en général trop important.
Néanmoins, la méthode des sommets est d'une utilité incontestable : la recherche de l'optimum
éventuel sur tout le domaine réalisable se ramène au calcul de l'optimum de la fonction
d'objectif restreinte à un sous ensemble fini. Ce résultat sera l'un des outils clé de la méthode du
simplexe.

Pour toute contrainte d'inégalité ( resp. contrainte de positivité ) d'un

(PL) donné, l'hyperplan associé ( resp. xi= 0) s'appelle hyperplan frontière .

Considérons un (PL) à p variables réelles. Un point A du domaine réalisable est
appelé sommet, s'il existe p hyperplans frontières dont l'intersection est réduite à A.

32
Théorème : Soit une application linéaire et un polyèdre de . Si Z admet son
optimum global en un point de , il est aussi atteint en un sommet de .
Sans nul doute, l'intérêt de ce théorème est immédiat :
L'optimum (que ce soit maximum ou minimum) d'un (PL), lorsqu'il existe, peut toujours
être réalisé sur un sommet.
La méthode des sommets pour la résolution d'un (PL), consiste donc à :
• déterminer tous les sommets du domaine réalisable,
• puis calculer la valeur de Z en chacun de ces sommets.
Le sommet doté de la meilleure valeur de Z serait une solution optimale. Une chose reste à
vérifier pour l'application de cette méthode : s'assurer tout d'abord que le (PL) considéré admet
bien une solution (i.e. l'optimum est fini). Cette condition est souvent difficile à vérifier.
Néanmoins, lorsque le domaine réalisable est borné, et par suite compact, l'existence d'une
solution optimale est certaine.

33
 Chapitre 5
Problème du Flot max
Le problème de flot maximal consiste à transporter la quantité maximale possible d’une origine
(source) à une destination (puits) données, sans dépasser les capacités des arcs.

Données : un graphe orienté G = (X,U), une capacité Cij > 0 pour tout arc (i,j)∈U, une source S
et un puits P.

Définition : Un flot dans le réseau est un vecteur d’entiers f = (fij) associés aux arcs tel que :

0 ≤ fij ≤ uij ∀ (i,j)∈U.

La valeur du flot est :

Algorithme de Ford-Fulkerson

Définition (Arcs-avant / arrière). Soit f un flot, et P un chemin dans le graphe non orienté
obtenu en remplaçant chaque arc de A par une arête. Un arc traversé dans P dans son orientation
originale est appelé arc-avant, un arc traversé dans l’autre sens est appelé arc-arrière.

Définition (Chaine augmentante) Si pour tout arc-avant (i, j) de P, fij < uij et pour tout arc-
arrière (i,j) de P, fji > 0, alors P est appelé chaîne augmentante.

Algorithme de Ford et Fulkerson

• Initialisation : f = 0.
• Alternance de deux phases :
1. Phase de marquage (recherche d’un chemin augmentant).
2. Phase d’augmentation (augmenter le flot sur le chemin trouvé en phase de marquage).
Ces deux phases sont répétées jusqu’au moment où il n’existe plus de chemin augmentant.

Phase 1 : (Saturation de tous les chemins)

• L’idée de cette phase l’algorithme : trouver un chemin augmentant et augmenter le flot
sur ce chemin.
• Définition1 : Un chemin est dit saturé s’il contient au moins un arc saturé.
• Définition2 : Un arc- avant (i,j) est dit saturé ssi Cij −fij =0.
1/ Choisir un chemin Ch non saturé.
2/ Calculer, v=min(Cu−fu), u∈ch.

34
3/ Calculer le nouveau flot de chaque arc u suivant la formule :
4/ Refaire les étapes précédentes jusqu’à saturé tous les chemins entre la source et le puits.

Phase 2 : (Saturation de toutes les chaînes)

• L’idée de cette phase l’algorithme : trouver une chaine augmentante et augmenter le flot
sur cette chaîne.
• Définition3 : Une chaine est dite saturée si elle contient au moins un arc-avant ou un arc-
arrière saturé.
• Définition4 : Un arc-arrière (i,j) est dit saturé ssi fij =0.
1/ Trouver une Chaîne Chn non saturée reliant le sommet source au sommet puits.
1.1 Si une telle chaîne existe, alors, aller à (2)
1.2 Sinon, arrêter l’algorithme et le flot actuel est un flot Smax.
2/ ∀ u un arc-avant, calculer d1=min(Cu−fu), u∈chn.
3/ ∀ r un arc-arrière, calculer d2=min(fr), r∈chn.
4/ Calculer : d=min(d1,d2)
5/ Calculer le nouveau flot de chaque arc suivant les formules suivantes et aller à (1) :
5.1 ∀ u un arc-avant, calculer :
5.2 ∀ r un arc-arrière, calculer :
Fin Algorithme.
Exemple : (Cet exemple est traité en cours, les étudiants sont tenus de porter la correction manuellement dans
cette partie).

35
Coupe minimale :
Définition : La coupe dans un graphe G = (X,U), est définie par le sous-ensemble non vide de
sommets Cp, est l’ensemble d’arcs noté δ+(Cp) sortant de Cp.
δ+(Cp) = {(i,j)∈X/ i∈Cp et j∈X−Cp}
• La coupe qui sépare S et P, i.e. telle que S∈Cp et P∈ X−CP.
• La capacité d’une coupe est la somme des capacités de ses arcs.
Théorème : La capacité d’une coupe est supérieure ou égale à la valeur d’un flot réalisable.
Théorème : La valeur d’un flot maximal est égale à la capacité d’une coupe minimale.

36
 Chapitre 6
Ordonnancement de projets
La réalisation d’un projet nécessite souvent une succession de tâches auxquelles s’attachent
certaines contraintes :

De temps : délais à respecter pour l’exécution des tâches ;

D’antériorité : certaines tâches doivent s’exécuter avant d’autres ;
De production : temps d’occupation du matériel ou des hommes qui l’utilisent..

Les techniques d’ordonnancement dans le cadre de la gestion d’un projet ont pour objectif de
répondre au mieux aux besoins exprimés par un client, au meilleur coût et dans les meilleurs
délais, en tenant compte des différentes contraintes.
L’ordonnancement se déroule en trois étapes :
La planification : qui vise à déterminer les différentes opérations à réaliser, les dates
correspondantes, et les moyens matériels et humains à y affecter.
L’exécution : qui consiste à la mise en œuvre des différentes opérations définies dans
la phase de planification.
Le contrôle : qui consiste à effectuer une comparaison entre planification et exécution,
soit au niveau des coûts, soit au niveau des dates de réalisation.
Il existe trois méthodes d’ordonnancement : le diagramme de Gantt, la méthode
MPM (Méthode des potentiels Métra), la méthode PERT (Program Research Technic).

I Le Diagramme de Gantt.
1. Principe.
Ce type de diagramme a été mis au point par un américain Henry Gantt.
On représente au sein d’un tableau, en ligne les différentes tâches et en colonne les unités
de temps (exprimées en mois, semaines, jours, heures…)

La durée d’exécution d’une tâche est représentée par un trait au sein du diagramme.

2. Réalisation.
Les différentes étapes de réalisation d’un diagramme de Gantt son les suivantes :
Première étape : On détermine les différentes tâches (ou opérations) à réaliser et leur
durée.
Deuxième étape : on définit les relations d’antériorité entre tâches.
Troisième étape : on représente d’abord les tâches n’ayant aucune antériorité, puis les
tâches dont les tâches antérieures ont déjà été représentées, et ainsi de suite…
Quatrième étape : on représente par un trait parallèle en pointillé à la tâche planifiée la
progression réelle du travail

37
 Exemple :

Temps
1 2 3 4 5 6 7 8 9 10 11 12 13
Tâche
A

D
E

Remarques :

Chaque colonne représente une unité de temps.

Les durées d’exécution prévues des tâches sont représentées par un trait épais. (4
unités de temps pour C).
Les contraintes de succession se lisent immédiatement.
ƒ Les tâches B et C succèdent à la tâche A.
ƒ D succède à B.
Le déroulement d’exécution des tâches figure en pointillé, au fur et à mesure des
contrôles. On est à la fin de la 6ème unité de temps, B est en avance d’une unité et, C
est en retard d’une unité.
On peut alors déterminer le chemin critique : qui est formé d’une succession de
tâches, sur le chemin le plus long en termes de durées. Il est appelé chemin critique
car tout retard pris sur l’une des tâches de ce chemin, entraîne du retard dans
l’achèvement du projet. (Chemin critique : A, B, D, E).
Avantages :
Permet de déterminer la date de réalisation d’un projet.
Permet d’identifier les marges existantes sur certaines tâches (avec une date de début
au plus tôt et une date au plus tard).
La date au plus tard de début d’une tâche, la date à ne pas dépasser sans retarder
l’ensemble du projet.
Inconvénient :
Ne résoud pas tous les problèmes, en particulier si l’on doit planifier des fabrications qui viennent
en concurrence pour l’utilisation de certaines ressources.

38
II La Méthode des potentiels métra.
Cette méthode a été développée par une équipe de chercheurs français.
1. Principe.
Les tâches sont représentées par des sommets et les contraintes de succession par
des arcs.
Chaque tâche est renseignée par la date à laquelle elle peut commencer (date au plus
tôt) et celle à laquelle, elle doit se terminer (date au plus tard).
A chaque arc est associé une valeur numérique, qui représente soit une durée
d’opération, soit un délai.

Exemple :

Tâche Durée Tâches antérieures

A 2
B 4
C 4 A
Date au plus tard
D 5 A, B
E 6 C,D

Date au plus tôt

0 2 2 5
2
A C

0 2 4 15 15
9 9
E 6 FIN
0 0
5
DEBUT
0 0 4 4
0
B D
4

39
Remarques :

La date de début au plus tôt d’une tâche est obtenue en cumulant la durée des tâches qui
précèdent sur la séquence la plus longue.
On initialise le sommet DEBUT avec une date au plus Tôt = 0.

Date au plus tôt de la tache j = Max( date au plus tôt de i + Durée Ti,j) pour tous les
prédécesseurs i de j.

40
 Les dates au plus tard : dates à laquelle doivent être exécutées les tâches sans remettre
en cause la durée optimale de fin du projet.

On initialise à l’étape terminale, le dernier sommet par la date au plus tard =

date au plus tôt.
Date au plus tard i = Min (Date au plus tard de j – durée Ti,j) pour tous les
successeurs j de i.

On peut alors déterminer le chemin critique : succession de tâches sur le chemin le

plus long au sens des durées. Pour toutes les tâches du chemin critique, les dates au plus
tôt et au plus tard coïncident. Chemin critique : B, D, E.
2. La marge totale.
La marge totale sur une tâche est le retard que l’on peut prendre dans la réalisation de cette
tâche sans retarder l’ensemble du projet.
Elle est obtenue, en faisant pour chaque tâche, la différence entre la date au plus tard de
début d’une tâche et la date au plus tôt.

Marge totale sur A = (2-0)=2

3. La marge libre.

La marge libre sur une tâche est le retard que l’on peut prendre dans la réalisation d’une
tâche sans retarder la date de début au plus tôt de tout autre tâche qui suit.

Si on appelle :
T j la date au plus tôt de la tâche qui suit la tâche considérée. T i La date de
début au plus tôt de la tâche i.
Di La durée de la tâche i.

Marge Libre de i = Min (T j – T i – D i,j ) pour tous les successeurs j de i.

i D i,j j

Marge libre sur A = 2 – 0 –2 =0

Marge libre sur C = 9 - 2- 4 = 3

41
III Méthode P.E.R.T (Program Evaluation and Research Task)

1. Principe.

Dans un graphe PERT :

Chaque tâche est représentée par un arc, auquel on associe un chiffre entre parenthèses qui
représente la durée de la tâche.

Entre les arcs figurent des cercles appelées « sommets » ou « événement » qui marquent
l’aboutissement d’une ou plusieurs tâches. Ces cercles sont numérotés afin de suivre l’ordre
de succession des divers évènements.

2. Réalisation

Pour construire un graphe PERT, on utilise la méthode des niveaux.

On détermine les tâches sans antécédents, qui constituent le niveau 1.

On identifie ensuite les tâches dont les antécédents sont exclusivement du niveau
1. Ces tâches constituent le niveau 2, et ainsi de suite…

Date au plus Date au plus tard

tôt
2 4
2
C(4)
A(2) 9 9 E(6) 15 15
X(0) 4
0 0 4
1 B(4) D(5)
4 4
3

Remarque :

Il a été nécessaire d’introduire une tâche fictive de durée égale à 0, pour représenter
la relation d’antériorité entre A et D.
Le cumul des tâches composant la séquence la plus longue (B, D, E) permet de
déterminer la date au plus tôt de réalisation du projet. Cette succession de tâches
constituent le chemin critique.

42
3. Dates et marges en représentation PERT.

Date au plus tôt.

On initialise la date au plus tôt du premier sommet à 0 :

T1=0 Désigne la date au plus tôt du sommet 1.

T i = Max (T j + Durée T i,j) pour tous les prédécesseurs j de i

Date au plus tard.

On initialise la date au plus tard du dernier sommet avec sa date au plus

tôt. T* n = T n ( T* n : désigne la date au plus tard du sommet n)

( T n : désigne la date au plus tôt du sommet n).

T* i = Min ( T* j – Durée T i,j) pour tous les successeurs j de i.

Marge totale

Marge totale i, j =T* j – T i – Durée T i,j

T* j : est la date au plus tard du sommet j. T i : date au plus tôt du

sommet i.
T i,j : durée de la tâche entre les sommets i et j.

Tâches A B C D E
Marges 4-0-2=2 4-0-4=0 9-4-4=1 9-4-5=0 15-9-6=0
totales

Remarque : sur le chemin critique, les marges totales des différentes tâches
sont nulles.

Marge Libre

Marge libre i,j = T j – Ti _ durée T i,j

Tâches A B C D E
Marges 2-0-2=0 4-0-4=0 9-2-4=3 9-4-5=0 15-9-6=0
libres

43
Bibliographie :

Quelques références sur la théorie des graphes

Livres

Pour débutants

Cogis O., Robert Cl., Théorie des graphes, Vuibert, 2003

Droesbeke F., Hallin M., Lefevre Cl., Les graphes par l'exemple, Ellipses, 1987
Lipschutz Seymour, Mathématiques discrètes, Série Schaum, McGraw-Hill, 1990

Pour aller plus loin

Claude Berge Graphes et hypergraphes ,2e édition, DUNOD Paris-Bruxelles-Montréal
Gondran M., Minoux M., Graphes et algorithmes, 2e édition, Eyrolles, 1986
Rüegg Alan, Processus stochastiques, Presses polytechniques romandes, 1989
Skiena Steven, Implementing Discrete Mathematics, Addison-
Wesley, 1990 (voir le site [Link])

44