Remerciez-le!

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

Recherche opérationnelle Pr. Abdessamad Kamouss 1 Intro PL Dualité Graphes Chem

Recherche opérationnelle Pr. Abdessamad Kamouss 1 Intro PL Dualité Graphes Chemin Ordonnancement Recherche Opérationnelle R.O. Pr. Abdessamad Kamouss Cycle Ingénieur ENSAM Casablanca Recherche opérationnelle Pr. Abdessamad Kamouss 2 Intro PL Dualité Graphes Chemin Ordonnancement Contenu du module 1 Introduction à la recherche opérationnelle 2 Modélisation et Programmation linéaire 3 Dualité 4 Généralités sur les graphes 5 Recherche de Chemin Optimal dans un graphe 6 Problèmes d’ordonnancement Recherche opérationnelle Pr. Abdessamad Kamouss 3 Intro PL Dualité Graphes Chemin Ordonnancement Déﬁnitions Déﬁnition (Cambridge Dictionary) Operational research UK (US operations research) The systematic study of how best to solve problems in business and industry. Déﬁnition (Wikipedia) Operations research, operational research, or simply OR, is the use of mathematical models, statistics and algorithms to aid in decision-making. Déﬁnition (ROADEF) Recherche Opérationnelle : approche scientiﬁque pour la résolution de problèmes de gestion de systèmes complexes. Recherche opérationnelle Pr. Abdessamad Kamouss 4 Intro PL Dualité Graphes Chemin Ordonnancement Recherche Opérationnelle Science du "comment mieux faire avec moins" des outils pour : rationaliser simuler optimiser planiﬁer 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 efﬁcaces et robustes. Recherche opérationnelle Pr. Abdessamad Kamouss 5 Intro PL Dualité Graphes Chemin Ordonnancement Recherche Opérationnelle Origines La seconde guerre mondiale créa un besoin urgent d’allouer de manière efﬁcace des ressources limitées aux différentes opérations militaires et aux activités au sein de chaque opération. L ’organisation militaire britanique, puis américaine, mis à contribution un grand nombre de scientiﬁques pour gérer ces allocations, et s’occuper d’autres problèmes stratégiques et tactiques. Ces scientiﬁques ont été appelés à poursuivre des recherches sur des opérations (militaires), et constituèrent les premières équipes de RO. Leurs succès encouragèrent la poursuite de l’utilisation de la RO dans d’autres domaines (commercial, industriel,...) Recherche opérationnelle Pr. Abdessamad Kamouss 6 Intro PL Dualité Graphes Chemin Ordonnancement Recherche Opérationnelle - autres déﬁnitions Déﬁnition La R.O ou la science de la décision est la discipline des méthodes scientiﬁques utilisables pour élaborer des meilleures décisions. Elle permet de rationaliser, de simuler, de planiﬁer et d’optimiser l’architecture et le fonctionnement des systèmes de production et d’organisation. En pratique, la R.O sert à résoudre différents types de problèmes difﬁciles (issus des mathématiques, de l’informatique, de l’économie, de l’industrie...) Une autre déﬁnition possible de la RO pourrait être la suivante : Déﬁnition Ensemble de méthodes d’analyse scientiﬁque des phénomènes d’organisation qui traite de la maximisation d’un proﬁt, d’une performance, d’un rendement ou bien de la minimisation d’un coût, d’une dépense. Recherche opérationnelle Pr. Abdessamad Kamouss 6 Intro PL Dualité Graphes Chemin Ordonnancement Recherche Opérationnelle - autres déﬁnitions Déﬁnition La R.O ou la science de la décision est la discipline des méthodes scientiﬁques utilisables pour élaborer des meilleures décisions. Elle permet de rationaliser, de simuler, de planiﬁer et d’optimiser l’architecture et le fonctionnement des systèmes de production et d’organisation. En pratique, la R.O sert à résoudre différents types de problèmes difﬁciles (issus des mathématiques, de l’informatique, de l’économie, de l’industrie...) Une autre déﬁnition possible de la RO pourrait être la suivante : Déﬁnition Ensemble de méthodes d’analyse scientiﬁque des phénomènes d’organisation qui traite de la maximisation d’un proﬁt, d’une performance, d’un rendement ou bien de la minimisation d’un coût, d’une dépense. Recherche opérationnelle Pr. Abdessamad Kamouss 6 Intro PL Dualité Graphes Chemin Ordonnancement Recherche Opérationnelle - autres déﬁnitions Déﬁnition La R.O ou la science de la décision est la discipline des méthodes scientiﬁques utilisables pour élaborer des meilleures décisions. Elle permet de rationaliser, de simuler, de planiﬁer et d’optimiser l’architecture et le fonctionnement des systèmes de production et d’organisation. En pratique, la R.O sert à résoudre différents types de problèmes difﬁciles (issus des mathématiques, de l’informatique, de l’économie, de l’industrie...) Une autre déﬁnition possible de la RO pourrait être la suivante : Déﬁnition Ensemble de méthodes d’analyse scientiﬁque des phénomènes d’organisation qui traite de la maximisation d’un proﬁt, d’une performance, d’un rendement ou bien de la minimisation d’un coût, d’une dépense. Recherche opérationnelle Pr. Abdessamad Kamouss 7 Intro PL Dualité Graphes Chemin Ordonnancement R.O - autres déﬁnitions Récapitulation La recherche opérationnelle est un des grands domaines d’application de l’informatique et des mathématiques appliquées dans l’industrie et en gestion. Elle regroupe un ensemble de méthodes, modèles et outils informatiques et mathématiques permettant, d’optimiser le processus de prise de décisions dans l’Entreprise. Recherche opérationnelle Pr. Abdessamad Kamouss 8 Intro PL Dualité Graphes Chemin Ordonnancement Recherche opérationnelle Les outils de RO : aident à trouver une solution où l’homme n’en trouvait pas une solution sur des problèmes nouveaux où l’homme n’a aucune expérience plusieurs solutions là où l’homme n’en envisageait qu’une seule solution aident à juger de la qualité d’une solution aident à conﬁrmer / justiﬁer des décisions Recherche opérationnelle Pr. Abdessamad Kamouss 9 Intro PL Dualité Graphes Chemin Ordonnancement Un premier problème Achat de billets d’avion Un homme d’affaires doit effectuer 5 voyages entre Casa (CAS) et Paris (PAR) selon les conditions suivantes : Il doit partir le lundi de CAS à PAR et revenir le mercredi de PAR à CAS. Un billet aller-retour : 400U. Réduction de 20 % si un weekend est inclus. Aller simple : 75 % du prix aller-retour. Question Comment acheter les billets pour les 5 semaines (à prix minimum)? Recherche opérationnelle Pr. Abdessamad Kamouss 10 Intro PL Dualité Graphes Chemin Ordonnancement Un premier problème Evaluation des alternatives Alternatives Acheter 5 CAS-PAR-CAS normaux. 5 x 400 = 2000 Acheter un CAS-PAR, 4 PAR-CAS-PAR comprenant un weekend et un PAR-CAS. 0.75 x 400 + 4 x 0.8 x 400 + 0.75 x 400 = 1880 Acheter un CAS-PAR-CAS pour le lundi de la première semaine et le mercredi de la dernière semaine, et 4 PAR-CAS-PAR comprenant un weekend pour les autres voyages. 5 x 0.8 x 400 =1600 La troisième alternative est la meilleure. Recherche opérationnelle Pr. Abdessamad Kamouss 11 Intro PL Dualité Graphes Chemin Ordonnancement Décision binaire Voyage sans redondance Un étudiant en quête d’une université projette de visiter les campus de trois universités au cours d’un voyage unique, débutant et ﬁnissant à l’aéroport de P. Les trois établissements sont dans les villes de A, B, et C. L ’étudiant ne veut visiter chaque ville qu’une seule fois. On veux maintenir le trajet total le plus court possible. Les distances entre ces villes sont données dans la Table suivante : Recherche opérationnelle Pr. Abdessamad Kamouss 12 Intro PL Dualité Graphes Chemin Ordonnancement Décision binaire Ville P A B C P 0 30 38 73 A 30 0 18 53 B 38 18 0 51 C 73 53 51 0 Table – Les distances inter-villes. Question Comment modéliser ce problème et ses contraintes? Recherche opérationnelle Pr. Abdessamad Kamouss 13 Intro PL Dualité Graphes Chemin Ordonnancement Décision binaire : modélisation Puisque n’importe quel trajet consiste en une série de petits déplacements entre deux villes, on numérote les villes comme suit : 1 pour P, 2 pour A, 3 pour B et 4 pour C. Ainsi, nous aurons une variable x1,2 égale à 1 si l’étudiant voyage de P à A au cours de son parcours total et 0 sinon. Puisqu’il n’y a pas de voyage d’une ville vers cette même ville, nous avons les contraintes : xi,i = 0, i = 1,...,4 Chaque ville ne devant être visitée qu’une seule fois, elle ne peut apparaître qu’une seule fois comme ville d’arrivé. Donc pour j ﬁxé avec j = 1,...,4, x1,j +x2,j +x3,j +x4,j = 1 d’où : 4 ∑ i=1 xi,j = 1, j = 1,...,4. Recherche opérationnelle Pr. Abdessamad Kamouss 14 Intro PL Dualité Graphes Chemin Ordonnancement Décision binaire : modélisation Puisque la même ville ne peut pas être une source d’un trajet plus qu’une fois, alors on pose la contrainte suivante : 4 ∑ j=1 xi,j = 1, i = 1,...,4. Aﬁn d’obtenir un véritable trajet ayant même origine et départ, nous devons rejeter les affectations qui décrivent des groupes déconnectés de petits déplacements comme x1,2 = x2,1 = 1 ou x3,4 = x4,3 = 1, avec toutes les autres variables égales à 0. Nous pouvons forcer ceci avec les contraintes : xi,j +xj,i ≤1, i = 1,...,4, j = 1,...,4. On peut décrire la distance totale associé à n’importe quel parcours autorisé par : 4 ∑ i=1 4 ∑ j=1 xi,jai,j. Recherche opérationnelle Pr. Abdessamad Kamouss 15 Intro PL Dualité Graphes Chemin Ordonnancement Décision binaire Voyage sans redondance Donc la modélisation du problème sera comme suit : min∑4 i=1∑4 j=1xi,jai,j xi,j ∈0,1, i = 1,...,4, j = 1,...,4. xi,i = 0, i = 1,...,4. ∑4 i=1xi,j = 1, j = 1,...,4. ∑4 j=1xi,j = 1, i = 1,...,4. xi,j +xj,i ≤1, i = 1,...,4, j = 1,...,4. Recherche opérationnelle Pr. Abdessamad Kamouss 16 Intro PL Dualité Graphes Chemin Ordonnancement R.O : Applications Problème du voyageur de commerce Un voyageur de commerce, basé à Casablanca doit visiter plusieurs clients situés sur différentes villes au Maroc. Il souhaite effectuer la tournée la plus courte possible Recherche opérationnelle Pr. Abdessamad Kamouss 17 Intro PL Dualité Graphes Chemin Ordonnancement R.O : Applications Problème e uploads/Science et Technologie/ 01-introduction.pdf