Manière de résoudre les problèmes

Basic problems: plus court chemin

RO = PROBLÈMES+ MÉTHODES

Best solution = solution optimale

Problèmes :

• KnapSack problem:

  • AKA : KP problem

  • Données

  • Objectif:

    Problème de type sac à dos : Prendre tout si on est libre à choisir

    Chaque objet va recevoir deux valeur : Utilité + Cout ( Place / poids )

    Décision : prendre ou pas pour maximiser l’utilité totale

• Bin Packing Problem : KP problem

  • Problème de remplissage:

  • Planning d’une matinée (4h)

  • Importance dépend de l’utilité de la tache : on va l’accorder un chiffre

  • 1D/ 2D/3D : Compléxite/ dimension de problème (Minimiser le nombre de tubes de tailles définiee… Minimiser le nombre de plaques de bois pour fabriquer …)

  • Exemple TSP: traveling salesman problem

    Choisir un point

    chaque point est visité une seule fois

  • VRP : Vehicle routing problem

    Localisation des entrepots

    Ordonnancement d’atelier

Résolution des problèmes :

• Méthode exacte : Donne la solution optimale ( Mathématiquement ) Pas d’autre solutino réalisable qui va faire mieux ).

  • Programmation dynamique, BnB

• Méthodes approchées : heuristiques + Méthaheuristiques. Très facile à expliquer, très difficile à resoudre.

  Il s’agit de trouver une idéee pour résoudre le problème réellement + formaliser l’idée en pseudo-code

  algorithme cherche des solutions réalisables ( ça doit respecter toutes les contraintes du problème )= réflechir à tete reposée.

  Raisonnement intuitif = Basé sur l’experience

  On ne peut jamais trouver la solution optimale on essaye de l’approcher

  GAP :

  c’est le gap entre la solution trouvée et une solution référentiel (en pourcentage )

  GAP = 100(sol - solopt) / solopt

  sol = solution heuristique