La Recherche Opérationnelle

La recherche
opérationnelle
Cours préparé et présenté par: Mme ZEMMOURI
Plan du cours
I- Définitions
II- Quelques exemples de problèmes

III- Résolution graphique du problème à deux variables
IV- La programmation linéaire
V- La méthode du simplexe
VI- Le simplexe sur Excel
Définitions
La recherche opérationnelle?
 Cambridge Dictionary
Operational research UK (US operations research)
The systematic study of how best to solve problems in
business and industry.
 Wikipedia
Operations research, operational research, or simply
OR, is the use of mathematical models, statistics and
algorithms to aid in decision-making
 Roadef
Recherche Opérationnelle : approche scientifique pour
la résolution de problèmes de gestion de systèmes
complexes.
Science du « comment mieux faire avec moins »
Des outils pour
rationaliser
simuler
optimiser
planifier
l’architecture et le fonctionnement des systèmes
industriels et économiques.
Des modèles pour analyser des situations complexes
Permet aux décideurs de faire des choix efficaces et

robustes
Les outils de RO-AD
aident à trouver
une solution où l’homme n’en trouvait pas
une solution sur des problèmes nouveaux où
l’homme n’a aucune expérience
plusieurs solutions là où l’homme n’en envisageait
qu’une
aident à juger de la qualité d’une solution
aident à confirmer / justifier des décisions
Exemple d’un problème de production.
Une usine fabrique 2 produits P1 et P2 nécessitant des
ressources d’équipement, de main d’oeuvre et de
matières premières disponibles en quantité limitée.
P1 P2 Disponibilité
Equipement 3 9 81
Main d’oeuvre 4 5 55
Matière première 2 1 20
P1 et P2 rapportent à la vente 6 euros et 4 euros par

unité.
Quelles quantités (non entières) de produits P1 et P2
doit produire l’usine pour maximiser le bénéfice total
venant de la vente des 2 produits ?
Pour modéliser ce problème, il va falloir:
1- choisir des variables adaptées.
2-exprimer la fonction à optimiser ( appelée fonction
objectif) en fonction de ces variables.
3- Exprimer les contraintes sur ces variables.
Les variables:
On appelle variable de décision toute quantité utile à la
résolution du problème et dont le modèle doit
déterminer la valeur.
La fonction objectif:
On appelle fonction objectif l’expression qui modélise la

quantité à optimiser en fonction des variables du
problème.
Les contraintes
On appelle contraintes du problème toutes les relations

limitant le choix de valeurs possibles pour les variables.
Application 1
Une fonderie fabrique trois qualités de bronze à partir
de cuivre et d’étain, en proportions variables. Elle
dispose d’une quantité mensuelle de 65 tonnes de cuivre
et de 5 tonnes d’étain.
Qualit Bénéfice brut % cuivre % étain

é (K€/t)
A 2 90 10
B 1,6 93 7
C 1,8 95 5
Quelle production maximise le bénéfice mensuel?

Application 2: Problème du consommateur
On peut acheter 4 types d’aliments, dont la teneur en
glucides et lipides est donnée dans le tableau suivant
(par unité de poids et exprimé en unités convenables)
Type 1 Type 2 Type 3 Type 4
Glucides 2 1 0 1
Lipides 1 2,5 2 4,5
Prix 2 2 1 8
Le problème du consommateur consiste à obtenir au

moindre coût au moins 12 unités de glucides et 7 unités
de lipides
Quelques exemples de problèmes
Problème d’affectation
Une fabrique M a 4 machines et 4 tâches à compléter.
Chaque machine doit lui voir assigner une tâche. Le
temps de mise en œuvre est donné par la table suivante :
T1 T2 T3 T4
Machine 1 14 5 8 7
Machine 2 2 12 6 5
Machine 3 7 8 3 9
Machine 4 2 4 6 10
La fabrique veut minimiser le temps total de mise en
œuvre.
Comment l’aider ?
Problème de transport
Soit un série de villes alimentées en électricité par des
centrales.
La situation est résumée par la table suivante :
Cité 1 Cité 2 Cité 3 Cité 4 Puissance fournie
(GWh)
Centrale 1 8 6 10 9 35
Centrale 2 9 12 13 7 50
Centrale 3 14 9 16 5 40
Demande 45 20 30 30
Ici, les coûts au milieu de la matrice sont ceux de transport
pour
1GWh.
Comment alimenter toutes les villes tout en minimisant les
coût ?
Le problème du sac à dos
Le problème du sac à dos, noté également KP (en

anglais, Knapsack Problem) est un problème
d’optimisation combinatoire. Il modélise une situation
analogue au remplissage d’un sac à dos, ne pouvant
supporter plus d’un certain poids, avec tout ou partie
d’un ensemble donné d’objets ayant chacun un poids et
une valeur.
Les objets mis dans le sac à dos doivent maximiser la
valeur totale, sans dépasser le poids maximum.
Le problème du voyageur de commerce
L’énoncé du problème du voyageur de commerce est

le suivant : étant donné n points (des villes) et les
distances séparant chaque point, trouver un chemin
de longueur totale minimale qui passe exactement
une fois par chaque point et revient au point de
départ.
III- Résolution graphique du problème à
deux variables
Considérons le problème suivant :
Max M = 40x1 + 60x2
sous les contraintes:

2x1 + x2 ≤ 70
x1 + x2 ≤ 40
x1 + 3x2 ≤ 90
x1 ≥ 0
x2 ≥ 0
Problème
Une usine de meubles désire fabriquer de nouveaux
modèles de bureaux M1 et M2. Les temps de
réalisation pour chacun de ces modèles dans les
ateliers de sciage, d’assemblage et de sablage ainsi que
le temps libre dans chacun de ces ateliers sont donnés
dans le tableau ci-dessous. Les profits que la
compagnie peut réaliser pour chacun de ces modèles
sont de 300 euros pour M1 et de 200 euros pour M2
La direction désire déterminer combien de bureaux de
chaque modèle elle doit fabriquer pour maximiser son
profit.
IV- La programmation linéaire
Notations:
1- forme canonique pure
2- Forme standard
3- variables d’écart
Proposition
Tout PL sous forme standard s’écrit de façon équivalente
en un PL sous forme canonique pure et inversement.
Théorème de dualité
Un problème de minimisation en programmation
linéaire est équivalent à un problème de maximisation
dans le sens
Application
Soit le problème de minimisation suivant:
min z = 2x+ 8y
x ≥ 100
y ≥ 100
x+ y ≥ 500
x+ 3y ≥ 900
3x + 2y ≥ 1200
x,y ≥ 0
Trouver le programme dual.
Exercice
Dans un gymnase, un groupe d’élève se charge de la
distribution de pains au chocolat et de croissants lors de
la pause de 10h. Pour pouvoir satisfaire la demande, ils
doivent disposer au minimum de 108 pains au chocolat
et de 96 croissants. Deux boulangers proposent pour le
même prix:
L’un le lot A comprenant 12 pains au chocolat et 8
croissants
L’autre le lot B composé de 9 pains au chocolat et 12
croissants
Déterminer le nombre de lots A et le nombre de lots B
qui doivent être achetés pour satisfaire la demande au
moindre coût.
V- La méthode du simplexe
Pour résoudre matriciellement un problème de
maximisation, les étapes sont :
1) Déterminer la colonne (sauf la dernière) dont
l’élément de la dernière ligne a la plus grande valeur
positive. C’est la colonne du pivot.
2) Déterminer la ligne du pivot en faisant le rapport des
éléments de la dernière colonne sur les éléments
correspondants de la colonne du pivot. La ligne du pivot
étant celle donnant le plus petit rapport non négatif.
3) Rendre le pivot unitaire.
4)Annuler tous les termes de la colonne du pivot.
5) Répéter les quatre premières étapes jusqu’à ce que
tous les éléments de la dernière ligne soient non
positifs.
6) Les colonnes ne contenant qu’un seul élément non
nul sont celles correspondant aux variables dans le
programme ; la valeur de ces variables est donnée dans
la dernière colonne, les variables hors programme
étant nulles.
7) La valeur maximale de la fonction économique (plus
exactement son opposé) est donnée dans la dernière
ligne, dernière colonne.

La Recherche Opérationnelle

Transféré par

Droits d'auteur :

Formats disponibles

La Recherche Opérationnelle

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

La Recherche Opérationnelle

Transféré par

Droits d'auteur :

Formats disponibles

La recherche

II- Quelques exemples de problèmes

Des modèles pour analyser des situations complexes

Permet aux décideurs de faire des choix efficaces et

P1 et P2 rapportent à la vente 6 euros et 4 euros par

On appelle fonction objectif l’expression qui modélise la

On appelle contraintes du problème toutes les relations

Qualit Bénéfice brut % cuivre % étain

Quelle production maximise le bénéfice mensuel?

Le problème du consommateur consiste à obtenir au

Le problème du sac à dos, noté également KP (en

L’énoncé du problème du voyageur de commerce est

Max M = 40x1 + 60x2

sous les contraintes:

Vous aimerez peut-être aussi