Cours de Recherche Operationnel

Recherche opérationnelle
JOUDAR Nour-Eddine
n.joudar@um5r.ac.ma,
2021/2022
JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Sommaire
1 Objectifs de ce cours
2 Introduction
3 Programmation mathématique
3.1 Modélisation mathématique
3.2 Résolution graphique
3.3 Résolution via méthode de simplexe
4 Sur quelques problèmes de théorie des graphes:
4.1 Problème du plus court chemin
4.1 Problème du flot maximal
4.1 Problème du transport

Objectifs du cours
Objectifs du
cours
• S'initier à la modélisation et la résolution de problèmes du monde réel et de
Introduction problèmes d'optimisation surgissant en sciences d’ingénieurs.
• Comprendre les qualités et les limites de différents modèles par rapport aux
Programmation hypothèses, à la complexité et l’effort de résolution.
mathématique • Expérimenter la résolution de problèmes à l'aide de modèles mathématiques en
utilisant les logiciels disponibles, et interpréter correctement les résultats.
Problèmes des • Acquérir les compétences de concevoir des algorithmes à base théories des
graphes
graphes.
• …….

Introduction
‘La recherche opérationnelle peut être définie comme l'ensemble des méthodes et techniques
rationnelles orientées vers la recherche du meilleur choix dans la façon d'opérer en vue
d'aboutir au résultat visé ou au meilleur résultat possible’. [Wikipédia].
Objectifs du
cours
Modélisation
Introduction En Recherche Opérationnelle (RO), modéliser un problème consiste à identifier: les
variables intrinsèques (inconnues), les différentes contraintes auxquelles sont soumises
Programmation ces variables et l'objectif visé (optimisation).
mathématique
Théorie des graphes
Problèmes des
graphes La théorie des graphes est la discipline mathématique et informatique qui étudie
les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces
modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en
référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces
arêtes sont parfois non-symétriques (les graphes sont alors dits orientés) et sont appelés
des flèches.
Programmation
Mathématique

Introduction
La programmation mathématique vise l’étude théorique des problèmes

d’optimisation ainsi que la conception et la mise en œuvre des algorithmes de
résolution.
Objectifs du
cours
Applications : - Systèmes Informatiques, réseaux et ordinateurs,…
- Electronique, automatique, réseaux et télécoms,…
Introduction - Economie: microéconomique, modèles d’entreprise,…
- Chimies, optimisation des procèdes chimiques, chimie
Programmation industrielle…
mathématique
Problèmes des
graphes

Définitions et concepts
Notions de bases
Définition: Programme Mathématique linéaire
Programme linéaire: modèle mathématique dans lequel la

Objectifs du fonction objectif et les contraintes sont linéaires.
cours
Introduction
Un programme mathématique est défini comme suit:
Programmation
mathématique Ou
Problèmes des
graphes
La fonction ‘f’ est appelée la fonction objectif ou fonction économique.

L’ensemble ‘C’ et sont appelées les contraintes (P) ou (P’).

Remarques
Objectifs du
cours • Dans toute la suite nous ne considérons que les programmes linéaires de
type (P). En effet,
Introduction
(1)
Programmation
mathématique • Dans le problème (P), il n’y a pas de contraintes égalités. En effet:
Problèmes des (2)

graphes

Définition
• On appelle solution réalisable ou bonne solution efficace du problème (P),

tout vecteur vérifiant les contraintes de (P).
Objectifs du • On appelle domaine réalisable de (P), l’ensemble de toute les solutions

cours réalisables de (P).
Introduction
• On appelle solution optimale ou optimum global de (P), une solution
réalisable qui minimise f(x) sur l’ensemble de toutes les solutions.
Programmation
mathématique Définition
Problèmes des
On dit que est un minimum local de (P) s’il existe un voisinage de
graphes tel que soit optimum global du problème suivant:

Programme linéaire
Objectifs du
Dans le cas où et où et toutes les et les sont des applications
cours linéaires, on dit qu’il s’agit d’un programme mathématique linéaire. Ce
programme s’écrit sous cette forme:
Introduction
Programmation
mathématique
Problèmes des
graphes Où, , et

Ainsi, un modèle linéaire doit vérifier les conditions suivantes:
❑ Le modèle doit avoir une fonction objectif à minimiser ou maximiser.
❑ La fonction objectif ainsi que les membres de gauches de chacune des

Objectifs du contraintes doivent être des fonctions linéaires.
cours
❑ Toutes les variables doivent être non négatives.

Introduction
❑ Toutes les contraintes s’écrivent avec des égalités ou avec des inégalités
Programmation larges.
mathématique
Autres classes des PM apparaissent dans la littérature à savoir:
Problèmes des
graphes
❑ Programmes mathématiques non linéaires.
❑ Programmes mathématiques quadratiques.
❑ Programmes mathématiques convexes
❑ …….

Modélisation mathématique
Avant de résoudre un problème issu des sciences d’ingénieurs, il faut bien commencer
par sa traduction par des relations mathématiques. Cette tâche exige l’identification de
quelque composantes relatives à ce problème:
Objectifs du
cours
❑ L’ensemble des actions: (Activités ou variables) qui s’offrent à l’agent de
Introduction décision
Programmation ❑ Les contraintes définissant la nature du système à étudier.

mathématique
❑ L’objectif visé exprimé sous forme d’une fonction mathématique
Problèmes des (fonction objectif ou économique)
graphes

Problème 1
Problème du fleuriste
Objectifs du
cours
Un fleuriste dispose de 45 roses, 36 tulipes et 27 marguerites achetées a M MAD.
Il veut offrir a ses clients deux types de bouquets de fleurs:
Introduction
• Type 1: bouquet a 80 MAD composé de 10 roses, 4 tulipes et 2
marguerites.
• Type 2: bouquet a 60 MAD composé de 6 roses, 6 tulipes et 6
Programmation marguerites.
mathématique
Le soucis du fleuriste est de déterminer le nombre du bouquet de chaque type
afin de maximiser son revenu total.
Problèmes des
graphes

Modélisation
Question: quelles sont les informations dont doit disposer le fleuriste pour résoudre
son problème?
Objectifs du
Réponse: Il lui suffit de connaitre le nombre de bouquets à préparer de chaque type.
cours
Variables
Notons par
Introduction ❑ : nombre de bouquets à préparer de type 1.
❑ : nombre de bouquets à préparer de type 2.
Programmation
mathématique
Fonction objectif
Question: quel revenu tirera le fleuriste de la vente de tous les bouquets préparés ?
Problèmes des Réponse: c’est la somme des revenus tirés des deux types des bouquets.
graphes
Le revenu total à tirer de la vente de tous les bouquets préparés est donné par:
(3)
La fonction objectif est donc donnée par:
Objectifs du
cours
Le fleuriste souhaite augmenter le maximum possible son revenu. Il lui suffirait
de laisser augmenter ou pour que z prenne une valeur aussi grande qu’il
Introduction
le souhaite.
(4)
Programmation
mathématique
Remarque: il y a bien sur des empêchement naturels, appelées les contraintes, qui
freinent le rêve d’un profit infini.
Problèmes des
graphes Contraintes
Contrainte de disponibilité: il faut que le nombre des fleurs utilisées de chaque
catégorie ne dépasse pas leur disponibilité .

o Le fleuriste dispose de 45 roses:
(5)
o Le fleuriste dispose de 36 tulipes:
(6)
Objectifs du
cours o Le fleuriste dispose de 27 marguerites:
(7)
Introduction
Contrainte de non négativité et d’intégrité: il faut que le nombre des bouquets soit
un entier positif ou nul: et des entiers
Programmation
mathématique Modèle obtenu
Problèmes des
Solution optimale:
graphes

Problème 2
Problème du régime
(Problème de régime). Le self-service d'un hôtel offre chaque jour à ses clients
Objectifs du quatre plats : plat1, plat2, plat3, plat4. Le prix d'une unité du plat1 vaut 20Dh, du
cours
plat2 vaut 30Dh, du plat3 vaut 40Dh et du plat4 vaut 100Dh. Le tableau suivant
nous donne la quantité de vitamines V1, V2, V3 et V4 dans une unité de chaque
Introduction plat :
Programmation Par unité V1 V2 V3 V4 Question: Un client suit un

mathématique
Plat1 400 3 2 2 régime alimentaire doit
manger au moins : 500
Problèmes des
graphes Plat2 200 2 2 4 unités de V1, 6 unités de
V2, 10 unités de V3 et 8
Plat3 150 0 4 1 unités de V4. Déterminer le
régime qui coûte le moins
Plat4 500 0 4 5 cher?
Problème 3
Problème du régime
(Problème de régime). On désire déterminer la composition, à coût minimal, d’un

Objectifs du aliment pour bétail qui est obtenu en mélangeant au plus trois produits bruts :
cours
orge et arachide.
• La quantité nécessaire par portion est de 400g.
Introduction
• L’aliment ainsi fabriqué devra comporter au moins 30% de protéines et au
plus 5% de ﬁbres.
Programmation
mathématique Quantité par gramme Coût
Problèmes des
Aliment Protéines Fibres Dh/Kg
graphes
orge 0.09 0.02 10.5
arachide 0.60 0.06 40.5

Résolution d’un programme mathématique
Définition
Forme standard d’un programme linéaire
Un programme linéaire est dit mis sous forme standard si toutes les
contraintes du problème sont des contraintes d’égalité.
Objectifs du
cours
Introduction
Où,
Programmation
mathématique
Remarque.
Problèmes des
graphes Nous pouvons toujours mettre un programme linéaire sous forme
standard en introduisant des variables supplémentaires appelées
variables d’écart ou variables de surplus.

Variables d’écarts
Considérons le programme linéaire (P):
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes
Le problème (P) peut être écrit sous la forme standard en ajoutant une variable d’écart à
chaque contrainte.

La forme standard du problème (PL) est alors:
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes
Remarque.
Les problèmes (PL) et (PS) sont équivalents, c’est-à-dire que (PL) et (PS) ont les
mêmes solutions.

Variables de surplus
Considérons le programme linéaire (PL):
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes
Le problème (P) peut être écrit sous la forme standard en ajoutant une variable d’écart a
chaque contrainte.

Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes
Remarque.
mêmes solutions.

Contraintes incompatibles et redondantes
Considérons le programme mathématique suivant:
Objectifs du
cours
Introduction
Avec A une matrice d’ordre (m,n).
Programmation Contraintes incompatibles

mathématique
Si , on dit que les contraintes sont incompatibles lorsque le système Ax=b
Problèmes des n’admet pas de solution.
graphes
Contraintes redondantes
Si , on dit qu’une contrainte est redondante si elle est répétée ou elle forme
une combinaison linéaire d’autres contraintes.

Hyperplans
Objectifs du
cours
Introduction
Programmation
mathématique
La i -ème contrainte donnée par:
Problèmes des
graphes
définit un hyperplan (une droite si n=2) qui divise l’espace en deux demi espace (demi
plans) cet hyperplan est la frontière des demi-espaces.
Un demi-espace est dit fermé ou ouvert selon la frontière en fait partie ou non.

Définitions
Convexité.
Un ensemble C est dit convexe si tout segment de droite dont les extrémités appartiennent à
C est inclus dans C.
Objectifs du
cours Modèle non borné.
Un modèle mathématique est dit non borné si son domaine réalisable est non borné, c.-à-d.,
Introduction
au moins une variable peut tendre vers l’infini sans quitter le domaine réalisable.
Programmation Polytope.
mathématique
Un polytope est un sous-ensemble de qui s’exprime comme l’intersection d’un nombre
Problèmes des fini de demi espaces fermés de .
graphes Un polytope borné est dit un polyèdre
Point extrême.
Un point est dit point extrême du domaine réalisable D si l’on peut pas l’écrire sous forme
une combinaison convexe des deux autre points du domaine D.
Exemple
Objectifs du
cours
Introduction
Programmation
mathématique Dresser le polyèdre associé au problème (P)?
Problèmes des Points extrêmes: (0,0),(6,0), (18,0), (0,6),(0,9)

graphes

Remarques et propriétés
Remarque.
Objectifs du Toute solution réalisable est une combinaison convexe de points extrêmes.
cours
Introduction
Propriété
Programmation Si un modèle mathématique admet une solution optimale, cette solution correspond a un
mathématique point extrême.
Problèmes des Propriété.

graphes
Si le domaine réalisable est borné et non vide, alors le problème associé possède au moins
une solution optimale.

Résolution par énumération explicite (Méthode graphique).
Principe.
Il s’agit de remplacer les points extrêmes dans la fonction objectif, puis chercher celui qui
Objectifs du minimise (maximise) cette fonction.
cours
Introduction
X Z
(6,0) 12
Programmation
mathématique (18,0) 36
Problèmes des (0,6) 30

graphes
(0,9) 45

Résolution par combinaison convexe.
Objectifs du
cours
et soient sont des points extrêmes du problème (P).

Introduction
Principe.
Programmation
mathématique La solution du problème vérifie la condition suivante:
Problèmes des
graphes

Cas particuliers
Cas particuliers: infinité des solutions
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Cas particuliers.
Cas particuliers: solution optimale infinie
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Cas particuliers.
Cas particuliers: aucune solution
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Résolution par combinaison convexe.
Objectifs du
cours
et soient sont des points extrêmes du problème (P).

Introduction
Principe.
Programmation
mathématique La solution du problème vérifie la condition suivante:
Problèmes des
graphes

Exemple
Résoudre les deux programmes mathématiques suivants:
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Méthode de simplexe
Méthode de simplexe matricielle
Forme canonique
Si la fonction objectif doit être maximisée et si toutes les contraintes sont des inéquations
du type < ou = , on dit que le programme linéaire se présente sous une forme canonique.
Objectifs du Matriciellement, un problème de programmation linéaire se présente sous sa forme
cours canonique de la manière suivante :
Introduction Forme canonique.
Programmation
mathématique
Problèmes des
graphes

Forme canonique
Exemple.
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes
Le problème (P) peut être écrit sous la forme standard en ajoutant une variable d’écart à
chaque contrainte.

Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes
Remarque.
mêmes solutions.

Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes
Le problème (P) peut être écrit sous la forme standard en ajoutant une variable d’écart a
chaque contrainte.

Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes
Remarque.
mêmes solutions.

Remarque.
Remarquons qu’avec l’introduction des variables d’écart, tout problème

Objectifs du sous forme canonique possède une forme standard équivalente. Notons
cours
encore que la méthode du simplexe requiert des bi 0. Par conséquent, les
contraintes qui ont un bi négatif doivent être transformées en contraintes
Introduction aux bi positifs. Cette transformation se fait simplement en multipliant la
contrainte par (-1).
Programmation
mathématique
Problèmes des
graphes

Méthode du simplexe
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

La deuxième contrainte s’écrit sous la façon suivante:

Objectifs du
cours
Comme B est non singulière, on obtient

Introduction
Programmation Lorsque toutes les variables hors base sont nulles, , on obtient:
mathématique
Problèmes des
graphes On appelle solution de base la solution :

Objectifs du Lorsque , et on parle de solution réalisable de base

cours
Exemple
Introduction
Programmation
mathématique
Problèmes des
graphes

Principe
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Principe
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Méthode de simplexe tabulaire: Exemple
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Forme standard
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Tableau initiale
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Forme standard
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Variable entrante
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Variable sortante
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Variable sortante
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Etape 5: Pivotage
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Etape 5: Pivotage
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Itération suivante
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Pivotage
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Fin de l’exemple
Objectifs du
cours
Introduction
Programmation
mathématique
Problèmes des
graphes

Cours de Recherche Operationnel

Transféré par

Droits d'auteur :

Formats disponibles

Cours de Recherche Operationnel

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours de Recherche Operationnel

Transféré par

Droits d'auteur :

Formats disponibles

Recherche opérationnelle

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

3.1 Modélisation mathématique

3.2 Résolution graphique

3.3 Résolution via méthode de simplexe

4 Sur quelques problèmes de théorie des graphes:

4.1 Problème du plus court chemin

4.1 Problème du flot maximal

4.1 Problème du transport

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

La programmation mathématique vise l’étude théorique des problèmes

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Définition: Programme Mathématique linéaire

Programme linéaire: modèle mathématique dans lequel la

La fonction ‘f’ est appelée la fonction objectif ou fonction économique.

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Problèmes des (2)

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

• On appelle solution réalisable ou bonne solution efficace du problème (P),

Objectifs du • On appelle domaine réalisable de (P), l’ensemble de toute les solutions

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

❑ Le modèle doit avoir une fonction objectif à minimiser ou maximiser.

❑ La fonction objectif ainsi que les membres de gauches de chacune des

❑ Toutes les variables doivent être non négatives.

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Programmation ❑ Les contraintes définissant la nature du système à étudier.

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

La fonction objectif est donc donnée par:

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Programmation Par unité V1 V2 V3 V4 Question: Un client suit un

(Problème de régime). On désire déterminer la composition, à coût minimal, d’un

arachide 0.60 0.06 40.5

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Considérons le programme linéaire (P):

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

La forme standard du problème (PL) est alors:

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Considérons le programme linéaire (PL):

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

La forme standard du problème (PL) est alors:

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Programmation Contraintes incompatibles

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Problèmes des Points extrêmes: (0,0),(6,0), (18,0), (0,6),(0,9)

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Problèmes des Propriété.

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Problèmes des (0,6) 30

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

et soient sont des points extrêmes du problème (P).

JOUDAR NOUR-EDDINE, cours de recherche opérationnelle, 2021/2022

Cas particuliers: infinité des solutions