Cours1 meta 4gi 2013 inro mc

Les métaheuristiques Pour L ? optimisation di ?cile Maria ZRIKEM ENSA de Marrakech Les métaheuristiques COptimisation combinatoire L ? homme envisage di ?cilement la multiplicité des combinaisons qui se présentent même dans les moindres faits de la vie lorsque plusieurs variables peuvent prendre chacune des états di ?érents Exemple Combien faut-il de temps à une famille de personnes prenant en commun deux repas journaliers pour épuiser toutes les possibilités de se grouper autour de la table familiale ENSA de Marrakech Les métaheuristiques COptimisation combinatoire ? f X ? R ?? fonction objectif ? X ?? ensemble de solutions possibles réalisables X est un ensemble ?ni mais de taille énorme ENSA de Marrakech Les métaheuristiques CProblèmes faciles et problèmes di ?ciles ? Algorithme polynomial le temps d ? exécution cro? t de façon polynomiale avec la taille du problème O nd ? Problèmes faciles classe P il existe des algorithmes polynomiaux ? Problèmes NP-dif ?ciles - on ne conna? t pas d ? algorithmes polynomiaux - on n ? arrive pas à démontrer la non-existence de tels algorithmes - s ? il existe un algorithme polynomial pour un de ces problèmes alors il existe des algorithmes polynomiaux pour toute la classe ENSA de Marrakech Les métaheuristiques CProblèmes faciles et problèmes di ?ciles L ? optimisation combinatoire ? consiste à trouver la meilleure solution entre un nombre ?ni de choix Autrement dit à minimiser une fonction avec ou sans contraintes sur un ensemble ?ni de possibilités Quand le nombre de combinaisons possibles devient exponentiel par rapport à la taille du problème le temps de calcul devient rapidement critique ENSA de Marrakech Les métaheuristiques CProblèmes faciles et problèmes di ?ciles O n O n O n O n O lg n ENSA de Marrakech Les métaheuristiques CExemple de problème facile Trouver le plus court chemin entre deux sommets dans un graphe ? Quelle est la taille de l ? espace des solutions ? Faut-il parcourir toutes les solutions pour trouver la meilleure ENSA de Marrakech Les métaheuristiques COptimisation combinatoire Problème d ? a ?ectation n t? ches doivent être a ?ectées à n machines t? che par machine Le coût d ? exécution de la t? che i par la machine j est cij Trouver l ? a ?ectation qui minimise le coût total ENSA de Marrakech Les métaheuristiques COptimisation combinatoire Problème du voyageur de commerce Un voyageur de commerce doit visiter n villes La distance entre les villes i et j est cij Trouver le plus court trajet cycles di ?érents pour le même ensemble de villes ENSA de Marrakech Les métaheuristiques COptimisation combinatoire begin input n number of cities C n x n non negative integer distance matrix min su ?ciently large number say n times the maximum element of C for all possible tours i e cyclic permutations of n ?nd length of tour if length min then min length store tour endif next tour end Les solutions possibles sont n Pour n l ? énumération des a ?ectations trajets

Documents similaires
1 hygiene Introduction L ? Hygiène la Santé et la Sécurité au Travail tiennent aujourd ? hui une place de plus en plus prépondérante dans la stratégie et le management de l ? entreprise car au-delà du drame humain et social qu ? occasionnent un accident d 0 0
Grt et gme Année Académique - COURS DE MANAGEMENT DES ORGANISATIONS CREATION D ? ENTREPRISE ALAIN M MANGA M LICENCE GRT GME CTable des matières PREMIERE PARTIE GESTION DES PROJETS INTRODUCTION GENERALE CHAPITRE LES GRANDS PRINCIPES DU MANAGEMENT Dé ?nitio 0 0
Automobile BAC professionnel Maintenance de véhicules automobiles option voitures particulières CSECTEUR AUTOMOBILE Nom du BAC Maintenance de véhicules automobiles voitures particulières Objectifs de la formation préparée Fiche détaillée Ce bac pro forme 0 0
Modele de cahier des charges pour une application mobile aventique 3 0 0
Livres ado Généralités Allgemeines Psychologie de la lecture RERO Lire-écrire de l'enfance à l'? ge adulte genèse des compétences pratiques éducatives impacts sur l'insertion professionnelle sous la dir de Jean-Pierre Gaté et Christine Gaux - Rennes Press 0 0
Exercice n°1 : (2 points) Évaluer les expressions suivantes dans l'ordre et do 0 0
Le portfolio en TC - BUT2 Enseignante : Marie-Christine PAVIS Le portfolio, tou 0 0
MODALITÉS PÉDAGOGIQUES Le programme est conçu afin de permettre de concilier fo 0 0
I. Obtenir la certification ISO 9001 Beaucoup de dirigeants de PME craignent d’ 0 0
Maya LEROY AgroParisTech Géraldine DERROIRE AgroParisTech Jeremy VENDÉ AgroPari 0 0
  • 28
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Aucune attribution requise
Partager
  • Détails
  • Publié le Apv 09, 2022
  • Catégorie Management
  • Langue French
  • Taille du fichier 58.3kB