Chapitre 0 :

Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction
Chapitre 0 : Introduction
Exemples

Abdelaziz CHETOUANI
École Nationale de Commerce et de Gestion - Oujda
Département de commerce
Module : Recherche opérationnelle

20 octobre 2020

1/15
 Sommaire

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples 1 Introduction

2 Exemples

2/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

3/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- • La recherche opérationnelle (RO) a commencé juste avant
TOUANI
la seconde guerre mondiale avec la constitution d'équipes
Sommaire de chercheurs en vue d'étudier les problèmes stratégiques
Introduction et tactiques engagées dans les opérations militaires.
Exemples
• L'objectif était de trouver la meilleure allocation des
ressources militaires limitées à travers l'usage de techniques
quantitatives

3/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- • La recherche opérationnelle (RO) a commencé juste avant
TOUANI
la seconde guerre mondiale avec la constitution d'équipes
Sommaire de chercheurs en vue d'étudier les problèmes stratégiques
Introduction et tactiques engagées dans les opérations militaires.
Exemples
• L'objectif était de trouver la meilleure allocation des
ressources militaires limitées à travers l'usage de techniques
quantitatives
• Après la 2GM, plusieurs applications en temps de paix ont
émergé, engendrant l'utilisation de la RO et de la science
du management dans plusieurs industries et activités.
• 1960 : La RO est devenue indispensable dans plusieurs
domaines : commerciales, industriel, télécommunication,
nance, etc..

3/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- • La recherche opérationnelle (RO) a commencé juste avant
TOUANI
la seconde guerre mondiale avec la constitution d'équipes
Sommaire de chercheurs en vue d'étudier les problèmes stratégiques
Introduction et tactiques engagées dans les opérations militaires.
Exemples
• L'objectif était de trouver la meilleure allocation des
ressources militaires limitées à travers l'usage de techniques
quantitatives
• Après la 2GM, plusieurs applications en temps de paix ont
émergé, engendrant l'utilisation de la RO et de la science
du management dans plusieurs industries et activités.
• 1960 : La RO est devenue indispensable dans plusieurs
domaines : commerciales, industriel, télécommunication,
nance, etc..

3/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI
Nature de la recherche opérationnelle
• La recherche opérationnelle est un processus d'aide à la
Sommaire

Introduction
décision impliquant une recherche dans les diérentes
Exemples
opérations et activités des organisations

4/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI
Nature de la recherche opérationnelle
• La recherche opérationnelle est un processus d'aide à la
Sommaire

Introduction
décision impliquant une recherche dans les diérentes
Exemples
opérations et activités des organisations
• Ses méthodes sont appliquées aux problèmes qui portent
sur la conduite et la coordination des opérations (activités)
au sein d'une organisation.

4/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI
Nature de la recherche opérationnelle
• La recherche opérationnelle est un processus d'aide à la
Sommaire

Introduction
décision impliquant une recherche dans les diérentes
Exemples
opérations et activités des organisations
• Ses méthodes sont appliquées aux problèmes qui portent
sur la conduite et la coordination des opérations (activités)
au sein d'une organisation.
• la recherche opérationnelle a été appliquée de manière
extensive dans divers secteurs tels la manufacture, le
transport, la construction, les télécommunications, la
planication nancière, la santé, l'armée et les services
publics (son champ d'action est très large).

4/15
 Introduction

Chapitre 0 :
Introduction Nature de la recherche opérationnelle
Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

5/15
 Introduction

Chapitre 0 :
Introduction Nature de la recherche opérationnelle
• La partie recherche du nom signie que la recherche
Abdelaziz
CHE-
TOUANI
opérationnelle utilise une approche qui ressemble à
Sommaire comment la recherche est conduite dans les disciplines
Introduction scientiques établies. Dans une large mesure, la méthode
Exemples
scientique est utilisée pour analyser le problème en
question.
• La recherche opérationnelle porte sur la gestion pratique de
l'organisation. Elle doit fournir des conclusions positives et
compréhensibles aux décideurs lorsque cela est nécessaire
pour la prise de décision. Elle nécessite de ce fait une
approche pluridisciplinaire

5/15
 Introduction

Chapitre 0 :
Introduction Nature de la recherche opérationnelle
• La partie recherche du nom signie que la recherche
Abdelaziz
CHE-
TOUANI
opérationnelle utilise une approche qui ressemble à
Sommaire comment la recherche est conduite dans les disciplines
Introduction scientiques établies. Dans une large mesure, la méthode
Exemples
scientique est utilisée pour analyser le problème en
question.
• La recherche opérationnelle porte sur la gestion pratique de
l'organisation. Elle doit fournir des conclusions positives et
compréhensibles aux décideurs lorsque cela est nécessaire
pour la prise de décision. Elle nécessite de ce fait une
approche pluridisciplinaire
• La recherche opérationnelle recherche la solution optimale
du problème posé à l'organisation. Elle utilise de ce fait une
approche de système et la solution est fournie grâce à
l'utilisation intensive des ordinateurs.
5/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-

Impacts de la recherche opérationnelle

TOUANI

Sommaire

Introduction

Exemples

6/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-

Impacts de la recherche opérationnelle

TOUANI

Sommaire
• La RO a un impact majeur sur l'amélioration de l'ecience
Introduction
de plusieurs organisations dans le monde.
Exemples

• La RO a apporté une contribution signicative dans

l'accroissement de la productivité des économies des
diérents pays.

6/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-

Impacts de la recherche opérationnelle

TOUANI

Sommaire
• La RO a un impact majeur sur l'amélioration de l'ecience
Introduction
de plusieurs organisations dans le monde.
Exemples

• La RO a apporté une contribution signicative dans

l'accroissement de la productivité des économies des
diérents pays.
• A titre d'illustration une douzaine de pays sont membres de
la Fédération Internationale des Sociétés de
Recherche Opérationnelle (IFORS) avec une société de
RO dans chacun des pays membres.

6/15
 Introduction

Chapitre 0 : Le tableau suivant permet de présenter une meilleure notion de

Introduction
la large application de la RO avec une liste de ses applications
Abdelaziz
CHE- utilisées dans les diérentes organisations.
TOUANI

Sommaire

Introduction

Exemples

7/15
 Introduction

Chapitre 0 :
Introduction
Tentative de dénition
Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

8/15
 Introduction

Chapitre 0 :
Introduction
Tentative de dénition
Abdelaziz • Ensemble de méthodes (algorithmiques, mathématiques, modélisation) an
CHE- de prendre des décisions optimales ou proches de l'optimum dans des
TOUANI
problèmes complexes, qui traitent de la maximisation d'un prot ou la
minimisation d'un coût.
Sommaire
• Ensemble de méthodes d'analyse scientique (maths et info.) des
Introduction
phénomènes d'organisation qui traite de la maximisation d'un prot ou de
Exemples la minimisation d'un coût. La R.O. est un outil d'aide à la décision.

8/15
 Introduction

Chapitre 0 :
Introduction
Tentative de dénition
Abdelaziz • Ensemble de méthodes (algorithmiques, mathématiques, modélisation) an
CHE- de prendre des décisions optimales ou proches de l'optimum dans des
TOUANI
problèmes complexes, qui traitent de la maximisation d'un prot ou la
minimisation d'un coût.
Sommaire
• Ensemble de méthodes d'analyse scientique (maths et info.) des
Introduction
phénomènes d'organisation qui traite de la maximisation d'un prot ou de
Exemples la minimisation d'un coût. La R.O. est un outil d'aide à la décision.

Quelques problèmes de recherche opérationnelle

• Comment aller le plus vite d'Oujda à Rabat, en voiture ?

8/15
 Introduction

Chapitre 0 :
Introduction
Tentative de dénition
Abdelaziz • Ensemble de méthodes (algorithmiques, mathématiques, modélisation) an
CHE- de prendre des décisions optimales ou proches de l'optimum dans des
TOUANI
problèmes complexes, qui traitent de la maximisation d'un prot ou la
minimisation d'un coût.
Sommaire
• Ensemble de méthodes d'analyse scientique (maths et info.) des
Introduction
phénomènes d'organisation qui traite de la maximisation d'un prot ou de
Exemples la minimisation d'un coût. La R.O. est un outil d'aide à la décision.

Quelques problèmes de recherche opérationnelle

• Comment aller le plus vite d'Oujda à Rabat, en voiture ?
• Comment ordonnancer les tâches d'un projet en fonction de la main
d'oeuvre, tout en minimisant sa durée ?

8/15
 Introduction

Chapitre 0 :
Introduction
Tentative de dénition
Abdelaziz • Ensemble de méthodes (algorithmiques, mathématiques, modélisation) an
CHE- de prendre des décisions optimales ou proches de l'optimum dans des
TOUANI
problèmes complexes, qui traitent de la maximisation d'un prot ou la
minimisation d'un coût.
Sommaire
• Ensemble de méthodes d'analyse scientique (maths et info.) des
Introduction
phénomènes d'organisation qui traite de la maximisation d'un prot ou de
Exemples la minimisation d'un coût. La R.O. est un outil d'aide à la décision.

Quelques problèmes de recherche opérationnelle

• Comment aller le plus vite d'Oujda à Rabat, en voiture ?
• Comment ordonnancer les tâches d'un projet en fonction de la main
d'oeuvre, tout en minimisant sa durée ?
• Comment investir ses 1000 dirhams d'économie de sorte à maximiser le
prot obtenu après deux ans ?

8/15
 Introduction

Chapitre 0 :
Introduction
Tentative de dénition
Abdelaziz • Ensemble de méthodes (algorithmiques, mathématiques, modélisation) an
CHE- de prendre des décisions optimales ou proches de l'optimum dans des
TOUANI
problèmes complexes, qui traitent de la maximisation d'un prot ou la
minimisation d'un coût.
Sommaire
• Ensemble de méthodes d'analyse scientique (maths et info.) des
Introduction
phénomènes d'organisation qui traite de la maximisation d'un prot ou de
Exemples la minimisation d'un coût. La R.O. est un outil d'aide à la décision.

Quelques problèmes de recherche opérationnelle

• Comment aller le plus vite d'Oujda à Rabat, en voiture ?
• Comment ordonnancer les tâches d'un projet en fonction de la main
d'oeuvre, tout en minimisant sa durée ?
• Comment investir ses 1000 dirhams d'économie de sorte à maximiser le
prot obtenu après deux ans ?
• Trouver un (plus court) chemin entre deux villes : problème du plus court
chemin dans les graphes

8/15
 Introduction

Chapitre 0 :
Introduction
Tentative de dénition
Abdelaziz • Ensemble de méthodes (algorithmiques, mathématiques, modélisation) an
CHE- de prendre des décisions optimales ou proches de l'optimum dans des
TOUANI
problèmes complexes, qui traitent de la maximisation d'un prot ou la
minimisation d'un coût.
Sommaire
• Ensemble de méthodes d'analyse scientique (maths et info.) des
Introduction
phénomènes d'organisation qui traite de la maximisation d'un prot ou de
Exemples la minimisation d'un coût. La R.O. est un outil d'aide à la décision.

Quelques problèmes de recherche opérationnelle

• Comment aller le plus vite d'Oujda à Rabat, en voiture ?
• Comment ordonnancer les tâches d'un projet en fonction de la main
d'oeuvre, tout en minimisant sa durée ?
• Comment investir ses 1000 dirhams d'économie de sorte à maximiser le
prot obtenu après deux ans ?
• Trouver un (plus court) chemin entre deux villes : problème du plus court
chemin dans les graphes
• Broadcast de coût minimum dans un réseau : problème des arbres
recouvrant de poids minimum.

8/15
 Introduction

Chapitre 0 :
Introduction
Tentative de dénition
Abdelaziz • Ensemble de méthodes (algorithmiques, mathématiques, modélisation) an
CHE- de prendre des décisions optimales ou proches de l'optimum dans des
TOUANI
problèmes complexes, qui traitent de la maximisation d'un prot ou la
minimisation d'un coût.
Sommaire
• Ensemble de méthodes d'analyse scientique (maths et info.) des
Introduction
phénomènes d'organisation qui traite de la maximisation d'un prot ou de
Exemples la minimisation d'un coût. La R.O. est un outil d'aide à la décision.

Quelques problèmes de recherche opérationnelle

• Comment aller le plus vite d'Oujda à Rabat, en voiture ?
• Comment ordonnancer les tâches d'un projet en fonction de la main
d'oeuvre, tout en minimisant sa durée ?
• Comment investir ses 1000 dirhams d'économie de sorte à maximiser le
prot obtenu après deux ans ?
• Trouver un (plus court) chemin entre deux villes : problème du plus court
chemin dans les graphes
• Broadcast de coût minimum dans un réseau : problème des arbres
recouvrant de poids minimum.
• Envoi d'un maximum d'information dans un réseau : problème du ot
maximum.
8/15
 Introduction

Chapitre 0 : Vue d'ensemble de la modélisation d'un problème de recherche opérationnelle

Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

9/15
 Introduction

Chapitre 0 :
• La détection d'un problème : Les nécessités de l'action viennent des
Introduction expériences vécues ; c'est la phase préscientique.
Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

10/15
 Introduction

Chapitre 0 :
• La détection d'un problème : Les nécessités de l'action viennent des
Introduction expériences vécues ; c'est la phase préscientique.
Abdelaziz
• La formulation du problème : Quel est le vrai problème à résoudre ? Quels
CHE- critères permettent de juger si le problème est résolu de façon satisfaisante ?
TOUANI

Sommaire

Introduction

Exemples

10/15
 Introduction

Chapitre 0 :
• La détection d'un problème : Les nécessités de l'action viennent des
Introduction expériences vécues ; c'est la phase préscientique.
Abdelaziz
• La formulation du problème : Quel est le vrai problème à résoudre ? Quels
CHE- critères permettent de juger si le problème est résolu de façon satisfaisante ?
TOUANI • L'élaboration d'un modèle : Représenter les principaux aspects de la
réalité par un ensemble de formules mathématiques, mettant en jeu les
Sommaire variables de décisions concernées et leurs interactions. On lance des
Introduction hypothèses, on élabore une théorie, on écrit un modèle. La phase de
Exemples
conceptualisation, de construction théorique ou la phase de
modélisation.

10/15
 Introduction

Chapitre 0 :
• La détection d'un problème : Les nécessités de l'action viennent des
Introduction expériences vécues ; c'est la phase préscientique.
Abdelaziz
• La formulation du problème : Quel est le vrai problème à résoudre ? Quels
CHE- critères permettent de juger si le problème est résolu de façon satisfaisante ?
TOUANI • L'élaboration d'un modèle : Représenter les principaux aspects de la
réalité par un ensemble de formules mathématiques, mettant en jeu les
Sommaire variables de décisions concernées et leurs interactions. On lance des
Introduction hypothèses, on élabore une théorie, on écrit un modèle. La phase de
Exemples
conceptualisation, de construction théorique ou la phase de
modélisation.
• La collecte des données : Préciser les paramètres du modèle en s'appuyant
sur l'information recueillie dans l'environnement du problème à résoudre. Le
processus peut requérir plusieurs cycles impliquant les étapes 3, 4 et 5.

10/15
 Introduction

Chapitre 0 :
• La détection d'un problème : Les nécessités de l'action viennent des
Introduction expériences vécues ; c'est la phase préscientique.
Abdelaziz
• La formulation du problème : Quel est le vrai problème à résoudre ? Quels
CHE- critères permettent de juger si le problème est résolu de façon satisfaisante ?
TOUANI • L'élaboration d'un modèle : Représenter les principaux aspects de la
réalité par un ensemble de formules mathématiques, mettant en jeu les
Sommaire variables de décisions concernées et leurs interactions. On lance des
Introduction hypothèses, on élabore une théorie, on écrit un modèle. La phase de
Exemples
conceptualisation, de construction théorique ou la phase de
modélisation.
• La collecte des données : Préciser les paramètres du modèle en s'appuyant
sur l'information recueillie dans l'environnement du problème à résoudre. Le
processus peut requérir plusieurs cycles impliquant les étapes 3, 4 et 5.
• La résolution du modèle : Recourir aux méthodes appropriées déjà
disponible si on a réussi à classer le problème parmi ceux pour lesquels, on
connait déjà une méthode d'approche. Sinon, il faut recourir à la simulation
ou inventer une technique de résolution.

10/15
 Introduction

Chapitre 0 :
• La détection d'un problème : Les nécessités de l'action viennent des
Introduction expériences vécues ; c'est la phase préscientique.
Abdelaziz
• La formulation du problème : Quel est le vrai problème à résoudre ? Quels
CHE- critères permettent de juger si le problème est résolu de façon satisfaisante ?
TOUANI • L'élaboration d'un modèle : Représenter les principaux aspects de la
réalité par un ensemble de formules mathématiques, mettant en jeu les
Sommaire variables de décisions concernées et leurs interactions. On lance des
Introduction hypothèses, on élabore une théorie, on écrit un modèle. La phase de
Exemples
conceptualisation, de construction théorique ou la phase de
modélisation.
• La collecte des données : Préciser les paramètres du modèle en s'appuyant
sur l'information recueillie dans l'environnement du problème à résoudre. Le
processus peut requérir plusieurs cycles impliquant les étapes 3, 4 et 5.
• La résolution du modèle : Recourir aux méthodes appropriées déjà
disponible si on a réussi à classer le problème parmi ceux pour lesquels, on
connait déjà une méthode d'approche. Sinon, il faut recourir à la simulation
ou inventer une technique de résolution.
• La validation du modèle : Confronter les conclusions obtenues du modèle
aux opinions des personnes qui ont susamment d'expérience du problème
traité pour apprécier ou critiquer la pertinence de la solution proposée.

10/15
 Introduction

Chapitre 0 :
• La détection d'un problème : Les nécessités de l'action viennent des
Introduction expériences vécues ; c'est la phase préscientique.
Abdelaziz
• La formulation du problème : Quel est le vrai problème à résoudre ? Quels
CHE- critères permettent de juger si le problème est résolu de façon satisfaisante ?
TOUANI • L'élaboration d'un modèle : Représenter les principaux aspects de la
réalité par un ensemble de formules mathématiques, mettant en jeu les
Sommaire variables de décisions concernées et leurs interactions. On lance des
Introduction hypothèses, on élabore une théorie, on écrit un modèle. La phase de
Exemples
conceptualisation, de construction théorique ou la phase de
modélisation.
• La collecte des données : Préciser les paramètres du modèle en s'appuyant
sur l'information recueillie dans l'environnement du problème à résoudre. Le
processus peut requérir plusieurs cycles impliquant les étapes 3, 4 et 5.
• La résolution du modèle : Recourir aux méthodes appropriées déjà
disponible si on a réussi à classer le problème parmi ceux pour lesquels, on
connait déjà une méthode d'approche. Sinon, il faut recourir à la simulation
ou inventer une technique de résolution.
• La validation du modèle : Confronter les conclusions obtenues du modèle
aux opinions des personnes qui ont susamment d'expérience du problème
traité pour apprécier ou critiquer la pertinence de la solution proposée.
• La prise de décision et l'implémentation de la solution : Comment
implémenter la solution obtenue ? Doit-on s'arrêter là ? Il y a ici un retour
possible vers le modèle initial pour le modier ou l'enrichir des observations
faites lors de la phase expérimentale. Une fois les révisions nécessaires
apportées, le modèle enrichi permettra de tirer des conclusions mieux
soutenues.
10/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

11/15
 Introduction

Les deux aspects de la Recherche Opérationnelle sont :

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

11/15
 Introduction

Les deux aspects de la Recherche Opérationnelle sont :

Chapitre 0 :
Introduction
• Dénition d'un modèle mathématique à partir d'un problème réel et
construire un modèle mathématique qui tente d'abstraire l'essentiel du
Abdelaziz
CHE-
problème réel : modéliser le problème sous une forme exploitable.
TOUANI • Résolution de ce modèle mathématique à l'aide d'Algorithmes : Trouver
une meilleur solution (solution optimale du problème examiné : Objectif
Sommaire managérial).
Introduction

Exemples

11/15
 Introduction

Les deux aspects de la Recherche Opérationnelle sont :

Chapitre 0 :
Introduction
• Dénition d'un modèle mathématique à partir d'un problème réel et
construire un modèle mathématique qui tente d'abstraire l'essentiel du
Abdelaziz
CHE-
problème réel : modéliser le problème sous une forme exploitable.
TOUANI • Résolution de ce modèle mathématique à l'aide d'Algorithmes : Trouver
une meilleur solution (solution optimale du problème examiné : Objectif
Sommaire managérial).
Introduction

Exemples

11/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

12/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- La recherche opérationnelle peut être sindé en deux parties :
TOUANI

Sommaire

Introduction

Exemples

12/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- La recherche opérationnelle peut être sindé en deux parties :
TOUANI

La Programmation Linéaire (PL)

Sommaire

Introduction

Exemples

12/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- La recherche opérationnelle peut être sindé en deux parties :
TOUANI

La Programmation Linéaire (PL)

Sommaire
Elle traite des problèmes d'optimisation (Maximisation ou Minimisation) où :
Introduction

Exemples

12/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- La recherche opérationnelle peut être sindé en deux parties :
TOUANI

La Programmation Linéaire (PL)

Sommaire
Elle traite des problèmes d'optimisation (Maximisation ou Minimisation) où :
Introduction
• L'objectif visé est modélisé sous la forme d'une fonction linéaire que l'on
Exemples
cherche à optimiser .

12/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- La recherche opérationnelle peut être sindé en deux parties :
TOUANI

La Programmation Linéaire (PL)

Sommaire
Elle traite des problèmes d'optimisation (Maximisation ou Minimisation) où :
Introduction
• L'objectif visé est modélisé sous la forme d'une fonction linéaire que l'on
Exemples
cherche à optimiser .
• Les contraintes sont modélisées par des équations et/ou des inéquations
linéaires.

12/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- La recherche opérationnelle peut être sindé en deux parties :
TOUANI

La Programmation Linéaire (PL)

Sommaire
Elle traite des problèmes d'optimisation (Maximisation ou Minimisation) où :
Introduction
• L'objectif visé est modélisé sous la forme d'une fonction linéaire que l'on
Exemples
cherche à optimiser .
• Les contraintes sont modélisées par des équations et/ou des inéquations
linéaires.

La théorie des graphes

12/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- La recherche opérationnelle peut être sindé en deux parties :
TOUANI

La Programmation Linéaire (PL)

Sommaire
Elle traite des problèmes d'optimisation (Maximisation ou Minimisation) où :
Introduction
• L'objectif visé est modélisé sous la forme d'une fonction linéaire que l'on
Exemples
cherche à optimiser .
• Les contraintes sont modélisées par des équations et/ou des inéquations
linéaires.

La théorie des graphes

Elle traite des problèmes assez variés qui ont tous une caractéristique commune
de pouvoir être visualisés :

12/15
 Introduction

Chapitre 0 :
Introduction

Abdelaziz
CHE- La recherche opérationnelle peut être sindé en deux parties :
TOUANI

La Programmation Linéaire (PL)

Sommaire
Elle traite des problèmes d'optimisation (Maximisation ou Minimisation) où :
Introduction
• L'objectif visé est modélisé sous la forme d'une fonction linéaire que l'on
Exemples
cherche à optimiser .
• Les contraintes sont modélisées par des équations et/ou des inéquations
linéaires.

La théorie des graphes

Elle traite des problèmes assez variés qui ont tous une caractéristique commune
de pouvoir être visualisés :
• des points représentant des individus, des objets, des situations...
• et qui sont joints par des èches symbolisant les relations qui existent entre
eux.

12/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

13/15
 Exemples

Chapitre 0 :
Introduction
Chemin le plus court / le plus long
Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

13/15
 Exemples

Chapitre 0 :
Introduction
Chemin le plus court / le plus long
Abdelaziz
CHE-
TOUANI
Soit un ensemble de villes et des chemins directs reliant ces villes entre elles.
• Le problème dit "du plus court chemin" consiste à trouver pour une ville de
Sommaire départ donnée et une ville d'arrivée donnée le chemin le plus court qui relie
Introduction
ces deux villes.
• Le problème peut également être de trouver un chemin le plus court pour
Exemples
chaque couple de villes.
• Pour certains problèmes, trouver le plus long chemin entre deux points peut
être intéressant.

13/15
 Exemples

Chapitre 0 :
Introduction
Chemin le plus court / le plus long
Abdelaziz
CHE-
TOUANI
Soit un ensemble de villes et des chemins directs reliant ces villes entre elles.
• Le problème dit "du plus court chemin" consiste à trouver pour une ville de
Sommaire départ donnée et une ville d'arrivée donnée le chemin le plus court qui relie
Introduction
ces deux villes.
• Le problème peut également être de trouver un chemin le plus court pour
Exemples
chaque couple de villes.
• Pour certains problèmes, trouver le plus long chemin entre deux points peut
être intéressant.

Ordonnancement / planication

13/15
 Exemples

Chapitre 0 :
Introduction
Chemin le plus court / le plus long
Abdelaziz
CHE-
TOUANI
Soit un ensemble de villes et des chemins directs reliant ces villes entre elles.
• Le problème dit "du plus court chemin" consiste à trouver pour une ville de
Sommaire départ donnée et une ville d'arrivée donnée le chemin le plus court qui relie
Introduction
ces deux villes.
• Le problème peut également être de trouver un chemin le plus court pour
Exemples
chaque couple de villes.
• Pour certains problèmes, trouver le plus long chemin entre deux points peut
être intéressant.

Ordonnancement / planication
Considérons la gestion d'un projet qui est constitué de diérentes tâches à
réaliser.
• Généralement, il existe une relation d'ordre entre ces tâches.
• Un premier problème consiste à trouver une planication des tâches qui
aboutissent à la réalisation du projet en un minimum de temps.
• Ensuite, il peut être intéressant de détecter les étapes dites "critiques" dont
le moindre retard peut aecter toute la suite du projet.

13/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

14/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz Sac à dos

CHE-
TOUANI

Sommaire

Introduction

Exemples

14/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz Sac à dos

CHE-
TOUANI Un randonneur prépare son sac à dos pour partir en excursion.
• Il veut éviter d'avoir un sac trop lourd en emportant le maximum des objets
Sommaire
utiles.
Introduction • Pour cela, il aecte une valeur quantitative à chaque objet en plus de son
Exemples poids (plus la valeur est importante, plus le randonneur juge l'objet
important).
• Le problème peut donc se formuler de la manière suivante : Trouver
l'ensemble des objets dont la somme des utilités est maximale tout en ne
dépassant pas un poids xé.

14/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz Sac à dos

CHE-
TOUANI Un randonneur prépare son sac à dos pour partir en excursion.
• Il veut éviter d'avoir un sac trop lourd en emportant le maximum des objets
Sommaire
utiles.
Introduction • Pour cela, il aecte une valeur quantitative à chaque objet en plus de son
Exemples poids (plus la valeur est importante, plus le randonneur juge l'objet
important).
• Le problème peut donc se formuler de la manière suivante : Trouver
l'ensemble des objets dont la somme des utilités est maximale tout en ne
dépassant pas un poids xé.

Aectation

14/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz Sac à dos

CHE-
TOUANI Un randonneur prépare son sac à dos pour partir en excursion.
• Il veut éviter d'avoir un sac trop lourd en emportant le maximum des objets
Sommaire
utiles.
Introduction • Pour cela, il aecte une valeur quantitative à chaque objet en plus de son
Exemples poids (plus la valeur est importante, plus le randonneur juge l'objet
important).
• Le problème peut donc se formuler de la manière suivante : Trouver
l'ensemble des objets dont la somme des utilités est maximale tout en ne
dépassant pas un poids xé.

Aectation
• Des modications de postes sont eectuées dans une entreprise.
• Plusieurs personnes doivent être aectées à de nouveaux postes.
• Ainsi, chacun classe par ordre de préférence les postes qu'il veut occuper.
• Le problème ici est d'attribuer à chaque personne un poste tout en essayant
de satisfaire au mieux le souhait de chacun

14/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction

Exemples

15/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction
Flot maximum
Exemples

15/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction
Flot maximum
Exemples
• Soient des châteaux d'eau ayant un débit constant vers un certain nombre
de villes, chacune ayant des besoins quantiés constants.
• L'eau est acheminée à travers des conduits dont le débit maximum est
connu.
• Le problème est de trouver un moyen de satisfaire au mieux les demandes
de chaque ville.

15/15
 Exemples

Chapitre 0 :
Introduction

Abdelaziz
CHE-
TOUANI

Sommaire

Introduction
Flot maximum
Exemples
• Soient des châteaux d'eau ayant un débit constant vers un certain nombre
de villes, chacune ayant des besoins quantiés constants.
• L'eau est acheminée à travers des conduits dont le débit maximum est
connu.
• Le problème est de trouver un moyen de satisfaire au mieux les demandes
de chaque ville.
• En d'autres termes, essayer d'apporter le plus d'eau possible vers les villes.

15/15