COURS DE RECHERCHE OPERATIONNELLE

COURS DE RECHERCHE OPERATIONNELLE

PLAN DU COURS

CHAPITRE 0 : NOTION DE RECHERCHE OPERATIONNELLE

CHAPITRE I : NOTION SUR LA THEORIE DES GRAPHES

I. Les graphes
1. Définition
2. Sommets, Arcs
3. Graphe représenté par une matrice booléenne
II. Chemin et cycle d’un graphe
1. Le chemin
2. Chemin simple et cycle
3. Chemin élémentaire
4. Graphe orienté ou non orienté
III. Cheminement
1. Algorithme de FORD
2. Algoritme de DIJKSTRA.
Exercices d’application

CHAPITRE II: APPLICATION DES GRAPHES

I. Recherche des chemins de valeur minimale
1. Algorithme de FORD
2. Algorithme de DIJKSTRA.
II. Recherche des chemins de valeur maximale
1. Algorithme de FORD
2. Algorithme de DIJKSTRA.
Exercices d’application
CHAPITRE III: LES ARBRES

I - Définitions

II- Arbre de valeur minimale

1. Algorithme de KRUSKAL
2. Algorithme de SOLLIN

III- Arbre de valeur maximale

1. Algorithme de KRUSKAL
2. Algorithme de SOLLIN
Exercices d’application

CHAPITRE IV:LES PROBLEMES DE FLOT

I. Flot de valeur maximale
1. Algorithme de FORD et FULKERSON
2. Exercice d’application
II. Flot de valeur minimale
1. Algorithme de FORD et FULKERSON 1ère Formulation
2. Algorithme de FORD et FULKERSON 2ère Formulation
3. Exercices d’application

CHAPITRE IV : LES TECHNIQUES D’ORDONNANCEMENT

I. Le diagramme de GANTT
II. La méthode des potentiels
III La méthode P.E.R.T
Exercices d’application

N’GUESSAN REMI 1
 COURS DE RECHERCHE OPERATIONNELLE

CHAPITRE 0 : NOTION DE RECHERCHE OPERATIONNELLE

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 d’utiliser au mieux ses moyens
militaires, à l’époque insuffisants (avions, forces antiaériennes, moyens maritimes. L’idée
fondamentale était de mettre autant de soin dans l’emploi des moyens qu’on en avait mis pour
les concevoir et les construire.

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 branche des mathématiques qu’est la théorie des
graphes, support théorique de la recherche opérationnelle, laquelle utilise également trois
autres branches fondamentales :

 Algèbre linéaire et programmation linéaire : résolution de systèmes d’équations et

d’inéquations linéaires par la méthode du simplexe.

 la statistique, usant du calcul des probabilités, notamment la théorie des files d’attente

 la théorie des graphes qui s’est surtout développé au 20è siècle, dans les années 50,
avec C. Berge, en France, et D. König en Allemagne. Elle s’appuie sur la théorie des
ensembles et les relations binaires.

L’essor cohérent des réseaux de chemin de fer, des lignes aériennes, du réseau téléphonique
doit beaucoup à la théorie des graphes.

Dans ce module, nous allons voir uniquement la recherche opérationnelle utilisant la théorie
des graphes.
L’objectif principal de ce cours est d’acquérir une connaissance de certaines techniques
considérées à l’heure comme des méthodes de base issue de la recherche opérationnelle
appliquée au système concurrentiel économique ou militaire en mettant en œuvre des
stratégies afin :

 d’optimiser une production, un bénéfice, face à une concurrence;

 de s’opposer (militairement) efficacement à un adversaire;
 de maîtriser, dans la mesure du possible, les phénomènes naturels (météorologie,
séismes, etc.).
Celles-ci se retrouvent en effet, sous des formes plus complexes, dans les analyses
professionnelles de faisabilité ou d’optimisation.

Les exemples et exercices qui accompagnent ce cours permettent aux étudiants de modéliser
des problèmes simples en utilisant les techniques de la Recherche Opérationnelle. Ces
exemples et exercices ne tiennent évidemment pas compte de tous les paramètres d’une
véritable analyse professionnelle. Ils sont simplifiés volontairement et sont choisis suivant
l’orientation des étudiants, en majorité dans le domaine de la gestion; mais les techniques
utilisées s’appliquent également à la modélisation en ingénierie et en sciences.

N’GUESSAN REMI 2
 COURS DE RECHERCHE OPERATIONNELLE

CHAPITRE I : NOTION SUR LA THEORIE DES GRAPHES

I. GRAPHES

Les graphes modélisent de nombreuses situations concrètes où interviennent des objets en

interaction tel que :
 Les interconnexions routière, ferrovière ou aériennes entre différentes agglomérations,
 Les liens entre les composants d’un circuit électronique,
 Le plan d’une ville et de ses rues en sens unique,…
Les graphes permettent de manipuler plus facilement des objets et leurs relations avec une
représentation graphique naturelle. L’ensemble des techniques et outils mathématiques mis au
point en Théorie des Graphes permettent de démontrer facilement des propriétés, d’en
déduire des méthodes de résolution, des algorithmes, afin de déterminer :
 Quel est le plus court chemin (en distance ou en temps) pour se rendre d’une ville à une
autre ?
 Comment minimiser la longueur totale des connexions d’un circuit ?
 Peut-on mettre une rue en sens unique sans rendre impossible la circulation en ville ?

En un mot un graphe permet de décrire un ensemble d’objets et leurs relations, c’est à dire les
liens entre les objets.
 Les objets sont appelés les noeuds, ou encore les sommets du graphe.
 Un lien entre deux objets est appelé une arête

1-Définitions
a- Graphe

Un graphe G est un couple (V,E) où

 V est un ensemble (fini) d’objets. Les éléments de V sont appelés les sommets du graphe.
 E est sous-ensemble de VxV. Les éléments de E sont appelés les arêtes du graphe.
Une arête e du graphe est une paire e=(x,y) de sommets. Les sommets x et y sont les
extrémités de l’arête.
Notation : G=(V , E)

Exemple Un exemple de graphe à 8 sommets, nommés a à h, comportant 10 arêtes

G=(V,E) avec V={ a, b, c, d, e, f, g, h } E={ (a,d), (b,c), (b,d), (d,e), (e,c), (e,h),
(h,d), (f,g), (d,g), (g,h) }

N’GUESSAN REMI 3
 COURS DE RECHERCHE OPERATIONNELLE

Un graphe peut être représenté par un ensemble de points (sommets) reliés entre eux par des
flèches. Une flèche relie un sommet xi à un sommet xj si xj Є E(xi)
Un sommet xj est dit suivant de xi à un sommet xj si xj Є E(xi) donc s’il y a une flèche de xi
vers xj on dit que xi est dit précèdent de xj
Deux sommets x et y sont adjacents si il existe l’arête (x,y) dans E. Les sommets x et y sont
alors dits voisins
Une arête est incidente à un sommet x si x est l’une de ses extrémités

Remarques
 Les objets représentés par les sommets sont sans importance pour la manipulation du
graphe.
 Un graphe est d’ordre n si il comporte n sommets.
 Toute la richesse des graphes vient évidemment de la grande diversité que peut avoir
l’ensemble de ses arêtes. Pour appréhender la structure d’un graphe, nous pouvons
commencer par la caractériser localement en regardant pour chaque sommet les autres
sommets auxquels il est relié, le nombre d’arêtes dont il est extrémité,…
 Un graphe est dit simple lorsqu’il existe au plus une arête liant deux sommet et dans le
cas contraire le graphe est multiple.

b- sous-graphe

Pour caractériser de manière moins locale la structure d’un graphe, il est possible de
rechercher des parties remarquables du graphe, en restreignant l’ensemble des sommets (sous
graphe).
Un sous graphe de G consiste à considérer seulement une partie des sommets de V et les
liens induits par E. Par exemple si G représente les liaisons aériennes journalières entre les
principales villes du monde, un sous graphe possible est de se restreindre aux liaisons
journalières entre les principales villes Africaines.

Définition
Pour un graphe G = (V, E)
Un sous graphe de G est un graphe H= (W, E (W)) tel que W est un sous-ensemble de V, et
E(W) sont les arêtes induites par E sur W, c’est à dire les arêtes de E dont les 2 extrémité sont
des sommets de W.
Un exemple de sous graphe sur le graphe de l’exemple introductif.

Le sous-graphe H induit par l’ensemble W={ b, c, d, g, h } de sommets

c- Graphe partiel

N’GUESSAN REMI 4
 COURS DE RECHERCHE OPERATIONNELLE

Pour caractériser de manière moins locale la structure d’un graphe, il est possible de
rechercher des parties remarquables du graphe, en restreignant l’ensemble des arêtes (graphe
partiel).
Un graphe partiel de G consiste à ne considérer qu’une partie des arêtes de E. En reprenant le
même exemple, un graphe partiel possible est de ne considérer que les liaisons journalières de
moins de 3 heures entre les principales villes du monde.
Définition

Un graphe partiel de G est un graphe I= (V,F) tel que F est un sous-ensemble de E.

Un sous graphe H de G est entièrement défini (induit) par ses sommets W, et un graphe partiel
I par ses arêtes F.
Un exemple de graphe partiel sur le graphe de l’ exemple introductif.

Le graphe partiel I défini par l’ensemble F={ (a,d), (b,d), (d,e), (e,h), (h,d), (f,g) } d’arêtes

2- sommets et arcs
Soit l’arc U=(x ,y) ; x et y sont des extrémités .
Boucle : arc(x,x)
Arcs adjoints : arcs ayant au moins une extrémité en commun
Sommet adjacents à x (ou sommet voisins de x) ensemble des suivants, des précedent de x.

3- Graphe représenté par une matrice booleenne

Soit un graphe dont les sommets sont désignés par des numéros de 1 à n.
La matrice booleenne de ce graphe est la matrice carrée d’ordre n dont les éléments aij sont
égaux à : 1 si le sommet j Є E(i)
0 si le sommet j Є E(i)
Exemple
Soit le graphe G défini ci-dessous par son dictionnaire des suivants. G= (v ,E) avec
V= {1, 2, 3, 4, 5, 6}
E= {(1,2) ;(2,3) ;(2,5) ;(3,4) ;(3,5) ;(4,2) ;(5,4) ;(6,1) ;(6,3)}

1 2 3 4 5 6
1 1
2 1 1
3 1 1
4 1
5 1
6 1 1

Matrice booléenne associé

N’GUESSAN REMI 5
 COURS DE RECHERCHE OPERATIONNELLE

II. CHEMIN & CYCLE

Dans un graphe il est naturel de vouloir se déplacer de sommet en sommet en suivant les
arêtes. Une telle marche est appelée une chaîne ou un chemin. Un certain nombre de questions
peuvent alors se poser :
 pour 2 sommets du graphe, existe-t-il un chemin pour aller de l'un à l'autre?
 Quel est l'ensemble des sommets que l'on peut atteindre depuis un sommet donné?
 Comment trouver le plus court chemin pour aller d'un sommet à un autre?

1-Chemin
a- Définition
 Un chemin est une liste de sommets telle qu'il existe dans le graphe une
arête entre chaque paire de sommets successifs.
 La longueur du chemin correspond au nombre d'arêtes parcourues : k-1.

b- Exemple
Un chemin de longueur 5 dans le graphe reliant les sommets f à b.

p=( f, g, h, e, d, b )

c- Remarque

Il existe bien d'autres chemins pour aller de f à b : par exemple (f, g, d, b) de longueur 3, le
chemin (f, g, d, h, e, d, b) de longueur 6, ou encore (f, g, d, h, e, d, h, e, d, b) de longueur 9, ...
(d, h, e, d) est appelé un cycle. Ce cycle pouvant être emprunté autant de fois que l'on veut, il
y a un nombre infini de chemins de f à b

2-Chemin Simple et Cycle

a- Définition

 Un chemin p est simple si chaque arête du chemin est empruntée une seule fois.
 Un cycle est un chemin simple finissant à son point de départ :

b- Exemple

N’GUESSAN REMI 6
 COURS DE RECHERCHE OPERATIONNELLE

Les chemins (f, g, d, b) et (f, g, d, h, e, d, b) sont simples. Le chemin (f, g, d, h, e, d, h, e, d ,

b) ne l'est pas : le cycle (d, h, e, d ) est emprunté 2 fois.

c- Remarque

Les termes de chemin et de circuit s'emploient en propre pour les graphes orientés. Pour les
graphes non orientés que nous manipulons ici, on parle de chaîne et de cycle. Cependant la
définition formelle est exactement la même dans les 2 cas, seule change la structure (graphe
orienté ou non) sur laquelle ils sont définis.

3- Chemin élémentaire
a- Définition
 Un chemin est élémentaire si chacun des sommets du parcours est visité
une seule fois :
 Un chemin élémentaire est donc un chemin simple et sans cycle.

b- Exemple

Le chemin (f, g, d, b) est élémentaire, le chemin (f, g, d, h, e, d, b) ne l'est pas : le sommet d

est visité 2 fois, ce qui crée le cycle (d, h, e, d).

c- Propriété
Dans un graphe G d'ordre n
 Tout chemin élémentaire est de longueur au plus n-1
 Le nombre de chemins élémentaires dans le graphe est fini

4- Connexité

N’GUESSAN REMI 7
 COURS DE RECHERCHE OPERATIONNELLE

La notion de connexité est liée à l'existence de chemins dans un graphe : depuis un sommet,
existe-t-il un chemin pour atteindre tout autre sommet? Les graphes connexes correspondent à
la représentation naturelle que l'on se fait d'un graphe. Les graphes non connexes apparaissent
comme la juxtaposition d'un ensemble de graphes : ses composantes connexes.

a- Définition
Un graphe est connexe ssi il existe un chemin entre chaque paire de sommets
b- Exemple

III.CHEMINEMENT
Lorsqu'un chemin existe entre deux sommets dans un graphe, l'être humain se pose
rapidement la question non seulement de trouver un tel chemin, mais bien souvent il est
intéressé par le plus court chemin possible entre ces deux sommets. Notre oeil est d'ailleurs
particulièrement efficace dans cette tâche, tant que le graphe est de taille raisonnable... Mais
dès que le graphe comporte plusieurs dizaines de sommets et d'arêtes, trouver le plus court
chemin entre deux points devient vite un problème.
Nous aimerions disposer d'une méthode systématique capable, pour tout graphe et pour toute
paire de sommets s et t, de déterminer le plus court chemin entre eux. Résoudre ce problème
va donc consister à proposer un algorithme, aussi rapide que possible. Le problème de trouver
un plus court chemin est le premier problème d'optimisation auquel nous sommes confrontés.
Ainsi nous avons à notre disposition des algorithmes comme FORD et DIJKSTRA qui nous
permettent de résoudre ces problèmes.

1- Algorithme de FORD
Cet algorithme fait la recherche des plus courts chemins du sommet A vers tous les autres
sommets dans un graphe quelconque.

Principe :

1-Numéroter les n sommets du graphe dans un ordre quelconque, mais on impose :

 X0= sommet de départ
 Xn-1= sommet d’arrivée

2- Affecter provisoirement à tout sommet xi (i=0) la valeur j= +et poser 0=0

3-Pour tout sommet xj telque ji= V (xi-xj) où V (xi-xj) = valutation de l’arc (xi-xj)

4-Contnuer ainsi jusqu’à ce que aucun i ne puise être modifié.

N’GUESSAN REMI 8
 COURS DE RECHERCHE OPERATIONNELLE

Explication
Pour chaque sommet, calculer son  associé (au départ égal à +). Ceci va permettre de
calculer la longueur du chemin le plus court.
Calcul : on part de la racine ( associé égal à 0). On empile les successeurs en calculant le 
associé (le sommet n’est empilé que si son nouveau  est inférieur au précédent calculé)

Parcourir le graphe pour trouver les chemins les plus courts à partir des  calculés à l’étape
précédente en partant du sommet extrémité finale des chemins

2- Algorithme de DIJKSTRA

L'algorithme de Dijkstra détermine les plus courts chemins dans un graphe avec des
valuations positives de ses arêtes, entre un sommet s et tous les autres sommets. Nous allons
nous intéresser plus particulièrement au calcul de la longueur D(x) d'un plus court chemin
entre s et x. Cet algorithme est une adaptation de l'algorithme de recherche pour calculer les
plus court chemin d'un sommet s à tous les autres sommets du graphe.
L'algorithme de Dijkstra est un algorithme de marquage, une adaptation pour le problème du
plus court chemin de l'algorithme général de recherche. Cet d’algorithme permet uniquement
la recherche des chemins minimums.

Principe

1- On note x1= sommet entrée, xn = sommet arrivée

2- On considère au départ de x1, les chemins d’un seul arc (étape1), puis ceux de 2 arcs
au plus, (étape 2)….. et ceux de t arcs au plus (étape t)
3- On pose D0 ={x1} et 1=0
4- Soit Dt l’ensemble des sommets marqués jusqu’à l’étape t.
5- A l’étape t>= 1 ; on considère l’ensemble des sommets qui n’appartiennent à Dt -1 mais
ayant un ascendant direct dans Dt -1
6- On prend xk comme le sommet qui réalise le minimum k des quantités :i+ V(xi-xj)
où xi Є Dt -1 et xj Є Dt -1
7- On marque xk de la valeur k
8- On s’arrête dès que xn Є Dt pour une certaine valeur de t.

N’GUESSAN REMI 9
 COURS DE RECHERCHE OPERATIONNELLE

CHAPITRE II: APPLICATION DES GRAPHES

I. Recherche des chemins de valeur minimale

Nous allons généraliser notre notion de plus court chemin dans le cas de graphes valués, où
chaque arête e est associée à une valeur, appelée souvent son poids, c(e). La valuation des
arêtes peut représenter des coûts de transit, des distances kilométriques, le temps nécessaire
pour parcourir les arêtes,...

Exemple

Le schéma ci-dessous représente les différents parcours pour aller d’un village A à un village
F, en région de montagne où l’étroitesse des routes impose une circulation à sens unique.

Déterminer le chemin le plus court en utilisant les algorithmes de FORD et de DIJKSTRA

1-Algoritme de FORD

-Solution-
1- Numéroter les sommets

2- Affecter les    et  0  0
3- Calcul des différents 

1   0  3 2  4  2
1  3 2  7
2  0  8 3  2  1
2  8 3  8

N’GUESSAN REMI 10
 COURS DE RECHERCHE OPERATIONNELLE

 4  1  2 5  4  7
4  5  5  12
 3  1  6 5  3  2
3  9  5  10

On a donc  x 0 , x 1 , x 3 , x 2 , x 4 , x 5  de longueur 10
2- Algorithme de DIJKSTRA

-Solution-

On pose D 0  x 1  1  0
t1  1
Déterminons les sommets  D 0 mais qui sont directement liés aux éléments de
D 0 : x2 , x3 , x4
Calcul des différents 

1  V  x1 , x 2   3
2  3

1  V  x1 , x 3   8  k  min   2 ,  3 ,  4   min 3 ;8 ; 6 
3  8  k  3   2 doncx k  x2

1  V  x1 , x 4   6
4  6 D 1  D 0  x 2   x 1 ; x 2 

t2  2
Déterminons les sommets  D 1 mais qui sont directement liés aux éléments de
D1 : x5 , x3 , x 4
Calcul des différents 

N’GUESSAN REMI 11
 COURS DE RECHERCHE OPERATIONNELLE

2  V x2 , x4   5  2  V x2 , x5   9
4  5 5  9

1  V  x1 , x 3   8  k  min   5 ,  3 ,  4   min 5 ;9 ;8 ; 6 
3  8  k  5   4 doncx k  x4

1  V  x1 , x 4   6
4  6 D 2  D 1  x 4   x 1 ; x 2 ; x 4 

t3  3
Déterminons les sommets  D 2 mais qui sont directement liés aux éléments de
D 2 : x5 , x3 , x6
Calcul des différents 

 4  V x4 , x3   7  4  V  x 4 , x 6   12
3  7  6  12

 2  V x2 , x5   9  k  min   5 ,  3 ,  6   min  7 ;9 ;8 ;12 

5  9  k  7   3 doncx k  x3

1  V  x1 , x 3   8
3  8 D 3  D 2  x 3   x 1 ; x 2 ; x 4 ; x 3 

t4  4
Déterminons les sommets  D 3 mais qui sont directement liés aux éléments de
D3 : x5 , x6
Calcul des différents 

 2  V x2 , x5   9  4  V  x 4 , x 6   12
5  9  6  12

3  V x3 , x5   8  k  min   5 ,  6   min 9 ;8 ;12 

5  8  k  8   5 doncx k  x5

N’GUESSAN REMI 12
 COURS DE RECHERCHE OPERATIONNELLE

D 4  D 3  x 5   x 1 ; x 2 ; x 4 ; x 3 ; x 5 
t5  5
Déterminons les sommets  D 4 mais qui sont directement liés aux éléments de D 4 : x 6
Calcul des différents 

 5  V  x 5 , x 6   10  4  V  x 4 , x 6   12
 6  10  6  12

 k  min   6   min 10 ;12 

 k  10   6 doncx k  x6

D 5  D 4  x 6   x 1 ; x 2 ; x 4 ; x 3 ; x 5 ; x 6 
Le chemin minimal est  x 1 ; x 2 ; x 4 ; x 3 ; x 5 ; x 6  de longueur 10

3- Organigramme de l’algorithme de DIJKSTRA

Convention relative à l’algorithme de DIJKSTRA

0 si i= j
V  x k , x j   V  x k , x j  si  x k , x j   U
+ ∞ si  x k , x j   U

N’GUESSAN REMI 13
 COURS DE RECHERCHE OPERATIONNELLE

D   x 1 ,  1  0
x j  V x 1 , x j , j  1

 k  min  j

x j  D

D  D  x k 
 j  min  j ;  k  V x k , x j 

NON
xn  D OUI
STOP

II- Recherche de chemin de valeur maximale

1- Algorithme de FORD

Les n sommets numérotés de 1 à n et remplacer +par -et la condition jiV (xi-xj) par
ji≤ V (xi-xj)

2- Algorithme de DIJKSTRA

L’algorithme de DIJKSTRA ne s’applique pas à la recherche du chemin de valeur maximale.

III- Exercices d’application

N’GUESSAN REMI 14
 COURS DE RECHERCHE OPERATIONNELLE

CHAPITRE III: LES ARBRES

Les arbres sont des graphes particuliers, très populaires en algorithmiques et en informatique.
Les graphes envisagés ici sont non orientés.

I- Définitions

1- Arbre
Un arbre est un graphe connexe sans cycle.
Soit n sommets (n2), on appelle arbre de n sommets un graphe de n sommets, connexe et
sans cycle (circuit).
Exemple

2- Forêt

Une forêt est un graphe sans cycle. Une forêt étant un graphe sans cycle, chacune de ses
composantes connexes est acyclique, et par définition connexe. La définition d'une forêt
correspond donc bien au sens usuel d'un ensemble d'arbres, chacune de ses composantes
connexes étant un arbre.

3- Propriété

Un arbre de n sommets comporte (n-1) arêtes

4- Remarque
Souvent, pour manipuler un arbre, nous particularisons un sommet du graphe que nous
appelons racine. Dans le cas des graphes non orientés, le choix d'une racine r dans l'arbre est
arbitraire. Dans le cas des graphes orientés, la racine est définie de manière unique comme le
sommet sans prédécesseur de l'arbre.
Le choix d'une racine revient dans un certain sens à orienter l'arbre, la racine apparaissant
comme l'ancêtre commun à la manière d'un arbre généalogique. Le vocabulaire de la théorie
des graphes s'en inspire directement : on parle de fils, de père, de frère,...

II- Arbre de valeur minimale

Imaginons que nous ayons à connecter des villes entre elles, par exemple avec un nouveau
réseau très haut débit. Un certains nombre de connexions directes point à point entre les villes
sont techniquement possibles. Il nous faut choisir lesquelles parmi ces connexions nous allons
effectivement mettre en place. La distance entre 2 villes dans le réseau final a peu
d'importance au vu des débits; cependant les coûts d'installation du réseau ne sont

N’GUESSAN REMI 15
 COURS DE RECHERCHE OPERATIONNELLE

évidemment pas les mêmes pour les différentes liaisons point à point. Nous aimerions donc
déterminer comment connecter toutes les villes en minimisant le coût total du réseau.

Le problème de l'arbre couvrant de poids minimum consiste à trouver un arbre couvrant

dont la somme des poids c(e) des arêtes est minimum.

Ce problème en théorie des graphes correspond à la recherche d'un arbre couvrant de poids
minimum. L'ensemble des connexions potentielles peut être représenté par un graphe G =
(V,E) dans lequel chaque arête e est associée à un coût c(e) positif. Connecter toutes les villes
correspond à sélectionner un ensemble d'arêtes F de G tel que le graphe partiel H = (V,F)
induit est connexe. Le poids de cette solution c(H) est définie comme la somme des poids de
ses arêtes.

On dispose de deux algorithmes qui sont :

 L’algorithme de KRUSKAL
 L’algorithme de SOLLIN

1- L’algorithme de KRUSKAL

L'algorithme de Kruskal se base sur la caractérisation des arbres comme des graphes
acycliques maximaux au sens de l'inclusion : on ne peut ajouter une arête à un arbre sans créer
de cycle
a- Principe
 Etablir une liste des arêtes par valuations croissantes. Dans le cas où k arêtes sont
de même valuation, on les distinguera en ajoutant ∑ >0 à la valeur de la seconde,
2 ∑ à la valeur de la 3 ème etc.…( on admet que les k valeurs restent inférieurs à la
valuation immédiatement supérieure dans le graphe)
 Choisir l’arête de valeur minimale puis successivement au fur et à mesure de la
construction de l’arbre, l’arête de valeur immédiatement supérieurs dans la liste,
ne formant pas de cycle avec les arêtes retenus jusque là. S’arrêter lorsque tous les
sommets du graphe sont connectés.
 Pour obtenir la valeur de l’arbre, additionner les valuations des (n-1) arêtes
obtenues, en ayant soin de faire ∑ =0.

Remarque : La solution (arbre) est unique si toutes les arêtes sont initialement de valeur
différentes.

b- Exemple
Considérons ci-dessous le graphe G dont les arêtes sont valuées par des coûts, on veut trouver
dans ce graphe un arbre de coût minimal en utilisant L'algorithme de Kruskal.

N’GUESSAN REMI 16
 COURS DE RECHERCHE OPERATIONNELLE

-Solution-

1-Etablir la liste de valuation croissante.

[B ,E]=1
[B ,F]=2
[B ,C]=3
[E ,C]=3+∑
[E ,F]=3+2∑
[A ,F]=3+3∑
[G ,D]=3+4∑
[A ,B]=4
[G ,F]=4+∑
[D ,E]=4+2∑
[A ,G]=5
[F ,D]=5+∑
[D ,C]=6

2- Construction de l’arbre

3- Une solution est donnée par l’arbre {[D ,G] ; {[G ,F] ; {[F ,A] ; {[F ,B] ; {[B ,E] ; {[B ,C]}
de valeur : 1+2+3+3+3+4= 16 minimale.

2-Algorithme de SOLLIN

a- Principe

 Etablir une liste des arêtes par valuations croissantes. Dans le cas où k arêtes sont de
même valuation, on les distinguera en ajoutant ∑ >0 à la valeur de la seconde, 2 ∑ à la
valeur de la 3ème etc.…( on admet que les k valeurs restent inférieurs à la valuation
immédiatement supérieure dans le graphe)
 A chaque étape de l’algorithme, choisir arbitrairement un sommet en dehors de ceux
qui ont déjà été retenues et reliés par l’arête de valuation la plus faible, ce sommet à
l’un des sommets auxquels il est adjacent.
 Lorsque l’ensemble des sommets a été utilisé entièrement :
- Ou bien le résultat obtenu est déjà un arbre et le problème est résolu.
- Ou bien on n’a encore que des sous arbres qu’on considérera comme des
sommets d’un multigraphe (c’est-à-dire graphe dont 2 sommets au moins sont reliés par

N’GUESSAN REMI 17
 COURS DE RECHERCHE OPERATIONNELLE

plus d’un arc), les arêtes de ce multigraphe étant toutes les arêtes qui sont susceptibles de
connecter 2à 2 ces sous arbres et l’on reprendra l’algorithme à la 2ème étape.

 Pour obtenir la valeur de l’arbre, additionner les valuations des (n-1) arêtes
obtenues, en ayant soin de faire ∑ =0.
b- Exemple

On reprend l’exemple précèdent. Considérons ci-dessous le graphe G dont les arêtes sont
valuées par des coûts, on veut trouver dans ce graphe un arbre de coût minimal en utilisant
L'algorithme de SOLLIN.

-Solution-

1-Etablir la liste de valuation croissante.

[B ,E]=1
[B ,F]=2
[B ,C]=3
[E ,C]=3+∑
[E ,F]=3+2∑
[A ,F]=3+3∑
[G ,D]=3+4∑
[A ,B]=4
[G ,F]=4+∑
[D ,E]=4+2∑
[A ,G]=5
[F ,D]=5+∑
[D ,C]=6

2- Construction de l’arbre

N’GUESSAN REMI 18
 COURS DE RECHERCHE OPERATIONNELLE

3- Etablir les sommets du multigraphe

4- Une solution est donnée par l’arbre {[D ,G] ; {[G ,F] ; {[F ,A] ; {[F ,B] ; {[B ,E] ; {[B ,C]}
ou {[D ,G] ; {[G ,F] ; {[F ,A] ; {[F ,B] ; {[B ,E] ; {[E ,C]} de valeur : 1+2+3+3+3+4= 16
minimale.
Remarque En remplaçant [EC] par [BC] On obtient deux nouveaux arbres de valeur
minimale.

III- Arbre de valeur maximale

1- Algorithme de Kruskal

Pour cet algorithme, il faut lire la liste des arêtes établie au 1ereétape dans l’ordre inverse c'est-
à-dire prendre la liste dans l’ordre décroissant.

2-Algorithme de SOLLIN

Pour cet algorithme, il faut relier le sommet choisi par l’arête de valeur maximale.

IV- Exercices d’application

N’GUESSAN REMI 19
 COURS DE RECHERCHE OPERATIONNELLE

CHAPITRE IV: LES PROBLEMES DE FLOT

Les flots permettent de modéliser une très large classe de problèmes. Leur interprétation
correspond à la circulation de flux physiques sur un réseau : distribution électrique, réseau
d'adduction, acheminement de paquets sur Internet, ... Il s'agit d'acheminer la plus grande
quantité possible de matière entre une source s et une destination t. Les liens permettant
d'acheminer les flux ont une capacité limitée, et il n'y a ni perte ni création de matière lors de
l'acheminement : pour chaque noeud intermédiaire du réseau, le flux entrant (ce qui arrive)
doit être égal au flux sortant (ce qui repart).

I- Définitions

1-Réseau
Un réseau est un graphe orienté N=(V,A) avec une valuation positive de ses arcs. La
valuation c(x,y) d'un arc (x,y) est appelée la capacité de l'arc.
On distingue sur N deux sommets particuliers : une source s et une destination t. Les autres
sommets sont les noeuds intermédiaires du réseau.
Exemple

Remarque Le choix d'une source et d'une destination est arbitraire et dépend simplement du
problème que nous avons à traiter sur le réseau.

2- Le flot
Un flot représente l'acheminement d'un flux de matière depuis une source s vers une
destination t. Le flot est ainsi décrit par la quantité de matière transitant sur chacun des arcs du
réseau. Cette quantité doit être inférieure à la capacité de l'arc, qui limite ainsi le flux pouvant
transiter par lui. De plus il n'est pas possible de stocker ou de produire de la matière aux
noeud intermédiaires : un flot vérifie localement une loi de conservation analogue aux lois de
Kirshoff en électricité.

Un flot F sur un réseau N=(V,A) est une valuation positive des arcs, c'est à dire une
application de A dans R+, qui vérifie les deux propriétés suivantes :

1. Pour tout arc a A, 0 F(a) c(a)

2. Pour tout sommet intermédiaire x V \ { s,t }, F(y,x) = F(x,y)

Exemple

N’GUESSAN REMI 20
 COURS DE RECHERCHE OPERATIONNELLE

3-Flot Maximum (MaxFlow)

La somme (x) = F(y,x) est le flot entrant au sommet x

La somme (x) = F(x,y) est le flot sortant du sommet x
La valeur | F | d'un flot F est définie comme le flot sortant moins le flot entrant en s : | F | =
(s) - (s)

Le problème du Flot Maximum consiste à trouver un flot Fmax de valeur maximale sur le
réseau N.

La valeur du flot correspond au flux net partant de s. La valeur du flot peut être définie de
manière équivalente comme le flux net arrivant à t, c'est à dire le flot entrant moins le flot
sortant de t. En effet pour tout noeud intermédiaire x, le flot entrant étant égal au flot sortant,
on a : (x) = (x)

Comment aborder un problème comme la recherche d'un flot maximum sur un réseau ? Nous
allons utiliser le paradigme très général de l'optimisation locale. Son principe consiste à se
donner une solution réalisable, c'est à dire un flot sur le réseau, et à essayer de l'améliorer à
chaque itération.

4-Saturation
Un arc (x,y) est saturé par un flot F si la valeur du flot sur l'arc égale sa capacité : F(x,y) =
c(x,y). Un chemin est saturé si l'un de ses arcs est saturé.

La capacité résiduelle d'un arc (x,y) est la quantité c(x,y) - F(x,y) de flot pouvant encore
transiter par lui. La capacité résiduelle d'un chemin est la plus petite capacité résiduelle de ses
arcs.

Saturer un chemin p de s à t consiste à augmenter le flot de ses arcs de la capacité résiduelle

du chemin.

II- Flot de valeur maximale

Un problème d'optimisation décrit un ensemble d'instances, les contraintes à satisfaire pour
qu'une solution soit réalisable et une fonction objectif à maximiser ou à minimiser.
L'optimum OPT(I) est la meilleure valeur possible de la fonction objectif d'une solution
réalisable pour une instance I du problème.
Dans un réseau pour déterminer un flot de valeur maximale nous allons utiliser l’algorithme
de FORD et FULKERSON sous deux formulations.

1- L’algorithme de FORD et FULKERSON 1ère formulation.

L'algorithme de Ford & Fulkerson délivre un flot maximum. Rien de tel pour l'algorithme de
Ford et Fulkerson qui par principe part d'une solution réalisable et l'améliore au fur et à
mesure des itérations...

a- Principe

 On part d’un flot réalisable initial    ij /  x i , x j   u  de valeur   

 A chaque étape, on essaie d’accroître le flot par le marquage de certains
sommets :

N’GUESSAN REMI 21
 COURS DE RECHERCHE OPERATIONNELLE

 Le sommet x1 porte la marque permanente m 1   ,   

 A un sommet xj, 2≤j≤n, est attribué une marque m j ayant la forme

m j  i, j 
 ou  où
i représente le sommet xi à partir duquel xj a été marqué.

 j  0 est la quantité dont on marque xj

+ indique que xi précède xj (marque directe) dans ce cas
 j 
 min  i , cr ij  c ij   ij 
- indique que xi précède xj (marque indirecte) dans ce cas
 j 
 min  i , cr ij   ji 
 Si le sommet xn a été marqué, sa marque  n représente l’augmentation de la valeur
du flot possible à cette étape. Pour réaliser cet accroissement :

 On construit, grâce aux marques la chaîne, allant de x1 à xn qui à permis le

marquage de xn .

 On endéduit un nouveau flot réalisable    ij /  x i , x j   u  de

valeur      n et de composante :
 ij   ij   n si (xi, xj) est un arc de la chaîne avec  j marque directe.

 ij   ij   n si (xi, xj) est un arc de la chaîne avec  j marque indirecte

 ij   ij Pour les autres arcs  u

On utilise ce flot initial pour une nouvelle itération

 Si le sommet xn ne peut être marqué, le flot φ obtenir à la fin de l’étape précédente est
un flot de valeur maximale.

b- Exemple
Obtenir un flot de valeur maximale dans le réseau ci-dessous. Les nombres associés aux arcs
représentent :
-Les capacités cij s’ils sont écrits au-dessus de l’arc
-Les flux élémentaires φ ij du flot initial s’ils sont écrits au-dessous de l’arc.

N’GUESSAN REMI 22
 COURS DE RECHERCHE OPERATIONNELLE

-Solution-

    5  3  8
Valeur du flot initial :
Le sommet x1 porte la marque m 1   ,  
Etape 1 : marquage des sommets
m2 n’est pas calculable à partir de m1 car  j 0
m 3  1, 5 ,  

m 5  3 , 4 ,   ou 4  min 5 ,  35  4 
m 2  5 , 2 ,   ou 2  min 4 ,  25  2 
m 4  2 ,1,  
m 7  4 ,1,   ou 1  min 1,  47  4 
Ici xn=x7 est marqué donc  7  1
La phase de marquage s’achève, on peut modifier le flot initial.
Le nouveau flot de valeur     8  1  9 Les composantes sont :
 13  3  1  4  24  3  1  4  12  5
 35  1  1  2  47  3  1  4  36  2
 25  2  1  1  57  3
 67  2
Etape 2 : marquage des sommets

m2 n’est pas calculable à partir de m1 car  j 0

m 3  1, 4 ,  
m 5  3 , 3 ,  
m 2  5 ,1,  
m 4 N’est pas calculable à partir de m2 car  j 0
On ne peut marquer x7 donc le flot de valeur maximale est égal à 9

2- L’algorithme de FORD et FULKERSON 2ème formulation.

N’GUESSAN REMI 23
 COURS DE RECHERCHE OPERATIONNELLE

On va associer à tout flot  existant au début de chaque étape un graphe G(  ), dit graphe
d’écart dont les arcs sont définis comme suit :
Pour tout x , x   U
i j

1-  x , x   U   siC
i j IJ   IJ  0
2-  x , x   U   si 
j i ij  0
Les chaines permettant de marquer xn à partir de x1 dans le graphe G correspondent aux
chemins joignant x1 à xn dans le graphe d’écart.

a- Principe

- Partir d’un flot initial réalisable

- Etablir le graphe d’écart en recopiant les C ij en sens directe mais seul les
 ij  0 représentent des arcs en sens inverse.
- On choisit un chemin quelconque de x1 à xn et en prenant la capacité résiduelle
minimale sur ce chemin.
- Modifier le flot initial avec la capacité résiduelle minimale sur ce chemin.
- Reproduire le graphe à la fin de cette étape.
- Continuer jusqu’à ce que il n’y ait plus de chemin joignant x 1 à xn dans le
graphe d’écart.
b- Exemple

Obtenir un flot de valeur maximale dans le réseau ci-dessous. Les nombres associés aux arcs
représentent :
-Les capacités cij s’ils sont écrits au-dessus de l’arc
-Les flux élémentaires φ ij du flot initial s’ils sont écrits au-dessous de l’arc.
On prend un Flot initial nul :     0

N’GUESSAN REMI 24
 COURS DE RECHERCHE OPERATIONNELLE

-Solution-

Flot initial réalisable     0

Etape 1
On choisit le chemin  x 1 , x 3 , x 5 , x 7  de capacité résiduelle minimale 3
Le nouveau flot est     0  3  3
Etape2
On choisit le chemin  x 1 , x 2 , x 4 , x 7  de capacité résiduelle minimale 4
Le nouveau flot est     3  4  7

Etape3
On choisit le chemin  x 1 , x 3 , x 6 , x 7  de capacité résiduelle minimale 2
Le nouveau flot est     7  2  9

Etape4

Il n’existe plus de chemin allant de x1 à x7 dans le graphe d’écart donc le dernier flot de valeur
    9 est un flot de valeur maximale.

III- Exercices d’application

N’GUESSAN REMI 25
 COURS DE RECHERCHE OPERATIONNELLE

CHAPITRE V : LES TECHNIQUES D’ORDONNANCEMENT

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 oeuvre 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),
 Le PERT (Program Evaluation and Research Task).

I Le Diagramme de Gantt.
Ce type de diagramme a été mis au point par un américain Henry Gantt.

1. Principe.
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 matérialisé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.

3- Exemple :

N’GUESSAN REMI 26
 COURS DE RECHERCHE OPERATIONNELLE

4- 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.
_ 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 terme 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).
5-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.
6-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.

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.

2- Détermination de la date de début au plus tôt

N’GUESSAN REMI 27
 COURS DE RECHERCHE OPERATIONNELLE

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.

3- Détermination de la date de début au plus tard

La date au plus tard est la date à laquelle doit être exécutée 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.

4- Détermination de 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

5- Détermination de 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.
Marge libre sur A = 2 – 0 –2 =0
Marge libre sur C = 9 - 2- 4 = 3

6- Le chemin critique
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.

7-Exemple :
Une entreprise s’intéresse à un procédé de construction d’un produit nouveau. Ce procédé fait
intervenir un certain nombre d’opérations. Leurs durées et les contraintes auxquelles elles sont
soumises, sont données dans le tableau suivant :

Déterminer un ordonnancement des opérations lequel minimise la durée d’exécution du

procédé de construction.

N’GUESSAN REMI 28
 COURS DE RECHERCHE OPERATIONNELLE

-Solution-

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és « 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…

3- Détermination de la date de début au plus tôt

On initialise la date au plus tôt du premier sommet à 0 :
T 1 = 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

4-Détermination de la 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).

N’GUESSAN REMI 29
 COURS DE RECHERCHE OPERATIONNELLE

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

5-Détermination de la 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.
Remarque : sur le chemin critique, les marges totales des différentes tâches sont nulles.

6-Détermination de la Marge Libre

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

7- Exemple
Une entreprise s’intéresse à un procédé de construction d’un produit nouveau. Ce procédé fait
intervenir un certain nombre d’opérations. Leurs durées et les contraintes auxquelles elles sont
soumises, sont données dans le tableau suivant :

Déterminer un ordonnancement des opérations lequel minimise la durée d’exécution du

procédé de construction.

-Solution-

N’GUESSAN REMI 30
 COURS DE RECHERCHE OPERATIONNELLE

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.

IV- Exercices d’application

N’GUESSAN REMI 31