Algorithme Exercices

Cours 9 : programmation linéaire (recherche opérationnelle) • • • • 1. Exemple introductif 2. La méthode du simplexe 3. Dictionnaires 4. Algorithme C. JARD Cours ALGO1 MMI+MIT 2007-2008 1 1. Introduction : la raffinerie • Production optimale d’une raffinerie produisant 4 produits finis (essence, kérosène, mazout et résidu) à partir de deux types de pétrole brut (brut1 et brut2), avec les paramètres suivants : Produit $/baril Essence Kérosène Mazout Résidu Rendement(%) Brut1, Brut2 80

de lave et les volcans (Service Géologique Américain ‘USGS’) 26 5.3. Informatique décisionnelle 26 5.4. Applications industrielles 27 6. Conclusion 27 Chapitre 4 : Model Meta heuristique proposé 28 1. Introduction 28 2. Les algorithmes génétiques 30 2.1. Présentation 30 2.2. Principe Général : 30 3. Formalisation du problème 33 4. La mise en œuvre de l’AG 34 4.1. Codage proposé 35 4.2. La procédure d’évaluation (la fonction fitness) 36 4.3. La procédure

[Kirkpatrick et al., 1983] et la Recherche Taboue [Glover, 1986]. La deuxième approche, appelée Méthode Évolutive, est plus récente puisqu’ elle date du début des années 90. Elle s’ est particulièrement faite connaître par l’ intermédiaire des algorithmes génétiques dont l’ origine remonte aux travaux de Holland [Holland, 1975]. Le but de ce chapitre n’ est pas de donner une description précise de l’ ensemble des métaheuristiques couramment utilisées en optimisation. Nous visons plutôt à guider toute

Note La règle (appelée « principe d’optimalité ») commune aux algorithmes de recherche de plus courts chemins peut s’énoncer ainsi : un plus court chemin [S1, Sn] entre deux sommets S1 et Sn d’un graphe est constitué de plus courts chemins reliant deux sommets du chemin [S1, Sn] ; on la démontre par l’absurde sans problème. La recherche du plus court chemin passe donc par la recherche des plus courts chemins reliant S1 à tous les sommets du graphe susceptibles de se trouver sur le trajet ;

Algorithmique sur les tableaux : Nous étudierons dans ce cours des algorithmes standards de recherche dans un tableau, ainsi que des algorithmes de tris. Recherches :  ●Recherche séquentielle ●Recherche dans un tableau trié ●Recherche dichotomique Tris :  ●Tri par sélection ordinaire ●Tri à bulles ●Tri par insertion séquentielle ●Tri par insertion dichotomique Nous aborderons sur ces exemples la complexité des algorithmes. Les algorithmes de recherche et tri seront essentiellement écrits à l'aide de fonctions

Bases, bases réalisables, solutions de base 4 Base & hors-base 4 Solution de base 4 Exemple 5 Caractérisation d’une base réalisable 5 Théorème 5 Solutions optimales 5 Caractérisation des bases optimales 5 Théorème 5 Exemple classique 6 Algorithme du simplexe – Méthode des tableaux 6 Méthode 6 Exemple classique 7 Analyse du tableau final du simplexe 8 Méthode révisée du simplexe 9 Convergence & Initialisation du simplexe 10 Théorème : Convergence de l’algorithme 10 Initialisation

e La m´thode du simplexe e Les probl`mes ` solution d´g´n´r´e e a e e ee Les deux phases du simplexe D´termination de la solution de base optimale e 1 n Nombre maximum de solutions de base :Cm = n! m!(n−m)! 2 Algorithme ”bˆte et m´chan” : ´num´ration de toutes les e e e e bases. 3 M´thode du simplexe : partir d’une solution de base e admissible et passer ` une solution de base voisine qui a am´liore la valeur de l’objectif. e 4 Solution voisine

cours • Les bases de l’algorithmique : – Paradigmes de résolution – Paradigmes de programmation – Eléments du langage algorithmique • Programmation modulaire • Récursivité, • Complexité Algorithmique, • Structures de Donnés (S2D), • Algorithmes de Tri et de recherche. Les bases de l’algorithmique : 1. Paradigmes de résolution 2. Paradigmes de Programmation 3. Eléments du langage algorithmique a. Notions de base. b. Objets et actions élémentaires. c. Les structures fondamentales

scientifiques et réalisations techniques Sujet :Les algorithmes génétiques dans la réalisation matérielle Problématique : Les algorithmes génétiques peuvent Ils surpasser les ingénieurs humains ? Sommaire: Qu’est-ce qu’un algorithme? Qu’est-ce qu’un algorithme génétique? Comment un algorithme génétique intervient dans la réalisation matérielle? Qu'est-ce qu'un algorithme? D'après la définition d'origine,un algorithme désigne une suite d'opération ou d'instruction qui permette

nombreux probl` emes r´eels peuvent ˆetre exprim´es comme 2. L’algorithme du simplexe des programmes lin´eaires. 3. Simplexe : comment ´eviter les pi`eges • Les programmes lin´ eaires peuvent ˆetre r´esolus efficacement 4. Dualit´e par certains algorithmes. 5. Programmation lin´eaire en nombres entiers • Ce sont d’excellents exemples de questions pratiques dont la r´esolution n´ecessite une combinaison de m´ethodes algorithmiques, de math´ematiques ´el´ementaires et de bon sens. Bibliographe :