Support du cours :
Recherche opérationnelle
Professeur : Mr. Tarik LAKHAL
Année Universitaire : 2021 - 2022
INTRODUCTION
La recherche opérationnelle (aussi
appelée aide à la décision) peut
être définie comme l'ensemble des
méthodes et techniques
rationnelles orientées vers la
recherche de la meilleure façon
d'opérer des choix en vue d'aboutir
au résultat visé ou au meilleur
résultat possible.
http://fr.wikipedia.org/wiki/Recherche_op%C3%A9rationnelle
Objectifs du Cours
Ce cours vise à familiariser
l’étudiant(e) à la recherche
opérationnelle qui consiste à trouver
une solution optimale à un problème
de décision posé via une méthode
adéquate.
➢ Méthodes scientifiques pour résoudre des
problèmes d'optimisation liés aux organisations
du monde réel.
➢ Une discipline à la croisée des mathématiques et
de l'informatique
• Prolongement de l'algorithmique *
• Manipulant des structures plus élaborées :
graphes ...
• Domaine d'application de la théorie de la
complexité algorithmique.
➢ Une boite à outils de méthodes, tant positives
que négatives, pour aborder sainement et
sereinement les problèmes d'optimisation.
*Un algorithme est une suite finie et non-ambiguë d’opérations ou d’instructions permettant
de résoudre un problème.
Problèmes de Prise de décision
l’entreprise
Formulation des modèles mathématiques
(Modélisation)
Traitement des problèmes
(Optimisation)
Interpretations
5
Voyageur de commerce
Un voyageur de commerce, basé à Rabat, doit
visiter ses clients à travers le Maroc, et il
souhaite effectuer la tournée la plus courte
possible.
Instance : n villes avec une matrice de
distances.
Solution : Tournée visitant chaque ville et
revenant au point de départ à Rabat.
6
Domaines d'application
• Conception, configuration et exploitation
de systèmes techniques complexes
(réseaux de communication, systèmes
d'information),
• Gestion de la chaîne logistique.
7
Exemple : La chaîne logistique
Définition 2 :
La fonction logistique de l’entreprise est
d’assurer au moindre coût la coordination
entre l’offre et la demande.
Plus précisément, la logistique “c’est
l’organisation de ce qu’il faut faire depuis
la commande jusqu’à la livraison au client
d’un bien ou service ”.
8
Production :
Maximiser le profit selon la disponibilité de la main
d'œuvre, la demande du marche, la capacité de
production, le prix de revient du matériau brut. . .
Transport :
Minimiser, à titre d’exemple, la distance totale
parcourue selon les quantités de matériaux à
transporter, la capacité des transporteurs, les points de
ravitaillement en carburant. . .
Stock
Le succès d’une organisation est déterminé, entre
autres, par un stockage intelligent.
9
Optimisation
Minimisation
Maximisation
•Les coûts
Profit •Les délais d’exécution (de
production)
Fonction économique (ou fonction objectif)
Soumise à des conditions (Contraintes).
10
Méthodes
Graphiques Algorithmiques
Inconvenient: Algorithme de
Valable en dim 2 Informatique
SIMPLEXE
uniquement
Programmation Logiciels de
Inconvenient:
informatique la R.O.
beaucoup de
calcul
•LINDO.
•Ms-Project
•STORM
11
Bibliographie :
« Précis de recherche opérationnelle Méthodes et exercices
d'application » Robert Faure, Bernard Lemaire, Christophe Picouleau
Collection: Sciences Sup, Dunod 2009 - 6ème édition.
✓ « Exercices Et Problèmes Résolus De Recherche Opérationnelle »
- Tome 3, dunod 2000. roseaux.
✓ « Recherche opérationnelle de gestion » Azoulay. Tome 1, Dunod
1996
✓ « Programmation linéaire par l’exemple » Droesbeke, Hallin et
Lelievre ellipses 1986
✓ « Techniques et application de la recherche opérationnelle » Alain
martel. Gaëtan Morin - 1979
✓ « Programmes, Jeux Et Réseaux De Transport » Claude Berge,
Dunod - 1962
« Invitation à la recherche opérationnelle » Kauffman-Faure Dunod,
✓ « Exercices de recherche opérationnelle » Desbazeille Dunod,
✓ « Outils mathématiques de gestion », Thierry Bertrand Édition
Bertrand-Lacoste
✓ …….
✓ …….
Chapitre I :
La programmation linéaire
• 1. Concepts fondamentaux
• 2. Résolution graphique
• 3. Résolution par l’algorithme de simplexe
• 4. Dualité
• 5. Applications économiques
13
Exemple introductif : Une usine peut produire cinq
produits (notés PROD1 à PROD5). La marge bénéficiaire
unitaire est donnée pour chacun des produits au tableau 1.1.
Chaque produit nécessite le passage par trois étapes de
fabrication. Les temps requis à chaque étape sont donnés
en heures pour chaque produit au tableau 1.2.
Enfin, il faut tenir compte des ressources en
facteurs disponibles données au tableau 1.3.
La question que se pose le gestionnaire de
l’usine est la suivante:
Quelles sont les quantités à fabriquer de chaque
produit pour maximiser le profit net ?
La programmation linéaire
Moyen pour mieux
comprendre la réalité utilisée
pour représenter les propriétés
fondamentales d’un
phénomène version idéale et
épurée.
Modèle
Problème réel formulation mathématique Algorithme solution
Programmation
linéaire
Construction d’un PL
La construction d’un modèle est, en général, une opération
en trois étapes :
1. - Le choix des variables de décision,
2. - L’expression de l’objectif en fonction de ces
variables,
3. - L’expression des contraintes en fonction de ces
variables.
La deuxième étape
• La deuxième étape consiste en la formulation de
l’objectif °.
• Ici, il s’agit de la somme des contributions de chacune
des productions au profit net de l’usine. Elle s’exprime
simplement par :
°L’objectif est la quantité que l’on veut minimiser ou maximiser.
La troisième étape
La formulation des contraintes *.
Ici, il y a trois contraintes générales :
La première concerne la limite d’utilisation des machines à
l’étape 1. Il y a trois machines, utilisées en deux pauses de huit
heures et ceci au maximum six jours par semaine, ce qui
donne un nombre maximum d’heures par semaine :
288 heures
disponibles.
* Les contraintes sont toutes les relations entre les variables qui limitent les valeurs possibles que peuvent prendre ces
variables.
• Une unité de produit 1 demande 12 heures sur machine
à l’étape 1. Si x 1 unités de produit 1 sont produites par
semaine, cela demande 12 x 1 heures sur la machine 1.
Par un raisonnement semblable pour les autres
produits, on obtient finalement la contrainte :
• La deuxième contrainte concerne la limite
d’utilisation des machines à la deuxième étape.
Le nombre maximum d’heures d’utilisation vaut :
et la contrainte s’exprime donc comme suit :
• La troisième contrainte concerne la limite
d’utilisation du personnel à la troisième étape.
• Et donc la contrainte s’exprime comme :
• Enfin, il ne faut pas oublier les contraintes dites de signe, à
savoir que nous ne pouvons pas produire des quantités
négatives:
Enfin, généralement on conclut l’étape de construction du
modèle, en regroupant l’objectif et les contraintes. On
obtient le programme mathématique linéaire suivant :
Exemple minimisation
• On se propose de réaliser une alimentation économique
pour des bestiaux, qui contient obligatoirement 4 sortes
de composants nutritifs, A, B, C et D. L’industrie
alimentaire produit précisément deux aliments M et N qui
contiennent ces composants :
• 1 Kg d’aliment M contient 100 g de A, 100 g de C, 200 g
de D;
• 1 Kg d’aliment N contient 100 g de B, 200 g de C, 100 g
de D.
• Un animal doit consommer par jour au moins 0.4 Kg de
A, 0.6 Kg de B, 2 Kg de C et 1.7 Kg de D. L’aliment M
coûte 10Dh le Kg et N coûte 4Dh le Kg.
•
• Formuler algébriquement le PL ainsi posé.
SOLUTION Exemple minimisation
Résolution d’un programme linéaire
• Selon la nature du PL, il peut être résolu de manières
différentes à savoir :
✓ Représentation graphique (ou méthodes des droites parallèles) c’est
une représentation géométrique plane dans le cas de deux variables
✓ Recensement des sommets de la région admissible
cette méthode est possible tant que le nombre des sommets n’est pas
assez grand, c’est-à-dire, le nombre des variables et des contraintes
reste très limité. On prend le sommet qui optimise la fonction objectif.
✓ Algorithme de simplexe (ou méthode de Dantzig)
cet algorithme est recommandé lorsque le nombre de variables est
quelconque. On distingue deux méthodes : méthode algébrique ou
méthode des tableaux
Résolution graphique: méthodes des droites
parallèles
• Cas d’un problème à deux variables de décision
• (représentation en géométrie plane)
•
Fonction objectif : Droite dans R²
Contraintes : Demi-plans dans R²
Contraintes de non négativité : cadran positif
Région admissible : Intersection des demi-plans de R2
Représentation graphique
•Équation cartésienne d’une droite (D):
• ax + by + c = 0 (a, b) (0,0)
•
•Si a = 0alors y = − c b est une droite horizontale passant par (0, − c b)
•Si b = 0 alors x = − c a est une droite verticale passant par (− c a ,0)
•Si c = 0 alors la droite (D) passe par l’origine
•Équation réduite de la droite (D) : si a 0alors
et b 0
• y = mx + p m0
•avec, m = − a b et p = − c b
•m est le coefficient directeur de (D)
• * Soit la droite (D) : 2x + 3y − 6 = 0
• u = (−3,2) est un vecteur directeur de (D).
•* Pour construire cette droite, il suffit de connaître deux points :
• « Par deux points on ne fait passer qu’une droite et une seule »
•* Déterminons, x 0 3
- la droite x = 1 y 2 0
• - la droite y = −2
•
y y x =1
(D)
A
2 2
1
-3 0 3 x 0 1 3 x
y = −2
• Soit la droite (D) d’équation :
ax + by + c = 0 (a, b ) (0,0)
•Alors, les demi-plans de frontière (D) sont :
•L’ensemble des points de coordonnées (x,y) telles que :
ax + by + c 0
•L’ensemble des points de coordonnées (x,y) telles que :
ax + by + c 0
• Exemple : Résoudre graphiquement 2x + 3y − 6 0
y
• Remarquons que pour l’origine :
2(0) + 3(0) − 6 0
• 2 Donc le demi plan ne contient
pas l’origine
0 3 x
Région admissible (ou faisable ou
possible)
Région limitée par l’ensemble des
équations de contraintes du
Contrainte de non négativité
problème et par les limites des
x2 variables de décision
Il existe 3 types de points admissibles
Point intérieur
Point frontière
Point extrême
Contrainte de non négativité
x1
polyèdre
Région admissible vide
minimiser z = x1 + 2 x2
x2 x1=8
sujet à
1
2 x1 + x2 8
− x + 8 x2 40
8
1
x1 8
6
x1, x2 0
-x1+8x2=40
4
x1
2 4 6 8 10 12 14 16 18
Région admissible bornée
x2
x1
Région admissible non bornée
x2
x1
Solution optimale
une solution une infinité de pas de solution
optimale unique solutions optimales optimale finie
x2 x2 x2
x1 x1 x1
Exemple 1
Région admissible bornée :
une solution optimale unique
x2 maximiser z = x1 + 2 x2
A (2,6) est l’unique sujet à
solution optimale
8
2 x1 + x2 4
Zmax=14 x
A + x2 8
6
1
− x1 + x2 4
x 5
4 1
x1, x2 0
x1
2 5 8
Exemple 2
Région admissible bornée :
une infinité de solutions optimales
x2 maximiser z = 2 x1 + 2 x2
sujet à
8
2 x1 + x2 4
Une infinité de x + x2 8
solutions optimales 1
− x1 + x2 4
x 5
4 1
x1, x2 0
x1
2 5 8
Exemple 3
Région admissible non bornée :
pas de solutions optimales finies
maximiser z = x1 − x2
sujet à
x2 x1=8
1
2 x1 + x2 8
− x + 8 x2 40
1
x1 8
8
x1 , x2 0
6
-x1+8x2=40 Pas de solutions
4
optimales
2
x1
2 4 6 8 10 12 14 16 18
Exemple 4
Région admissible non bornée :
une solution optimale unique
minimiser w = x1 − x2
sujet à
x2 x1=8
B(8,6) est l’unique 1
2 x1 + x2 8
solution optimale − x + 8x 40
1 2
wmin=2 x1 8
8
B x1, x2 0
6
-x1+8x2=40
4
x1
2 4 6 8 10 12 14 16 18
Exemple 5
Région admissible non bornée :
une infinité de solutions optimales
x2 mi z = x1 + 1 / 2 x2
12 sujet à
x1 + x2 8
10 − x + 8 x 40
1 2
8 2 x1 + x2 12
x1, x2 0
6
-x1+8x2=40
Une infinité de
4 solutions optimales
x1
2 4 6 8 10 12 14 16 18
