Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 1 Introduction à la recherche opérationnelle Présentation La recherche

Chapitre 1 Introduction à la recherche opérationnelle Présentation La recherche opérationnelle (RO) est la discipline des mathématiques appliquées qui traite des questions d’uti- lisation optimale des ressources dans l’industrie et dans le secteur public. Depuis une dizaine d’années, le champ d’application de la RO s’est élargi à des domaines comme l’économie, la finance, le marketing et la planification d’entreprise. Plus récemment, la RO a été utilisée pour la gestion des systèmes de santé et d’éducation, pour la résolution de problèmes environnementaux et dans d’autres domaines d’intérêt public. Exemples d’application — Planifier la tournée d’un véhicule de livraison qui doit passer par des points fixés à l’avance puis revenir à son point de départ en cherchant à minimiser la distance parcourue est un problème typique de recherche opérationnelle. On appelle ce problème le problème du voyageur de commerce. — Remplir un conteneur avec des objets de tailles et de valeurs variables. Si le conteneur a une capacité finie, on va chercher à maximiser la valeur placée dans le conteneur. On appelle ce problème le problème du sac-à-dos. — Ordonnancer les tâches sur un chantier. Pour chaque tâche T, on connaît sa durée. De plus, on connaît les autres tâches dont T dépend directement et combien de temps avant ou après le début de chacune d’elles T doit démarrer. On désire minimiser la durée totale du chantier. On dit que ce problème est un problème d’ordonnancement . Chacun de ces problèmes peut bien sûr être compliqué à l’envie. Dans ce cours, on restera relativement simple quelques contraintes de plus suffissent en effet à faire de ces problèmes de véritables sujets de thèse (par exemple pour le remplissage de conteneur un sujet de thèse peut consister en : plusieurs types de conteneurs, plusieurs produits à stocker, des incompatibilités). 6 CHAPITRE 1. INTRODUCTION À LA RECHERCHE OPÉRATIONNELLE 1.1 Histoire La recherche opérationnelle est née pendant la Seconde Guerre mondiale des efforts conjugués d’éminents ma- thématiciens (dont von Neumann, Dantzig, Blackett) à qui il avait été demandé de fournir des techniques d’op- timisation des ressources militaires. Le premier succès de cette approche a été obtenue en 1940 par le Prix Nobel de physique Patrick Blackett qui résolut un problème d’implantation optimale de radars de surveillance. Le qualificatif "opérationnelle" vient du fait que les premières applications de cette discipline avait trait aux opérations militaires. La dénomination est restée par la suite, même si le domaine militaire n’est plus le principal champ d’application de cette discipline, le mot "opérationnelle" prenant alors plutôt le sens d’"effectif". Ce sont donc ces mathématiciens qui ont créé une nouvelle méthodologie caractérisée par les mots-clés modélisation et optimisation. A partir des années 50, la recherche opérationnelle fait son entrée dans les entreprises. En France, des entreprises comme EDF, Air France, la SNCF créent à cette époque des services de recherche opérationnelle (qui existent toujours). La discipline commence à être enseignée dans les universités et les grandes écoles. Puis, au milieu des années 70, sans doute à cause d’un excès d’enthousiasme au départ et à l’inadéquation des moyens informatiques à l’application des méthodes de la RO, la discipline s’essouffle. A partir du milieu des années 90, on assiste à un retour en force la RO, les outils informatiques étant maintenant à la hauteur des méthodes proposées par la recherche opérationnelle. On assiste depuis à une explosion du nombre de logiciels commerciaux et l’apparition de nombreuses boîtes de conseil. Pour la France, notons Ilog (65 millions d’euros de CA), Eurodécision (2,8 millions d’euros de CA), Artelys (1,6 millions d’euros de CA) à l’étranger Dash-Optimization (racheté début 2008 pour 32 millions de dollars par Fair Isaac), IBM Optimization et beaucoup d’autres (le site de INFORMS Institute of Operations Research and Management Science en liste près de 240) Les racines. Si l’on cherche à trouver des précurseurs à la Recherche Opérationnelle, on peut penser à Alcuin ou à Euler qui se sont tous deux intéressés à des problèmes du type RO, bien qu’aucune application n’ait motivé leur travail. Alcuin est le moine irlandais chargé par Charlemagne de construire l’école palatine et qui inventa le problème du loup, de la chèvre et du chou devant traverser une rivière dans une barque où au plus un élément peut prendre place. Un homme devait transporter de l’autre côté d’un fleuve un loup, une chèvre et un panier de choux. Or le seul bateau qu’il put trouver ne permettait de transporter que deux d’entre eux. Il lui a donc fallu trouver le moyen de tout transporter de l’autre côté sans aucun dommage. Dise qui peut comment il a réussi à traverser en conservant intacts le loup, la chèvre et les choux. Euler est le mathématicien allemand à qui les notables de Königsberg demandèrent s’il était possible de parcourir les ponts de la ville en passant sur chacun des 7 ponts exactement une fois (voir Figure 1.1). Ce genre de problème se rencontre maintenant très souvent dans les problèmes de tournées du type facteur ou ramassage de déchets ménagers, dans lesquels il faut parcourir les rues d’une ville de façon optimale. Euler trouva la solution en 1736 - un tel parcours est impossible - en procédant à une modélisation subtile par des mots. La solution actuelle, 1.1 Histoire 7 Figure 1.1 – Königsberg et ses 7 ponts beaucoup plus simple, utilise une modélisation par un graphe. On voit sur cet exemple qu’une bonne modélisation peut simplifer de manière drastique la résolution d’un problème. Le premier problème de recherche opérationnelle à visée pratique a été étudié par Monge en 1781 sous le nom du problème des déblais et remblais. Considérons n tas de sable, devant servir à combler m trous. Notons ai la masse du ième tas de sable et bj la masse de sable nécessaire pour combler le jème trou. Quel plan de transport minimise la distance totale parcourue par le sable? La solution que proposa Monge est intéressante et procède par une modélisation dans un espace continu dans lequel on cherche une géodésique - malheureusement, elle n’est pas correcte. La solution correcte pour trouver l’optimum est connue depuis les années 40 et utilise la programmation linéaire, ou mieux, la théorie des flots. Modélisation et optimisation [Wikipedia] 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. 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. Cette phase essentielle s’appelle la modélisation. La résolution d’un problème dépend crucialement du modèle choisi. En effet, pour un même problème, différentes modélisations sont possibles et il n’est pas rare que le problème semble insoluble dans une modélisation et trivial 8 CHAPITRE 1. INTRODUCTION À LA RECHERCHE OPÉRATIONNELLE dans une autre. D’autre part, tous les éléments d’un problème ne doivent pas être modélisés. Par 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. Souvent, la phase de modélisation est accompagnée ou précédée de nombreuses discussions avec le commanditaire (lequel n’a d’ailleurs pas toujours une idée claire de ce qu’il cherche à obtenir- ces discussions lui permettent alors également de préciser ses objectifs). Une des vrais difficultés de départ est de savoir quels éléments doivent être modélisés et quels sont ceux qui n’ont pas besoin de l’être. Il faut parvenir à trouver le juste équilibre entre un modèle simple, donc plus facilement soluble, et un modèle compliqué, plus réaliste, mais plus dificile à résoudre. Cela dit, pour commencer, un modèle simple est toujours préférable et permet souvent de capturer l’essence du problème, de se construire une intuition et de proposer des solutions faciles à implémenter. 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 : — 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? — Quelles sont les contraintes? Une fois identifiées les variables de décision, quelles sont les valeurs autori- sées pour ces variables? — Quel est l’objectif ou le critère? Quelle est la quantité que l’on veut maximiser ou minimiser? Rappelons immédiatement que, en toute rigueur, on n’optimise qu’une seule quantité à la fois. On ne peut pas demander d’optimiser à la fois la longueur d’un trajet et son temps de parcours : le trajet le plus court peut très bien passer par un chemin vicinal et le trajet le plus uploads/Science et Technologie/chapitre-01-intoduction-a-la.pdf