XL pour MAC Répartition et optimisation selon de choix

[monkey.be]

Bonjour tout le monde,

J'avais déjà fait un post sur ce forum qui m'avait bien aidé, à propos de la même problématique. J'aimerais à présent améliorer mon outil

Je résume la situation: Je suis enseignant et dans mon école, tous les jeudis, nous proposons des ateliers (sportifs, créatifs, informatiques, etc.).

Concrètement, toutes les 3 semaines, les élèves reçoivent un listing d'ateliers auxquels s'inscrire. Il y a à peu près une trentaine d'ateliers disponibles, chacun avec une limite d'inscription. Chaque élève rempli une enquête dans laquelle ils sélectionne, par ordre de préférence, ses 4 ateliers auxquels il voudrait bien participer. (choix 1 > choix 2 > choix 3 > choix 4). Concrètement, c'est là que démarre mon travail. Je reçois le résultat de l'enquête avec pour chaque élève, ses 4 choix (sous forme de numéro, de 1 à 30 s'il y a 30 ateliers):

Élève 1 - Choix 1 - Choix 2 - Choix 3 - Choix 4
Élève 2 - Choix 1 - Choix 2 - Choix 3 - Choix 4
Élève 3 - Choix 1 - Choix 2 - Choix 3 - Choix 4
...

Le fichier excel que j'utilise (et qui m'a été proposé sur ce forum) me permet de remplir les ateliers (en fonction de leur capacité) grâce aux choix des élèves. Pour info, je mélange la liste des élèves pour que le premier de la liste (qui aura d'office son premier choix) ne soit pas toujours le même.

Les ateliers se remplissent petit à petit et lorsqu'un atelier est complet, on passe au choix suivant de l'élève. Le souci rencontré est qu'on a des ateliers qui remportent beaucoup plus de succès que d'autres. Par exemple, un atelier Football aura plus d'intéressés qu'un atelier Tricot... Forcément, je me retrouve avec une série d'élève qui n'ont pas pu être placés parce que les 4 ateliers de leurs choix ont été remplis par des élèves qui les précèdent dans la liste.

Mon outil n'optimise donc pas le placement de mes élèves. Dans un monde idéal, il me faudrait un outil qui optimise le placement pour que 100% des élèves ayant rempli l'enquête trouvent chaussure à leur pied (indépendemment de la hiérarchie de leurs choix donc...).

Dans le fichier ci-joint, vous trouverez dans le premier onglet, l'outil de placement en fonction de la capacité maximale des 30 ateliers proposés. Dans la colonne I, le numéro de l'atelier dans lequel l'élève est inscrit. Si au lieu d'un numéro, il est indiqué "FAUX", cela signifie que ses 4 choix sont déjà complets.

J'espère que ma problématique est claire et que quelqu'un pourra m'aider. Je sais même pas si c'est possible d'optimiser cela via Excel...

Merci d'avance,
monkeybe

 

[gbinforme]

Forcément, je me retrouve avec une série d'élève qui n'ont pas pu être placés parce que les 4 ateliers de leurs choix ont été remplis par des élèves qui les précèdent dans la liste.

Bonjour,
En fait ton outil est très efficient mais pour éviter d'avoir des non pourvus la seule chose à faire c'est de faire évoluer l'offre. Si tu as 100 élèves qui choisissent les mêmes 4 ateliers qui n'ont que 80 places tu ne trouveras aucun outil pour te proposer les 20 places qui manquent à ton offre. Comment pourrait-on les affecter à un atelier délaissé dont ils ne veulent pas ?
De 25 à 30 : 156 places pour 748 demandes bien que le 28 soit ok !
le 15 avec 161 demandes pour 20 places !
Je pense avoir bien étudié ton cas mais si quelqu'un arrive à trouver ta solution je suis prêt à le complimenter.

 

[crocrocro]

Bonjour le fil,
@monkey.be, je continue à examiner votre demande mais il me semble qu'il y a une erreur dans le texte d'accompagnement de la feuille Votes des élèves :

La colonne A permet d'affecter un numéro aléatoire à chaque étudiant.
La colonne B contient les noms des étudiants
Les colonnes C1, C2 et C3 leurs choix par ordre de préférence
Les valeurs de la colonne A sont recopiées en colonne F (c'est nécessaire car la colonne A est une matrice qui ne peut pas être triée)
Puis les étudiants sont triés selon la colonne F
Le groupe est alors affecté en colonne G de la façon suivante:
Choix 1 si les affectations antérieures sont inférieures à 3
Sinon choix 2 si les affectations sont <3
Sinon choix 3 si les affectations sont <3
Sinon affectation du premier groupe <3

N'est-ce pas plutôt la colonne H et non F ?
Je vous ferai une proposition (un fichier) en utilisant le Solveur :
Ce ne sera donc pas la formule en I qui pilotera l'affectation.
Le tri des étudiants sera également inutile.
- P1 : Chaque étudiant devra avoir une affectation (contrainte rédhibitoire).
- P2 : Pour chaque atelier, le nombre d'étudiants ne pourra être supérieur au maximum (contrainte rédhibitoire)
- P3 : Chaque choix C1, C2, C3, C4 sera pondéré par un coefficient dont vous déciderez la valeur. L'a comparaison entre les choix (pondérés) et l'affectation finale à un groupe permettra de donner un niveau d'adéquation pour étudiant et donc pour la somme à l'ensemble
On va attribuer une valeur à chaque paramètre P1, P2 et P3.
Par exemple :
si au moins un étudiant n'a pas d'affectation P1 = 100 000, sinon 0
si au moins un atelier a un nombre d'étudiants affecté supérieur à sa capacité P2 = 100 000, sinon 0.
on pourrait ajouter une contrainte chaque atelier doit avoir au minimum 10% de sa capacité maximale affecté et si ce n'est pas le cas P2 = 1000
pour chaque étudiant, si son affectation ne correspond à aucun de ses choix, P3= 1000
sinon, P3 = Coeff1 (si Groupe = C1), Coeff2 (si Groupe = C2), Coeff3 (si Groupe = C3),
avec par exemple Coeff1 = 0, Coeff2 = 10, Coeff3 = 20, Coeff4 = 30 (ici c'est linéaire)

La somme de ces 3 paramètres P1 + P2 + somme (P3) sera utilisée par le solveur qui va essayer de trouver la combinaison la meilleure (somme la plus faible) parmi toutes les combinaisons d'affectation possibles.
Le fait d'avoir valorisé P1 et P2 à 100 000 si la condition dont ils sont le reflet n'est pas respectée permet d'interdire la combinaison dont ils sont le résultat.
C'est le jeu des Coeff1, 2 et 3 qui permettront d'ajuster (dynamiquement) les choix sans se retrouver coincé.
Je ne peux pas dire combien de temps mettra le solveur pour trouver une bonne solution, cela dépendra évidemment des choix des étudiants.
Le paramétrage même du solveur permet de s'arrêter au bout d'un moment (solution courante non améliorée depuis 30 secondes, une minute ...)

[EDIT] : je viens de voir que @gbinforme a répondu à une discussion qui date de 2022 !!! Tant pis, je finis mon devoir
[EDIT 2] : Le solveur s'avère être une mauvaise piste.
Le nombre de variables maximum pour le solveur est de 200, le nombre d'étudiants, donc d'affectations dépasse les 400. Donc inutilisable.
De plus le nombre de combinaisons possibles (indépendamment des choix et contraintes) est de 400 puissance 30 (30 ateliers), nous aurions le résultat en ... 2030.
J'ai réfléchi à une solution qui pourrait marcher, mais, vu que la discussion n'est plus d'actualité, je vais la remiser par devers moi

 

[gbinforme]

Bonjour @crocrocro
Effectivement la demande date de 2022 et je ne comprends pas comment elle est venue en tête de la page
Il faut être positifs : cela nous aura agité les neurones à tous les deux !