Remerciez-le!

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

Modélisation & Etudes de cas (VHH : Cours : 1h0 + TP: 1h30) M1.Romarin/RO Respo

Modélisation & Etudes de cas (VHH : Cours : 1h0 + TP: 1h30) M1.Romarin/RO Responsable-Module : Pr H.AIT HADDADENE Responsable-TP : Dr Y.DJEDDI Programme : - Introduction Générale ; - Modèles Mathématiques particuliers et Etude de cas. Références : - C.Aslangul, Des mathématiques pour les sciences, Concepts, méthodes et techniques pour la modélisation, De Bock Editions 2011; - Y.Hamam & H.Talbot, Introduction à la Programmation Mathématique, Programmation Linéaire et Optimisation Combinatoire Groupe, E.S.I.E.E., poly_optim_2009.pdf; - A.Martel, Techniques et applications de la recherche opérationnelle, G.Morin éditeur, 1979; - ROADEF, www.roadef.org/content/roadef/rod.html; - Eurodecision, www.eurodecision.fr; - J.Teghem, Programmation Linéaire, Editions Ellipses, 1996; - Différents fichiers en PDF.  http://forum.openopt.org (19/12/2008) OpenOpt : nouveau forum d'optimisation numérique  news:sci.op-research Le forum de R.O  news:comp.constraints Le forum sur la Programmation par Contrainte  CiteSeer : Scientific Literature Digital Library Excellent moteur biblio !  optimization-online.org (21/11/2008) Excellente source d'articles pdf en ligne (moteur)  LEMON: Library of Efficient Models and Optimization in Networks (https://lemon.cs.elte.hu/) (11/11/2009) Bibliothèque C++ de graphes simple à compiler, et couplable avec un solveur linéaire tel que Glpk. Cette biblothèque fair désormais partie du projet COIN-OR  vOptSolver: solver of Multiobjective linear optimization problems (https://github.com/vOptSolver/vOptSolver) (21/09/2017)  http://perso.ensta-paristech.fr/~diam/ro/ 1) Introduction Générale MANAGEMENT D’UN PROJET Dans une entreprise, des ouvriers O doivent exécuter un certain nombre de tâches pour achever un projet. L’ensemble de toutes les tâches possibles étant T. On désire que tous les ouvriers qui doivent exécuter la tâche t le fassent simultanément. Chaque ouvrier ne pouvant se présenter qu’à une tâche au plus chaque semaine. Quel est le nombre minimum de semaines nécessaires pour terminer toutes les tâches (i.e. le projet) ? Modélisation : Pour toute tâche t, soit e(t)  O l’ensemble des ouvriers devant exécuter la tâche t ; formons le graphe G=(T, E), où (t, t’)  E si e(t)  e(t’)  Ø, i.e. si les deux tâches t et t’ ne peuvent être exécutées simultanément. A chaque coloration des sommets de ce graphe correspond une affectation possible pour l’ensemble des tâches et vice versa; le problème revient donc à chercher le nombre chromatique χ(G) de G. UN PROBLEME D’INVESTISSEMENT Une investisseuse a 50000 U.M. à investir parmi les quatre prochaines possibilités: bourse X, bourse Y, obligations X et obligations Y ; pour la période d'un an. Un maximum de 10500 U.M. peut être investi en obligations X, et un maximum de 10000 U.M. en obligations Y. Investir dans la bourse X implique un risque important c'est pour cela qu'on décide de ne pas investir plus d'un quart de l'investissement total. La quantité investie dans la bourse Y doit être au moins trois fois la quantité investie dans la bourse X. En outre, l'investisseuse a besoin que l'investissement d'obligations soit au moins si grand que la moitié de l'investissement dans les bourses. Les retours sur investissement par an s'envisagent selon le suivant tableau: Bourse X Bourse Y Obligations X Obligations Y 20% 10% 9% 11% Quelle est la manière optimale de faire l'investissement pour obtenir le maximum de bénéfices? Modélisation : Déterminer les variables de décision et les représenter de manière algébrique. Dans ce cas:  X1: investissement en bourse X  X2: investissement en bourse Y  X3: investissement en obligations X  X4: investissement en obligations Y Déterminer les contraintes et les formuler comme équation ou inéquations dépendants des variables de décision. Ces contraintes sont déduites des décisions prises par l'investisseuse sur la manière d'investir et l'investissement maximum qu'on peut réaliser:  X1+X2+X3+X4 ≤ 50000 ; X1 ≤ 12500 ; X3 ≤ 10500 ; X4 ≤ 10000 ; 3X1 - X2 ≤ 0  0,5X1+ 0,5X2 - X3 - X4 ≤ 0 Présenter toutes les conditions implicitement établies conformément à la nature des variables: qu'elles ne peuvent pas être négatives, qu'elles soient entières, qu'elles ne peuvent que prendre valeurs déterminées, ... Dans ce cas, la seule condition est que les investissements ne peuvent pas être négatifs:  Xi ≥ 0 Déterminer la fonction objectif:  Maximiser Z = 0.2·X1 + 0.1·X2 + 0.09·X3 + 0.11·X4 UN PROBLEME DE COUVERTURE Une ville est composée de 11 départements. On cherche à placer des casernes de pompiers où une caserne peut servir le département dans lequel elle est installée et aussi les départements voisins (se trouvant dans le voisinage direct). L’objectif est de minimiser le nombre de casernes à installer. Nous considérons pour chaque voisinage une variable de décision xj (j = 1,…11). xj=1 si une caserne est installée dans le voisinage n°j, 0 sinon. Nous obtenons le modèle suivant : 11 10 9 8 7 6 5 4 3 2 1 x x x x x x x x x x x Z Min            1 x x x x 4 3 2 1     1 x x x x 5 3 2 1     1 x x x x x x 6 5 4 3 2 1       1 x x x x x 7 6 4 3 1      1 x x x x x x 9 8 6 5 3 2       1 x x x x x x 8 7 6 5 4 3       1 x x x x 8 7 6 4     1 x x x x x x 10 9 8 7 6 5       1 x x x x x 11 10 9 8 5      1 x x x x 11 10 9 8     1 x x x 11 10 9    xj{0 , 1} j = 1,…,11 La première contrainte indique qu’on doit installer une caserne dans le département 1 ou l’un de ses départements voisins. La 2ème contrainte est pour le département 2 et ainsi de suite. On cherche un sous ensemble de j qui couvre tous les départements de la ville avec un coût minimal. Une solution optimale serait x3 = x8 = x9 = 1. Qu’est ce que c’est la R.O. ? - On peut définir la Recherche Opérationnelle (RO) comme l'ensemble des domaines scientifiques, des outils et des problèmes touchant aux questions d'ordre décisionnel (dit aussi stratégique) ou d'optimisation de systèmes complexes. L'expression « systèmes complexes » est à prendre au sens : difficile à comprendre pour un individu sans l'aide d'un modèle ou d'un ordinateur. Les problèmes sont rendus complexes par leur dimension qui peut être importante, mais surtout par leur structure qui peut-être par exemple combinatoire, concurrentielle, stochastique etc. - La RO est une discipline scientifique qui s’intéresse à la compréhension et à la résolution de problèmes de décision se posant dans les organisations. Elle vise à l’amélioration du fonctionnement des organisations (entreprises, organismes publics...) par l’application d’une approche scientifique. Champs d’application : Gestion de production (alloc de ressources limitées, ordonnancement, ...), Logistique (pbs de localisation, gestion de flux, ...), Gestion de ressources humaines (affectation, élaboration de planning...), Optimisation dans les réseaux, Décision stratégiques... Il est difficile pour un individu de pouvoir maîtriser tous les aspects du problème à l’étude, de sorte que la RO est généralement plus un travail d’équipe, avec des experts en mathématiques, statistiques et probabilités, ingénierie, économie, administration, informatique, …. (voir fichier associé) La recherche opérationnelle aborde les problèmes de décision par le biais d’une procédure en sept étapes: 1. Formuler le problème •Définir le problème. •Spécifier les objectifs. •Déterminer les parties de l’organisation à être étudiées et les intervenants à être impliqués. 2. Observer le système •Déterminer les paramètres influant le problème. •Recueillir les données afin d’estimer la valeur des paramètres. 3. Poser le problème sous la forme d’un modèle mathématique 4.Vérifier le modèle Les résultats du modèle sont-ils compatibles avec la réalité? Sous quelles conditions le modèle est-il valide? 5. Choisir la meilleure variante Parmi les variantes générées par le modèle, choisir celle qui permet le mieux de satisfaire les objectifs de l’organisation. 6. Présenter les résultats et les conclusions aux décideurs • Il peut être utile de proposer plusieurs avec toutes les informations correspondantes afin de laisser aux décideurs la liberté de faire le choix final d’une solution à implanter (ceci dépend des consignes qui nous ont été données au départ). • Il est possible que nos recommandations soient refusées si le problème n’était pas bien défini, ou si les intervenants appropriés n’étaient pas inclus dans l’étude. 7.Implantation et évaluation de recommandations Suite à l’acceptation de l’étude par les décideurs, l’ingénieur : • Assiste à l’implantation des recommandations. • Assure le suivi en s’assurant que les hypothèses sous lesquelles a été faite l’étude, demeurent valides. Processus d’aide à la décision : Qu’est-ce que la recherche op´ erationnelle ? Un ensemble de m´ ethodes scientiﬁques cherchant ` a r´ esoudre efficace- ment les probl` emes pos´ es par les activit´ es des organisations humaines. Un ensemble de techniquesmath´ ematiques uploads/Finance/ m1-romarin-ro-modelisation-amp-etudes-de-cas-vhh-cours-1h0-tp-1h30.pdf