Introduction à la recherche

opérationnelle
Hejer KHLIF HACHICHA
[email protected]
 2

Plan

• Qu’est ce que la Recherche Opérationnelle ?

• Méthodologie de la RO
• Champs d'application
• Différentes techniques de la RO
• Méthodes de résolution
• Objectif du cours
• Planning du cours
 3

Qu’est ce que la Recherche Opérationnelle ?

• Discipline dont l’objet est d’aider les gestionnaires à

prendre des décisions efficaces et robustes en utilisant
des modèles et des méthodes scientifiques adaptées
pour analyser des situations complexes.

• Ensemble de méthodes (algorithmiques, mathématiques,

modélisation) afin de prendre des décisions optimales ou
proches de l’optimum dans des problèmes complexes, qui
traitent de la maximisation d’un profit ou la minimisation
d’un coût.
 4

Méthodologie de la RO
Détection du
problème

Prise de décision et
implémentation de la Formulation
solution

Validation Modélisation
du modèle

Collecte des
Résolution
données
 5

Sac à dos
 6

Bin Packing
 7

Voyageur de commerce
 8

Tournées de véhicules
 9

Champs d'application
• Production : Ordonnancement et
planification

Exemple1: Définir le programme de

production qui maximiser le profit
selon disponibilité de la main
d’œuvre, demande du marché,
capacité de production, prix de
revient du matériau brut. . .

Exemple 2: Dimensionnement des

ateliers de production
Déterminer le Nombre de ressources
(humaines ou matérielles) minimale
pour satisfaire une demande.
 10

Autres Champs d'application

• Localisation géographique des usines et des entrepôts

• Gestion financière : planification des investissements, choix de

portefeuille, gestion des crédits et emprunts,

• Politique de maintenance du matériel et des équipements,

• Gestion des stocks,

• Marketing : choix de produits, nombre de vendeurs

• Gestion du personnel : recrutement des employés, affectation

des tâches,

• Planification des projets ...

 11

Différentes techniques de la RO
• Théorie des graphes et des réseaux,
• Le problème du plus court chemin,

• Le problème d’arbre de poids minimal:

• Le problème de flot maximal,

• Le problème de flot maximal à coût minimal,

• Le problème de planification de projets

• Programmation mathématique
• Programmation linéaire

• Programmation linéaire en nombres entiers

• Programmation non linéaire

• …

• Théorie des files d’attentes,

• Simulation,
 12

Techniques de résolution
Méthodes exactes
Programme linéaire : Algorithme simplexe
Solveur Cplex
Solveur Excel
Lindo
Théorie des graphes:
Problème de plus cours chemin algorithme de Bellman
Problème de flot max algorithme de Dijikstra

Méthodes approchées : heuristiques et Méta heuristiques

 13

Objectifs du cours

• Apprendre à traduire des problèmes réels en modèles

• Découvrir quelques techniques de modélisation

 14

Planning du cours
• Introduction à la théorie des graphes
• Le problème de plus court chemin:
• Modélisation
• Techniques de résolution
• Planification de projet
• Le problème flot maximale
• Modélisation
• Technique de résolution
• La programmation linéaire
• Modélisation
• Techniques de résolution
• TP
• Solveur Excel
• Solveur Lindo
Théorie des graphe:
concepts de base
 16

Plan
• Introduction
• Classification des problèmes
• Notion de base
 17

Introduction

 Les graphes permettent de modéliser un grand nombre de

problèmes de réseaux (transport, télécommunication, etc.)
ainsi que des problèmes n’ayant en apparence aucun rapport
avec les réseaux physiques (ordonnancement, gestion de
ressources humaines, gestion des approvisionnement etc.).
 18

Classification des problèmes de réseaux

• On distingue principalement 5 classes de problèmes :

• Le problème du plus court chemin,
• Le problème d’arbre couvrant de poids minimal:
• Le problème de flot maximal,
• Le problème de flot maximal à coût minimal,
• Le problème de planification de projets
 19

Le problème du plus court chemin,

7
A
2 2 D 5
4
5 1
O B 3 T
1
E 7
4
C 4
Le problème du plus court chemin (PCC) consiste à déterminer un chemin
joignant deux sommets particuliers : l’origine ou la source S et la destination
ou le puits T, de longueur minimale
 20

Le problème d’arbre couvrant de poids

minimal

7
A
2 2 D 5
4
5
B 3 1 T
O
1
E 7
4
C 4
un arbre couvrant de poids minimal de ce graphe est un arbre
couvrant (sous-ensemble qui est un arbre et qui connecte tous les
sommets ensemble) dont la somme des poids des arêtes est minimale
 21

Problème de flot max

7
A
2 2 D 5
4
5
B 3 1 T
O
1
E 7
4
C 4
Le problème de flot max consiste à déterminer de la capacité maximale du flux
qu’on peut transfert depuis un sommet source et vers un sommet donnée ,
 22

Classification des problèmes de réseaux

• On distingue principalement 5 classes de problèmes :

• Le problème du plus court chemin,
• Le problème d’arbre couvrant de poids minimal:
• Le problème de flot maximal,
• Le problème de flot maximal à coût minimal,
• Le problème de planification de projets
 23

Graphes orientés : Quelques définitions

 Un graphe G=[X,U] est déterminé par la donnée de :

 Un ensemble X dont les éléments sont appelés des sommets ou des nœuds.
N=|X| (le nombre de sommets)  G est dit graphe d’ordre N.

 Un ensemble U dont les éléments u  U sont des couples ordonnés de sommets

appelés des arcs.
u=(i,j)  i extrémité initiale et j extrémité finale de u.

 Un arc dont les extrémités coïncident est appelé une boucle.

u4
2 u3 3 4
u9
u1 u2 U8 est une boucle
u6
u7

u5 5
1 u8
 24

Graphe orienté / Graphe non orienté

• Un arc est dit orienté si le flux correspondant à cet arc est
positif dans un sens et nul dans l’autre : le flux est donc
unidirectionnel.

• Un arc est dit non orienté si le flux correspondant est

bidirectionnel: On parle alors d’arête et non plus d’arc.

• Un graphe est dit orienté si tous ses arcs sont orientés.

Graphes orientés : Quelques définitions
 Le sommet j est un successeur (ou suivant) du sommet i s’il existe un
arc ayant i comme extrémité initiale et j comme extrémité finale.
L’ensemble des successeurs de i est noté i .

i j

 Le sommet i est un prédécesseur (ou précédent) du sommet j s’il

existe un arc ayant i comme extrémité initiale et j comme extrémité
finale. L’ensemble des prédécesseurs de i est noté i-1 .

 i  i-1 constitue l’ensemble des voisins de i.

 Si G=[X,U] est un graphe et si X est connu, G peut être parfaitement

déterminé par la donnée de i (ou i-1 ) pour chaque sommet i.

25
 26

Exemple
 27

Graphe valué

• Soit G=(X,U) ;
u=(i,j)U  l(u) ou lij   appelé longueur de l’arc u.
• On dit alors que le graphe G est valué par les longueurs l(u).
Chaînes - Chemin
• Une chaîne entre 2 nœuds est une séquence d’arêtes telle que
chaque arête de la séquence ait une extrémité commune avec
l’arête précédente et une extrémité commune avec l’arête suivante.

Les arcs (A, B), (B, D) et (E, D)

constituent une chaîne qui relie
A à E.
les arcs (C, A), (A, B) et (B, D)
constituent un chemin allant de
A à E.

• Un chemin est une chaîne dont tous les arcs sont orientés dans
le même sens

31
Cycle - Circuit
• Un cycle est une chaîne dont les extrémités coïncident

les arcs (C, B), (B, D), (E, D) et

(C, E) constituent un cycle

les arcs (A, B), (B, C) et (C, A)

constituent un circuit

• Un circuit est un chemin dont les extrémités coïncident

32
 33

Longueur de chemin

 La longueur d’un chemin µ joignant le sommet i au sommet j

est donnée par :

l (  )   l (u )
7 u

A
2 2 D 5
4
5 1
O B 3 T
1
E 7
4 C 4
Encore quelques définitions importantes
Sous-graphe:

 Soit G=[X,U] un graphe. Etant donné AX, un sous-graphe engendré

par A est le graphe GA dont les sommets sont les éléments de A et dont
les arcs sont les arcs de G ayant leurs deux extrémités dans A.

Le sous-graphe H induit par

l'ensemble A={ b, c, d, g, h } de
sommets.

Si G est le graphe représentant les routes de la Tunisie, celui qui

représente les routes du Cap Bon est un sous-graphe
35
Encore quelques définitions importantes
Graphe partiel:

 Soient G=[X,U] un graphe et VU. Le graphe partiel engendré par V

est le graphe ayant le même ensemble X de sommets que G et dont
les arcs sont ceux de V (on élimine de G les arcs U-V).

Le graphe partiel I défini par

l'ensemble
F={ (a,d), (b,d), (d,e), (e,h), (h,d),
(f,g) } d'arêtes.

Si G est le graphe représentant les routes de la Tunisie, celui qui

représente les routes nationales est un graphe partiel.

36
Problème du plus court
chemin
 38

Longueur de chemin

 La longueur d’un chemin µ joignant le sommet i au sommet j

est donnée par :

l (  )   l (u )
7 u

A
2 2 D 5
4
5 1
O B 3 T
1
E 7
4 C 4
 39

Problème du plus court chemin (PCC)

Définition :
• Le problème de plus court chemin entre deux sommets i et j consiste

à déterminer un chemin µ(i,j), de i à j, de longueur minimale.

• Les longueurs des arcs peuvent correspondre à :

• des distances physiques,
• des coûts de transport,
• des dépenses de construction de l’arc,
• des temps de parcours, …
 40

Problème du plus court chemin (PCC)

Remarque:
 La longueur d’un chemin comprenant un circuit de longueur strictement
négative est non bornée (il suffit d’emprunter ce circuit une infinité de
fois)

 Ce type de circuit est appelé circuit absorbant.

 L’absence d’un circuit absorbant constitue une condition nécessaire à

l’existence d’un chemin de longueur minimale.
 41

Illustration
 Le parc SEERVADA offre à ses visiteurs des circuits de randonnée et des visites
écologiques. Les voitures n’y sont pas admises, seules quelques pistes permettent
aux petits trains transportant les touristes du parc de circuler entre les différents
points de visite. Le point O est l’entrée du parc et le point T représente une très
belle vue panoramique.
Quel est le chemin offrant la distance minimale entre l’entrée et la vue
panoramique?
 Problème de plus court chemin
 42

Exemple 1 : Stratégie de
remplacement d’équipements
• Une étudiante a besoin d’une voiture pour ses 5 années d’études
universitaires. Au début de sa première année (t = 0), elle achète une
voiture neuve et au début de chaque année t, elle a la possibilité de
soit garder sa voiture durant l’année [t, t+1[, soit vendre sa voiture au
prix v(i), où i est l’âge de la voiture au moment de la vente et acheter
une autre neuve au prix p(t). A la fin de sa dernière année d’études,
l’étudiante revendra sa voiture sans en racheter d’autre.
• Le coût annuel de maintenance d’une voiture dépend de son âge i au
début de chaque année t et est désigné par r(i). Les valeurs p(t), v(i)
et r(i) étant supposées actualisées à la date 0, l’objectif est de
déterminer une politique qui permet à l’étudiante de bénéficier d’une
voiture durant les 5 années d’études et ce avec un coût total minimal.

• Montrer que l’objectif revient à déterminer un plus court chemin entre

deux sommets particuliers dans un graphe qu’on précisera.
Exemple 1 : Stratégie de
remplacement d’équipements

0 1 2 … T

• Un sommet est associé à chaque date (T+1 sommets)

• Un arc relie deux sommets i et j  Décision d’acheter une voiture à la
date i et de le vendre à la date j (j>i)
• La longueur d’un arc = coût d’achat + coût de fonctionnement – prix
de vente)

ji
l ij  p( i )   r ( s )  v ( j  i )
s 1

 Politique optimale de remplacement  Plus court chemin

43 de 0 à T
 44

Exemple 1 : Stratégie de
remplacement d’équipements
Age de la voiture (ans) i /Année t 0 1 2 3 4 5
Prix d’achat p(t) 12.000 14.000 15.000 15.000 16.000 -
Prix de récupération (DT) 9.000 6.000 2.000 1.000 0
Coût annuel de maintenance (DT) 2.000 4.000 5.000 9.000 12.000 -