Recherche Opérationnelle

Science du <<comment mieux faire avec moins >>

Des outils pour
o Rationaliser
o Simuler
o Optimiser
o Planifier
 Recherche Opérationnelle
Science du <<comment mieux faire avec moins >>
Des outils pour
o Rationaliser
o Simuler
o Optimiser
o 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
 Recherche Opérationnelle
 Une discipline à la croisée des mathématiques et de l’informatique
 Une boite à outils de méthodes, tant positives que négatives, pour aborder sainement et sereinement les
problèmes d’optimisation
 Les outils de RO
o aident à trouver
i. une solution où l’homme n’en trouvait pas
ii. une solution sur des problèmes nouveaux où l’homme n’a aucune expérience
iii. plusieurs solutions là où l’homme n’en envisageait qu’une
o aident à juger de la qualité d’une solution
o aident à confirmer / justifier des décisions
 Recherche Opérationnelle
Domaines d'application
o Conception, configuration et exploitation de systèmes techniques complexes (réseaux de
communication, systèmes d’information)
o Gestion de la chaîne logistique (transports, production, stocks. . . )
i. production: maximiser le profit selon disponibilité de la main d’œuvre, demande du marché,
capacité de production, prix de revient du matériau brut. . .
ii. Transports : minimiser distance totale parcourue selon quantités de matériaux à transporter,
capacité des transporteurs, points de ravitaillement en carburant. . .
o Gestion stratégique d’investissements
 Recherche Opérationnelle
Domaines d'application
o Conception, configuration et exploitation de systèmes techniques complexes (réseaux de
communication, systèmes d’information)
o Gestion de la chaîne logistique (transports, production, stocks. . . )
i. production: maximiser le profit selon disponibilité de la main d’œuvre, demande du marché,
capacité de production, prix de revient du matériau brut. . .
ii. Transports : minimiser distance totale parcourue selon quantités de matériaux à transporter,
capacité des transporteurs, points de ravitaillement en carburant. . .
o Gestion stratégique d’investissements
o Et aussi
santé, instruction publique, voirie, ramassage et distribution de courrier, production et
transport d’énergie, télécommunications, banques, assurances. . .
o Grande importance dans le milieu industriel : production, transport, emploi du temps, finance. . .
 Recherche Opérationnelle
Face à un problème pratique de décision

o Aspects mathématiques
i. contraintes, objectifs, simplifications
o Modélisation
i. graphes, programmation linéaire, …
o Analyse des modèles et résolution
i. étude de complexité : que peut-on espérer pour le temps de résolution imparti ?
ii. mise au point d’algorithmes
 Recherche Opérationnelle
Face à un problème pratique de décision

o Aspects mathématiques
i. contraintes, objectifs, simplifications
o Modélisation
i. graphes, programmation linéaire, …
o Analyse des modèles et résolution
i. étude de complexité : que peut-on espérer pour le temps de résolution imparti ?
ii. mise au point d’algorithmes
o Implémentation et analyse des résultats
i. valider par rapport à la demande
ii. itérer avec le demandeur si nécessaire
o Déploiement des solutions
i. Intégration logicielle
 Recherche Opérationnelle
Programmation lineaire
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Introduction

L’importance de l’optimisation et la nécessité d’un outil simple pour modéliser des problèmes de décision que soit
économique, militaire ou autres on fait de la programmation linéaire un des champs de recherche les plus actifs au
milieu du siècle précédent. Les premiers travaux (1947) sont celle de George B. Dantzig et ses associés du
département des forces de l’air des Etats Unis d’Amérique.
Les problèmes de programmations linéaires sont généralement liés à des problèmes d’allocations de ressources
limitées, de la meilleure façon possible, afin de maximiser un profit ou de minimiser un coût. Le terme meilleur fait
référence à la possibilité d’avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le même
profit. Ces décisions sont en général le résultat d’un problème mathématique.
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Les conditions de formulation d’un PL

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 :
1. Les variables de décision du problème sont positives
2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces variables, c’est à dire,
que la fonction ne peut pas contenir par exemple un produit croisé de deux de ces variables. La fonction qui
représente le critère de sélection est dite fonction objectif (ou fonction économique).
3. Les restrictions relatives aux variables de décision (exemple: limitations des ressources) peuvent être
exprimées par un ensemble d’équations linéaires. Ces équations forment l’ensemble des contraintes.
4. Les paramètres du problème en dehors des variables de décisions ont une valeur connue avec certitude
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Les étapes de formulation d’un PL :

Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d’un programme linéaire :
1. Identifier les variables du problème à valeur non connues (variable de décision) et les représenter sous forme
symbolique (exp. 𝑥𝑥1 , 𝑦𝑦1 ).
2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système d’équations linéaires.
3. 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.
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Présentation Théorique
Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire dite fonction objectif en
satisfaisant certaines équations et inégalités dites contraintes. En langage mathématique, on décrira de tels modèles
de la manière suivante :

Soient N variables de décision 𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥𝑛𝑛 , l’hypothèse que les variables de décision sont positives implique que
𝑥𝑥1 ≥ 0, 𝑥𝑥2 ≥ 0, … , 𝑥𝑥𝑛𝑛 ≥ 0.
La fonction objectif est une forme linéaire en fonction des variables de décision de type
𝑧𝑧 = 𝑐𝑐1 𝑥𝑥1 + 𝑐𝑐2 𝑥𝑥2 + ⋯ + 𝑐𝑐𝑁𝑁 𝑥𝑥𝑁𝑁
où les coefficients 𝑐𝑐1 , … , 𝑐𝑐𝑁𝑁 doivent avoir une valeur bien déterminée (avec certitude) et peuvent être positifs,
négatifs ou nuls. Par exemple le coefficient 𝑐𝑐𝑖𝑖 peut représenter un profit unitaire lié à la production d’une unité
supplémentaire du bien 𝑥𝑥𝑖𝑖 , ainsi la valeur de 𝑧𝑧 est le profit total lié à la production des différents biens en quantités
égales à 𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥𝑁𝑁 ,
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Présentation Théorique
Supposons que ces variables de décision doivent vérifier un système d’équations linéaires définis par M inégalités
𝑎𝑎11 𝑥𝑥1 + 𝑎𝑎12 𝑥𝑥2 + … + 𝑎𝑎1𝑁𝑁 𝑥𝑥𝑁𝑁 ≥ 𝑏𝑏1
𝑎𝑎21 𝑥𝑥1 + 𝑎𝑎22 𝑥𝑥2 + … + 𝑎𝑎2𝑛𝑛 𝑥𝑥𝑁𝑁 ≥ 𝑏𝑏2
…
𝑎𝑎𝑀𝑀1 𝑥𝑥1 + 𝑎𝑎𝑀𝑀2 𝑥𝑥2 + … + 𝑎𝑎𝑀𝑀𝑁𝑁 𝑥𝑥𝑁𝑁 ≥ 𝑏𝑏𝑀𝑀
où les coefficients 𝑎𝑎𝑀𝑀1 , … , 𝑎𝑎𝑀𝑀𝑀𝑀 𝑒𝑒𝑒𝑒 𝑏𝑏1 , … , 𝑏𝑏𝑀𝑀 doivent avoir une valeur bien déterminée (avec certitude) et peuvent
être positifs, négatifs ou nuls. Le paramètre 𝑏𝑏𝑗𝑗 représente la quantité de matière première disponible dont le bien 𝑥𝑥𝑖𝑖
utilise une quantité égale à 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑖𝑖 .
En suivant les étapes de formulation ci-dessus, on peut représenter le PL comme suit :

Max 𝑐𝑐1 𝑥𝑥1 + 𝑐𝑐2 𝑥𝑥2 + ⋯ + 𝑐𝑐𝑁𝑁 𝑥𝑥𝑁𝑁

S.c 𝑎𝑎11 𝑥𝑥1 + 𝑎𝑎12 𝑥𝑥2 + … + 𝑎𝑎1𝑁𝑁 𝑥𝑥𝑁𝑁 ≥ 𝑏𝑏1
𝑎𝑎21 𝑥𝑥1 + 𝑎𝑎22 𝑥𝑥2 + … + 𝑎𝑎2𝑛𝑛 𝑥𝑥𝑁𝑁 ≥ 𝑏𝑏2
…
𝑎𝑎𝑀𝑀1 𝑥𝑥1 + 𝑎𝑎𝑀𝑀2 𝑥𝑥2 + … + 𝑎𝑎𝑀𝑀𝑁𝑁 𝑥𝑥𝑁𝑁 ≥ 𝑏𝑏𝑀𝑀
𝑥𝑥1 ≥ 0, 𝑥𝑥2 ≥ 0, … , 𝑥𝑥𝑛𝑛 ≥ 0
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Exemples de formulations
La tâche de formulation demande généralement une certaine expertise et connaissance du problème pour pouvoir
relever facilement les différentes composantes du problème et ainsi donner un programme qui modélise au mieux la
situation réelle. Dans ce qui suit, on présentera quelques exemples de formulation en programme linéaire liés à
différents problèmes de décision :
 Exemple 1 : Problème d’agriculture

Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de tomates et celles de piments. Il dispose
de 480 heures de main d’oeuvre et de 440 𝑚𝑚3 d’eau. Un hectare de tomates demande 1 heure de main d’oeuvre, 4
𝑚𝑚3 d’eau et donne un bénéfice net de 100 dinars. Un hectare de piments demande 4 heures de main d’oeuvre, 2 𝑚𝑚3
d’eau et donne un bénéfice net de 200 dinars. Le bureau du périmètre irrigué veut protéger le prix des tomates et ne
lui permet pas de cultiver plus de 90 hectares de tomates. Quelle est la meilleure allocation
de ses ressources ?
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Exemple 1 : Problème d’agriculture
Formulation du problème en un PL :
Etape 1 : Identification des variables de décision. Les deux activités que l’agriculteur doit déterminer sont les
surfaces à allouer pour la culture de tomates et de piments :
o 𝑥𝑥1 : la surface allouée à la culture des tomates
o 𝑥𝑥2 : la surface allouée à la culture des piments
On vérifie bien que les variables de décision 𝑥𝑥1 et 𝑥𝑥2 sont positives : 𝑥𝑥1 ≥ 0, 𝑥𝑥2 ≥ 0
Etape 2 : Identification des contraintes. Dans ce problème les contraintes représentent la disponibilité des facteurs de
production :
o Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte liée à la limitation de la surface de
terrain est 𝑥𝑥1 + 𝑥𝑥2 ≤ 150.
o Eau : la culture d’un hectare de tomates demande 4 𝑚𝑚3 d’eau et celle d’un hectare de piments demande 2 𝑚𝑚3
mais l’agriculteur ne dispose que de 440𝑚𝑚3 . La contrainte qui exprime les limitations des ressources en eau est
4𝑥𝑥1 + 2𝑥𝑥2 ≤ 440
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Exemple 1 : Problème d’agriculture
Formulation du problème en un PL :
Etape 2 : (Suite)
o Main d’oeuvre : Les 480 heures de main d’oeuvre seront départager (pas nécessairement en totalité) ente la
culture des tomates et celles des piments. Sachant qu’un hectare de tomates demande une heure de main d’oeuvre
et un hectare de piments demande 4 heures de main d’oeuvre alors la contrainte représentant les limitations des
ressources humaines est 𝑥𝑥1 + 4𝑥𝑥2 ≤ 480.
o Les limitations du bureau du périmètre irrigué : Ces limitations exigent que l’agriculteur ne cultive pas plus de 90
hectares de tomates. La contrainte qui représente cette restriction est 𝑥𝑥1 ≤ 90.
Etape 3 : Identification de la fonction objectif. La fonction objectif consiste à maximiser le profit apporté par la
culture de tomates et de piments. Les contributions respectives 100 et 200, des deux variables de décision 𝑥𝑥1 et 𝑥𝑥2
sont proportionnelles à leur valeur. La fonction objectif est donc . z=100𝑥𝑥1 +200𝑥𝑥2
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Exemple 1 : Problème d’agriculture
Formulation du problème en un PL :
Le programme linéaire qui modélise le problème d’agriculture est :
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Exemple 2 : Problème de médecine

Un spécialiste en médecine a fabriqué un médicament (des pilules) pour guérir les sujets atteints d’un rhume. Ces
pilules sont fabriquées selon deux formats :
o Petite taille : elle contient 2 grains d’aspirine, 5 grains de bicarbonate et 1 grain de codéine.
o Grande taille : elle contient 1 grain d’aspirine, 8 grains de bicarbonate et 6 grains de codéine.

Pour guérir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de bicarbonate et 24 grains de codéine.
Déterminer le nombre de pilules minimales à prescrire au sujet pour qu’il soit guérit.
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Exemple 3 : problème de production
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Exemple 4 : Problème d’alimentation
 Recherche Opérationnelle
Formulation d’un programme linéaire (PL)
 Exemple 5 : Sélection de Médias
Une entreprise désire effectuer une campagne publicitaire dans la télévision, la radio et les journaux pour un produit
lancé récemment sur le marché. Le but de la campagne est d’attirer le maximum possible de clients. Les résultats d’une
étude de marché sont donnés par le tableau suivant :

Pour la campagne, on prévoit de ne pas payer plus que 800DT pour toute la campagne et on demande que ces objectifs
soient atteints :
1. Au minimum 2000 femmes regardent, entendent ou lisent la publicité ;
2. La campagne publicitaire dans la télévision ne doit pas dépasser 500 DT ;
3. Au moins 3 spots publicitaires seront assurer par la télévision locale et au moins de deux spots par la télévision par
satellite.
4. Le nombre des publicités dans la radio ou dans les journaux sont pour chacun entre 5 et 10.