Aide à la décision

Introduction à l’optimisation

Tout problème industriel consiste, sous certaines conditions, à maximiser un profit ou minimiser les dépenses. Dans ce contexte, profit et dépenses ne font pas toujours référence à une variable monétaire, cela peut aussi se traduire par le temps, la distance ou autres.

Bien souvent, le problème est énoncé de manière brute, c’est-à-dire par un texte ou un cahier des charges. L’industriel n’était pas expert dans le domaine de l’écriture d’un problème mathématique, le cahier des charges comprend toutes sortes de données, utiles ou non pour sa modélisation.

Même dans le cadre où vous êtes vous-même commanditaire, il se peut que vous ne connaissiez pas l’étendue de votre problème, et que vous découvrez au cours de l’eau les différentes contraintes et variables à faire face.

Un autre problème s’annonce une fois la modélisation mathématique effectuée : quel outil informatique utilisé pour résoudre ce problème ? quel algorithme choisir ? sa simulation ? sa complexité ? son optimalité ?

Construire et résoudre un problème industriel demandent donc de la rigueur, de la souplesse d’esprit et de suivre une démarche de modélisation précise.

Optimisation et aide à la décision

Un problème D est de décision si la réponse est binaire : Oui ou Non. On note Oui(D) l’ensemble des instances auxquelles on répond Oui.
Prenons le problème de décision suivant : soit un graphe G pondéré, existe-t-il un arbre couvrant ? Oui(D) = {sous-graphe de G connexe non cyclique}. Le problème : existence d’un arbre couvrant de poids ≤ k est aussi un problème de décision. Le problème d’optimisation est de rechercher la valeur k de telle sorte qu’elle soit minimale.

Construction d’une problème d’optimisation

Afin de mieux comprendre les deux notions, nous allons prendre un exemple :

Vous souhaitez faire un tour d’Europe, en visitant un certain nombre de villes dans un laps de temps de 6 mois. De plus, vous souhaitez rester une certaine durée dans chaque lieu afin de pouvoir visiter les zones touristiques et admirer le paysage.

Ce genre de problème a différentes façons d’être modélisation en fonction de ce qu’on souhaite faire : être le plus rapide, favoriser les zones densément touristiques, etc. Il faut sélectionner une décision parmi un ensemble de décision possible de manière à optimiser le critère choisi.

La modélisation comporte une recherche de minimum ou de maximum, il s’agit donc d’une optimisation. Les problèmes d’aide à la décision contiennent tous les trois points suivants :

  • Le type de décision : ce que l’on veut faire (ici nous cherchons une optimisation)
  • Les décisions possibles : ce que l’on peut faire (le domaine de définition)
  • Le critère de sélection : comment on choisit (la modélisation du problème).

Le problème étudié se place dans un certain contexte qui sera traduit en paramètres. Toutes les relations entre ces derniers sont représenté dans le modèle. Ce dernier peut soit prendre le forme d’un modèle mathématique, soit un graphe.

La modélisation n’est qu’une représentation schématique du problème, seuls les éléments jugés pertinents sont retenus dans la construction de la décision. Elle procède par simplifications et omissions.

L’environnement du modèle peut aussi jouer un rôle. Que ce soit déterministe ou avec incertitude, il est présent via des lois de probabilité, du stochastique, etc. au sein des contraintes.

Le critère de sélection peut amener à des solutions différentes en fonction du paramètre mis en avant. Dans certains cas, le modèle ne présente qu’un seul critère de sélection, on parle alors de recherche opérationnelle.

Tous les modèles sont constitués de trois composants de base:

  • Les variables de résultat sont des sorties. Le reflètent le niveau d’efficacité du système. Ce sont des variables dépendantes.
  • Les variables de décision décrivent des actions alternatives.
  • Les variables incontrôlables sont des facteurs qui affectent le résultat mais ne sont pas sous le contrôle du décideur. Soit ces facteurs sont fixes ou ils peuvent varier.

Les composants sont reliés entre eux par des expressions mathématiques dans une structure de modèles quantitatifs. Un principe de choix est un critère qui décrit l’acceptabilité d’une solution d’approche.

Un modèle peut être un modèle normatif ou un modèle descriptif. Dans le premier, la solution choisie est manifestement la meilleure de toutes les alternatives possibles. Pour la trouver, il faut examiner toutes les alternatives et prouver que celle qui est sélectionnée est effectivement la meilleur (on parle d’optimisation). Les modèles descriptifs étudient des actions alternatives sous différentes configurations d’entrées et de processus. Toutes les alternatives ne sont pas vérifiées, seul un ensemble donné le sont.

Modélisation d’un problème

Les quatre étapes de la modélisation d’un problème industriel sont les suivantes :

  • Quelles sont les données du problème ? récolter les données du problème, comprendre le problème;
  • Comment modéliser le problème ? les trois points de l’aide à la décision
    • Quelles décisions doit-on prendre ? sélectionner/placer des objets, définir un ordre ou une quantité, choisir un évènement, effectuer une opération particulière;
    • Quels sont les contraintes du problème ? respecter des capacités ou des contraintes de précédence;
    • Quel est l’objectif recherché ? maximiser un profit, minimiser des coûts ou une quantité;
  • Quelle est la complexité de ce problème ? polynomiale, Np, Np-difficile;
  • Comment résoudre le problème ? concevoir des algorithmes (exacts vs approchés) donnant des solutions réalisables/optimales, développer des méthodes alternatives ou hybrides

En fonction de la modélisation mathématique, le modèle peut aussi servir de simulation. Il est alors possible de voir l’impact de certaines décisions dans un contexte différent de celui étudié (comme l’étude de sensibilité du simplexe).

La prise de décision implique trois phases majeures suivies par la phase de validation:

  • Collecte d’informations: Examiner et identifier le problème (variables, fonctions, valeurs, etc.).
    • Identification du problème: Identification des buts et objectifs organisés liés à un problème. Pour déterminer si un problème existe, identifiez ses symptômes, déterminez leur ampleur et définissez-le explicitement. Certains problèmes peuvent survenir lors de la collecte et de l’estimation des données comme le manque de données, des données imprécises ou inexactes, une mauvaise estimation, une surcharge d’information, des données simulées, etc.
    • Classification du problème: La classification du problème est le placement d’un problème dans une catégorie définissable. Cela conduit à une approche par une solution standardisée.
    • Décomposition des problèmes: De nombreux problèmes complexes peuvent être divisés en sous-problèmes. Certains problèmes non structurés peuvent avoir des sous-problèmes très structurés.
  • Conception: Construire un modèle qui représente le système.
    • Comprendre le problème: La modélisation implique l’abstraction du problème à des formes quantitatives et / ou qualitatives.
    • Un modèle est construit, testé et validé: Pour un modèle mathématique, les variables sont identifiées et les relations entre elles sont établies. Tous les modèles sont constitués de trois composantes de base: les variables de décision, les variables incontrôlables et les variables de résultat. Les relations mathématiques lient ces composants ensemble. Dans un modèle non quantitatif, les relations sont symboliques ou qualitatives.
  • Choix: Pour sélectionner une solution au modèle.
    • Recommandation d’une solution: Lorsque le problème est résolu, une solution est choisie en fonction du modèle. Celle-ci est recommandée sur l’ensemble des solutions.
    • Evaluation d’une solution: L’évaluation est possible si les variables de résultat donnent une solution quantitative. Une relation de préférence sur l’ensemble de la solution donne un ordre: f (a) ⪯ f (b) signifie que f (b) est meilleur ou égal à f (a) où a, b sont des variables et f (.) est une fonction mathématique basée sur les variables de résultat. b est la meilleure solution ssi: f (x) ⪯f (b) pour tout x dans l’ensemble de la solution.
  • Implémentation: Implémenter un logiciel pour résoudre n’importe quelle instance du modèle.
    • Implémentation classique/itérative: les algorithmes itératifs utilisent des constructions répétitives comme des boucles et parfois des structures de données supplémentaires comme des piles pour résoudre les problèmes donnés.
    • Récursivité: un algorithme récursif est un algorithme qui fait référence à lui-même à plusieurs reprises jusqu’à ce qu’une condition de terminaison corresponde.
    • Logique: un algorithme logique est composé d’une composante logique et d’une composante de contrôle.
    • Déterministe ou non déterministe: les algorithmes déterministes résolvent le problème avec une décision exacte à chaque étape de l’algorithme, tandis que les algorithmes non déterministes résolvent les problèmes par « devinettes ». Un algorithme déterministe est un algorithme qui, donné une entrée particulière, produira toujours la même sortie.
    • Exact ou approximatif: Alors que de nombreux algorithmes atteignent une solution exacte, les algorithmes d’approximation recherchent une approximation proche de la vraie solution. Quand il n’est pas possible de trouver la meilleure solution en temps humain, on peut chercher une solution approchée par des algorithmes moins complexes.
    • Série, parallèle ou distribué: ces implémentations dépendent des architectures informatiques, c’est-à-dire du nombre de processeurs qui peuvent travailler sur un problème en même temps, et comment décomposer l’ensemble du processus en processus indépendants.
    • Paradigme: Brute-force; Diviser et conquérir; Programmation dynamique; Chercher; Randomisé; Réduction. Ensuite, nous devons vérifier la terminaison, la correction et la complétude de l’algorithme.
  • Validation: Pour valider le logiciel s’il présente un temps de calcul raisonnable et une bonne solution.
    • La complexité du meilleur cas: C’est la complexité pour résoudre le problème pour la meilleure entrée de taille n.
    • La complexité du pire des cas: C’est la complexité pour résoudre le problème pour la pire entrée de taille n.
    • Complexité moyenne des cas: C’est la complexité pour résoudre le problème en moyenne. Cette complexité n’est définie que par rapport à une distribution de probabilité sur les entrées. Par exemple, si toutes les entrées de la même taille sont supposées être également susceptibles d’apparaître, la complexité moyenne des cas peut être définie par rapport à la distribution uniforme sur toutes les entrées de taille n.

 

Solution et décision

Une fois que le modèle a été créé et qu’une solution a été trouvé, il est important de l’analyser afin de valider le modèle. Ce dernier n’était qu’une représentation schématique du problème, il peut ne pas convenir à l’objectif recherché. Une solution met en évidence la validité des choix de décision et des choix du modèle. Seul le décideur / commanditaire peut valider l’approche effectuée.

Le schéma du processus d’aide à la décision est le suivant :

aidedecision

Aparté

L’aide à la décision requiert une grande capacité d’abstraction, une bonne connaissance de l’algorithmique et de la théorie des graphes, ainsi que des problèmes de complétude calculatoire.

Publicités