Un algorithme de répartition

[Auwx0]

Bonjour a tous, Je suis actuellement en maths spé et je travaille sur mon tipe, et j'ai trouvé ce forum en faisant des recherches sur mon sujet. Je vous serais très reconnaissant de m'aider, ne serait-ce qu'en me redirigeant vers des livres/magazines/sites adéquats parce que franchement j'avance en tâtonnant car je ne trouve pas de documentation qui s'intéresse à mon sujet.

Alors je vous expose la chose :

Je me donne un certain budget, un certain nombre de cursus possibles chacun ayant un nombre de places illimitées et un coût prédéterminé, et des élèves qui vont chacun effectuer 3 choix parmi ces cursus : leur préféré, leur deuxième préféré et leur troisième.

Mon but est, tout en restant dans les limites de mon budget, d'assigner les élèves de manière à optimiser le contentement moyen : par exemple en disant qu'être assigné à son premier choix apporte 100% de contentement, à son deuxième 70 et à son troisième 40, je fais la moyenne du contentement des élèves.
Une autre idée étant juste d'optimiser le rapport (contentement moyen)/(coût) et d'enlever l'idée de budget.


Je pense d'abord assigner les élèves ayant comme premier choix le cursus le moins cher, mais pour ceux d'après je ne trouve pas de manière systématique pour répartir les élèves : dans chaque simulation que je me donne je dois réfléchir et avancer du mieux possible sans trop savoir où je vais.


Bref merci de m'avoir lu, et merci de m'aider si possible

[pseudocode]

Envoyé par Auwx0

Je me donne un certain budget, un certain nombre de cursus possibles chacun ayant un nombre de places illimitées et un coût prédéterminé, et des élèves qui vont chacun effectuer 3 choix parmi ces cursus : leur préféré, leur deuxième préféré et leur troisième.

Mon but est, tout en restant dans les limites de mon budget, d'assigner les élèves de manière à optimiser le contentement moyen

On dirait un problème de sac à dos, non ?

[Auwx0]

Pas exactement : je dois attribuer tous les élèves, pas seulement assez pour remplir mon budget.
Et en plus les élèves n'ont pas une valeur de contentement ni de coût fixe puisqu'elle dépend du cursus attribué.

A la limite en considérant les cursus a la place des élèves on fixe le coût mais le problème du contentement n'est pas résolu.

[Franck Dernoncourt]

Voici en PJ une méthode simple pour obtenir la satisfaction globale maximale.

Présentation du problème type :

• n personnes se voient proposé n postes.
• Chacune classe ces postes en fonction de ses préférences, en notant avec une note de 0 à 20.
• Comment affecter une personne à un poste de façon à obtenir la satisfaction globale maximale.

Bon ensuite il faudra trouver un moyen pour y insérer la question du budget, mais ça peut toujours donner des idées.

[Auwx0]

effectivement ça se rapproche beaucoup de ce que je cherche, merci

En revanche il manque effectivement le problème du coût et le problème de la non bijection entre l'ensemble des élèves et celui des cursus. Mais je vais déjà bosser dessus et voir ce que je peux modifier.