XL 2016 Répartition élèves ateliers

[andco]

Bonjour à tous
Tout d'abord, merci et bravo pour la mine d'informations, d'astuces, de fichiers.
J'ai fait une recherche sur le forum et ce dont j'ai besoin a déjà été plus ou moins abordé mais comme je n'ai aucune connaissance des macros je n'arrive pas à adapter les contributions à ma propre situation.
Voici ma problématique. Je suis directeur de Segpa et nous organisons chaque année une mise en réseau pour les élèves de 4e avec quatre autres établissements. C'est à dire que nos élèves ont la possibilité d'aller découvrir les ateliers des autres établissements sachant que :
- chaque établissement a 16 élèves maximum sauf un qui en a 32
- chaque élève fait trois vœux qu'il classe par ordre de préférence
- chaque élève doit participer à deux ou trois ateliers selon les années
- un élève ne peut pas faire deux fois le même atelier
- un élève ne peut pas faire un atelier de son propre établissement
- il ne peut y avoir plus de 4 élèves d'un même établissement dans un atelier
- nous nous engageons à ce que tous les élèves aient au moins leur premier vœu et au moins deux de leurs trois veux
Je vous joins le fichier avec la base des élèves et la liste des ateliers.

Merci d'avancer à tous et toutes pour vos contributions.
Belle journée

 

[crocrocro]

Donc, ma solution n'est pas un jeu avec un algorithme "malin", mais plutôt jouer le jeu x fois en "brute force" avec un minimum de règles mais chaque infraction entraîne des points de pénalité et au bout, le jeu avec le moins de points est choisi.

tout à fait d'accord, mais quand j'écris

Je donnerais bien pour nom à cet algorithme "Le Solveur Magique de Bsalv"

je faisais référence au Solveur d'Excel, qui fonctionne sur le même principe en utilisant la "force brute".
Pour ce genre de problème (Choix possibles pour une colonne de tableau parmi une liste de valeurs avec un ensemble de contraintes), j'ai l'habitude de l'utiliser, sachant qu'ici, il n'y a pas une mais 3 colonnes (vœux 1 2 et 3), ce qui change la donne.
Pour le problème qui nous occupe, j'étais parti sur une mauvaise piste et comme vous aviez donné une bonne solution, je ne me suis pas penché sur une solution avec le solveur.
J'ai essayé quelques adaptations à votre code pour avoir une solution meilleure que la vôtre (58 - 30 - 8) mais je ne trouve pas mieux.
Je pense que, compte tenu du jeu d'essai, il n'existe peut-être pas mieux.
Comme je l'ai déjà dit la contrainte 4 élèves du même établissement pour un atelier ne me parait pas équitable puisqu'un établissement a 32 élèves alors que tous les autres en ont 16 :
Pour E1, E2, E4 et E5, 16 élèves à répartir dans 3 établissements de 2 et 1 établissement de 4 ateliers.
Pour E3, 32 élèves à répartir dans 4 établissements de 2 ateliers, donc avec une répartition égale, 4 élèves par atelier ce qui est déjà la limite autorisé. Donc difficile en plus de respecter les vœux de chacun. Et encore, il faudra respecter la limite de 8 élèves par atelier.
Il me paraitrait plus équitable d'avoir une limite = Nombre d'élèves de l'établissement / 4, soit 4 élèves pour E1, 2, 4 et 5 et 8 pour E3.
Une petite remarque sur votre code : il me semble que dans le tableau Tabel4, la pondération par le Poids (compteurs * Poids) est inutile ici puisque le test sur la cellule "penalites" pour accepter ou non une affectation (jour1 2 3) aléatoire dans le tableau est Range("penalites").Value2 > 0.
Mais peut-être que quelque chose m'a échappé 😕.
Je n'ai pas (encore) regardé votre nouveau fichier.
Encore bravo pour cette "force brute" mais dans un gant de velours 😉

 

[bsalv]

96*3 = 288 variables type "integer", cela me semble trop pour solveur.
Dois-je faire un effort pour par exemple 30 élèves au lieu de 96 ?

 

[crocrocro]

96*3 = 288 variables type "integer", cela me semble trop pour solveur.
Dois-je faire un effort pour par exemple 30 élèves au lieu de 96 ?

On peut essayer de contourner les limites du solveur. Parfois on y arrive parfois pas.
Avec pour Objectif, comme vous l'avez fait dans la macro bBest.
Pour plage variable, le solveur n'acceptant pas les plages discontinues, une colonne correspondant à la concaténation Jour1 - Jour2 - Jour3 converti en numérique (du style votre codage binaire pour les vœux exaucés mais là en base supérieure avec une contrainte associée correspondant à toutes les combinaisons d'ateliers également converties en numérique et injectées dans une plage. Tout çà c'est un ébauche de réflexion toute théorique.
Pour ce qui concerne votre question

Dois-je faire un effort pour par exemple 30 élèves au lieu de 96 ?

je suppose qu'elle s'adresse à @andco.
Cela fait bien 96 élèves = (4 x 16) + (1 x 32)
EDIT :
Une stratégie serait de décomposer chaque boucle en 2 étapes :
Etape 1 : faire un traitement aléatoire pour affecter uniquement les élèves de E3 (facteur limitant)
Etape 2 : faire un traitement aléatoire pour affecter uniquement les élèves des autres établissements.
Mais c'est peut-être ce genre d'effort que vous évoquer.

 

[bsalv]

en rouge,les 8 premiers élèves à résoudre avec solveur.
On est partie avec une solution existante et puis j'ai effacé le résultat de 8 premiers.
Apparament, après 5 minutes, solveur n'a pas encore trouvé un début de solution ....

 

[crocrocro]

Bonjour,
@bsalv, je n'ai pas regardé vos derniers fichiers 🙁
J'ai essayé de retoucher votre fichier (du post 24 je crois) pour appliquer ce que je disais précédemment

Une stratégie serait de décomposer chaque boucle en 2 étapes :
Etape 1 : faire un traitement aléatoire pour affecter uniquement les élèves de E3 (facteur limitant)
Etape 2 : faire un traitement aléatoire pour affecter uniquement les élèves des autres établissements.

en pj le fichier mais je ne fais pas mieux que votre 58 - 30 - 8 si le but est de maximiser les 111 prioritairement.
J'ai fait un 57 - 32 - 7 (avec 89 pour 111 + 110, 88 pour vous).
Pas mieux avec une dizaine de tests (de 1000 boucles).
Mais il n'y a peut-être pas mieux avec le jeu d'essai actuel (bricolé aléatoire)
Quelques explications :
Dans la feuille, j'ai ajouté des paramètres sur lesquels on peut jouer :

- Limite et type Lim (voir commentaires de cellule)
- Points si KO (voir commentaires de cellule)
J'ai modifié la formule de calcul des points (colonne Points de Tabel2) qui s'appuie sur les paramètres i2:i4 (i3 et i4 sont calculés).
En jouant sur tous les paramètres, selon que l'on décide de privilégier les 111 ou les 111 + 110, on aboutit à des best différents.
J'ai enrichi la barre d'état pour savoir où on en est en cours de traitement
La 1ère étape dans chaque boucle fait les affectations pour les élèves de E3.
On teste le résultat intermédiaire en fonction des paramètres (Limite, Type Lim)
Si ko, on passe directement à la boucle suivante (ces boucles avortées durent chez moi 0.3 secondes). Ce qui permet de gagner du temps et donc d'y aller fort sur le nombres de boucles mais si on est trop restrictif, on peut passer à côté de solutions au final meilleures.
Si ok, on poursuit la boucle, étape 2 avec les affectations des élèves des autres établissements en tenant compte pour le Best des paramètres Points KO en i2:i4. Chaque boucle complète dure cher moi 1.2 secondes.

J'ai masqué les colonnes A,B,C, mis en commentaires l'autofit des solutions .... pour avoir tous les tableaux sur la même page (plus pratique pour la mise au point). A remettre donc en place.
Dans le tableau Tabel4, comme je l'ai déjà dit, le poids me parait inutile (non confirmé), j'ai remplacé la formule =PUISSANCE(10;[@count]-5) par 1 sur les count > 1.
Les commentaires dans le code sont les miens pour me repérer dans le code de @bsalv qui a mis les siens dans une version que je n'ai pas utilisée.

Ajout d'une feuilles avec quelques stats.

Pour ma part, je pense avoir fait le tour de la question.
@andco a à sa disposition nos fichiers.
"Mon" fichier est le fichier de @bsalv 😍 sur lequel je n'ai fait que quelques adaptations
Il pourra avec des vœux réels et en jouant sur les paramètres, en s'aidant de trèfles à 4 feuilles, fers à cheval ... essayer de trouver la meilleure solution.

 

[andco]

@crocro / @bsalv
très impressionné
J'avoue que vous m'avez un peu beaucoup perdu dans vos explications.
Je regarde tout ça à tête reposée.
Un grand merci encore une fois pour vos retours.

 

[crocrocro]

J'avoue que vous m'avez un peu beaucoup perdu dans vos explications.

Dans cette discussion, nous avons surtout échangé @bsalv et moi par rapport à nos propositions.
En essayant de trouver une solution qui permette d'obtenir le meilleur résultat.
Mais probablement, la solution proposée dans les premiers posts par @bsalv vous convient.
Elle permet, avec le jeu d'essai bidon de respecter toutes vos règles avec :
- 58 élèves sur 96 dont tous les vœux sont satisfaits
- 30 élèves sur 96 dont les vœux n° 1 et n° 2 sont satisfaits
- et les 8 autres, dont les vœux n° 1 et n° 3 sont satisfaits.
C'est un beau résultat obtenu par @bsalv
A vous donc de tester en réel et de nous faire part de vos remarques, questions ... 🙂

 

[bsalv]

@crocrocro, j'essaie à comprendre l'avantage de votre proposition, mais je ne le vois pas.
C'est certain que les ateliers "E3" sont plus facile accèssible que les autres ateliers avec (96-32) = 64 élèves pour 4 ateliers = 16 par atelier. Pour les autres ateliers, il y a (96-16 ) = 80 pour 2 classes = 40 élèves par classe. Donc, en moyenne, il y a moins de concurrence dans les ateliers E3 que pour les autres ateliers, mais mes leçons de statistique, cela fait 45 ans que je les ai eu.... Il faut calculer la probabilité pondorée, mais je ne sais plus le faire ... .
Dans cette version, on assigne en 3 boucles les voeux 1 à 3 mais dans chaque boucle, comme vous le voulez, on commence avec les voeux des élèves E3 et puis le reste. Après 250 essais, mon meilleur résultat était "53-36-7", un petit peu pire que "58-30-8".
A refaire avec 1.000 boucles ?

 

[crocrocro]

@bsalv, c'est le contraire que je fais, c'est à dire que je commence à caser les élèves E3 dans les ateliers des autres établissements qui comme je l'ai dit dans un post précédent,

Pour E3, 32 élèves à répartir dans 4 établissements de 2 ateliers, donc avec une répartition égale, 4 élèves par atelier ce qui est déjà la limite autorisé. Donc difficile en plus de respecter les vœux de chacun. Et encore, il faudra respecter la limite de 8 élèves par atelier.

En commençant par les élèves E3, on est sûr de ne pas dépasser la limite de "8 élèves par atelier" après les avoir casés. On en aura 4. Ensuite on peut s'attaquer aux autres élèves qui sont plus facilement casables par rapport à la règle "4 élèves d'un même établissement par atelier".
Pour remplir un camion de déménagement, commencer par les meubles les plus encombrants.
Mais de toute façon, ma stratégie, ici n'est pas payante.

 

[bsalv]

je l'ai fait comme vous l'avez proposé, je commençais chaque fois à assigner les élèves "E3" dans un atelier qui n'est pas E3.

De toute façon, un résultat de "53-36-7" ou "58-30-8", la différence à premier vue, n'est pas si grand.
Et si on atteint un résultat "60-30-6" ou "58-35-3" après une heure de calculation, "et alors ..."

 

[crocrocro]

je l'ai fait comme vous l'avez proposé, je commençais chaque fois à assigner les élèves "E3" dans un atelier qui n'est pas E3.

De toute façon, un résultat de "53-36-7" ou "58-30-8", la différence à premier vue, n'est pas si grand.
Et si on atteint un résultat "60-30-6" ou "58-35-3" après une heure de calculation, "et alors ..."

Oui, c'est pourquoi j'avais conclu dans mon post #37 adressé à @andco

Mais probablement, la solution proposée dans les premiers posts par @bsalv vous convient.
Elle permet, avec le jeu d'essai bidon de respecter toutes vos règles avec :
- 58 élèves sur 96 dont tous les vœux sont satisfaits
- 30 élèves sur 96 dont les vœux n° 1 et n° 2 sont satisfaits
- et les 8 autres, dont les vœux n° 1 et n° 3 sont satisfaits.
C'est un beau résultat obtenu par @bsalv