RESSOURCES EN LIGNE ET ACTUALITÉS
SCIENTIFIQUES FRANCOPHONES

7379 - Introduction aux techniques d'optimisation combinatoire

Ressource pédagogique

Auteur :: Rivreau, David (UCO. Université catholique de l'Ouest. IMA. Institut de mathématiques appliquées. Angers. France)
Page source :: Page personnelle du Pr. Rivreau, http://www.math-appli-uco.fr/~rivreau/Cours/Course3.html
Langue :: français

Spécialité :: Sciences exactes - Mathématiques - Analyse numérique, calcul scientifique
Mots clés :: algorithmique ; optimisation
Table des matières :: 1 - Introduction à la théorie de la complexité
2 - Topologie de problèmes
2.1 - Problèmes de « routing »
2.2 - Programmation linéaire
2.3 - Problèmes d'affectation
2.4 - Problèmes de découpe
2.5 - Problèmes d'ordonnancement
3 - Méthodes heuristiques
3.1 - Introduction
3.2 - Algorithmes construisant une solution
3.3 - Techniques de voisinage
4 - Méthodes exactes
4.1 - Recherche arborescente
4.2 - Programmation dynamique
Bibliographie
Résumé :: Ce support de cours traite des terminologies et formalismes utilisés pour décrire les problèmes (d'affectation, de découpe ou d'ordonnancement) d'optimisation combinatoires les plus souvent rencontrés en pratique. Les méthodes adaptées aux données de grande taille, telles que les techniques de voisinages, sont explicitées. Le dernier chapitre est consacré aux recherches arborescentes et à la programmation dynamique, qui constituent les principales méthodes exactes usitées dans le cas des données de taille moyenne. Le document contient quelques algorithmes et une bibliographie exhaustive. (d'après le résumé de l'auteur)

Niveau d'études :: 2e cycle
Pré-requis :: Notion de programmation linéaire et bonne compréhension de l'analyse du 1er cycle
Objectifs pédagogiques :: Avoir des éléments d'appréciation de l'efficacité d'un algorithme et de gestion de difficultés nées d'un problème d'optimisation combinatoire.

gratuit

Notice mise en ligne le 16/09/2004