background preloader

TIPE 2016-2017 Optimalité : choix, contraintes, hasard - Copie

Facebook Twitter

«Optimalité : choix, contraintes, hasard.» un thème où l’on retrouve la déraisonnable efficacité des mathématiques grâce à l’informatique. — Pixees. Trois mots clés qui se fédèrent en une théorie. ©IHP – Maison des mathématiques. Les mathématiques se mettent au service de problèmes concrets pour produire grâce à l’informatique, les meilleures solutions. Choix. Pour faire un choix, pour prendre une décision, il faut clairement disposer d’informations et d’une représentation (ou “modèle”) de la situation qui réclame ce choix.

Que la proposition de décision soit confiée à l’humain-e ou à la machine, à moins de choisir au hasard, la situation va devoir être estimée, et un critère de choix devoir être arbitré. Contraintes. Hasard. Hasard: Phénomène imprédictible.Si je jette une pièce de monnaie qui retombe aléatoirement si pile ou face, pas d’erreur, ce n’est pas le fait du hasard. Hasard: Mécanismes exploratoires. Comment en savoir plus sur ces éléments ? Trois articles permettent d’illustrer et de rentrer dans ce sujet. Et l’optimisation ? Bien entendu, cette présentation ne peut-être exhaustive. Le choix ne manque pas. Qui est le chef ? Une question ? Contactez-nous !

Jeux à champ moyen : définition wikipédia. Gestion des stocks et de la production intégrant des retours de produits : thèse de Samuel Vercraene, 2012. Abstract : Flows of returns due to recycling and reusing waste are developing in order to preserve the limited natural resources of our planet. These new flows interact with the traditional production flows. Therefore, in order to provide customers with the best service level and minimize the stock in the supply chain, the control of the return flows appears to be of highest importance.

We address this problem by modeling a situation with a limited porduction capacity and we consider an operational production/inventory problem that incorporates flows of returns. We model three continuous-time production/inventory problems with limited produc- tion capacities, random lead times, and linear costs. Résumé : De nombreux retours de produits dus au recyclage et à la réutilisation des déchets se développent dans le but de préserver les ressources naturelles limitées de notre planète. Mean field games : T. Tao, 2010 [en anglais] John Nash, la théorie des jeux et la question du bon choix : article du Monde, mai 2013. Le mathématicien et prix Nobel John Forbes Nash est mort à l'âge de 86 ans. L'occasion de revenir sur sa spécialité, la théorie des jeux.

LE MONDE SCIENCE ET TECHNO | • Mis à jour le | Philippe Pajot Le mathématicien américain John Forbes Nash est mort à l'âge de 86 ans. Ci-dessous, un article datant de mai 2013 où il est question de sa spécialité, la théorie des jeux. « Gouverner, c'est choisir », disait Pierre Mendès France. Commençons par quelques questions pour montrer que notre intuition des probabilités est facilement faussée, induisant de mauvais choix. Autre exemple troublant. Dans cette dernière étape, celle de l'ouverture de la porte, le meneur de jeu vous demande si vous préférez conserver votre choix initial et ouvrir cette porte, ou bien si, au contraire, vous préférez changer de choix et ouvrir l'autre porte.

La bonne connaissance des caractéristiques d'un jeu peut ainsi aider à gagner. Cet intérêt des économistes pour la théorie des jeux s'est accéléré dernièrement. Cours de Pierre-Louis Lions au Collège de France. Apprentissage automatique et Big Data : Simon Lacoste-Julien, 2014. Algorithmique du style : de nouveaux espaces pour la composition et l’improvisation : François Pachet, 2015. Les jeux à champ moyen - Brèves de Maths, 2013. Embouteillage en Algarve, Portugal. Dans cette autre brève sur la congestion, il est question d’équilibre atteint par un grand nombre d’automobilistes qui cherchent individuellement à minimiser leur temps de parcours mais qui subissent les conséquences des choix des autres automobilistes via la congestion éventuellement provoquée. En termes physiques, on pourrait voir l’automobiliste dans son véhicule comme une particule qui est soumise à l’action du champ créé par toutes les autres particules (i.e. les autres véhicules).

Tout comme dans cette brève, cette situation où des acteurs rationnels prennent des décisions qui amènent à une situation d’équilibre relève de la théorie des jeux. La théorie des jeux à champ moyen, proposée en 2006 indépendamment par J-M. Pour un nombre fini d’agents, ce type de jeux est bien décrit par la théorie des équilibres de Nash, mais on est alors confronté à de grandes difficultés car il faut tenir compte de toutes les interactions. Pour en savoir plus : Équilibre de Nash, inventeur du jeu de Hex : Brèves de maths, 2013. John Forbes Nash, Jr. John Forbes Nash Jr est né en 1928 à Bluefield aux États-Unis, en Virginie-Occidentale. Poussé par ses enseignants sur la voie des mathématiques, il prépare une thèse à l’université de Princeton.

Durant ces années, il a inventé le jeu de hex pour la salle commune des élèves et des professeurs. John Nash s’intéresse à la fois à la théorie des jeux et à des problèmes de géométrie ou de topologie. Pour expliquer la notion d’équilibre introduite par Nash dans son mémoire de thèse, observons Paul et Carole jouer de façon rationnelle de la façon suivante : dans les tableaux ci-dessous, Paul choisit la ligne (haute H ou basse B) et Carole, elle, choisit la colonne (gauche G ou droite D). Trois exemples de jeu à deux joueurs et deux stratégies par joueur.

Dans le premier jeu de la figure ci-dessus, on voit que Paul a intérêt à choisir la ligne du haut : en effet, que Carole choisisse G ou D, Paul gagne plus avec H qu’avec B. Pour en savoir plus : Richard Bellman et la programmation dynamique - Brèves de Maths, 2013. Richard Bellman (1920-1984). Richard Bellman est né le 26 août 1920 à New York.

À la fin de ses études universitaires à Baltimore, il est d’abord instructeur des armées avant d’être affecté au projet Manhattan entre 1944 et 1946. Il prépare ensuite une thèse sur les équations différentielles à Princeton sous la direction de Lefschetz et commence une carrière académique. Attiré par la théorie des nombres, il est aussi séduit par les défis mathématiques posés par les applications. In those days applied practitioners were regarded as distinctly second-class citizens of the mathematical fraternity. […] when invited to speak at various […] seminars, Bellman delighted in justifying his choice of applied over pure mathematics as being motivated by the real world’s greater challenges and mathematical demands.

Il décide de rejoindre la RAND corporation en 1952. Quand Bellman rejoint RAND, on lui propose de travailler sur des problèmes de prise de décision multi-niveaux. Pour en savoir plus : J. Créer de nouvelles routes peut générer davantage d’embouteillages ou le paradoxe de Braess-Brèves de Maths, 2013. La très fréquentée 42ème rue de New York. Sa fermeture à la circulation en 1990 a, contre toute attente, fluidifié la circulation. Les embouteillages constituent un véritable fléau pour nos métropoles modernes. Ils ont un coût exorbitant, que ce soit en termes environnementaux ou en temps de travail perdu. Une étude récente du cabinet britannique CEBR estime ce coût en France à 3,88 milliards d’euros. Créer de nouvelles routes ou élargir les routes existantes semble être une solution de bon sens (bien qu’onéreuse). Braess, mathématicien allemand, a été le premier à découvrir un phénomène qui déroutait les habitants de Stuttgart à la fin des années 1960 : l’apparition d’embouteillages monstres après de gros travaux d’amélioration du réseau routier de la ville.

Il faut chercher l’explication dans le comportement rationnel des automobilistes. L’étude des optima et des équilibres pour des situations de trafic congestionné constitue un domaine de recherche extrêmement fécond et actif. Le prix de l'anarchie ou le paradoxe de Braess, Étienne Ghys, 2009. Deux paradoxes Pour expliquer cela, nous allons commencer par décrire un autre phénomène découvert par A.C. Pigou — un économiste — en 1920 [2]. Supposons que deux villes et , de part et d’autre d’un fleuve, soient reliées par deux routes. La première est excellente, très large, mais elle fait malheureusement un grand détour : il faut une heure pour la parcourir, et ceci quel que soit le nombre de véhicules qui l’empruntent (dans des limites raisonnables, par exemple jusqu’à 1000 véhicules par heure). Supposons maintenant que 1000 automobilistes/heure souhaitent aller de à . 1- Le comportement égoïste. 2- Le comportement social.

C’est la remarque de Pigou : un système de communication régulé de manière « centralisée », imposant des comportements à certains individus, peut circuler beaucoup mieux qu’un système dans lequel chacun peut choisir son comportement comme bon lui semble. Passons au paradoxe de Braess illustré sur la figure suivante [3]. Deux routes joignent et . Un peu de théorie. Dossier thématique sur transport optimal dans Images des mathématiques. Les mathématiques, la clé d'un trafic fluide ?  - 31/07/2015 - ladepeche.fr.

Si vous prenez la route ce week-end à l'occasion du grand chassé-croisé de l'été et que les centaines de kilomètres de bouchons attendus vous angoissent, rassurez-vous: des mathématiciens tentent d’alléger vos souffrances en définissant des systèmes de régulation du trafic. Dynamique des fluides, équations aux dérivées partielles, théorie des jeux: autant d'outils mathématiques qui nous dépassent mais pourraient éviter aux automobilistes de rester coincés dans leur voiture...et à l'économie française d'en pâtir. Les embouteillages ont coûté 17 milliards d’euros à l'économie française en 2013, et devraient peser à hauteur de 22 milliards d'ici 2030, selon une étude signée du fournisseur d'information routière INRIX et du Centre for Economics and Business Research (Cebr).

Soit plus que le trou de la Sécu en 2014. "J'étudie des équations qui décrivent l'écoulement d'un gaz ou d'un fluide", explique-t-elle à l'AFP. 'comportement égoïste' Le bon sens pourrait inciter à rajouter des routes. Création d'un Inria Innovation Lab pour réduire la consommation en carburant des avions. Partenariat Recherche - Industrie Le partenariat entre Safety Line et l’équipe de recherche COMMANDS se concrétise aujourd’hui par la création d’un Inria Innovation Lab. Baptisé OSCAR (OptimiSation of Consumption for AiRplanes), et créé pour une durée de trois ans, ce laboratoire commun vise à améliorer le développement du produit OptiClimb et à fournir aux compagnies aériennes des outils de programmation des vols, et de pilotage des performances opérationnelles. Le bénéfice industriel se traduit par l’optimisation de la consommation de carburant et la diminution des émissions de CO2.

L’Inria Innovation Lab OSCAR Suite d’une collaboration déjà fructueuse Partenaires depuis trois ans, Safety Line et l’équipe COMMANDS d’Inria Saclay – Île-de-France ont précédemment travaillé sur l’optimisation des vitesses de montée dans la planification des vols. Intégration et application opérationnelle de technologie innovante. Convexité et optimisation : cours de Guy Cohen, 2000, corr. 2006. Optimisation et apprentissage : Alexandre d'Aspremont, 2014. La programmation par contraintes expliquée à ma garagiste ou à mon fleuriste : Charlotte Truchet, 2015.

Parmi les grandes familles d'approches et de langages informatiques, on entend parfois parler de « programmation par contraintes ». Un chercheur du domaine vous expliquerait peut-être que « c'est un paradigme de programmation déclarative permettant de traiter des problèmes fortement combinatoires ». Euh... Heureusement, Binaire a son joker : une enseignante-chercheure Charlotte Truchet, spécialiste du domaine, qui sait expliquer ses recherches.

Thierry Viéville. Photo de www.picturalium.com CC-BY Venez, je vous emmène visiter la boutique de Denis, fleuriste dans un petit village, un beau matin de printemps. Le matin, à l'ouverture, Denis prépare des bouquets tout prêts pour les clients pressés. Il pourrait faire ses bouquets au petit bonheur, un peu au hasard, mais il rencontre un problème. . © www.theplantgame.com Fleurs et Informatique : quand les plantes s'étudient avec les sciences du numérique Enfin, on écrit des contraintes sur les variables. . © www.theplantgame.com. La programmation par contraintes : Étienne Parizot, Sylvain Soliman, François Fages, 2004. Lorsque les contraintes sont nombreuses, la résolution d'un problème est en pratique très difficile. Surtout si on exige de trouver la meilleure solution possible... © potowizard - Fotolia.com Supposons qu'on veuille organiser la rotation des avions dans un aéroport, en optimisant l'utilisation des pistes, l'emploi du temps du personnel navigant, l'attente des voyageurs, l'acheminement des bagages, etc.

Pas question que deux atterrissages se suivent à moins d'une minute ! Tout est dans l'approche Selon l'approche traditionnelle en informatique, il s'agirait de rechercher un algorithme général (écrit dans un langage tel que le C, Pascal ou Java) capable de résoudre le problème et de s'adapter facilement si on rajoute un vol, par exemple, ou si on supprime une compagnie. Déplacer la difficulté Il n'y a pourtant pas de miracle, et la difficulté intrinsèque du problème doit bien se retrouver quelque part. À chaque problème sa solution. Optimisation : quand le mieux n'est pas l'ennemi du bien : conférence Pierre Martinon, 2009. Conception interactive d’environnements urbains durables à base de résolution de contraintes : thèse de Bruno Belin, 2014.

Abstract : The design of more sustainable cities has emerged as a central society issue. A city, in the early stage of its design process, can be seen as a balanced set of urban shapes (residential, commercial, artisanal and industrial units, roads, schools, parks, ...). These shapes need to be spatially organized following complex rules based on a systemic view of the city, including social, economic, ecological and transportation aspects. In this thesis, we provide a computer-aided decision tool to assist urban planners and decision makers in the task of designing sustainable cities. We cast the urban planning problem as an optimization problem that we solve with local search techniques, by iteratively swapping the urban shapes.

At this stage, our tool automatically organizes urban shapes over a given empty, spatially delimited territory. Résumé : La conception de villes plus durables est devenue un problème de société central. Publications dans les conférences JFPC (Journées Francophones de Programmation par Contraintes) Search 293 results save search Type of document Author Domaine Laboratory Language Type of deposit Year Title Compulsory field(s) not filled in.

Contact support.ccsd.cnrs.fr hal.support@ccsd.cnrs.fr. Colisweb améliore son modèle de livraison avec Inria. Collaboration © Colisweb C’est un problème complexe que Colisweb a soumis à l’équipe Inocs d’Inria Lille - Nord Europe : déterminer à l’avance le planning d’une flotte de livreurs, sans connaître leur charge de travail. Objectif : proposer des livraisons immédiates sans surcoût. Prévoir l’imprévu. Voilà, en résumé le défi que Colisweb a lancé à l’équipe Inocs d’Inria Lille - Nord Europe (commune avec l’ULB et Centrale Lille*). La livraison de proximité : un problème complexe La promesse de Colisweb est donc ambitieuse : cette jeune société lilloise implantée dans l’écosystème EuraTechnologies, propose de réaliser des livraisons urbaines selon deux modes.

Optimiser les charges de travail grâce à la programmation mathématique À l’heure actuelle, le système Colisweb fonctionne grâce à un tandem homme-machine. La success story de Colisweb Née il y a 3 ans, Colisweb a installé son siège à Lille, au cœur d’EuraTechnologies, un parc d’activités de 150 000 m2 dédié aux nouvelles technologies. Algorithme génétique : définition wikipédia. Le hasard fait bien les choses : exposé de Corinne Touati (vidéo 1), 2013. Le hasard fait bien les choses : exposé de Corinne Touati (vidéo 2), 2013. Le hasard fait bien les choses : Denis Talay, 2009.

La conquête du hasard : Fernando Corbalán, Gerardo Sanz, 2013. Introduction à la théorie des jeux : Sébastien Konieczny. Les mathématiques de l'évolution : documentaire de Régis Ferrière. Hasard et chance du 27 juin 2016 - France Inter. Peut-on calculer le hasard ? France culture 8/12/2016. Références bibliographiques.