Optimisation d'un arrangement
Répondre à la discussion
Affichage des résultats 1 à 4 sur 4

Optimisation d'un arrangement



  1. #1
    muzbang

    Optimisation d'un arrangement


    ------

    Bonjour,

    J'ai une problématique assez simple.

    J'ai N entités (E) que je souhaite distribuer dans N positions (P), en fonction des préférences des entités pour des positions.
    Chaque entité est unique
    Chaque position est unique.
    Chaque entité doit être affectée à une (et une seule) position
    (et chaque position ne peut se voir attribuer qu'une et une seule entité)

    J'ai une répartition de base "aléatoire".
    Typiquement E1 dans P1, E2 dans P2 etc
    Pour chaque couple entité / position, j'ai une valeur de préférence.

    Je voudrais trouver la solution optimale qui maximise les préférence des entités (de manière globale)

    Par ex voici mes données de départ
    E1 - P1 - 10
    E1 - P2 - 5
    E1 - P3 - 6
    ...
    E1 - Pn - X
    ...
    En - Pn
    etc pour chaque couple E/P
    (qui peuvent aussi se présenter sous une matrice de taille NxN)

    Autrement dit sur les 3 lignes présentées l'entité E1 préfère la position P1 (10), puis la position P3 (6) puis P2 (5)

    J'ai une matrice de coûts de transition qui dit que quand on enlève E1 de P1, ça lui fait perdre X points (en l’occurrence 10) et ça luis fait gagner 5 points (si on la met en P2) ou 6 points si on la met en P3.
    (et donc quand on mettra une autre entité En en P1 celle ci perdra ses points de la position n pour gagner ceux de la position 1)

    Voilà à peu près où j'en suis de la problématique, sachant que je pense programmer ça en C++, avec idéalement un algorithme pas trop gourmand en temps d'exécution, même si je ne compte pas appliquer à plus de N=10 (ce qui en l’occurrence représente quand même 3.628.800 arrangements possibles)

    Je me doutes qu'il doit exister des algorithme pour cette problématique mais je ne trouve pas
    L'option de dénombrer toutes les possibilités et de calculer la somme des coûts est une option, mais est-ce vraiment efficace ( ? )

    Si vous avez des commentaires ou des sources à partager, je vous en serai reconnaissant

    Merci

    -----

  2. #2
    iPhysics

    Re : Optimisation d'un arrangement

    Bonjour,

    Le type de problème que tu décris est une famille très célèbre en optimisation combinatoire qu'on appelle "problème d'affectation". En général, on peut résoudre en temps polynomial avec l'algorithme hongrois (je ne suis pas expert, je te laisse aller vérifier).

  3. #3
    muzbang

    Re : Optimisation d'un arrangement

    OK merci,
    Effectivement en poursuivant mes recherches je suis tombé sur ce fameux algorithme hongrois que je vais devoir déchiffrer. Pas simple, vu que le hongrois est une des langues les plus complexes au monde

    Traité de plaisanterie j'ai aussi réussi à mettre un nom sur la configuration. Il s'agit d'un graphe biparti complet

    Et effectivement c'est bien un classique...

    Merci pour avoir pris le temps de répondre

    Ya plus qu'à...
    Ps: je vais probablement aussi rajouter des contraintes à un moment donné, mais apriori sans complexités. Ça fera peut être même gagner du temps d'exécution de réduire le champ des possibles.

  4. #4
    iPhysics

    Re : Optimisation d'un arrangement

    Heureusement que la méthode hongroise porte mal son nom alors !
    En effet, du , c'est une aubaine quand on sait que la plupart des problèmes d'optimisation combinatoire sont NP-complets (une aubaine si tant est que P != NP).

    Attention que paradoxalement, rajouter des contraintes peut au contraire complexifier le code (exemple, pour passer d'un problème LP à un problème ILP, on réduit le champ des possible aux entiers ce qui rend les problèmes souvent combinatoires). En optimisation combinatoire, c'est en réalité plutôt rare que les problèmes "sur mesure" soient adaptés aux algorithmes de résolution exacte en un temps raisonnable, on utilise majoritairement des métaheuristiques comme l'algorithme génétique ou le recuit simulé.

    Bonne exploration !

  5. A voir en vidéo sur Futura
  • Discussions similaires

    1. Equation et Arrangement !
      Par inviteaf7e4316 dans le forum Mathématiques du collège et du lycée
      Réponses: 2
      Dernier message: 02/05/2012, 22h35
    2. [Microbiologie] Arrangement cellulaire
      Par invitef403c8b9 dans le forum Biologie
      Réponses: 2
      Dernier message: 07/11/2011, 20h31
    3. Arrangement cristallin
      Par inviteed4c160a dans le forum Physique
      Réponses: 0
      Dernier message: 19/10/2011, 21h06
    4. Arrangement d'un polymère
      Par invite18557941 dans le forum Chimie
      Réponses: 4
      Dernier message: 04/02/2011, 16h07
    5. combinaisons, arrangement
      Par inviteec33ac08 dans le forum Mathématiques du supérieur
      Réponses: 2
      Dernier message: 07/08/2010, 16h57