Cours de

RECHERCHE
OPERATIONNELLE
Destiné aux étudiants de 1er Master Ingénieur
Civil
Prof. Dr Ir Arthur KANIKI TSHAMALA

1
 Engagements pédagogiques
 Intitulé du cours : Recherche Opérationnelle
 Code : …
 Volume horaire : 30h Th+15h TP=45 heures

 Méthodes d’enseignement et d’apprentissage

- Cours théorique ex cathedra (rétro ou vidéo projecteur)
- Pas de dictée!!!
- Diapositives et notes disponibles
- Cours (y compris exercices d’application)
 Travaux pratiques : comprennent
- Exercices d’application (dans l’auditoire chaque étudiant avec son PC)
- Séminaire (recherche et présentation)
Méthodes d’évaluation :
- Épreuve écrite : Questions théoriques et exercices avec ou sans notes
- Épreuve pratique : Résolution des exercices en utilisant l’outil informat
 Langues : Français

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 2

Civil
 Engagements pédagogiques
Crédits :
- Charge de travail de l’étudiant
- Adapté de l’Union Européenne : ECTS (European Credit Transfert System)
# Quantité de travail d’une unité d’enseignement par rapport à l’ensem
# Travail: Cours, TP, stages, recherches, enquêtes, exercices à domicile
# Une année d’études=60 ECTS  1.500 heures de travail (convention
1 ECTS=25 heures (charge de travail de l’étudiant)
- Recherche Opérationnelle : 6 ECTS soit 150 heures
Si “présentielles”=58 H  au moins 92 H « personnelles »

 Objectif général : Acquérir les connaissances des méthodes et

techniques d’analyse professionnelle de faisabilité et d’optimisation
permettant de prendre des décisions rationnelles face à des problèmes
complexes de nature combinatoire, aléatoire ou concurrentielle
 Pré-réquis : Notions de mathématiques (particulièrement d’algèbre
linéaire)
 Finalité : rendre l’étudiant capable d’utiliser les méthodes et
techniques rationnelles pour résoudre des problèmes complexes

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 3

Civil
 Contenu du cours théorique
Introduction
Définition
Historique
Domaine d’application

Chap. I Programmation linéaire

Définitions et notations
Théorèmes fondamentaux
Algorithme du simplexe
Méthode graphique de résolution
Résolution à l’aide du solveur Excel et à l’aide de
LINDO
Programmation en nombre entier
Exercices
Chap. II Éléments de la théorie de jeux et
stratégies
Introduction
Types de jeux
Représentations des jeux
Choix d’un critère
Exercices
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er
Master Ingénieur 4
Civil
 Contenu du cours théorique

Chap. III Théorie des graphes et applications

Notions et rappels mathématiques
Notions de chemin et de circuit
Applications
Recherche de chemins hamiltoniens
Recherche de chemins de valeur optimale
Recherche du plus court trajet
Problème d’ordonnancement
… à réaliser sous
forme de séminaire
Chap. IV Problèmes de gestion
Gestion de stocks
Gestion d’équipements

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 5

Civil
 INTRODUCTION
I. Définition : R.O. (aide à la décision) est l’ensemble des méthodes et
techniques rationnelles d’analyse et de synthèse des phénomènes
d’organisation utilisables pour élaborer de meilleures décisions.

Phénomènes d’organisation Modèles

: conceptuels
Techniques
Techniques de
d’analyse
Hommes, machines, Autres théories
synthèse
produits en relations
actives
R.
O

Problèmes complexes

Décideur
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 6
Civil
II. Historique :
INTRODUCTION
- XVIIème siècle : Notions d’espérance mathématique (Blaise Pascal)
- XVIIème et XVIIIème siècle : Notions d’analyse combinatoire
- XXème siècle : Gestion de stock, Formule du lot économique
(Wilson)=origine
 Organisation et nom de la discipline : Vers la seconde Guerre
mondiale
« opérationnelle » : à l’origine  opérations militaires

Exemple : Patrick Blackett (Angleterre) et implantation optimale de radars de

III. Domaine d’application : Résolution des problèmes
surveillance
- Combinatoire : grand nombre de solutions possibles (installation centres
distributions)
- Aléatoire : posé en termes incertains
- Concurrentiel : termes dépendent des stratégies (décideur) et des réactions
des tiers
… domaine réservé à des situations où le sens commun se révèle faible ou
impuissant
Problème combinatoire :

Question : Installer 1 centre de distribution parmi 3 sites offerts de

sorte que les coûts de transport entre ces centres et les clients soient
minimums
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 7
Civil
 INTRODUCTION
Problème
combinatoire : Plusieurs
solutions admissibles, mais
une seule est optimale

Kolwezi
Site B

Likasi

Lubumbashi

Lusaka

Site C
Site A

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 8

Civil
 INTRODUCTION
Problème
combinatoire : Plusieurs
solutions admissibles, mais
une seule est optimale

Kolwezi
Site B

Likasi

Lubumbashi

Lusaka

Site C
Site A

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 9

Civil
 INTRODUCTION
Problème
combinatoire : Plusieurs
solutions admissibles, mais
une seule est optimale

Kolwezi
Site B

Likasi

Lubumbashi

Lusaka

Site C
Site A

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 10

Civil
 INTRODUCTION
3!
C31  3
1!(3  1)!

Solution
B

Solution
C

Attention :
Explosion
Solution combinatoire !!!
30!
A 5
C30  142506
5!(30  5)!
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 11
Civil
 INTRODUCTION
Problème aléatoire :

Question : Déterminer le nombre minimum de guichet à ouvrir de

sorte à avoir moins (chiffrer) de chance d’attendre trop longtemps
(chiffrer) avant d’être servi

 Guichet unique :
Attendre au moins 1h

 Guichet A : Attendre moins de 5

min Combien de guichets
pour attendre moins
de 15 min ?
 Guichet B : Attendre moins de 10
min

 Guichet C : Attendre moins de 7

min
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 12
Civil
 INTRODUCTION
Problème concurrentiel :

Question : Quelle quantité de produit mettre sur le marché de manière à

garder la rareté… alors qu’il y a des concurrents qui ont plusieurs activités et
cherchent à vous contrecarrer
 La Recherche Opérationnelle permet :
- Industrie de manufacture : plans de production, disposition des machines, problèmes de découpe, livraison, etc.
- Finance : maximiser le profit sous contrainte
- Énergie : réseau de distribution
- Informatique : implantation des serveurs (nombre et localisation), traitement en temps réel ou en différé, etc.

 Dans les entreprises ?

- Faible utilisation (ignorance, coût, recours au cabinet conseil, etc.)
- Apport des ingénieurs internes
- Faible application des modèles (problèmes complexes: volonté
commerciale, contraintes légales, climat social, etc.  poids dans la décision
- Événements peu fréquents

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 13

Civil
 Chap. I Programmation
linéaire
I.1. Théorèmes fondamentaux

I.1.1. Définitions
i. Un ensemble de points C de Rn est dit convexe si le segment de droite qui relie
deux points quelconque de C est contenu dans C. En d’autres termes C est
convexe si pour tout X1, X2 Є C, on a :

X 3 X 1  (1   ) X 2  C où 0≤α≤1

C’est-à-dire toute combinaison linéaire convexe de 2 points est encore un point de C

ii. Un point X de sous-ensemble convexe C de Rn est appelé sommet, si il ne peut
être exprimé comme combinaison linéaire convexe de deux autres points
distincts de C, c’est-à-dire la relation :
X X 1  (1   ) X 2 où 0<α<1 entraîne X1=X2=X

B B

A
A C
2 sommets 3 sommets Infinités de sommets

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 14

Civil
 Chap. I Programmation
[Link] appelle linéaire
polyèdre convexe dans Rn un sous-ensemble
convexe
borné C qui possède un nombre fini des sommets.
Une combinaison linéaire de 3 points A1, A2, A3 est dite convexe si et
seulement si
X  1 X 1   2 X 2   3 X 3 avec 0≤αi≤1 et  i 1

A1 A1
Cas du triangle
M
X
M  1 A  (1   1 ) A2  0 A3
A2 A3
A2 A3 X1

Prenons maintenant un point X à l’intérieur du triangle et traçons une

droite passant par le point X. On peut écrire que :
X  1 A1  (1   1 ) X 1

X 1  1 A2  (1  1 ) A3

X 1 A1  (1  1 ) 1 A2  (1  1 )(1  1 ) A3

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 15

Civil
 Chap. I Programmation
Récapitulation linéaire
On appelle polyèdre (du grec poly = plusieurs et hedra = base, facette) un solide
de l'espace limité par un nombre fini de polygones plans : ses faces. En ce sens,
le dièdre (2 faces) et le trièdre (3 faces) ne sont pas des polyèdres !
Le minimum de faces d'un polyèdre est 4 : il s'agit alors d'un tétraèdre. On
appelle arête d'un polyèdre toute intersection de deux faces.

Convexe s'oppose à étoilé (on dit

aussi croisé) un polyèdre convexe
est situé entièrement dans un
même demi-plan constitué par
l'une quelconque de ses faces

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 16

Civil
 Chap. I Programmation
Cas du parallélogramme linéaire
A1 X1 A2
X X 1  (1   ) X 2 (1)
X
X 1   A1  (1   ) A2 (2)
A4 X2 A3
X 2 A3  (1  ) A4 (3)

(2) et (3)  (1) Avec 0  1 0   1 0  1

X  A1  (1   ) A2   (1   )A3  (1  ) A4 
X  A1   (1   ) A2  (1  ) A3  (1   )(1  ) A4  1   2   3   4 1
   (1   )  (1  )  (1   )(1  ) 1
     )  (1   )(  1  ) 1

N.B. On voit qu’il n’y a pas une seule façon de prouver qu’un point pris à
l’intérieur du polyèdre est une combinaison linéaire convexe des autres points
distincts sauf si le point est choisi sur le périmètre du polyèdre
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 17
Civil
 Chap. I Programmation
I.1.2. Théorème d’optimalité linéaire
Dans un programme linéaire dont l’ensemble des solutions réalisables
est un polyèdre convexe, l’optimum de la fonction économique est
nécessairement atteint en un sommet du polyèdre.
I.2. Algorithme du simplexe
I.2.1. Principe

Cheminer le long du polyèdre convexe des sommets en sommets en

améliorant à chaque étape la valeur de la fonction économique.
-Polyèdre : nombre fini de sommets
-Fonction économique : optimum atteint après nombre fini d’opération
I.2.2. Forme générale
n
Optimise z ( x , x ,..., x )  C x sous les n

r 1 2 n 
j 1
j j
contraintes x j Pj  P0 x1 , x2 ,..., xn 0
j 1

Fonction Fonction économique = Fonction -

économique objectif
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 18
Civil
 Chap. I Programmation
I.2.3. Exemple : Problème de linéaire
transport
Supposons que 250 et 450 containers sont disponibles aux dépôts D1 et
D2 et que les magasins A,B et C ont commandés 200 containers chacun.
Les coûts de transport par containers sont les suivants.
Magasin A B C
Dépôt D1 3,4 2,2 2,9 But : Minimiser le coût total de
transport en respectant les
Dépôt D2 3,4 2,4 2,5 disponibilités et les demandes
Xj nombre de containers transportés du dépôt i vers le magasin j (i=1,2 ;
j=A,B,C)
 Minimiser Z = 3,4x1A+2,2x1B+2,9x1C+3,4x2A+2,4x2B+2,5x2C
Sous les contraintes :
- de disponibilité x1 A  x 2 A 200
- de demande
x1B  x 2 B 200
x1 A  x1B  x1C 250
x1C  x 2C 200
x 2 A  x 2 B  x 2C 450
xij 0, à valeurs entières
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 19
Civil
 Chap. I Programmation
linéaire
L’application de la méthode du simplexe nécessite la connaissance des
éléments suivants :

 Coordonnées d’un sommet de départ  1ère solution réalisable;

 Formule de passage d’un sommet à un autre  formule de
changement de base;
 Influence d’un changement de base sur la valeur de la fonction
économique;
 Critère de sélection d’un sommet suivant afin d’améliorer la valeur de
la fonction économique;
 Critère permettant de détecter que la fonction économique est non
bornée sur l’ensemble de solution réalisable
Important (voir notes de cours)
• -Équation de changement de base
• -Influence de changement de base sur la fonction économique
• -Critères déterminant le changement de base

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 20

Civil
 Chap. I Programmation
linéaire a11 x1  a12 x 2  ...  a1n x n b1
I.2.4. Disposition pratique
a 21 x1  a 22 x 2  ...  a 2 n x n b2
Optimise z ( x , x ,..., x )  C x sous les
n
.
r 1 2 n 
j 1
j j contraintes .
.
Si on a une solution de base réalisable a m1 x1  a m 2 x 2  ...  a mn x n bm
(supposé explicité) de départ : x1 , x 2 ,..., x n 0

C1 C2 Cr Cm … Cn
Base Ci P0 P1 P2 Pr Pm … Pn
P1 C1 b1 1 0 0 0 … x1n
… linéaire parce que les
P2 C2 b2 0 1 0 0 … x2n égalités sont au premier
degré par rapport aux
Pr Cr br 0 0 1 0 … xrn variables

Pm Cm bm 0 0 0 1 … xmn

Z0 0 0 0 0 … -zk-Ck

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 21

Civil
 Chap. I Programmation
Exemple : Résoudre le programme linéaire
linéaire 3 x1  x2  x4  2 x5 7
suivant - 2èmes  2 x1  4 x2  x3 12
-1ères
contraintes x 0
j
: contraintes :
Min Z  x1  3 x2  2 x5  4 x1  3 x2  8 x5  x6 10
1° Ordonner en respectant le nombre de 2ème 3ème base
- x3, x4 et x6 apparaissent dans une seule base
variables
contrainte 3 x1  x2  0 x3  x4  2 x5  0 x6 7
$

$
$

- Si x1, x2 et x5 sont nuls on a une solution de  2 x  4 x  x  0 x  0 x  0 x 12

1 2 3 4 5 6
départ  4 x1  3x2  0 x3  0 x4  8 x5  x6 10
- A cette solution correspond la valeur nulle
2° Dresser le tableau (disposition
de Z
pratique)
1ère base
1 -3 0 0 2 0
Base Ci P0 P1 P2 P3 P4 P5 P6 Coef. dans Z

P4 0 7 3 -1 0 1 2 0
P3 0 12 -2 4 1 0 0 0
P6 0 10 -4 3 0 0 8 1

Coef. dans Z Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 22
Civil
 Chap. I Programmation
linéaire
3° Déterminer la valeur de la fonction économique
Min Z  x1  3 x2  2 x5

- Calculer Z0=ΣCi.P0
3 x1  x2  0 x3  x4  2 x5  0 x6 7
- Calculer Zk=Σ[Link]-Cj  2 x1  4 x2  x3  0 x4  0 x5  0 x6 12
 4 x1  3x2  0 x3  0 x4  8 x5  x6 10
On peut constater qu’avec la solution de base réalisable Zk=-Cj
Cj
1 -3 0 0 2 0
Base Ci P0 P1 P2 P3 P4 P5 P6 Pj
P4 0 7 3 -1 0 1 2 0
P3 0 12 -2 4 1 0 0 0
P6 0 10 -4 3 0 0 8 1
0 -1 3 0 0 -2 0 Zk
Z0

4° Changement de base
-Le vecteur Pj qui doit entrer dans la base est celui pour lequel Zk est max (maximum local)
-Chercher le pivot qui indique le vecteur à chasser de la base
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 23
Civil
 Chap. I Programmation Min Z  x1  3 x2  2 x5
-Le pivot correspond à P0/Pj min linéaire
1 -3 0 0 2 0
7/(-1)=-7
Base Ci P0 P1 P2 P3 P4 P5 P6
L4 P4 0 7 3 -1 0 1 2 0 12/(4)=3 
P3 0 12/4 -2/4 4 /4 1/4 0/4 0 /4 0 /4
10/
L6 P6 0 10 -4 3 0 0 8 1 (3)=3,3

0 -1 3 0 0 -2 0
-Diviser la ligne du pivot par le pivot -Appliquer la combinaison linéaire avec la ligne du pivot
1 -3 0 0 2 0 L’4=1L’2+L

Base Ci P0 P1 P2 P3 P4 P5 P6 4
L’6=-3L’2+L6

L’ P4 0 10 5/2 0 1/4 1 2 0
L’42 P2 3 -1/2 1 1/4 0 0 0
-Règle du
-3
rectangle
L’6 0 1 -5/2 0 -3/4 0 8 1
P6 (rec tan gle )
-9 1/2 0 -3/4 0 -2 0 xj 
pivot
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 24
Civil
 Chap. I Programmation Min Z  x1  3 x2  2 x5

linéaire

Base Ci P0
1
P1
-3
P2
0
P3
0
P4
2
P5
0
P6
10/(5/2)=4 
P4 0 10/(5/2)5/2/(5/2) 0 /(5/2) 1/4/(5/2) 1/(5/2) 2/(5/2) 0/(5/2) 3/(-1/2)=-6
L2 P2 -3 3 -1/2 1 1/4 0 0 0
1/(-5/2)=-2/5
L6 P6 0 1 -5/2 0 -3/4 0 8 1

-9 1/2 0 -3/4 0 -2 0

1 -3 0 0 2 0 L’2=1/2L’1+L2

Base Ci P0 P1 P2 P3 P4 P5 P6 L’6=5/2L’1+L6

L’ P1 1 4 1 0 1/10 2/5 4/5 0

L’12 P
2
-3 5 0 1 3/1 1/5 2/5 0
0
0 11 10 1
L’6 P6
0 0 -1/2 1
-11 0 0 -4/5 -1/5 -12/5 0

La solution optimale est : Z=-11 x1=4 x2=5 x3=0 x4=0 x5=0 x6=11
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 25
Civil
 Chap. I Programmation
Exercice : Résoudre le programme linéaire
linéaire x1  x4  6 x6 9
suivant 3 x1  x2  4 x3  2 x6 2
Min Z  x1  x2  x3  x4  x5  x6

1 3 5 6 x  2 x  x  2 x 6
I.2.5. Variables artificielles et variables
d’écart
Variable artificielle
En général on ne dispose pas d’une première solution de base admissible
et la procédure du simplexe ne peut démarrer. On utilise alors la
méthode dite de la base artificielle. Celle-ci consiste à modifier le
programme initial en ajoutant à chaque contrainte i une nouvelle
variable vi affectée d’un coefficient M infiniment grand dans la fonction
économique.
Comme M>>> Z est aussi >>>> éliminer les Pvi en premier lieu
Variable d’écart
Quand une contrainte i est une inégalité on ajoute à cette contrainte une
variable d’écart ti avec un signe + ou – pour obtenir une égalité. A la
variable ti correspond le vecteur Pti

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 26

Civil
 Chap. I Programmation
Exemple : Résoudre le programme linéaire x1  x2 5
linéaire
suivant x1  x2 1
Max Z  x1  x2

Min - Z  x1  x2
Comme on ne sait pas maximiser on va minimiser l’opposé
x1  x 2  t1 5
Pour avoir l’égalité on ajoute des variables d’écart
x1  x 2  t 2 1
Comme on n’a pas une solution de base réalisable on ajoute une variable
artificielle
x1  x 2  t1 5 x1  x 2  t1  0t 2  0v 2 5
Min  Z  x1  x 2  Mv 2
x1  x 2  t 2  v 2 1 x1  x 2  0t1  t 2  v 2 1

-1 -1 0 0 M Convention : Scinder
Base Ci P0 P1 P2 Pt1 Pt2 Pv2 la ligne de Z en deux

Pt1 0 5 1 1 1 0 0
Pv2 M 1 1 1 0 -1 1

M M M 0 -M 0
0 1 1 0 0 0
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 27
Civil
 Chap. I Programmation
linéaire
-1 -1 0 0 M
Dès qu’un vecteur
Base Ci P0 P1 P2 Pt1 Pt2 Pv2 artificiel est chassé il
Pt1 0 4 0 0 1 1 -1 ne peut plus rentrer :
on l’ignore et on
P1 -1 1 1 1 0 -1 1 ignore sa colonne

-1 0 0 0 0 -M
0 0 0 1 -1

-1 -1 0 0
Base Ci P0 P1 P2 Pt1 Pt2
Pt2 0 4 0 0 1 1
P1 -1 5 1 1 1 0

-5 0 0 -1 0

La solution optimale est : Z=5 x1=5 x2=0

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 28
Civil
 Chap. I Programmation
linéaire
SÉANCE T.P. N°1
Exercice
Une usine fabrique 2 pièces P1 et P2 dans deux ateliers A1 et A2. Les temps d’usinage sont pour P1 de 3
heures dans A1 et de 6 heures dans A2 et pour P2 de 4 heures dans A1 et de 3 heures dans A2.
Le temps de disponibilité hebdomadaire de l’atelier A1 est de 160 heures et celui de l’atelier A2 de 180
heures.
La marge bénéficiaire est de 1.200 pour une pièce P1 et 1.000 pour une pièce P2.
Question : Quelle production de chaque type doit-on fabriquer pour maximiser la marge hebdomadaire?
1° Établissement du programma linéaire
A1 A2 Si x1=P1 et x2=P2 on a :
Bénéfice
P1 P2 Z 1200 x1  1000 x2

P1 P2 P1 P2
Les contraintes sont :
1200/P1 1000/P2
3 x1  4 x2 160
3h/P1 4h/P2 6h/P1 3h/P2
6 x1  3 x2 180
160h/semaine 180h/semaine x1 , x2 0
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 29
Civil
 Chap. I Programmation
linéaire
2° Résolution par l’algorithme du simplexe
Z 1200 x 1  1000 x2

classique
1ère itération 1200 1000 0 0 3 x1  4 x 2  t1  0t 2 160
Base Ci P0 P1 P2 Pt1 Pt2 6 x1  3 x 2  0t1  t 2 180
Pt1 0 160 3 4 1 0

Pt2 0 180 6 3 0 1

0 -1200 -1000 0 0

2ème itération 1200 1000 0 0

Base Ci P0 P1 P2 Pt1 Pt2
Pt1 0 70 0 5/2 1 -2

P1
12
30 1 1/2 0 1/6
00

360 0 -400 0 200

00
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 30
Civil
 Chap. I Programmation
linéaire
2° Résolution par l’algorithme du simplexe
Z 1200 x 1  1000 x2

classique
3 x1  4 x 2  t1  0t 2 160
6 x1  3 x 2  0t1  t 2 180
3 ème
itération 1200 1000 0 0
Base Ci P0 P1 P2 Pt1 Pt2
P2 10
00
28 0 1 2/5 -5/4

P1 16 1 0 -1/5 19/24
12
00

472 0 0 160 10150

La solution optimale
00 est : Z=47200 x1=16 x2=28

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 31

Civil
 Chap. I Programmation
linéaire
3° Résolution graphique
Z 1200 x 1  1000 x2

x2 d1 3 x1  4 x2 160
70 d2 6 x1  3 x2 180
La solution optimale
60 correspond au x1 , x2 0
sommet (16,28)
50 Représentation de la fonction objectif
40 Z= 1200x1+1000x2 est un ensemble
30
de droites ayant pour pente m=-6/5
(si x2 est l’ordonnée). L’optimum est
20
Domaine des obtenu en augmentant Z jusqu’à la
10 solutions limite du domaine

10 20 30 40 50 60 70 x1

d2 d1

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 32

Civil
 Chap. I Programmation
linéaire
Exemple d’une fonction à minimiser Min Z  x1  x2

2x1  x2 12 d2
5x1  8x2 74 d3

x1  6x2 24 d1

A (0,12)  Z = 12 14

B (2,8)  Z = 10  12
A
10
C (11,5;2)  Z = 13,5
8 B d1
D (0,24)  Z = 24 d2
6 d3

2
C
0
0 5 10 15 20 D 25 30

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 33

Civil Z
 Chap. I Programmation Cellules
linéaire
4° Résolution dans MS références
Excel
 1°: Saisir les données du programme dans une colonne (colonne A)

 2°: Renseigner les cellules (colonne B)

 3°: Introduire les formules (colonne C)
 Identifier les cellules des résultats et les laisser vide ($C$2 : $C$3)
 Introduire les formules ($C$4 : $C$5)
 Déterminer les valeurs des contraintes hors contraintes logiques ($C$6 :
 $C$7)
Introduire la formule de la fonction économique ($C$8)

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 34

Civil
 Chap. I Programmation
linéaire
3° Résolution dans MS
 4°: Dans menu outils (2003) ou données Excel(2007) cliquer sur « solveur »
(l’activer dans les macro si il ne l’est pas encore)

Solution
 5°: Introduire les informations demandées
 Cellule cible à définir = fonction - objectif (saisir directement ou copier)
 Cellules variables=cellules des réponses (à modifier)
 Contraintes (y compris les contraintes logiques)
 6°: Cliquer sur résoudre et créer le rapport (fichier à donner à l’enseignant)

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 35

Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire
… certains problèmes peuvent être impossibles, à solutions multiples ou
à solution infinie. Comment les reconnaître ?
a) Problèmes
impossibles
… si une ou plusieurs variables artificielles ou d’écart sont présentes
dans la base dans le tableau de simplexe optimal : cela signifie que la
solution donnée par ce tableau n’est pas réellement réalisable

Exemple :
Max Z  4x1  3x 2 x1  x2 2
3x1  x2 10

Après introduction des variables d’écart et des variables artificielles on trouve :

x1  x2  t1  0t2  0v1 2 Max Z  4x1  3x 2  Mv1

3x1  x2  0t1  t2  v1 10

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 36

Civil
 Chap. I Programmation
linéaire
I.2.6. Problèmes irréguliersx  x  t  0t  0v 2
1 2 1 2 1 Max Z  4x1  3x 2  Mv1
a) Problèmes
impossibles 3x1  x2  0t1  t2  v1 10
1ère itération 4 3 0 0 -M
Base Ci P0 P1 P2 Pt1 Pt2 Pv1
Pt1 0 2 1 1 1 0 0

Pv1 -M 10 3 1 0 -1 1

-10M -3M -M 0 M 0
-4 -3 0 0 0

2ème itération
4 3 0 0 -M
Base Ci P0 P1 P2 Pt1 Pt2 Pv1
Le tableau de simplexe est
P1 4 2 1 1 1 0 0
optimal avec une variable
Pv1 -M 4 0 -2 -3 -1 1 artificielle dans la base
-4M 0 2M 3M M 0
8 0 1 4 0 0

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 37

Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire
x  x  t  0t 2 1 2 1 2 Max Z  4x1  3x 2
a) Problèmes
impossibles  3x1  x2  0t1  t2   10
Autre possibilité (éviter l’introduction d’une variable artificielle)
1ère itération 4 3 0 0
Base Ci P0 P1 P2 Pt1 Pt2
Pt1 0 2 1 1 1 0

Pt2 0 -10 -3 -1 0 1

0 -4 -3 0 0

2ème itération 4 3 0 0
Base Ci P0 P1 P2 Pt1 Pt2 Le tableau de simplexe est
P1 4 2 1 1 1 0 optimal avec une variable
d’écart dans la base
Pt2 0 -4 0 2 3 1

8 0 1 4 0

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 38

Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire
a) Problèmes
impossibles
La résolution par MS Excel donne une solution qui n’est pas réalisable …
Max Z  4x1  3x 2

x1  x2 2
3x1  x2 10
Aucun des menus


« rapports » n’est
disponible
2  0 2

6  0 10 x
On peut encore vérifier
graphiquement que la solution est
impossible …
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 39
Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire
b) Problèmes à solutions multiples

Graphiquement : lorsque la pente de la droite représentant la fonction

objectif est égale à la pente de l’une des contraintes restrictives
Max Z  x1  3x2
6
Exemple :
2x1  6x2 30 d1
5
x1 10 d2
x2  4
C
d3 4
B
A (0,0)  Z = 0
3 d1
d3
B (0,4)  Z = 12

 D
2

C (3,4)  Z = 15


1

D (10;5/3)  Z = 15 A E
0
0 2 4 6 8 10 12
E (10,0)  Z = 10
En réalité, tous les points du segment CD sont des solutions Z
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 40
Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire 2x1  6x2 30
Max Z  x1  3x2 x1 10
b) Problèmes à solutions multiples x2  4
Le solveur donne plusieurs solutions lorsqu’on change des valeurs initiales

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 41

Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire 2x1  6x2 30
Max Z  x1  3x2 x1 10
b) Problèmes à solutions multiples x2  4
La résolution par l’algorithme du simplexe donne un tableau optimal avec
une variable d’écart dans la base

1 3 0 0 0 1 3 0 0 0

Base Ci P0 P1 P2 Pt1 Pt2 Pt3 Base Ci P0 P1 P2 Pt1 Pt2 Pt3

Pt1 0 30 2 6 1 0 0 Pt1 0 6 2 0 1 0 -6

Pt2 0 10 1 0 0 1 0 Pt2 0 10 1 0 0 1 0

Pt3 0 4 0 1 0 0 1 P2 3 4 0 1 0 0 1

0 -1 -3 0 0 0 12 -1 0 0 0 3

1 3 0 0 0

Base Ci P0 P1 P2 Pt1 Pt2 Pt3

P1 1 3 1 0 0,5 0 -3

Pt2 0 7 0 0 -0,5 1 3

P2 3 4 0 1 0 0 1

15 0 0 -0,5 0 0

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 42

Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire
c) Problèmes à solution infinie
Graphiquement : on peut déplacer la droite de la fonction objectif
indéfiniment de manière à accroître la valeur, en gardant toujours une
intersection non vide avec l’ensemble des solutions réalisables
Max Z  x  2x  Mv 1 2 1

Max Z  x1  2x 2 x1  x2 2
Exemple : x1  x2  t1  0t2  0v1 2
x2 3
0x1  x2  0t1  t2  v1 3

1 2 0 0 -M
Base Ci P0 P1 P2 Pt1 Pt2 Pv1
P1 0 2 1 1 -1 0 0

Pv1 -M 3 0 1 0 -1 1

-3M 0 -M 0 M 0
-1 -2 0 0 0

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 43

Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire x  x 2
Max Z  x1  2x 2 1 2

c) Problèmes à solution infinie x2 3

1 2 0 0 -M
Base Ci P0 P1 P2 Pt1 Pt2 Pv1
P2 2 2 1 1 -1 0 0

Pv1 -M 1 -1 0 1 -1 1

-M M 0 -M M 0
4 1 0 -2 0 0

1 2 0 0 -M
Base Ci P0 P1 P2 Pt1 Pt2 Pv1
P2 2 3 0 1 0 -1 ? 1

Pt1 0 1 -1 0 1 -1 ? 1

0 0 0 0 0 M
6 -1 0 0 -2 2

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 44

Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire
Max Z  x  2x x1  x2 2 1 2

c) Problèmes à solution infinie x2 3

Le solveur indique que les valeurs des cellules définies ne convergent pas…

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 45

Civil
 Chap. I Programmation
I.2.6. Problèmes irréguliers linéaire
Max Z  x1  2x2 x1  x2 2
c) Problèmes à solution infinie
x2 3

3.5

2.5

1.5
d1
d2
1

0.5

0
0 0.5 1 1.5 2 2.5 3 3.5
-0.5

-1
Z

L’ensemble des solutions réalisables est non borné :

 on peut augmenter indéfiniment la valeur de la fonction objectif
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 46
Civil
 Chap. I Programmation
I.2.7. Rapport de sensibilité linéaire
→ Le solveur fournit beaucoup d’informations en plus de la solution optimale

→ Le rapport de sensibilité permet d’analyser l’impact de changements de

paramètres du modèle (coûts, membres de droite, paramètres des contraintes) sur
la solution optimale. On parle alors de l’analyse post-optimale.

→ Hypothèse fondamentale : Cette analyse ne vaut que si on change un seul

paramètre, tous les autres restant inchangés

→ Cette analyse est aussi appelée « analyse marginale » car les conclusions
qu’on en tire ne sont valides que pour de petits changements (changement à la
marge).

→ Règle d’or de l’analyse de sensibilité :

- Rapetisser la région admissible ne peut pas améliorer la valeur de
l’objectif
- Agrandir la région admissible ne peut pas empirer la valeur de l’objectif

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 47

Civil
 Chap. I Programmation
linéaire 2x  x 12
I.2.7. Rapport de sensibilité Exemple 1 2
Min Z  x1  x2 5x1  8x2 74
Tableau « contraintes » x1  6x2 24

Termes de gauche Coût marginal (associé à Termes de droite

des contraintes chaque contrainte) des contraintes

Augmentation et réduction admissible : Intervalle

de variation
Intervalle des changements du membre de droite
pour lesquels le CM (et son interprétation)
demeurent valides
→ Le CM mesure l’impact sur la fonction objectif si on augmente le membre de droite
de la contrainte concernée
→ Quand on maximise amélioration signifie augmentation et vice-versa
→ Une contrainte inactive a nécessairement un CM de zéro
→ Ce tableau donne des indications sur les variations de la valeur optimale de Z mais rien à
propos des effets sur les solutions optimales (elles changent mais restent dans le coin)
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 48
Civil
 Chap. I Programmation
linéaire 2x  x 12
I.2.7. Rapport de sensibilité Exemple 1 2
Min Z  x1  x2 5x1  8x2 74
Tableau « Cellules variables » x1  6x2 24

Range of optimality 1  1;1  0,375 2;0,625

1  0,6;1  0,5 1,6;0,5

12  13;12  2,75 25;9, 25

Range of feasibility 74  22;74  26 96;48
24  26;24  1E  30 50; 1E 30

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 49

Civil
 Chap. I Programmation
linéaire
I.3. Programmation en nombre entier
→ … il arrive que certaines variables soient astreintes à être entières
Ex. nombre d’avions, de camions, etc.
→ l’arrondi (excès ou défaut) peut ne pas être optimal et parfois non admissible
 x  y 1
Exemple Max y
3 x  2 y 12
2 x  3 y 12
x, y  
- Les points rouges vérifient les contraintes et les
pointillés rouges montrent l'enveloppe convexe de
ces points.
- Les solutions optimales sont (1,2) et (2,2).
- Les lignes bleues et l'axe des abscisse délimitent
les couples de réels qui satisfont toutes les
contraintes sauf la contrainte d'intégralité.

Exercices : voir séances de TP

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 50

Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
II.1. Introduction
Exemples des  Jeu de dame  Combat de Karaté  Vente d’un produit
Jeux  Match de football  Guerre  Agriculture

 Situation d’antagonisme
Objet d’un
GAGNER Nécessité d’élaborer une
jeu
stratégie
Jeu à somme
nulle Ce qui est gagné par l’un est perdu par l’autre

Gain = 50% Gain = 50%

Gain = 0% Client Gain =
100%

Vendeur 1 Vendeur 2

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 51

Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
Stratégie
ACTION 1
- Élaborer des actions
- Imaginer des réactions
- Changer actions jusqu’à obtenir le
NON
gain REACTION GAIN ?
Complexité
OUI
- Inventorier les actions possibles
- Inventorier les réactions possibles FIN
ACTION 2

- Déterminer la stratégie optimale

Nécessité d’élaborer des NON

REACTION GAIN ?
théories
Nécessité de formaliser les jeux
OUI

Approche mathématique de problèmes de stratégie FIN ACTION 3

Concerne des situations où les choix de 2 protagonistes (ou plus) ont des
conséquences pour l’un comme pour l’autre
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 52
Civil
 Chap. II Éléments de la théorie de jeux et
Historique : 3 étapes stratégies
essentielles
1°) Neumann et Morgenstern : formalisation des jeux où les choix sont les
mêmes et qui sont à somme nulle

2°) Jeux à somme non - nulle

3°) Théorie des jeux combinatoires  Base de l’intelligence artificielle

Exemple : Signalisation sur un carrefour à plusieurs voies

II.2. Types de jeux

1. Jeux coopératifs : On cherche la meilleure situation pour les 2 joueurs
 Si le jeu est à somme nulle : l’un gagne et l’autre perd au premier tour et la
situation est inversée au tour suivant, ainsi de suite.
Exemple : Feux rouges au croisement des routes  Les conducteurs passent à
tour de rôle
Bonne solution ?
 Si le jeu est à somme non - nulle : partage équitable des gains
Exemple : - Déterminer les quotas de ventes
- Éviter les croisements des routes
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 53
Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
 Théorie de la négociation : négociation suppose un jeu à somme non -
nulle
En absence d’un point d’équilibre sur la ligne du jeu, on trouve un
arrangement extérieur à cette ligne qui apporte beaucoup à l’un sans
coûter trop à l’autre.
Stratégie dite : Win - win ou
gagnant
Exemples : - J’accepte à ce prix là, mais nous me payez cash
- Si je vous en prends deux, vous m’accordez 5% de remise
- J’accepte à ce prix là, mais tu me déposes chez moi après

2. Coopétition : Compétition transparente

On fait la concurrence mais on partage les informations…

 En étant émetteur d’information stratégique on prend une position
dominante dans un groupe de compétiteurs

Exemples : - Secret d’une technique difficile au Karaté

- Montrer les documents importants ou les résolutions à ses concurrents
de classe
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 54
Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
3. Jeu à somme nulle et non - nulle :
 Somme nulle : Ce que gagne l’un est nécessairement perdu par
l’autre Exemples : Jeu d’échecs
 Somme non - nulle : Certaines issues sont globalement plus
profitables ou plus
dommageables pour tous
Exemples : Informations, communications, etc.
4. Jeu synchrone ou asynchrone :
 Synchrone : Décision simultanée
 Asynchrone : (Alternatif) On joue l’un après l’autre profitant ainsi de
l’information
5. Jeux répétés : Jouer et rejouer;
sur le coup de l’adversaire
Possibilité de prendre le risque de perdre « pour voir »
ou tester
 Conséquence les autres joueurs…
: Phénomènes de réputation qui influencent les choix
stratégiques
des autres joueurs
 On peut ou non connaître d’avance le nombre de coups…
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 55
Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
6. Jeu à information complète et à information parfaite :
 Information complète : Chaque joueur connaît lors de sa prise de
décision
- ses possibilités d’action
- les possibilités d’action des autres joueurs
- les gains résultants de ces actions
- les motivations des autres joueurs
 Information parfaite : Chaque joueur connaît en détails toutes les
actions
effectuées avant son choix…
Exemples : Jeu d’échecs = jeu à information complète et
parfaite
! Les situations réelles sont rarement à
information complète…
 Information incomplète : l’une des conditions précédentes n’est pas
vérifiée…

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 56

Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
7. Jeu à mémoire parfaite et à mémoire imparfaite :
 Mémoire parfaite : Chaque joueur se rappelle à tout moment de la
suite de
coups qui ont été joués précédemment….
 Mémoire imparfaite : Suppose une sorte d’amnésie de la part des
joueurs…
II.3. Représentations des jeux
1. Forme extensive : Arbre de décision décrivant les actions possibles des
joueurs…
2. Représentation tabulaire : Tableau à double - entrée qui énumère sur
chaque côté les stratégies possibles des joueurs respectifs. Dans la case à
la croisée de deux stratégies, on note le couple de gains des deux joueurs.
Ce tableau est appelé, par convention, « matrice des paiements ».
Stratégie A1 Stratégie A2 Stratégie A3
B A
Stratégie B1 Gain A1B1 Gain A2B1 Gain A3B1

Stratégie B2 Gain A1B2 Gain A2B2 Gain A3B2

Stratégie B3 Gain A1B3 Gain A2B3 Gain A3B3

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 57

Civil
 Chap. II Éléments de la théorie de jeux et
II.4. Choix d’un critère
stratégies
 Exemple d’un jeu contre la nature :
Un marchand doit stocker une quantité d’un article donné en début
d’année. Il a constaté dans le passé que selon la pluviosité de l’année
et selon la quantité stockée en début d’année, il réalisait en fin d’année
des gains qui sont consignés dans le tableau ci-dessous. Quelle est la
décision qu’il doit prendre?
Pluviosité
sèche moyenne pluvieuse
d1=10 10.000 12.500 10.000
d2=15 9.500 15.000 15.000
d3=20 9.000 14.000 20.000

1. Critère de Wald ou de Von Neumann (maximin ou pessimiste) :

Considérer la nature comme un adversaire malveillant qui cherchera à
minimiser le gain pour chaque décision…
Pour d1 le gain sera de   Comportement neumannien :
10.000
Pour d2 le gain sera de 9.500 Attitude d’un joueur ne prenant
Pour d3 le gain sera de 9.000 aucun risque
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 58
Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
2. Critère optimiste ou du maximax :
Considérer la nature comme un collaborateur complaisant qui cherchera à
se comporter de manière à maximiser le gain pour chaque décision
Pluviosité
sèche moyenne pluvieuse
d1=10 10.000 12.500 10.000
d2=15 9.500 15.000 15.000
d3=20 9.000 14.000 20.000

Pour d1 le gain sera de 12.500

Pour d2 le gain sera de 15.000
Pour d3 le gain sera de 
20.000
3. Critère de Laplace :
Considérer la nature comme étant complètement indifférente et donner à
chaque pluviosité la même probabilité de réalisation. Adopter la décision
qui maximise l’espérance mathématique du gain. C’est la décision d 3.

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 59

Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
4. Critère de Hurwitz :
Consiste à choisir la décision qui rend max la
H (d i ) M i  (1   )mi
fonction H :
vec 0≤α≤1
est le degré d’optimisme
Mi désigne le gain maximum pour la décision di
mi désigne le gain minimum pour la décision di Pluviosité
peut être considéré comme degré d’optimisme sèche moyenne pluvieuse
si α=0 on retrouve le critère pessimisted1=10 10.000 12.500 10.000
si α=1 on retrouve le critère optimiste d2=15 9.500 15.000 15.000
d3=20 9.000 14.000 20.000
5. Critère de Savage (ou du minimax) :
Obligation de définir une nouvelle matrice dont chaque élément représente
l’écart entre le gain réalisé et celui qui aurait pu être obtenu : « matrice des
regrets » et y appliquer le critère du minimax.
Pluviosité
sèche moyenne pluvieuse
d1=10 0 2.500 10.000 10.000
d2=15 500 0 5.000 5.000
d3=20 1.000 1.000 0 1.000 
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 60
Civil
 Chap. II Éléments de la théorie de jeux et
6. Critère de Bayes : stratégies
Exploitation des informations sur les états possibles de la nature…
Prendre la décision qui maximise l’espérance mathématique du gain :
Multiplier toutes les colonnes par α1, α2 et α3 avec α1+ α2+ α3=1

!
Laplace donne à chaque état de la nature une même
probabilité de réalisation. Ici, l’état de la nature est plus ou
moins connu.
II.5. Conclusion

Un même problème peut être abordé avec des critères différents.

Si plusieurs critères conduisant à la même décision, celle-ci sera
« bonne ». Sinon les points faibles et les points forts pour chaque
décision pourront conduire à un compromis.

Exercice : jeu avec point de selle (page 68)

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 61

Civil
 Chap. II Éléments de la théorie de jeux et
stratégies
Fonctions et touches à utiliser :
- MAX(Série Nbres)
- MIN(Série Nbes)
- ABS(Nbre)
- Mise en forme conditionnelle
- F4 (calcul de la matrice de regret)

Pluviosité Critères
Hurwitz
Sèche Moyenne Pluvieuse Minimax Maximax Laplace α=0,3 Minimax Bayes
1 10000 12500 10000 10000 12500 10833,3 10750 10000
Stratégies 2 9500 15000 15000 9500 15000 13166,7 11150 5000
3 9000 14000 20000 9000 20000 14333,3 12300 1000
Décisions 10000 20000 14333,3 12300 1000

10000 12500 10000 0 2500 10000

9500 15000 15000 500 0 5000

9000 14000 20000 1000 1000 0

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 62

Civil
 Chap. III Théorie des graphes et
applications
III.1. Notions et rappels mathématiques sur la théorie des graphes

Considérons un ensemble finiX x1 , x2 ,..., xn et une application multivoque

( X , )
définie sur cet ensemble. On dit que le couple
constitue un graphe G d’ordre n. On peut représenter un graphe à l’aide
d’un dessin : « représentation sagittale du graphe ».

B C
x2 x3

A x4 F
x1 x6
D

x5
E

 A chaque élément de X on fait correspondre un point appelé sommet du

graphe
que l’on repère par le même symbole que l’élément de X correspondant
;
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 63
Civil
 Chap. III Théorie des graphes et
B
applications
C
x2 x3

A x4 F
x1 x6
D

x5
E

Deux sommets xi et xj sont ensuite reliés par une flèche allant de xi vers xj 
sixxji .
Cette flèche appelée arc du graphe matérialise la relation entre les deux
éléments xi et xj de l’ensemble X ;
 Si (xi,xj) est un arc appartenant à Γ, xi est appelé extrémité initiale de
l’arc, xj
extrémité terminale de l’arc.
 Si xi =sommets
Deux xj, ce couple
sontest
ditsappelé une boucle
adjacents s’ils sont extrémités d’un même arc.
Deux arcs
sont dits adjacents s’ils on en commun un sommet.
Un sommet est dit isolé s’il n’est extrémité que d’une boucle
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 64
Civil
 Chap. III Théorie des graphes et
Sur la figure on voit que :
applications
B C
x2 x3

X x1 , x2 , x3, x4, x5, x6 

x1 x2 , x4 , x5  x2 x2 , x3 

A x4 F
x1 x6
D

x3 x1 , x2 , x4 , x5  x4 x5 , x6  x5

E

5 x5 , x6  des arcs

xL’ensemble 6 x2 , x3  complètement l’application du graphe,
xdétermine
tout comme
l’application Γ détermine l’ensemble U des arcs du graphe; pour cette
raison on peut
écrire indifféremment le graphe sous la forme G={X, Γ} ou sous la forme
 Au
G=
graphe
{X, U}.
d’ordre n :
G on peut associer une matrice carrée
M  a i
j
 
i i j  
définie para j 1 si x , x  U , et a j 0 si x , x  U
i i j   Indice inférieure=ligne
Indice supérieure=colonne
 Cette matrice est dite « matrice associée au graphe ». Elle le définit
complètement.
Elle peut être soit littérale (latine) ou booléenne
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 65
Civil
 Chap. III Théorie des graphes et
applications B C
La matrice associée au graphe de la figure est :
x x 2 3

Matrice booléenne A x4 F
x1 x6
D

x5
E

Matrice latine

 Un graphe est dit sans boucle lorsque

la
diagonale principale de la matrice qui
lui est
associée nej contient
 Lorsque on que
dit des
qu’il zérosune boucle
existe
ai 1
: en xi
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 66
Civil
 Chap. III Théorie des graphes et
III.2. Notions de chemin etapplications
de
circuit
- On appelle chemin, une séquence d’arcs ou suite ordonnée d’arcs telle
que
l’extrémité terminale de chaque arc coïncide avec l’extrémité initiale de
 L’extrémité initiale du 1er arc est
l’arc suivant
d appelée extrémité initiale du
b chemin;
c  L’extrémité terminale du dernier
a
est appelée extrémité terminale
du chemin.

Extrémité initiale du chemin Extrémité terminale du chemin

Un chemin est dit simple s’il n’emprunte pas 2 fois le même arc

x2 x3
x1 x2 x4 x3 x2 x4 x5 n’est pas simple
x1 x5
x4

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 67

Civil
 Chap. III Théorie des graphes et
- Un chemin est dit élémentaire lorsqu’il ne passe qu’une et une seule
fois par applications
chacun des sommets qui le composent ou encore, s’il ne passe pas 2 fois
par le
même sommet x1 x2 x4 x3 x2 x6
x2 x 3
n’est pas
élémentaire
x1 x5
x4 x1 x2 x4 x3 x2 x4 x5
x6 n’est pas simple

Un chemin dont les 2 extrémités coïncident est appelé circuit

- On appelle longueur d’un chemin, le nombre de ses arcs (chaque arc
étant compté
autant de fois qu’il est emprunté)
N.B : - Un chemin ou circuit qui passe une fois et une seule par chaque sommet du
graphe est appelé hamiltonien. Il peut être caractérisé par la double propriété : être
élémentaire et de longueur n, dans le cas d’un circuit, ou n – 1, dans le cas d’un
chemin, n étant l’ordre du graphe. On utilisera avec profit, pour la recherche des
chemins et circuits hamiltoniens, la méthode de composition latine décrite par A.
Kaufmann et Y. Malgrange

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 68

Civil
 Chap. III Théorie des graphes et
III.3. Applications applications
La théorie des graphes est fortement exploitée dans les domaines
suivants :
 Recherche de chemins hamiltoniens dans un graphe ou réseau ;
 Recherche de chemins de valeur optimale ;
 Problèmes de transport et d’affectation ;
!
Dans ce cours on se
 Problèmes de flot maximal ; limitera à quelques
 Problèmes d’ordonnancement cas seulement
III.4. Recherche de chemins hamiltoniens
III.4.1. Définition
Le chemin hamiltonien est le plus long chemin élémentaire dans un
graphe.
On peut rencontrer plusieurs chemins hamiltoniens dans un graphe.
III.4.2. Rappel de relations dans un graphe
l’addition de deux chemins est une notion ensembliste de ces deux chemins
(a,b,c)+(e,f,i)  (a,b,c) et (e,f,i)
- la multiplication de deux chemins est la concatenation de ces chemins
(a,b,c).(c,e,f)  (a,b,c,e,f)
Pour multiplier deux matrices, il faut que le nombre de colonnes de la
1ère matrice soit égale au nombre de lignes de la 2ème matrice
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 69
Civil
 Chap. III Théorie des graphes et
applications
Rappel sur les applications linéaires - Matrices
 Matrice carrée : Une matrice carrée de dimension n est un tableau de
nombres
réels disposés suivant n lignes et n colonnes

 a11 a12 a13   l1  i : ième ligne
Pour n = 3, on a      
M aij   a21 a22 
a23   l2   C1 C2 C3  j : jème colonne
a 
 31 32 a33   l3 

 Transposée d’une matrice (M͂ ): Matrice obtenue en permutant les

vecteurs lignes et les vecteurs colonnes 
 a11 a 21 a31   C1 
     
~
M aij   a12
~ a 22 
a32   C 2   l1 l 2 l3 
a    
 13 23 a33   C 3 

3 0  5  1 3  0  5  1  2
 Addition de 2 matrices carréesM  1  M '   M ' '  M  M '      
2 4  4 2   2 4   4 2   6 6 
 

 Produit de deux matrices carrées   0   5 

  1,3   1,3  

M .N   4  2     1.0  34  1 5  32   12 11 
  1 3  0  5  0   5    20  44 2 5  42    16  2 
M   N   MN ≠ NM  2,4   2,4  
 2 4 4 2   
  4  2 

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 70

Civil
 Chap. III Théorie des graphes et
applications
Exercices : On donne M1 et M2 et on demande de calculer, en utilisant MS
Excel, les expressions suivantes:
1) M1.M2 2) 1/M1 3) 2M2 4) 1/M1
1 4 2 6  1 3 2 1
   
0 4 2 1  0 3 2 6
M 1  M 2  1
1 2 3 1 2 1 0
   2 
3 1 0 2   4 1 1 2
  2 

1) Produit de deux matrices

Marche à suivre :
) Saisie de la matrice M1 dans une plage (on peut éventuellement la nommer)

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 71

Civil
 Chap. III Théorie des graphes et
Marche à suivre : applications
2) Idem M2

3) Choix de la cellule de la réponse et saisie de la fonction (PRODUITMAT)

4) Définition des éléments de chaque matrice (sélection des plages)
5) Validation (enter) : un seul résultat apparaît dans une cellule (26 dans ce cas)
6) Sélection de la plage de la réponse (partant de la cellule de la formule)
7) Exécution de la touche F2
8) Exécution simultanée des touches MAJ+CTRL+Entrée
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 72
Civil
 Chap. III Théorie des graphes et
Marche à suivre : applications
Autre possibilité (à partir de l’étape 2):
3) Sélection de la plage de la réponse
4) Exécution de la touche F2
5) saisie de la fonction (PRODUITMAT)
6) Exécution simultanée des touches MAJ+CTRL+Entrée

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 73

Civil
 Chap. III Théorie des graphes et
applications
2) Inverse d’une matrice (1/M1)
Marche à suivre :
) Saisie de la matrice M1 dans une plage 3) Exécution de la touche F2
2) Sélection de la plage de la réponse 4) saisie de la fonction (INVERSEMAT)
5) Exécution simultanée des touches MAJ+CTRL+Entrée
3) Produit d’une matrice par un scalaire (2M2)
Marche à suivre :
1) Saisie de la matrice M2 dans une plage
2) Sélection de la plage de la réponse
3) Exécution de la touche F2
4) saisie de la formule du produit (=2*M2)

5) Exécution simultanée des touches MAJ+CTRL+Entrée

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 74
Civil
 Chap. III Théorie des graphes et
applications
III.4.3. Algorithme de KAUFMANN-MALGRANGE

(Permet de rechercher les chemins et circuits hamiltoniens)

1ère étape : Recherche de chemin de longueur 1
- On construit la matrice latine associée M1
- On déduit la matrice déduite M͂ 1 en supprimant les lettres qui se répètent
2ème étape : Recherche de chemin de longueur 2
- On détermine la matrice M2=M͂1.M͂1
- On déduit la matrice déduite M͂ 2 en supprimant les lettres qui se répètent
3ème étape : Recherche de chemin de longueur 3
- On détermine la matrice M3=M͂2.M͂1
- On déduit la matrice déduite M͂ 3 en supprimant les lettres qui se répètent
Kème étape : Recherche de chemin de longueur K
- On détermine la matrice MK=M͂K-1.M͂1 et MK=M͂i.M͂ j avec i+j=K
- On déduit la matrice déduite M͂ K
- Circuit hamiltonien, la dernière étape est n ; s’il existe, il apparaît dans la
diagonale gauche
- Chemin hamiltonien, la dernière étape est n-1
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 75
Civil
 Chap. III Théorie des graphes et
Exemple Déterminer, par la applications
méthode de composition latine, les
chemins et circuits hamiltoniens du graphe suivant
B C
 On commence par construire la matrice latine
correspondante
E
D
A

M1= F G

1ère étape : Recherche de chemin de longueur 1

- On construit la matrice latine associée M1 M͂1
- On déduit la matrice déduite M͂ 1 en =
supprimant les lettres qui se répètent
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 76
Civil
 Chap. III Théorie des graphes et
2ème
applications
étape : Chemin de longueur 2
- On détermine la matrice M2=M͂1.M͂1
- On déduit la matrice déduite M͂ 2

M2=M͂ 1. M͂ 1 X
=

M2 M͂͂2
= =

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 77

Civil
 Chap. III Théorie des graphes et
3ème
applications
étape : Chemin de longueur 3
- On détermine la matrice M3=M͂2.M͂1
- On déduit la matrice déduite M͂ 3
M͂3
=
On obtient les chemins
hamiltoniens en calculant
~ ~
M 6 M 5 x M 1
A B C D E F G
ACGBEBF
ABECDGF ABECDFG
A O O ADFGBEC O ACDFGBE
AGBECDF ACBEDFG
ACBEDGF
BEGFACD BECDFAG
B BECDGFA O BEDGFAC O O
BECGFAD BEDFACG
CBEDGFA CBFAGED CDFAGBE CDFABEG
C O O O
M͂6 CGBEDFA
DGFABEC
CBEGFAD CDGFABE
DGFACBE
CBEDFAG
DFABECG
D O O O O
= EDFACGB
DFAGBEC DFACGBE DFACBEG

EGBCDFA EDGFACB ECGBFAB EDGACBF EDFABCG

E O O
ECDGBFA ECDFAGB EGBFACD ECBFADG
ECDGFAB
FAGBECD FACBEDG
F O O FADGBEC FACDGBE O
FACGBED FABECDG
G GBECDFA O GBEDFAC GFABECD GFACBED O O

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 78

Civil
 Chap. III Théorie des graphes et
applications
On obtient la liste des circuits hamiltoniens en calculant M7=M͂6.M͂ 1
 On obtient une matrice diagonale:
A B C D E F G
ACGBEDFA
ABECDGFA
A
ACBEDGFA
ACBEDGFA
BECFGFAB
BEDGFACB
B
BECDFAGB
BEDFACGB
CBEDGFAC
CGBEDFAC
C
CDFAGBEC
CDGFABEC
DGFABECD
DFAGBECD
D
DGFACBED
DFACGBED
EDFACGBE
es circuits différents sont au nombre de 4 E
EDGFACBE
ECDFAGBE
ECDGFABE
FAGBECDF
FACGBEDF
F
FACBEDGF
FABECDGF
GBECDFAG
GBEDFACG
G
GFABECDG
GFACBEDG

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 79

Civil
 Chap. III Théorie des graphes et
III.5. Recherche de chemins de valeur optimale –
applications
Algorithme de Ford
 Un chemin optimal : est soit minimal soit maximal
Pour chercher le chemin optimal dans un graphe il doit remplir certains critères
graphe doit être sans boucle ;
graphe doit être antisymétrique ; (2 sommets ne doivent pas être reliés par 2 a
graphe doit être simplement connexe (pas de sommet isolé);
graphe doit être valué (c'est-à-dire que les arcs doivent avoir une certaine valeu
entrée du graphe doit avoir 1 seul élément (1 singleton), de même que la sortie
graphe doit être sans circuit.
III.5.1. Chemin de valeur minimale
e
étape : Baptiser tous les sommets et ce, dans n’importe quel ordre
me
étape : - Affecter provisoirement au sommet initial la valeur λa=0
- Aux
3ème étape : Siautres sommets
le graphe on affecte
contient la valeur
n sommets, =+α (xcomprendra
cetteλxétape ≠ a) n–1
sous
étapes. Cette étape consiste à calculer les valeurs
successives λx des
Ce calculsommets.
se fait de la manière suivante :
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 80
Civil
 Chap. III Théorie des graphes et
a) Sous-étape 1 : - Déterminer l’ensemble des descendants directs du
sommet applications
initial a ; on les note Γa+
- Remplacer λy par λa +v(a,y), ssi λy - λa >v(a,y)
b) Sous-étape 2 : - Déterminer l’ensemble des descendants directs du
sommet
suivant b ; on les note Γb+
- Remplacer λx par λb +v(b,x), ssi λx - λb >v(b,x)
c) Sous-étape x : - Déterminer les descendants directs de x ; notés Γx+
- Remplacer λx par λ’x +v(x’,x), ssi λx – λ’x >v(x’,x)

d) Dernière sous-étape (n-1)ème sous étape :

- Déterminer le dernier élément qui est le singleton Z
4ème étape : - Si-dans le graphe
Remplacer il existe
λZ par une oussi
λx +v(x,Z), plusieurs autres relations,
λZ - λx >v(x,Z)
alors il faut
recommencer la 3ème étape chaque fois que cela se présente
et ce, à
partir de la sous-étape (b).
- Continuer avec l’algorithme jusqu’à ce qu’aucun λx ne sera
modifiable.
Ces λx représentent les valeurs minimales des chemins qui vont de a
vers x. Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 81
Civil
 Chap.
5ème étape : - Pour III leThéorie
retrouver chemin, ondes graphes
part du dernier sommetet Z puis on
applications
détermine les prédécesseurs (les ancêtres directs) x de Z, on les
note ΓZ-
- Pour trouver les autres sommets, on recherche les
prédécesseurs x de y
tel que λy – λx = v(x,y); on remonte ainsi jusqu’au sommet
Exemple : On donne le graphe ci-dessous et on demande de trouver le
initial.
plus court
chemin entre a et z par l’algorithme de FORD
 Il y a 7 sommets, d’où la 3ème
d
étape comprendra 7-1= 6 sous
b 8 10 étapes.
5 z  Les différents descendants sont :
2 7

a b, c, d  e z

5 f 6

9 4
a
10
1 b d , e, f  f e, z
2

3
c e
c
e d c, f , z
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 82
Civil
 Chap. III Théorie des graphes et
applications d
 +
+

becdaf
b 8 10
5 z
2 7
Étape Étape 5 f 6
2 3 9 4
a 1
10
2
Γ
a
+ Γ b
+
Γ
c
+ Γ
d
+
Γ
e
+ Γ
f
+

3
c
λa 0 0 e

λb +α 5 a b, c, d 
λc +α 10
Pour b on remplace λb par λa+v(a,b) ssi λb - λa >v(a,b)
λd +α
?
λe +α  λb = λa +α – 0 > 5 Oui
+v(a,b)=0+5=5
λf +α Pour c on remplace λc par λa+v(a,c) ssi λc - λa >v(a,c)
λz +α ?
 λc = λa +α – 0 > 10 Oui
+v(a,c)=0+10=10
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 83
Civil
 Chap. III Théorie des graphes et
applications d
 +
+

becdaf
b 8 10
5 z
2 7
Étape Étape 5 f 6
2 3 9 4
a 1
10
2
Γ
a
+ Γ b
+
Γ
c
+ Γ
d
+
Γ
e
+ Γ
f
+

3
c
λa 0 0 e

λb +α 5 a b, c, d 
λc +α 10
Pour d on remplace λd par λa+v(a,d) ssi λd - λa >v(a,d)
λd +α 2
?
λe +α +α  λd = λa +α – 0 > 2 Oui
+v(a,d)=0+2=2
λf +α +α
λz +α +α

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 84

Civil
 Chap. III Théorie des graphes et
applications d
 +
+

becdaf
b 8 10
5 z
2 7
Étape Étape 5 f 6
2 3 9 4
a 1
10
2
Γ
a
+ Γ b
+
Γ
c
+ Γ
d
+
Γ
e
+ Γ
f
+

3
c
λa 0 0 0 e

λb +α 5 5 b d , e, f 
λc +α 10 10
Pour d on remplace λd par λb+v(b,d) ssi λd - λb >v(b,d)
λd +α 2 2 ?
λe +α +α 14  On garde 2 2–5>8 No
n
λf +α +α Pour e on remplace λe par λb+v(b,e) ssi λe - λb >v(b,e)
λz +α +α ?
 λe = λb +α – 5 > 9 Oui
+v(b,e)=5+9=14
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 85
Civil
 Chap. III Théorie des graphes et
applications d
 +
+

becdaf
b 8 10
5 z
2 7
Étape Étape 5 f 6
2 3 9 4
a 1
10
2
Γ
a
+ Γ b
+
Γ
c
+ Γ
d
+
Γ
e
+ Γ
f
+

3
c
λa 0 0 0 0 e

λb +α 5 5 5 b d , e, f  c e

λc +α 10 10 10
Pour f on remplace λf par λb+v(b,f) ssi λf - λb >v(b,f)
λd +α 2 2 2 ?
λe +α +α 14 13  λf = λb +α – 5 > 7 Oui
+v(b,f)=5+7=12
λf +α +α 12 12 Pour e on remplace λe par λc+v(c,e) ssi λe - λc >v(c,e)
λz +α +α +α +α ?
 λe = λc 14 – 10 > 3 Oui
+v(c,e)=10+3=13
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 86
Civil
 Chap. III Théorie des graphes et
applications d
 +
+

becdaf
b 8 10
5 z
2 7
Étape Étape 5 f 6
2 3 9 4
a 1
10
2
Γ
a
+ Γ b
+
Γ
c
+ Γ
d
+
Γ
e
+ Γ
f
+

3
c
λa 0 0 0 0 0 e

λb +α 5 5 5 5
d c, f , z
λc +α 10 10 10 6
Pour c on remplace λc par λd+v(d,c) ssi λc - λd >v(d,c)
λd +α 2 2 2 2 ?
λe +α +α 14 13 13  λc = λd +v(d,c)=2+4=6 10 – 2 > 4 Oui
λf +α +α 12 12 7 Pour f on remplace λf par λd+v(d,f) ssi λf - λd >v(d,f)
λz +α +α +α +α ?
 λf = λd +v(d,f)=2+5=7 12 – 2 > 5 Oui

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 87

Civil
 Chap. III Théorie des graphes et
applications d
 +
+

becdaf
b 8 10
5 z
2 7
Étape Étape 5 f 6
2 3 9 4
a 1
10
2
Γ
a
+ Γ b
+
Γ
c
+ Γ
d
+
Γ
e
+ Γ
f
+

3
c
λa 0 0 0 0 0 0 e

λb +α 5 5 5 5 5 d c, f , z e z

λc +α 10 10 10 6 6
Pour z on remplace λz par λd+v(d,z) ssi λz - λd >v(d,z)
λd +α 2 2 2 2 2 ?
λe +α +α 14 13 13 13  λz = λd +α – 2 > 10 Oui
+v(d,z)=2+10=12
λf +α +α 12 12 7 7 Pour z on remplace λz par λe+v(e,z) ssi λz - λe >v(e,z)
λz +α +α +α +α 12 12 ?
 On garde 12 12 – 13 > 1 No
n
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 88
Civil
 Chap. III Théorie des graphes et
applications d
 +
+

becdaf
b 8 10
5 z
2 7
Étape Étape 5 f 6
2 3 9 4
a 1
10
2
Γ
a
+ Γ b
+
Γ
c
+ Γ
d
+
Γ
e
+ Γ f
+

3
c
λa 0 0 0 0 0 0 0 e

λb +α 5 5 5 5 5 5 f e, z
λc +α 10 10 10 6 6 6
Pour e on remplace λe par λf+v(f,e) ssi λe - λf >v(f,e)
λd +α 2 2 2 2 2 2 ?
λe +α +α 14 13 13 13 9  λe = λf +v(f,e)=7+2=9 13 – 7 > 2 Oui
λf +α +α 12 12 7 7 7 Pour z on remplace λz par λf+v(f,z) ssi λz - λf >v(f,z)
λz +α +α +α +α 12 12 12 ?
 On garde 12 12 – 7 >6 No
n
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 89
Civil
  +
ecdbaf


Chap. III Théorie des graphes et

Étape Étape applications
Étape
+
+
2 3
c
4

Γa+ Γb+ Γc+ Γd+ Γe+ Γf+ Γc+ Γd+ Γe+ Γf+

0 0 0 0
d c, f , z
λa 0 0 0 0 0
λb +α 5 5 5 5 5 5 5 5 Pour c λc par λd+v(d,c) ssi λc - λd >v(d,c)
λc +α 10 10 10 6 6 6 6 6 ?
6–2>4
λd +α 2 2 2 2 2 2 2 2 No
 On garde 6
λe +α +α 14 13 13 13 9 9 9 n
Pour f λf par λd+v(d,f) ssi λf - λd >v(d,f)
λf +α +α 12 12 7 7 7 7 7 ?
λz +α +α +α +α 12 12 12 12 7–2>5
 On garde 7 No
c e Pour e on remplace λ par λ +v(c,e) ssi λ - λ >v(c,e) n
e c e c
?
 On garde 9 9–6>3 No
n
Cours de Recherche Opérationnelle destiné aux étudiants de 1 Master Ingénieur
er 90
Civil
  +
ecdbaf


Chap. III Théorie des graphes et

Étape Étape applications
Étape
+
+
2 3
c
4

Γa+ Γb+ Γc+ Γd+ Γe+ Γf+ Γc+ Γd+ Γe+ Γf+

0 0 0 0 0
d c, f , z
λa 0 0 0 0 0
λb +α 5 5 5 5 5 5 5 5 5 Pour z λz par λd+v(d,z) ssi λz - λd >v(d,z)
λc +α 10 10 10 6 6 6 6 6 6 ?
12 – 2 > 10
λd +α 2 2 2 2 2 2 2 2 2 No
 On garde 12
λe +α +α 14 13 13 13 9 9 9 9 n

λf +α +α 12 12 7 7 7 7 7 7
λz +α +α +α +α 12 12 12 12 12 10

e z Pour z on remplace λz par λe+v(e,z) ssi λz - λe >v(e,z)

?
 λz = λe +v(e,z)=9+1=10 12 – 9 > 1 Oui
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 91
Civil
  +
ecdbaf


Chap. III Théorie des graphes et

Étape Étape applications
Étape
+
+
2 3
c
4

Γa+ Γb+ Γc+ Γd+ Γe+ Γf+ Γc+ Γd+ Γe+ Γf+

λa 0 0 0 0 0 0 0 0 0 0 0
λb +α 5 5 5 5 5 5 5 5 5 5 Pour z λz par λf+v(f,z) ssi λz - λf >v(f,z)
λc +α 10 10 10 6 6 6 6 6 6 6 ?
10 – 7 > 6
λd +α 2 2 2 2 2 2 2 2 2 2 No
 On garde 10
λe +α +α 14 13 13 13 9 9 9 9 9 n

λf +α +α 12 12 7 7 7 7 7 7 7
λz +α +α +α +α 12 12 12 12 12 10 10

f e, z Pour e on remplace λe par λf+v(f,e) ssi λe - λf >v(f,e)

?
 On garde 9 9–7>2 No
n
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 92
Civil
  +
ecdbaf


Chap. III Théorie des graphes et

Étape Étape applications
Étape
+
+
2 3
c
4
Idem Γf+
Γa+ Γb+ Γc+ Γd+ Γe+ Γf+ Γc+ Γd+ Γe+ Γf+ Γe+ Γf+

λa 0 0 0 0 0 0 0 0 0 0 0 0 0
λb +α 5 5 5 5 5 5 5 5 5 5 5 5
λc +α 10 10 10 6 6 6 6 6 6 6 6 6
λd +α 2 2 2 2 2 2 2 2 2 2 2 2
λe +α +α 14 13 13 13 9 9 9 9 9 9 9
λf +α +α 12 12 7 7 7 7 77 7
7 7
λz +α +α +α +α 12 12 12 12 12 10 10 10 10 La valeur du
chemin minimal
e z Pour z on remplace λz par λe+v(e,z) ssi λz - λe >v(e,z)
est 10

?
 On garde 10 10 – 9 > 1 No
n
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 93
Civil
 Chap. III Théorie des graphes et
Étape 5
applications
Retrouver le chemin en partant du dernier sommet (Z) et en
déterminant les prédécesseurs (les ancêtres directs) x de Z, qu’on
note ΓZ-
Pour trouver les autres sommets, on recherche les prédécesseurs x de
y tel que λy – λx = v(x,y); on remonte ainsi jusqu’au sommet initial.

 d , e, f 
 d
z b 8 10
? 7
5 z
Pour d on vérifie que λz-λd=v(d,z) 10 – 2 = 10
2
5 f 6

8 ≠ 10 9 4
a
?
1
10
2

Pour e on vérifie que λz-λe=v(e,z) 10 – 9 = 1 3

c
On retient e 1=1 e
?
Pour f on vérifie que λz-λf=v(f,z) 10 – 7 = 6
3≠6
e c, b, f 
?
Pour c on vérifie que λe-λc=v(c,e) 9–6=3
3=3 On retient c
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 94
Civil
 Chap. III Théorie des graphes et
applications
e c, b, f  d
?
b
Pour b on vérifie que λe-λb=v(b,e) 9–5=9
8 10
5 z
4≠9 5
2 7
f 6

? 9 4

Pour f on vérifie que λe-λf=v(f,e) 9–7=2 a

10
1
2
On retient f 2=2
3
c

 a, d 
 e
c
? f b, d  ?
Pour a on vérifie que λc-λa=v(a,c) 6 – 0 = 10 7–5=7
6 ≠ 10 Pour b λf-λb=v(b,f)
2≠7
?
Pour d on vérifie que λc-λd=v(d,c) 6–2=4
?
Pour d λf-λd=v(d,f) 7–2=5
On retient d 4=4
5=5
d a, b On retient encore d
? ?
Pour a λd-λa=v(a,d) 2–0=2 Pour b λd-λb=v(b,d) 2 – 5 = 8
On retient a 2=2 -3 ≠ 8
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 95
Civil
 Chap. III Théorie des graphes et
applications
III.5.2. Chemin de valeur maximale
ère
étape : Idem que pour le chemin de valeur minimale
me
étape : - Affecter provisoirement au sommet initial la valeur λa=0
- Aux autres sommets on affecte la valeur λx=-α (x ≠ a)
3ème étape : Cette étape consiste à calculer les valeurs successives de λx de
la
a) Sous-étapemanière suivante :l’ensemble des descendants directs du
1 : - Déterminer
sommet
initial a ; on les note Γa+
- Remplacer λy par λa +v(a,y), ssi λy - λa <v(a,y)
b) Sous-étape 2 : - Déterminer l’ensemble des descendants directs du
sommet
suivant b ; on les note Γb+
- Remplacer λy par λb +v(b,y), ssi λy - λb <v(b,y)
4ème et 5ème étape : Rechercher les chemins de valeur maximale

Exercices : Voir séance des TP

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 96

Civil
 Chap. III Théorie des graphes et
applications
I.6. Recherche du plus court « trajet » : Algorithme de Dijkstra
Trajet : Chaîne, cycle, chemin ou circuit
 On attribue au départ le poids 0 au sommet A (initial) et l’infini à
tous les autres; puis, tant qu’il reste des sommets non sélectionnés
:

i. On regarde tous les sommets non sélectionnés, on sélectionne

le sommet X dont le poids est le plus faible

ii. Pour chaque sommet Y adjacent à X on calcule la somme S :

S = poids de X + poids de l’arête qui relie X à Y

iii. Si S est inférieure au poids de Y (soit un poids déjà calculé, soit

l’infini) on raye le poids marqué et on le remplace par S en
notant le sommet X d’où l’on vient

iv. Si S est supérieure au poids déjà marqué, on ne change rien

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 97

Civil
 Chap. III Théorie des graphes et
applications
II.6. Recherche du plus court « trajet » : Algorithme de Dijkstra
Exemple : On donne le graphe ci-dessous et on demande de trouver le
plus court
trajet entre A et E par l’algorithme de Dijkstra
1ère
étape : on affecte au sommet initial une valeur nulle, à ses sommets
adjacents la valeur des arcs correspondants et à tous les autres sommets
restants une valeur infinie (tans qu’on y sera pas encore passé)
10A
0 B
Partant de A nous
pouvons aller vers F A 10 5
∞
et le poids du trajet C
est 9
9 3
8
9A 13
F 4
15
5

2
E
∞ D ∞
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 98
Civil
 Chap. III Théorie des graphes et
applications
II.6. Recherche du plus court « trajet » : Algorithme de Dijkstra
2ème étape : sélectionner le sommet correspondant au plus court trajet
(l’encadrer ou le mettre en surbrillance), identifier ses sommets adjacents
et calculer le poids du trajet total pour s’y rendre en partant du sommet
initial A
Partant de F nous 10A
pouvons aller vers
B
0
C, D et E;
En allant vers C le
poids total du trajet A 10 5
∞
sera de 12; on C 12F
barre l’infini et on
note 12F 9 3
8
9A 13
F 4
15
5

2
E
D

∞ 24F ∞ 14F
3ème étape : De tous les sommets non encore sélectionnés, identifier et
sélectionner celui de poids minimal et reprendre l’étape N°2
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 99
Civil
 Chap. III Théorie des graphes et
applications
II.6. Recherche du plus court « trajet » : Algorithme de Dijkstra
De tous les sommets non encore
sélectionnés, B est le sommet de De tous les sommets non encore
faible poids : on le sélectionne sélectionnés, C est le sommet de
faible poids : on le sélectionne

Partant de B nous 10A

pouvons aller vers
B
0
∞
C, D et E;
En allant vers C le
poids total du trajet A 10 5
sera de 15; 15 C 12F
étant supérieur à
12 on conserve 12 9 3
et on rejette cette 8
possibilité 9A 13
F 4
15
5

2
De D on ne peut plus aller E
qu’en E et le poids sera de D
16

On retrouve le chemin en lisant

∞ 24F ∞ 14F
16D - 14F – 9A soit E-D-F-A qui 23B De 2 sommets non encore
donne le chemin AF-FD-DE de sélectionnés, D est le sommet de
longueur 16 16D faible poids : on le sélectionne

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 100

Civil
 Chap. III Théorie des graphes et
applications
II.6. Recherche du plus court « trajet » : Algorithme de Dijkstra
B
Cet algorithme peut être résumé dans un A 10 5
tableau de manière suivante : C
9 3
8
13
F 4
15
5

2
E
D
Sommet retenu
Recherches successives à chaque étape
A B C D E F

Départ
0 +∞ +∞ +∞ +∞ +∞ A0
De A vers… 10 +∞ +∞ +∞ 9A F
De F vers…
A 9A10A
10 12 14 24 B
De B vers… A F
12 F F
14 23 C 12F
F F B
De C vers… 14 23 D 14F
F B
De D vers… 16 D E 16D
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 101
Civil
 SEANCE DES TRAVAUX PRATIQUES
Programme linéaire primal et dual
Exercice 1 : Écrire et résoudre le programme dual du programme
suivant
x1 2 1
Max Px  x1  x2
x1  x2 3 2

 x1  x2 1
Règles de passage d’un programme primal à un programme dual
a) Le nombre de variables du dual est égal au nombre de contraintes hors
contraintes logiques du primal et vice-versa;
b) Le vecteur coefficient de la fonction objectif du primal devient vecteur
second membre des contraintes du dual et vice-versa;
c) Les contraintes dans le dual sont de sens opposé à celles du primal;
d) Les variables du dual comme celles du primal ne peuvent être
négatives;
e) Si le primal est un problème à max, le dual est un problème à min, et
on montre qu’à l’optimum, la valeur de la fonction objectif de l’un égale à
la valeur de la fonction objectif de l’autre.
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 102
Civil
 SEANCE DES TRAVAUX PRATIQUES
Programme linéaire primal et dual
Exercice 1 : Écrire et résoudre le programme dual du programme
suivant
x1 2
1
Max Px  x1  x2
x1  x2 3 2

 x1  x2 1
- Deux variables dans le primal  deux contraintes dans le dual 
(règle a)
- Contraintes de sens opposé (règle c) 
1
- Vecteur coefficient de la fonction objectif devient vecteur second 
membre des contraintes (règle b) 2
Dy 2 y1  3 y 2  y3
- Vice-versa (règle b) 1
Min Dy 2 y1  3 y 2  y3
- Max de vient Min (règle b) 1
- Vice-versa (règle a) y1  y2  y3  5
2 x1 1; x2 2 Max Px 
2
Résolution y2  y3 1
3 1 5
y1 0; y2  ; y3  Min D y 
4 4 2
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 103
Civil
 SEANCE DES TRAVAUX PRATIQUES
Exercice 2 : Résolution des équations avec MS Excel
Fonction : « Valeur cible »

On connaît la valeur numérique résultat d'une équation et on cherche les valeurs des inconnues
Principe : Considérer l’équation comme une formule d’Excel et les
inconnues comme des références à des cellules
Utiliser la fonction « valeur cible » qui fait varier la valeur d’une cellule
spécifiée jusqu’à ce qu’une formule dépendant de cette cellule prenne
la valeur souhaitée
 1°: Renseigner les zones cellule à définir, Valeur à atteindre, Cellule à
modifier (réf ou non) et valider
 2°: Choisir la commande valeur cible (menu outils)
 3°: Le bouton Pause permet de rechercher pas à pas

 4°: Lorsque la valeur cible est atteinte, les résultats sont affichés. Sinon :
message d’erreur
 5°: Pour conserver la solution trouvée, cliquer sur OK. Sinon le bouton
Annuler rétablit les valeurs d’origine.
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 104
Civil
 SEANCE DES TRAVAUX PRATIQUES
L’équation peut s’écrire : x2-
Exemple : Résoudre l’équation x -x- 2
x=12
12=0
 1°: Renseigner les zones et valider
 2°: Choisir la commande valeur
cible (menu outils)

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 105

Civil
 SEANCE DES TRAVAUX PRATIQUES
Résoudre :

1) x3-2x2+x-4=0
2) 1,46x4-2,6x3-x-5=0
3) 2x – ln x – 4 = 0 (Rép. 2,45 et 0,019)
4) 2x = 4x (Rép. 0,31 et 4)
5) Log x = 1/x (Rép. 2,506)
6) 4x = cos x (Rép. 0,24)
7) x ln x -14 = 0 (Rép. 7,13)
8) 4x – 7 sin x = 0 (Rép. ±1,73 et 0)
9) ex + e-3x – 4 = 0 (Rép. 1,382 et -0,401)

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 106

Civil
 Chap. III Théorie des graphes et
applications
III.7. Problème d’ordonnancement
On dit que l’on a affaire à un problème d’ordonnancement lorsque, en vue
de la réalisation d’un objectif quelconque, il faut accomplir un ensemble de
tâches (ou opérations) elles-mêmes soumises à un ensemble de contraintes

… il s’agit de l’application des graphes pour optimiser les enchaînements

III.7.1. Types de contraintes
 Contraintes potentielles :

- Contraintes de succession : telle tâche ne peut pas commencer avant que telle
autre ne soit terminée, ou simplement, parvenue à un certain degré d’achèvement

•la tâche i précède la tâche j = succession totale ;

•la tâche i doit être aux 2/3 commencée avant que j commence = succession partielle

- Contraintes de localisation temporelle : telle tâche ne doit pas commencer

avant telle date ou doit être achevée à telle date (disponibilité dans le temps : si
par exemple, un équipement n’est disponible qu’entre les instants t1 et t2)

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 107

Civil
 Chap. III Théorie des graphes et
applications
III.7. Problème d’ordonnancement
III.7.1. Types de contraintes
Formalisation :

Soit di : la durée de la tâche i données

dj : la durée de la tâche j

ti : la date de début de la tâche i inconnues

tj : la date de début de la tâche j

Contraintes : si i précède j, t i + d i  t j  di  t j - t i
si 2/3 i précède j, ti + 2/3 di  tj  2/3 di  tj -ti

d’une manière générale,  ij

di  tj – ti càd  ij  tj - ti (où  ij est une donnée)
 Contraintes disjonctives : exclusion mutuelle car les tâches ne peuvent pas se
faire en même temps (exemple : les tâches i et j utilisent une même ressource (par
exemple une seule machine, …) [ti, ti + di] ∩ [tj, tj + dj] = Ø

 Contraintes cumulatives : les moyens sont limités, en main d’œuvre, en

équipement, en budget
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 108
Civil
 Chap. III Théorie des graphes et
applications
III.7. Problème d’ordonnancement
III.7.1. Types de contraintes
Illustration d’une solution à un problème d’ordonnancement : Diagramme de GANTT

Chronogramme ou calendrier de réalisation d’un chantier

charpentiers
couvreurs Ne pas oublier qu’il existe toujours
plom biers plusieurs solutions (calendriers) et qu’il
m açon s’agit de trouver celle qui est optimale
0 10 20 30 40 50

III.7.2. Méthodes de résolution

Deux méthodes sont principalement utilisées (problèmes à contraintes potentielles) : les méthodes
MPM (française) et PERT (américaine). Leurs buts sont :
- Établir un ordonnancement : en déterminant pour chaque tâche la date t i de début de la tâche i
- Minimiser la durée totale du projet
- Énumérer les tâches critiques : celles qui, si elles subissent un retard, décalent la fin prévue du
projet
- Évaluer les marges des
Cours de tâches non
Recherche critiques destiné aux étudiants de 1 er
Opérationnelle Master Ingénieur 109
Civil
 Chap. III Théorie des graphes et
applications
III.7. Problème d’ordonnancement
III.7.3. Méthode PERT
(Program Evaluation and Review Technic ou Program Evaluation Research Task)
Exemple : Déterminer le chemin critique du graphe de la figure
5
 Les sommets représentent les 9 3
événements et les arcs les opérations 2
6
9
8 5
 Un graphe peut avoir plusieurs 8 6
9

4
chemins critiques (un chemin non

4
10 3 10
5 13
critique peut devenir aussi critique) 1 13 3 6 8
12
 Le projet commence à 1 et se 9

6
5
7
9

13
termine à 12 17

8
4 6
 Sur les arcs on marque une valeur 10
11
4
de durée (1 à 2 = 8 jours) 7

Pour déterminer le chemin critique on détermine les dates au plus tôt et les dates au plus tard
 Date au plus tôt = date au plus tôt E1 : 0 E2 : 0+8=8 E3 : (1-3) 0+13=13 
événement précédent + durée (2-3) 8+4=12
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 110
Civil
 Chap. III Théorie des graphes et
applications 5
9 3
E D au plus tôt D au plus tard 2 9
6
8 5
E1 0 8 6
9

4
10 3 10
E2 8 5 13
1 13 3 6
E3 13 8
12
9

6
5
7
9
E4 20

13
17

8
4 6
E5 17 10
11
4
E6 23 7

E7 37
E4 : (1-4) 0+9=9 E7 : (4-7) 20+10=30
E8 29
(3-4) 13+7=20  (6-7) 23+5=28
E9 (8-7) ? +8= ?
E5 : (2-5) 8+9=17
E10 (8-7) 29 +8= 37 
E11 E6 : (2-6) 8+6=14 E8 : (6-8) 23+3=26
E12 (3-6) 13+10=23  (3-8) 13+6=19

(4-8) 20+9=29
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 111
Civil
 Chap. III Théorie des graphes et
applications
9
5
3
E D au plus tôt D au plus tard 2
6
9
8 5
8 6
E1 0 9

4
10 3 10
5 13
E2 8 1 13 3 6 8
E3 13 9
12

6
5
7
9

13
E4 20 17

8
4 6
11
E5 17 10
4
7
E6 23
E7 37 E9 : (5-9) 17+3=20
E8 29 (6-9) 23+8=31 E11 : (8-11) 29+13=42 
(3-9) 13+9=22 (4-11) 20+6=26
E9 33 (8-9) 29+4=33  (7-11) 37+4=41
E10 48 E10 : (9-10) 8+6=14
E11 42 (8-10) 29+5=34
E12 : (10-12) 48+13=61 
(11-10) ? + 6= ? (11-12) 42+17=59
E12 61
(11-10) 42 +6= 48 
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 112
Civil
 Chap. III Théorie des graphes et
applications
9
5
3
E D au plus tôt D au plus tard 2
6
9
8 5
8 6
E1 0 9

4
10 3 10
5 13
E2 8 1 13 3 6 8
E3 13 9
12

6
5
7
9

13
E4 20 17

8
4 6
11
E5 17 10
4
7
E6 23
E7 37 38  Date au plus tard = date au plus
tard événement suivant - durée (8-7) 38 – 8 = 30
E8 29 29
E11 : (11-12) 61-17=44 E8 : (8-7) ? – 8 = ?
E9 33 43
(11-10) ? - 6= ? (8-9) 43 – 4 = 39
E10 48 48 (11-10) 48 - 6= 42 
(8-10) 48 – 5 = 43
E11 42 42 E : (10-12) 61-13=48
10
(8-11) 42 – 13 = 29 
E12 61 61 E9 : (9-10) 48 - 5=43 E7 : (7-11) 42 - 4= 38
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 113
Civil
 Chap. III Théorie des graphes et
D au plus tôt
applications 5
E D au plus tard
2 9

E1 0 0 6
10
E2 8 9 1 13 3 6 8
E3 13 13 12

E4 20 20 4
11
E5 17 40 7

E6 23 26
E6 : (6-9) 43 – 8 = 35 E3 : (3-4) 20 – 7 = 13 
E7 37 38 (6-8) 29 – 3 = 26  (3-6) 26 – 10 = 16
E8 29 29 (3-8) 29 – 6 = 23

E9 33 43
(6-7) 38 – 5 = 33
E2 : (2-3) 13 – 4 = 9 
E5 : (5-9) 43 – 3 = 40 (2-5) 40 – 9 = 31
E10 (2-6) 26 – 6 = 20
E11
48
42
48
42 E4 : (4-8) 29 – 9 = 20  E1 : (1-2) 9 – 8 = 1
E12 61 61
(4-7) 38 – 10 = 28
(4-11) 42 – 6 = 36
(1-3) 13 – 13 = 0 
(1-4) 20 – 9 = 11
Les événements qui sont sur le chemin critique sont donc : E 1 - E3 - E4 - E8 - E10 - E11 - E12
Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 114
Civil
 FIN DU COURS
THEORIQUE

Cours de Recherche Opérationnelle destiné aux étudiants de 1 er Master Ingénieur 115

Civil