Optimisation planning de rencontres
Bonjour à tous,
Je reviens vers vous car vous m'avez beaucoup aidé la dernière fois.
Je me retrouve face à un problème d'optimisation pour une série de rencontres.
J'ai X individus dans une réunion et je souhaiterais organiser des rencontres.
Chaque individu fera trois rencontres et on leur demande de remplir à l'avance un formulaire dans lequel ils vont marquer qui ils veulent rencontrer et donner une pondération à chaque choix.
Les rencontres sont simultanées et donc si Etienne rencontre Marc dans le premier Slot, Marc ne peut pas être rencontré par quelqu'un d'autre à ce slot.
Les données auront ce format:
Qui / Premiere rencontre / Deuxieme rencontre / Troisieme rencontre / Poids 1 / Poids 2 / Poids 3
Etienne Jerome Marc Pierre 1 8 1
Marc Paul Etienne Jerome 2 6 2
Jerome Pierre Marc Etienne 3 3 4
Pierre Etienne Marc Jerome 4 4 2
Paul Marc Jerome Pierre 3 4 3
Qui se lisent:
Etienne veut rencontrer : {Jerome; Marc; Pierre} avec des poids respectifs de {1;8;1}
Je voudrais trouver un optimum (qui serait la somme maximale des poids) et donc un planning des rencontres. comment m'y prendre?
Avec pour contrainte que tout le monde ait 3 RDV (si possible)
Merci infiniment pour votre aide,
Bien à vous,
E
Bonjour,
L'ordre des rencontres est à respecter ?
Etienne veut rencontrer Marc à la 2nde et surtout pas à la 1ère ?
eric
Excuse moi Eric de n'avoir pas precisé ce paramètre, non. L'ordre n'a aucune importance. Serait il possible de trouver toutes les solutions optimales (somme des bonheurs)dans differents onglets (Ws.add)? Si le nombre de personnes n'est pas suffisant certains n'auront pas toutrs leurs rencontres remplies.. si tu sais resoudre cela pourrais tu rajouter une colonne pour mettre un X pour les personnes les moins importantes afin de les laisser eux sans leur troisième rencontre? À minima deux rencontres par personne! Je complexifie mais sachant que tu fais des codes qui me sont incompréhensibles je sais que tu en es capable.. si tu veux me donner ton numéro en privé je me ferais une joie de t'appeler pour faire connaissance et pour t'exposer mon problème! Un excellent WE!
E
Hummm, pour l'instant je tâtonne pour voir comment ça se présente.
Mais je ne suis pas sûr de pouvoir le mener à terme. Bien occupé ce we et plus ou moins absent la semaine prochaine.
Mais si ça peut débroussailler pour les suivants....
Je n'ai fait que le cumul pour voir et déjà des questions.
Si Marc note 4,4,3 (j'ai supposé qu'ils avaient un total de 10 à répartir ?) et que 3 autres notent 8 pour une rencontre avec lui il n'aura aucune rencontre désirée. Comment comptes-tu régler ce pb ?
Quant à générer les meilleures solutions c'est très complexe.
Si tu as un système de notation correct on peut tenter la force brute : on essaie au hasard et on retient les mieux notées. Il faut que ce soit rapide pour en explorer un maximum. Plus tu attends, plus tu as de chance d'améliorer le score. Peu de chance d'avoir LA meilleure mais plusieurs compromis acceptables.
J'imagine plutôt affecter en priorités les meilleurs scores puis descendre.
Et puis il faudrait un peu plus de données, c'est un peu léger pour se mettre sous la dent...
C'est qui les personnes les moins importantes ?
Le peu que j'ai fait en PJ
eric
Ils ont un total de 10.
Si personne ne veut rencontrer quelqu'un on le mettra au pif avec des gens qui sont dans son même cas
L'optimum étant la somme des scores des rencontres souhaitées exaucées.
Etienne Jerome Marc Pierre 1 8 1
Si etienne a ses trois rencontres exhaussées le bien-être collectif sera de 10.
Le but étant de maximiser le bien être collectif sous contrainte que tout le monde ait trois rencontres ou deux pour quelques uns, si possible ceux qui sont pas importants. Avec des X!
Il y aura au maximum 50 personnes avec au plus trois souhaits et je n'ai pas de problème de laisser tourner une macro pendant des jours sur un ordinateur.
Donc le bruit de force me parait une bonne option!
Lister toutes les possibilités et calculer leur rendu puis afficher celles avec le score maximum.
Le résultat souhaité étant un planning avec chaque personne et ses rencontres respectives.
Merci beaucoup ça m'aide déjà un peu
Je ne veux pas te casser ton WE c'est très gentil déjà de m'aider!
Si l'illumination te vient, ce serait fantastique pour mon speed dating, sinon je le ferais à la main au bruit de force au stylo!
Bien à toi,
E
Bonjour,
tu as oublié ça :
Si Marc note 4,4,3 (j'ai supposé qu'ils avaient un total de 10 à répartir ?) et que 3 autres notent 8 pour une rencontre avec lui il n'aura aucune rencontre désirée. Comment comptes-tu régler ce pb ?
Finalement si il faut en explorer le maximum ça ne joue pas.
eric
Si Marc a 4,4,2 et que les autres ont 8.. il n'aura en effet aucune rencontre préférée.
Par la suite j'essaierai peut être de faire quelques ajustements manuels pour que tout lz monde soit heureux
Bonjour,
J'ai avancé dessus mais pas assez de données pour tester.
J'ai beau brasser dans les sens tes 10 malheureuses rencontres il ne me trouve qu'une seule solution à chaque fois.
Si tu pouvais fournir un jeu de données plus conséquent pour pourvoir tester correctement stp.
eric
Bonsoir Eric,
Merci pour ton aide!
Ci-joint un classeur avec plus de données.
Bien à toi,
E
Bonsoir,
Je me suis un peu penché sur ton problème... Ça me fait 3 projets sous le coude qui se classent un peu dans la même catégorie, mais d'un point de vue pratique rien de réutilisable d'un projet sur l'autre...
Il est vrai que lorsqu'on demande aux participants de valoriser leurs choix préférentiels, par rapport à quelqu'un qui valorise 4 3 3, celui qui valorise 8 1 1 (voire 9 1 ou 10) se met en meilleure position d'obtenir satisfaction, mais c'est le but !
D'un autre côté, quelqu'un de très demandé, si la réciprocité possible lui permet d'escompter satisfaction pour certains de ces choix, il sera loin d'avoir la garantie de les voir tous satisfaits, justement parce que très demandé. Mais cela fait partie des règles.
Il me semble qu'au niveau de l'organisation, l'objectif est d'obtenir l'indice de satisfaction global le plus élevé possible, sachant qu'il est dépendant de la concentration ou dispersion des demandes : une dispersion élevé permettra d'obtenir un indice de statisfaction plus élevé que si les demandes sont concentrées sur un nombre réduit de participants.
Egalement, quand le nombre est impair, un reste sur le carreau à chaque tour...
Bref pour l'instant je n'en suis qu'aux préparatifs : un tableau ordonné selon le poids des demandes émises de tous les duos possibles. Sur le tableau suivant (groupes de traitement...) pas encore très compliqué pourtant la fatigue s'est fait sentir et j'ai eu du mal à ajuster les indices pour obtenir le résultat voulu...
Je ne peux promettre de solution (même mauvaise) pour l'instant car je ne suis pas entré dans le coeur du sujet : simulation et évaluation des configurations possibles.
Bonne soirée à tous.
Salut MFerrand,
Pour info avec le 2nd jeu de données je n'arrive qu'à 30% de rencontres placées.
C'est l'heure de la pause pour moi aussi
Messieurs bonjour,
J'espère que je ne vous empêche pas de dormir!
Pour ce qui est des personnes les moins importantes, enlever 0,01 à leur scores permettrait de les faire passer en deuxième ?
Besoin que je fasse un jeu de données avec 50 participants?
Merci!!
E
Tu bidouilles les règles
Il peut être concevable que des participants disposent d'un poids supérieur à d'autres dans leurs choix (par exemple disposer de 20 points à répartir au lieu de 10), mais on ne peut décider dans le déroulement de la procédure que l'un doit prévaloir sur un autre...
Mon idée était de faire au début un ajustement pour les personnes les moins importantes.
Leur enlever 1% de leur score attribué:
S'il a attribué 1,8,1 son nouveau score serait
0.99,7.92,0.99
Comme ça la procédure privilégiera les autres vu que c'est une maximisation du score cible.
N'est-ce pas une façon de simplifier les privilèges?
E
Bonjour,
Pour ce qui est des personnes les moins importantes, enlever 0,01 à leur scores permettrait de les faire passer en deuxième ?
Arrivé un peu tard, pour l'instant je n'en tiens pas compte.
Pour des raisons de vitesse (il faut en explorer le maximum en un temps donné) tout s'effectue sur des entiers, c'est donc -1 qu'il faudrait faire. Pas sûr que ça chamboule grand chose, tu dis...
Pour l'instant ça tourne bien. Je ne délivre pas encore de fichier vu que la sortie des résultat n'est pas encore faite. Ainsi que le comblement avec des rencontres aléatoires mais ça ça sera en tout dernier, autant ne pas encombrer les tableaux le temps que tu contrôles et annonces les bugs. Le plus dur et le plus long est fait mais là je vais manquer de temps.
eric
Bonjour Eric,
Il suffit de multiplier tout par 100 et enlever 1 alors pour rester en entiers? Cela serait applicable?
Enlever 1 transformerait les 1 en 0 et donc n'augmenterait pas l'optimum.
C'est super que tu t'y attelles, je te remercie pour ton aide, cela va m'apprendre un paquet de trucs je présume!
Je ne veux surtout pas t'encombrer dans ta vie personnelle/professionnelle, tu en as déjà beaucoup fait
Bien à toi,
E
Re,
Petit pb. Je suis absent qq jours, je pensais en faire un peu ici mais j'ai oublié tous mes chargeurs :-s
Je vais donc y aller à l'économie...
eric
Bonjour,
Ca m'a donné un peu de fil à retordre mais voici une version fonctionnelle.
Je n'ai pas tenu compte des 'pas importants'. Avec le système choisi (tirage aléatoire amélioré) peu de chance de tomber sur un cas où ça changerait grand chose. Ca ralentirait inutilement.
Je te sors les 5 meilleurs scores, les 5 qui ont les meilleurs % de placement, et celui qui attribue le plus de rencontres 1.
Ca croit assez rapidement au début, ensuite il faut un peu de chance pour améliorer significativement.
Cliquer sur Stopper pour avoir les résultats.
Plus d'explications sur Sheet2
Teste déjà ça, on verra le remplissage des trous plus tard.
eric
Edit : autre version, j'ai changé l'algorithme pour la feuille Max RV : je compte le nombre de rv par personne sans tenir compte de sa position (1 à 3)
Phase 1 : je privilégie 1 RV jusqu'à ce que chacun ait au moins 1 rv demandé.
Phase 2 : quand c'est atteint je maximise le nombre avec 2 RV, puis avec 3 RV, puis meilleur score si toujours égalité.
Au delà de 100000 tirages il n'y a plus guère d'évolution. J'envisage de relancer à partir de la liste re-triée pour tenter d'améliorer encore. Dis si c'est suffisant comme ça ou si ça t'intéresse.
Bonjour,
Dernières modifs.
Vu qu'au bout d'un certains nombre de tirages il n'y avait plus guère d'amélioration j'ai supprimé la perméabilité et je repars d'une liste triée tous les 22000 tirages. Ca donne de meilleurs résultats plus rapidement.
En 2 min qq chose de correct, encore plus d'améliorations dans les 5 min. Après tu peux laisser tourner 2-3h et on ne doit plus être loin des solutions optimum.
eric
Tu ne nous empêches pas de dormir mais toi tu as du mal à te réveiller...
J'y ai passé qq heures pour rien je vois.
eric