Recherche Opérationnelle: Introduction, Modélisation Et Résolution Graphique
Recherche Opérationnelle: Introduction, Modélisation Et Résolution Graphique
Recherche Opérationnelle: Introduction, Modélisation Et Résolution Graphique
graphique
I Introduction
II Modélisation
La recherche opérationnelle
• n’est pas une science pour des chercheurs purs, car elle est axée sur la pratique
• est purement quantitative et utilisera donc des techniques quantitatives
• repose sur la construction de modèles n’est pas une science exigeant des qualités de leadership
• est une aide pour la préparation de décisions
• se situe dans un environnement complexe
• est multidisciplinaire et repose sur un travail d’´équipe est performante lorsque la situation est
complexe.
Domaines d’application:
La gestion
des
L’économie systèmes de
santé
D’autres La gestion
La domaines Domaines des
Domaines d’intérêt d’application systèmes
planification d’application La finance
d’entreprise public d’éducation
la résolution
des
Le problèmes
marketing environnem
entaux
• Les problèmes d'organisation rencontrés dans une entreprise ne sont pas mathématiques dans leur nature.
Mais les mathématiques peuvent permettre de résoudre ces problèmes.
• Pour cela, il faut traduire le problème dans un cadre mathématique, cadre dans lequel les techniques de la
recherche opérationnelle pourront s'appliquer. Cette traduction est le modèle du problème, ou ce qu’on
appelle « la modélisation ».
Définition: Un modèle mathématique est une traduction de la réalité pour pouvoir lui appliquer les outils, les
techniques et les théories mathématiques, puis généralement, en sens inverse, la traduction des résultats
mathématiques obtenus en prédictions ou opérations dans le monde réel.
Exemple: lorsqu'on souhaite planifier une tournée, la couleur du véhicule n'a pas d'intérêt. Le statut du
conducteur, la nature du véhicule ou du produit transporté peuvent, eux, en avoir, et seule une
compréhension de l'objectif de l'optimisation de la tournée peut permettre de trancher.
Une des vrais difficultés de départ est de savoir quels éléments doivent être modélisés et Comment Procéder ?
quels sont ceux qui n'ont pas besoin de l'être
-Recherche Opérationnelle- Cr M.OUDMANE
Modélisation et Optimisation:
Ce qui est demandé au chercheur opérationnel, c'est de proposer une meilleure utilisation des ressources, voire une
utilisation optimale.
Les bonnes questions à se poser, face à un problème du type Recherche Opérationnelle, sont les suivantes :
→1: Quelles sont les variables de décision ? C'est-à-dire quels sont les éléments de mon modèle que j'ai le droit de
faire varier pour proposer d'autres solutions ?
→ 2: Quelles sont les contraintes ? Une fois identifiées les variables de décision, quelles sont les valeurs autorisées
pour ces variables ?
→3: Quel est l'objectif ou le critère ? Par exemple: Quelle est la quantité que l'on veut maximiser ou minimiser ?
Une fois le modèle écrit, le chercheur opérationnel va proposer un algorithme de résolution qui
tiendra compte de l'objectif qui lui a été fixé.
• La programmation linéaire est l’une des plus importantes techniques d’optimisation utilisées en recherche
opérationnelle. Ceci est dû à la facilité de la modélisation, à l’efficacité des algorithmes développés et à
l’existence sur le marché de nombreux logiciels.
L’objectif de programmation linéaire est de déterminer l’affectation optimale de ressources rares entre des
activités ou produits concurrents. Les situations économiques demandent souvent qu’on optimise une
fonction sous plusieurs contraintes prenant la forme d’inégalités.
Définition 1: La programmation linéaire peut se définir comme une technique mathématique permettant de
résoudre des problèmes de gestion et particulièrement ceux où le gestionnaire doit déterminer, face à
différentes possibilités, l’utilisation optimale des ressources de l’entreprise pour atteindre un objectif spécifique
comme la maximisation des bénéfices ou la minimisation des coûts
Exemple: La main-d’œuvre, les matières premières, les capitaux, ... qui sont disponibles en quantité limitée et
qu’on veut répartir d’une façon optimale entre un certain nombre de processus de fabrication
L’approche pour résoudre ce type de problèmes sera divisée en deux étapes principales :
➔ a) La modélisation du problème sous forme d’équations ou d’inéquations linéaires qui permettra ainsi
de bien identifier et structurer les contraintes que doivent respecter les variables du modèle ; de plus, on doit
définir l’apport de chaque variable à l’atteinte de l’objectif poursuivi par l’entreprise, ce qui se traduira par
une fonction à optimiser.
➔b) La détermination de l’optimum mathématique à l’aide de certaines techniques propres à la
programmation linéaire.
• La formulation du modèle de programmation linéaire est l’étape la plus délicate de la résolution d’un problème.
Elle nécessite un effort de conception qui doit aboutir à la détermination de trois éléments :
→ 1.Identifier les variables de décision : Identifier les variables du problème à valeur non connues (variable de
décision) et les représenter sous forme symbolique (exp. x1, y1 ).
→ 2. Identifier les Contraintes : Identifier les restrictions (les contraintes) du problème et les exprimer par un
système d’équations linéaires.
→ 3. Identifier la Fonction objectif (économique) : Identifier l’objectif ou le critère de sélection et le représenter
sous une forme linéaire en fonction des variables de décision. Spécifier si le critère de sélection est à maximiser ou
à minimiser.
Fonction objectif
Contrainte 1
Sous
contrainte
Contrainte 2
Contrainte 3
Contraintes de non
négativité
• La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que le décideur doit
valider avant de pouvoir les utiliser pour modéliser son problème. Ces hypothèses sont :
Énoncé:
• Une entreprise fabrique deux produits A et B, en utilisant une machine m et deux matières premières p et q.
On dispose chaque jour de 8 heures de m, de 10 kg de p et de 36 kg de q.
• On suppose que :
— la production d’une unité de A nécessite 2 kg de p et 9 kg de q, et utilise la machine m durant 1 heure ;
— la production d’une unité de B nécessite 2 kg de p et 4 kg de q, et utilise la machine m durant 2 heure ;
— les profits réalisés sont de 50 dh par unité de A et 60 dh par unité de B.
L’objectif que poursuit l’entreprise est de maximiser le profit qu’elle pourra tirer, par jour, de ces 2 produits en
utilisant au mieux ses ressources.
Modélisation du
II III
Identification Identification Identification
problème I des variables
de décision
des
contraintes
de la fonction
objectif
Quelles sont les informations dont doit disposer le gérant de l’entreprise pour Maximiser son profit?
Quel profit l’entreprise retirera-t-elle de la vente de ces deux produits ? Il s’agit d’additionner les bénéfices à tirer
de chacun des 2 produits :
— pour le produit A, elle retire 50 dh par unité et en fabrique x1 unités ; cette production lui rapporte donc un
profit de (50 x1) dh
— de même, la quantité x2 du produit B lui permet de faire un profit de (60 x2) dh. Le profit total à tirer des
deux produits s’élève donc à : (50 x1 + 60 x2) dh
• Nous dénoterons ce profit total par z : z = 50 x1 + 60 x2
• Nous cherchons évidemment à rendre z aussi grand que possible en donnant à x1 et x2 des valeurs
appropriées
→Cette fonction z, qui traduit l’objectif de notre problème, s’appelle fonction objectif ou fonction
économique. Et, comme nous cherchons à rendre z aussi grand que possible, nous écrivons :
Max z = 50 x1 + 60 x
→Contrainte relative à la machine m : Le temps d’utilisation de la machine m pour fabriquer les produits A et
B ne peut excéder les 8 heures disponibles :
→Contrainte de non négativité (positivité): Elles assurent que la solution ne comporte pas des valeurs
négatives (inacceptables).
Énoncé:
Un agriculteur souhaite que son troupeau consomme la plus faible ration quotidienne de trois éléments nutritifs A,
B et C.
Les exigences quotidiennes sont de 16 pour A, 12 pour B et 18 pour C. L’agriculteur achète deux types d’aliments
P et Q :
— une unité de P comprend 2 unités de A, 1 unité de B et 1 unité de C ; et elle coûte 20 dh ;
— une unité de Q comprend 1 unité de A, 1 unité de B et 3 unités de C ; et elle coûte 40 dh.
L’agriculteur cherche la combinaison la moins coûteuse des quantités de P et Q qui respectera l’exigence de
consommation minimale d’éléments nutritifs pour son troupeau .
• Appelons x1 et x2 les quantités des aliments P et Q qu’il faut acheter. L’objectif de l’agriculteur est
évidemment de minimiser le coût total des aliments qu’il faut acheter.
• Mathématiquement cela s’écrit :
• Enfin, il faut pas oublier qu’on peut pas acheter des quantités négatives de P ou Q
Domaine réalisable : Ensemble de tous les jeux de valeurs des variables de décision satisfaisant
toutes les contraintes et restrictions de signe du PL (ensemble des solutions réalisables ou solutions
admissibles).
Solution réalisable : On appelle solution réalisable toute solution vérifie les contraintes du PL (y compris
les contraintes de positivité).
Solution optimale : Solution réalisable qui optimise (max ou min) la fonction ´économique.
Représentation
des lignes de Représentation
Détermination
contraintes et graphique de la
I- l’ensemble des II- fonction III- de la solution
solutions optimale
objectif
réalisables
Rappel de la géométrie:
Chacune des équations aix1 + bix2 = ci définit une droite qui partage le plan en deux demi-plans P1 et P2
d’équation
Chaque contrainte détermine l’un des deux demi-plans (P1) ou (P2) que l’on trouvera en vérifiant si un
point particulier (l’origine (0, 0) par exemple) est contenu dedans ou non
0
0 20 40 60 80 100 120 140
160
140
120
100
80
Région
60
2X1+2X2=240 réalisable
40 ( Polyèdre)
3X1+X2=140
20
0
0 20 40 60 80 100 120 140
Le domaine Hachuré représente le domaine du plan formé par
l’ensemble des points vérifiant toutes les contraintes ( l’ensemble
des solutions réalisables)
• la fonction Z = 25 X1 +15X2 représente pour Z fixé l’équation des courbes de niveau ( de droites de pente -5/3 )
.Maximiser Z revient à déplacer la courbe de niveau le plus loin possible de l’origine puisque les coefficients
X1 et X2 sont positifs.
• Les limites imposées sur X1 et X2 étant données et représentées graphiquement par le domaine des solutions
réalisations. Donc pour maximiser Z, on cherchera la plus haute courbe qui a une intersection non vide avec le
domaines des solutions réalisables. Dans notre Cas c’est le point B sur le graphique
Calculer la valeur
Représentation Localiser toutes de la fonction
des lignes de les solutions de objectif en
contraintes et base ( les points chacun de ces
I- l’ensemble des II- III-
d’intérsection points et
solutions des droites des sélectionner la
réalisables contraintes) solution
optimale
O (0,0) Z=0
A ( 0,120) Z=1800
B( 10,110) Z=1900
A B C (140/3,0) Z=3500/3
O
C
• Énoncé:
Une entreprise a besoin de trois matières premières A, B et C pour fabriquer un produit. Il lui faut au
moins 14 kg de A, 12 kg de B et 18 kg de C. Elle ne peut acheter que les mélanges X et Y .
Le produit X contient 2 kg de A, 1 kg de B et 1 kg de C.
Le produit Y contient 1 kg de A, 1 kg de B et 3 kg de C.
Le produit X coûte 20 dh et Y coûte 40 dh.
Par ailleurs elle ne peut pas acheter plus de 14 kg de X et 16 kg de Y
La question qui se pose est la suivante : "Quelle quantité de X et Y doit-on acheter pour répondre aux
besoins de l’entreprise au moindre coût ?"
• La technique de résolution graphique reste la même, mais, puisqu’il s’agit de la recherche d’un
minimum, la droite la plus proche de l’origine et qui reste en contact avec la région réalisable, fournit
le minimum.