RO Graphe

Programme de cours :
*Partie I : Théorie des graphes et applications
Chapitre I : Les éléments de la théorie des graphes
Chapitre II : Les chemins optimaux
Chapitre III : Ordonnancement des tâches
*Partie II : Programmation Linéaire
Partie I : Chapitre I : Les éléments de la théorie des graphes

I - Graphes non Orientés

1 - Définition
Un graphe fini G = (V,E) est défini par l’ensemble fini V = { X1,X2, … ,Xn } dont les éléments sont
appelés Sommet et par l’ensemble fini E = {e1, e2, …, e3} dont les éléments sont appelés Arêtes.
Une Arête ’e’ de ‘E’ est définie par une paire non ordonnée de sommets appelée les extrémités
de ‘e’. Si l’Arête ‘e’ relie les sommets a et b, on dira que ces sommets sont adjacents
a b ou incident avec e.
e
On appelle ordre d’un graphe, le nombre de sommet N de ce graphe
exemple : N = 5. 5 1

4 2

3
2 - Quelques types de graphe
Un graphe est simple si au plus une arrête relie 2 sommets et si il n’y a pas de boucles sur un
sommet. On appelle Boucle, une arête qui relie un sommet à lui-même.
On appelle multi graphe, un graphe avec une boucle ou avec plusieurs arêtes reliant les 2
mêmes sommets
exemple 1

2 4

Un graphe est connexe si il est possible à partir de n’importe quel sommet de rejoindre tous les
autres en suivant les arêtes.
Un graphe est complet si chaque sommet du graphe est relié directement à tous les autres
sommets
exemple 1

2
4
3
II - Graphes Orientés :
Un Graphe Orienté G = (X,U) est déterminé par un couple formé par 2 éléments
X = {x1,x2 , … ,xn} Un ensemble fini dont les éléments sont appelés des Sommets et
U = {u1,u2,…,un} Un ensemble fini dont les éléments sont appelés Arcs
NB : Les arcs ont un sens et les arêtes n’en ont pas.

Exemple :
u1 x2 u2
x1
u6
u5
x5 x3
u4
u3
x4

Pour U = ( x, y ) On dira que U est arc qui relie x à y ( x est l’extrémité initiale et y est l’extrémité
finale ).

III - Degré
1 - Degré d’un sommet
On appelle degré de sommet x et on note d(x) le nombre d’arête incidentes à ce sommet
NB : Une boucle sur un sommet compte double, car elle est extrémité initiale et finale

Dans un graphe simple, on peut aussi définir le degré d’un sommet comme étant le nombre de
ses voisins
2 - Degré d’un graphe
C’est le degré maximum de tous ses sommets
IV - Représentation matricielle d’un graphe ( Matrice d’Adjacence )
On peut représenter un graphe simple par un matrice d’adjacence. Une matrice d’ordre (n x m)
est un tableau de n lignes et m colonnes .
Le copule ( i, j ) désigne l’intersection de la ligne i et de la colonne j. Dans un matrice
d’adjacence, les lignes et les colonnes représentent les sommets du graphe. La présence du
chiffre 1 à la position ( i, j ) signifie que le sommet i est adjacent au sommet j. Dans le cas
contraire, c’est le chiffre 0.
 X1 X2 X3 X4
X2
X1 0 0 1 0
X2 0 1 1 0 X1 X3
X3 0 0 0 0
X4 0 1 1 0 X4

On peut aussi représenter un graphe simple en la liste des sommets auquel il est adjacent. Ce
sont les listes d’adjacences.

0 0 1 0
0 1 1 0
M= 0 0 0 0
0 1 1 0

V - Chaîne et Cycle
Définition
Une chaîne est une suite finie de sommet reliée entre eux par des arêtes.
Une chaîne simple est une chaîne qui n’utilise pas 2 fois les mêmes arêtes.
Une chaîne eulérienne d’un graphe G est une chaîne passant une et une seule fois par chacune
des arêtes de G.
Une chaîne hamiltonienne d’un graphe G est une chaîne passant une et seule fois par chacun
des sommets de G.
Un Cycle est une chaîne qui revient à son point de départ.
Un Cycle hamiltonien d’un graphe G est un cycle passant une et seule fois par chacun des
sommets de G.
Un Cycle eulérien d’un graphe G est un cycle passant et une seule fois par chacune des arêtes de
G.
Un graphe est dit eulérien s’il possède un cycle eulérien.
Un graphe est dit hamiltonien s’il possède un cycle hamiltonien.

• Exemple : A
A
A A
E B B
E E
E B
B C D
D C D C
D C Hamiltonien et Ni l’un ni l’autre
Eulérien
Eulérien
Hamiltonien
 Coloration d’un graphe
Il s’agit de colorier le graphe de tel sorte que les sommets adjacents soient de couleurs
différentes.
Définition
Soit G = (V,E)
Un sous ensemble v de G est un Stable si il ne comprend que des sommets non adjacent 2 à 2.
Une coloration avec K couleur est donc une partition de l’ensemble des sommets en K stable.

Comment colorier un Graphe :

Algorithme de coloration de Welsh et Powel :
1 - Placez les sommets du graphe dans l’ordre décroissant de leur degré
2 - En parcourant la liste dans l’ordre, attribuer une couleur non encore utilisée au premier
sommet non encore coloré et attribuer cette même couleur à chaque sommet non encore
coloré et non adjacent à un sommet de cette couleur.
3 - Si il reste des sommets non colorés dans le graphe, revenir à l’étape 2 si non fin.
Cette algorithme couramment utilisé permet d’obtenir une assez bonne coloration d’un graphe,
c’est à dire une coloration n’utilisant pas un trop grand nombre de couleur. Cependant, il
n’assure pas que le nombre de couleur soit minimum.
B
Exemple : R
V1 V6
Sommets V1 V7 V3 V5 V4 V6 V2 B
Couleurs R B V V R B B V2 B
V5 V
V7
V3
V
V4 R
Exercice :
5 étudiants A,B,C,D,E doivent composer sur certaines matières M1, M2, M3, M4, M5, M6.
Les examens ne se tiennent qu’une seule fois, chaque étudiant ne peut passer qu’une seule
matière par jour. La liste des inscriptions aux examens est la suivante :

A M1 M2 M3 M6
B M3 M4 M1 M5
C M2 M6 1
D M3 M4 M5
E M3 M6 M2 M4
1 M3 1
1
 Sommet M3 M2 M4 M6 M1 M5
Couleur R V V B B B

Jours Lundi Mardi Jeudi

Matière M6,M1,M5 M2,M4 M3
Candidat A,D,E A,B,C,D A,B,D,E

quel est le nombre de jour minimal nécessaire pour faire passer tous les étudiants : 3 jours
 CHAPITRE II CHEMINS OPTIMAUX

I - LES ARBRES
On appelle arbre, tout graphe connexe sans cycle.
Un graphe est dit connexe lorsqu’il existe un chemin reliant 2 sommets quelconques.
Un graphe sans cycle mais non connexe est appelé forêt
Une feuille ou sommet pendant est un sommet de degré 1.
1 - Arbre Couvrant
Un arbre couvrant aussi appelé arbre maximal est un graphe partiel
Chercher un arbre couvrant dans un graphe G c’est chercher un arbre qui touche tous les
sommets dans G et de poids total minimum.
Algorithme de Prime :
Initialisation
A = Ø ( Contiendra toutes les arêtes de l’arbre )
Y = { X } X un sommet quelconque de G
Tant que ( Y ≠ X ) faire
Chercher e = ( x, y ) de poids minimum
tel que x C X | y c’est-à-dire
A=AU{e}
Y=YU{y}
fin tant que
Retourner A
Comme exemple d’application de cet algorithme nous avons l’envoie de message dans un
réseau, la construction d’un réseau routier, approvisionnement des points de vente à partir d’un
magasin unique.
X = { 1,2,3,4,5,6,7}
Y=X
Y e A 1 2
{1} (1,2) (1,4) (1,2)
1 2 3
{ 1, 2 } (1,4) (2,3) (2,4) (2,5) (1,2) (2,3) 4 6 5
4 6
{ 1, 2, 3 } (1,4) (2,4) (2,5) (3,5) (3,6) (1,2) (2,3) (1,4)
{ 1, 2, 3, 4 } (2,5) (3,5) (3,6) (4,5) (4,7) (1,2) (2,3) (1,4) (4,5) 4 3 5 8 6
{ 1, 2, 3, 4, 5 } (3,6) (4,7) (5,6) (5,7) (1,2) (2,3) (1,4) (4,5) (4,7) 7
{ 1, 2, 3, 4, 5, 7 } (3,6) (7,6) (1,2) (2,3) (1,4) (4,5) (4,7) (7,6) 4 3
{ 1, 2, 3, 4, 7, 5, 6 } --- --- 7
 A = { (1,2) (2,3) (1,4) (4,7) (4,5) (7,6) }
=1+2+4+4+3+3
= 17

Le poids total minimum est de 17.

Autre exemple :
Trouver l’arbre couvrant

Y e A
{1} (1,2) (1,4) (1,5) (1,5)
5 5
1 2 3 { 1, 5 } (1,2) (1,4) (5,2) (5,3) (5,4) (5,6) (1,5)(5,4)
{ 1, 5, 4 } (1,2) (5,2) (5,3) (5,6) (1,5)(5,4)(5,3)
3 2 4 2 1 { 1, 5, 4, 3 } (1,2) (5,2) (3,2) (3,6) (1,5)(5,4)(5,3)(3,6)

4 6 { 1, 5, 4, 3, 6 } (1,2) (5,2) (3,2) (1,5)(5,4)(5,3)(3,6)(5,2)

5
1 3 { 1, 5, 4, 3, 6, 2 } --- ---

A=2+1+4+2+1
= 10.
II - Chemin Optimal :
Soit G un graphe valué. Le problème du chemin optimal ou du plus cours chemin issu d’un
sommet x admet une solution si :
- x est une Racine
- G ne contient pas de circuit absorbant
NB : On appelle circuit absorbant, un circuit de longueur négative ou de poids négatif.
Un sommet x est dit racine si il existe dans le graphe un chemin joignant x à tous les autres
sommets.
Algorithme de recherche du plus court chemin : ALGORITHME DE DIJKSTRA
Cette algorithme est utilisé pour la recherche des plus courts chemins dans un graphe à
valuation positive
Initialisation
n = le nombre de chemins de G
Pred = Tableau des Prédécesseurs initialisés à 0
Dist = Tableau des distances initialisées à 0
dist(s) = 0
W = Matrice des poids des arcs
C = Liste des sommets à traiter
D = Ø ( liste des sommets déjà traités )
Traitement
tant que C ≠ Ø faire
x = sommet de C le plus proche de s
retirer x de C etle mettre dans D
Pour tout sommet y € C faire
si dist(x) + W(x,y) < dist(y) alors
dist(y) = dist(x) + w(x,y)
et Pred(x) = x
fin si
fin pour
fin tant que
Fin
Exemple 1
Appliquer l’algorithme précédent pour déterminer les chemins les plus court depuis le sommet
A vers les autres sommets du graphe et faire l’arbre de parcourt sur le graphe.

3 B 2

A 5 C
1 1 5
1
2
3
15
F D
6 2
E

D C Dist Pred
A B C D E F A B C D E F
Ø {A,B,C,D,E,F} 0 ∞ ∞ ∞ ∞ ∞ 0 0 0 0 0 0
{A} {B,C,D,E,F} 0 3 5 ∞ ∞ 1 0 A A 0 0 A
{A,F} {B,C,D,E} 0 2 5 16 7 1 0 F A F F A
{A,F,B} {C,D,E} 0 2 4 16 7 1 0 F B F F A
{A,F,B,C} {D,E} 0 2 4 9 6 1 0 F B C C A
{A,F,B,C,E} {D} 0 2 4 8 6 1 0 F B E C A
{A,F,B,C,E,D} Ø
(A,F) (F,B) (B,C) (C,E) (E,D)
Exemple 2 :
Appliquer l’algorithme de Dijkstra partant du sommet 1 sur le graphe suivant :
4 5
1
5
10 7
15 4
3 3

2 3 3
D C Dist Pred
1 2 3 4 5 1 2 3 4 5
Ø {1,2,3,4,5} 0 ∞ ∞ ∞ ∞ 0 0 0 0 0
{1} {2,3,4,5} 0 15 ∞ ∞ 4 0 1 0 0 1
{1,5} {2,3,4} 0 15 11 9 4 0 1 5 5 1
{1,5,4} {2,3} 0 12 11 9 4 0 4 5 5 1
{1,5,4,3} {2} 0 12 11 9 4 0 4 5 5 1
{1,5,4,3,2} Ø

(1,5) (5,4) (4,2) (5,3)

 CHAPITRE III : ORDONNANCEMENT DES TACHES
INTRODUCTION
Ordonnancer les tâches c’est planifier l’exécution des tâches qui ont une certaine durée et qui
ont entre elles des relations d’antériorité. Il existe plusieurs algorithmes possibles pour résoudre
les problèmes d’ordonnancement. Les 2 plus fréquemment utilisés sont la méthode PERT et la
méthode MPM.
LA METHODE MPM :
Exemple d’étude :
L’entreprise Alpha a procédé à la dépression d’un certains nombre de tâches à effectuer.
On a rempli la colonne des antériorités avec les tâches qui doivent être exécutées avant celles
considérées. Une évaluation du temps de chaque tâches a également été proposée.

Tâches Durée en Semaine Antériorité

A 3 --
B 4 A
C 5 A
D 2 A
E 2 B,C
F 3 D

Proposons un agenda des différentes tâches, en indiquant le nombre de semaines minimum puis
maximum à entrevoir avant la fin des différentes tâches. Pour cela nous allons nous servir de la
méthode MPM.
1 - Le Graphe des niveaux
À partir du tableau, on réalise un premier graphe appelé graphe de niveau, dont les sommets
sont les tâches et qui permet de mettre en évidence les antériorités

B
E

A C
F
D
Niveau 1 Niveau 2 Niveau 3
 2 - Le graphe orienté
On crée le graphe orienté dont les sommets sont les tâches, on crée
tâches fictives qui sont les tâches Début et Fin.
Les Arcs sont les relations d’antériorités immédiates. Ils sont valués par la durée de la tache
source.
Chaque sommet comporte 3 zones qui contiennent respectivement le nom de la tâche, le début
au plus tôt et le début au plus tard.

B 4
3 4 E
3
8 8 2
Début A
3 C 5
Début Début 0 0 Fin
au plus au plus 3 3 10 10
tôt (0) tard (0) 3 3
F
D 2
5 7
3 5

3- Date au plus tôt :

On traite les sommets par niveau en partant du début. Pour chaque sommet i on note la date ti
qui la longueur du plus long chemin de la tâche initiale à la tâche i.
4- Date au plus tard :
On traite les sommets en partant de la fin. Pour chaque sommet, on note la date t*i qui est la
longueur du plus court chemin de la tâche i à la tâche fin
5- Tâche et chemin critique :
- Il y a des tâches critiques, celles pour lesquelles on a début au plus tôt = début au plus tard.
(A,C,E)
- Les tâches critiques définissent 1 ou plusieurs chemins critiques composéh des Tâches dont
l’exécution ne doit connaitre aucun retard pour que le projet soit achevé au plus tôt.
NB : Avec la méthode MPM on a toujours au moins un chemin critique.
6- Marge totale :
On appelle marge totale, le retard maximum que peut avoir une tâche sans retarder la fin du
projet. On l’obtient en calculant t*i-ti.
 Tâches Marge
Totale
A 0
B 1
C 0
D 2
E 0
F 2

Diagramme de Gantt :
Il s’agira de représenter graphiquement le déroulement du projet

0 1 2 3 4 5 6 7 8 9 10

A
B
C
D
E
F
Partie II : PROGRAMMATION LINEAIRE

INTRODUCTION
1 - Définition
La recherche opérationnelle encore appelée aide à la décision est l’ensemble des méthodes
scientifiques cherchant à résoudre efficacement le problème posé par les activités et les
organisations humaines. La recherche opérationnelle propose des modèles pour analyser des
situations complexes et permet au décideur de faire le choix le plus efficace.
2 - Quelques champs d’applications
La recherche opérationnelle s’applique dans le dimensionnement des réseaux , les files
d’attentes, la gestion des productions, emploie du temps.
3 - Méthodologie de la recherche opérationnelle :
Cette méthodologie suit en général le schéma suivant :

• La formulation du problème :
o Détermination des objectifs, des contraintes
o L’dentification des données disponibles

• La modélisation : Il s’agit ici de déterminer le type de modèle à utiliser

• La résolution du modèle :
o Le choix du modèle
o La validation
• La validation des résultats :
• Le déploiement de la solution

Problème

Formulation

Modèle

Algorithme

Solution

Validation
Mise en
Œuvre
Quelques définitions :
L’optimisation est recherche du maximum ou du minimum d’une fonction, ainsi que les valeurs
des variables qui maximisent ou minimisent la fonction.
La programmation linéaire ou optimisation linéaire, est une branche des mathématiques qui
s’intéresse à l’optimisation des fonction linéaires comportant plusieurs variables indépendantes,
soumises à des contraintes pouvant être représentées à l’aide d’équations ou d’inéquations
linéaires.
La fonction économique est une fonction qui traduit ce que l’on veut maximiser ou minimiser.
Les variables de décisions : Ce sont des variables indépendantes dont la fonction économiques
dépend

Résolution d’un problème de programmation linéaire :

Pour résoudre un problème de programmation linéaire, nous disposons de 2 méthodes.

• La méthode Graphique :
La méthode graphique permet de résoudre un problème de programmation linéaire ayant
seulement 2 variables de décision. Cela permet de visualiser le principe général de la
programmation linéaire. Cette méthode est beaucoup trop longue et difficile, voir
impossible à visualiser si il y a plus de 2 variables de décision.
• La méthode du Simplexe :
C’est une méthode algorithmique plus rapide pour résoudre les problèmes comportant
un grand nombre de variables. Elle est généralement programmée et calculée à
l’ordinateur.
Une fonction linéaire à plusieurs variables peut être représentée par une équation de la forme
équation de la forme y = a1X1 + a2X2 + … + anXn, où y est la variable dépendante, a1, a2 … an
sont les étudiants constants réelles. x1 x2 … xn sont des variables indépendantes.
Méthode du Simplexe : Le directeur d’une manufacture de meuble décide de fabriquer 2
nouveaux modèles de tables. Le modèle régulier et le modèle chic. Le modèle régulier requiert
1h de sciage, 2h d’assemblage et 1h de finition. Le modèle chic nécessite 2h de sciage, 1h
d’assemblage et 1h de finition. La manufacture dispose quotidiennement de 20h à l’atelier de
sciage, de 22h à l’atelier d’assemblage et de 12h à l’atelier de finition. Les profits que la
compagnie peut réaliser pour chacun des modèles sont de 20$ pour le modèle régulier et de
30$ pour le modèle chic. Le directeur désir déterminer le nombre de meuble de chaque modèle
qu’il doit fabriquer par jour pour obtenir un profit maximal.
Etape 1 - Identifier les variables du problème :
X1 = Le nombre d’unité du modèle régulier
X2 = Le nombre d’unité du modèle chic
P = Le profit en $ à maximiser
Etape 2 - Déterminer la fonction économique à maximiser :
P = 20(X1) + 30(X2)
Etape 3 - Définir les contraintes à l’aide d’une équation linéaire. Ne pas oublier les contraintes de
non négativités
X1 + 2(X2) <= 20
2(X1) + X2 <= 22
X1 + X2 <= 12
X1 >= 0, X2 >= 0
La fonction économique et ses contraintes ainsi définies constitue la forme canonique du
problème.

Etape 4 - Traduire toutes les inéquation en équation, en ajoutant les variables d’écart aux
contraintes. La nouvelle formulation du problème est appelée forme standard.
X1 + 2(X2) + E1 = 20
2(X1) + X2 + E2 = 22
X1 + X2 + E3 = 12
20(X1) + 30(X2) - P = 0

Etape - 5 Représenter le problème sous forme matricielle :

X1 + 2(X2) + E1 =20
2(X1) + X2 + E2 =22
X1 + X2 + E3 =12
20(X1) + 30(X2) - P =0

1 2 1 0 0 0 20
2 1 0 1 0 0 22
1 1 0 0 1 0 12
20 30 0 0 0 -1 0
Etape - 6 Déterminer la colonne du pivot : C’est la colonne sauf la dernière dont l’élément de la
dernière ligne à la plus grande valeur.
Colonne Pivot

1 2 1 0 0 0 20
2 1 0 1 0 0 22
1 1 0 0 1 0 12
20 30 0 0 0 -1 0

Etape - 7 Déterminer la ligne du pivot : Pour ce faire , divisez chaque élément de la dernière
colonne, sauf le dernier élément par les éléments correspondant de la colonne du pivot. La ligne
où le résultat de la division est le plus petit sans être négatif est la ligne du pivot.
Colonne Pivot

1 2 1 0 0 0 20 Ligne Pivot (Lp)

2 1 0 1 0 0 22
1 1 0 0 1 0 12
20 30 0 0 0 -1 0

Etape 8 - Encadrer le pivot : Le pivot est l’élément situé à l’intersection de la colonne et de la

ligne du pivot. Pivot

1 2 1 0 0 0 20 Lp

2 1 0 1 0 0 22 L1
1 1 0 0 1 0 12 L2
20 30 0 0 0 -1 0 L3

Etape 9 - Annuler tous les éléments de la colonne du pivot sauf le pivot lui-même : En faisant des
opérations élémentaires de ligne de la forme aLi - bLp.

1 2 1 0 0 0 20 Lp

3 0 -1 2 0 0 24 2L1 - Lp
1 0 -1 0 2 0 4 2L2 - Lp
5 0 -15 0 0 -1 -300 L3 - 15Lp
Etape 10 - Répéter les étapes 6 , 7, 8 et 9 jusqu’à ce que tous les éléments de la dernière ligne
soient négatifs ou nuls :

1 2 1 0 0 0 20 L1

3 0 -1 2 0 0 24 L2
1 0 -1 0 2 0 4 Lp
5 0 -15 0 0 -1 -300 L3

0 2 2 0 -2 0 16 L1 - Lp

0 0 2 2 -6 0 12 L2 - 3Lp
1 0 -1 0 2 0 4 Lp
0 0 -10 0 -10 -1 -320 L3 - 5Lp
Tous les éléments de la dernière ligne sont désormais nuls ou négatifs, Nous pouvons passer à
l’étape suivante.

Etape 11 - Encadrer les pivots : Ce sont les éléments qui sont les seuls à être non nul dans leur
colonne.

0 2 2 0 -2 0 16
0 0 2 2 -6 0 12
1 0 -1 0 2 0 4
0 0 -10 0 -10 -1 -320

Etape 12 - Rendre tous pivots unitaires en multipliant leur ligne par une constante appropriée
aux besoins. Rendre le coefficient de la fonction économique à 1, en multipliant la dernière ligne
par une constante approprié.

0 1 1 0 -1 0 8 x 1/2

0 0 1 1 -3 0 6 x 1/2
1 0 -1 0 2 0 4
0 0 10 0 10 1 320 x (-1)
Etape 13 - Déterminer la solution optimale : Pour ce faire, poser toutes les variables libres = 0.
Les variables libres sont celles dont la colonne ne contient pas de pivot.

0 1 0 0 0 0 8
0 0 0 1 0 0 6
1 0 0 0 0 0 4
0 0 10 0 10 1 320

X1 + 2(X2) + E1 =20
2(X1) + X2 + E2 =22
X1 + X2 + E3 =12
20(X1) + 30(X2) - P =0
Par analogie, nous obtenons :
0 + X2 + 0 =8
0 + 0 + E2 =6
X1 + 0 + 0 =4
0 + 0 + P =320

X1 = 4
X2 = 8
P = 320 E2 = 6 ( Pas essentiel au travail demandé )
Rappel du problème à résoudre : Le directeur désir déterminer le nombre de meuble de chaque
modèle qu’il doit fabriquer par jour pour obtenir un profit maximal.
X1 = Le nombre d’unité du modèle régulier ( 4 par jour )
X2 = Le nombre d’unité du modèle chic ( 8 par jour )
P = Le profit en $ à maximiser ( 320 $ )