Topic outline

  • General

    Ce cours a pour objectif de sensibiliser à la démarche de l'aide à la décision : analyse d'un problème, modélisation, résolution, analyse de la solution.

    Auteure : Anne-Marie CHARLES, Université de Paris IX

    Édition : AUNEGe, Université de Paris IX

    Présentation de la ressource : http://ressources.aunege.fr/notice/view/aunege-225 

    • Objectifs et Prérequis

      Objectifs du cours

      Ce cours a pour objectif de sensibiliser à la démarche de l'aide à la décision :

      • Analyse d'un problème ;
      • Modélisation ;
      • Résolution ;
      • Analyse de la solution.

      Prérequis du cours

      Pour aborder ce cours il faut maitriser le formalisme et l'écriture mathématique, par exemple l'utilisation aisée du signe somme est nécessaire.

      En termes de connaissance, seule la résolution des systèmes d'équations linéaires est un prérequis.

      En ce qui concerne les outils bureautiques il faut savoir manipuler Excel.

      Le niveau de référence en mathématiques peut être celui d'un L2 de Sciences économiques.


      • Introduction

        Objectifs de l'introduction

        Cette introduction donne un aperçu détaillé du contenu du module de modèles d'aide à la décision :

        • Le contexte ;
        • L'auteur ;
        • Le découpage : cours, exercices et bibliographie ;
        • Les points abordés par chacun des éléments composant le module.
      • Leçon 1

        Objectifs et prérequis 

        La démarche de l'aide à la décision :

        • C'est une leçon d'introduction à la problématique de l'aide à la décision et de la recherche opérationnelle.
        • Elle comporte aussi les notions élémentaires essentielles sur les algorithmes.
        • C'est un préalable à toutes les autres leçons.
      • Leçon 2

        Objectifs et prérequis 

        Les graphes, un outil de modélisation :

        • Dans cette leçon on introduit les concepts dans les graphes qui seront exploités par la suite.
        • Cette leçon est nécessaire pour les 3 leçons suivantes, pour celui qui n'a jamais vu cela.
        • Pour les autres qui peuvent passer plus rapidement elle peut constituer un rappel.
      • Leçon 3

        Objectifs et prérequis 

        Le problème du plus court chemin :

        • Dans cette leçon on définit le modèle de plus court chemin.
        • On présente des exemples d'application.
        • On propose un algorithme de résolution dans le cas où les longueurs des arcs sont toutes positives.
      • Leçon 4

        Objectifs et prérequis 

        Résolution de problèmes de plus court chemin :

        • Dans cette leçon, on propose des algorithmes de résolution pour le cas des graphes sans circuit ainsi que pour celui d’un graphe quelconque.
        • Elle suppose connue la leçon 3.
      • Leçon 5

        Objectifs et prérequis

        Le problème central de l'ordonnancement :

        • Dans cette leçon, on introduit le problème central de l'ordonnancement de tâches dont l'objectif est l'élaboration d'un calendrier d'exécution des différentes tâches d'un projet liées entre elles par des contraintes d'antériorité de manière à réaliser l'ensemble des tâches dans le temps le plus court.
        • On le modélise par un problème de plus long chemin dans un graphe.
        • Il devient alors possible de le résoudre en s’appuyant sur les résultats des leçons 2 et 3 précédentes qui constituent des pré-requis.
      • Leçon 6

        Objectifs et prérequis 

        Problèmes de flots dans un graphe :

        • Dans cette leçon, on introduit un nouveau concept dans les graphes : la notion de flot qui permet de prendre en compte les aspects de "quantités" circulant sur un "réseau".
        • Elle pourrait être vue immédiatement après la leçon 2 qui introduit les principales notions sur les graphes.
        • Les 3 leçons suivantes ne nécessitent que la leçon d'introduction. Elles doivent être prises dans cet ordre mais s'il n'est pas nécessaire de les voir toutes les 3, ce serait dommage de ne pas le faire !
      • Leçon 7

        Objectifs et prérequis 

        La programmation linéaire : outil de modélisation :

        • Nous abordons dans cette leçon un autre type de modélisation.
        • Un problème d'optimisation va être représenté par un problème de programmation mathématique : les variables de décision sont des variables numériques, la représentation des décisions possibles et du critère fait appel à des équations ou fonctions mathématiques.
        • Plus précisément on introduit ici le problème particulier de programmation linéaire et on présente un certain nombre d'exemples de modélisation.
        • Nous traitons aussi la résolution graphique d'u problème de programmation linéaire ce qui permet d'introduire l'analyse de sensibilité.
      • Leçon 8

        Objectifs et prérequis 

        La programmation linéaire – Résolution analytique :

        • Dans cette leçon on aborde un algorithme de résolution d'un problème de programmation linéaire : l'algorithme du simplexe.
        • On le présente d'abord sur un exemple avant d'en donner le principe général.
        • On voit ensuite comment un outil comme Excel permet de résoudre un problème de programmation linéaire.
      • Leçon 9

        Objectifs et prérequis 
        La programmation linéaire : Analyse de sensibilité :

        • On aborde dans cette leçon la partie analyse de sensibilité de la résolution d'un problème de programmation linéaire.
        • Il s'agit d'étudier les conséquences d'une variation d'un coefficient de la fonction objectif et du second membre d'une contrainte.
        • Les 2 précédentes constituent un prérequis.
        • Cette leçon nécessite l'utilisation du tableur Excel.
      • Leçon 10

        Objectifs et prérequis 
        Intro aux problèmes combinatoires difficiles : Le problème du voyageur de commerce et le problème de coloration :
        • Dans cette leçon, dont l'objectif est de sensibiliser à l'existence de problèmes dits difficiles et la nécessité d'utiliser des méthodes de résolution approchées, on présente deux problèmes très célèbres, celui du voyageur de commerce et celui de la coloration d'une carte de géographie.
        • Pour cette leçon, outre la leçon1, quelques définitions sur les graphes rappelées en leçon 2 sont nécessaires.
      • Leçon 11

        Objectifs et prérequis 

        Les problèmes d'ordonnancement avec ressources :

        • Dans cette leçon, on retrouve le problème d’ordonnancement déjà vu leçon 5 mais en ajoutant la prise en compte de contraintes portant sur les ressources.
        • Après un exemple d’introduction, on définit le problème, et on aborde le cas où des tâches doivent être effectuées par un seul opérateur puis par deux opérateurs successifs.
        • Après avoir souligné la difficulté de la grande majorité des problèmes d’ordonnancement, on présente des méthodes de résolution approchées.
        • On termine par la présentation du problème particulier du bin packing.
        • Cette leçon ne nécessite aucun prérequis autre que la leçon 1 et la leçon 10 pour en comprendre la problématique.
        • En particulier la leçon 5 (problème central de l'ordonnancement) n'est pas indispensable.
      • Leçon 12

        Objectifs et prérequis

        Intro à la programmation linéaire en nombre entiers :

        • On aborde dans cette leçon la problématique de programmation linéaire en nombres entiers.
        • On s'intéresse essentiellement à la modélisation de ces problèmes et non à leur résolution et on présente quelques-uns des très nombreux problèmes susceptibles d'être modélisés par un problème de programmation linéaire en nombres entiers.
        • La leçon intitulé : "La programmation linéaire : un outil de modélisation" est un préalable ainsi que la leçon 10 "Introduction aux problèmes combinatoires difficiles".