Problème d'affectation

salut ,


je suis nouveau sur ce forum et j´ai besoin vraiment de l´aide

je suis a la recherche d´un Algortihme pour resoudre le probleme suivant :

Une liste de 40 Etudiants
Une liste de 10 Projets

au fait chaque etudiant choisi 3 projets

et sur chaque projet il y a seulement 4 place pour etudiant


donc la question c de trouver un algorithme qui me permet d´attribuer a

chaque etudiant un des projets choisi et quitablement


Merci

ben il manque des règles de gestion
le choix des étudiants est il par ordre de préférence ou est ce trois projets sans ordre ?

salut

oui le choix des etudiants est par ordre de preference

exemple

Etudiant 1 1(premier choix), 5(deuxieme choix), 3(troisieme choix)

Salut et bienvenue sur le forum de developpez.com.

Tu as un peu cherché ?
As-tu un début d'algorithme ?

oui

j´avais essayer de parecourir la liste des Etudiants et voir si le projet choisi par un etudiant est libre si oui j´attribue c projet a l´etudiant sinon le deuxieme choix ainsi de suite

mais lá les premiers sur la liste seront favoriser donc c pas equitable

Il te suffira de choisir aléatoirement un élève qui n'a jusqu'à maintenant jamais été choisi.

Pour cela, tu peux jetter un oeil ici : http://www.developpez.net/forums/sho...d.php?t=191130
(notamment la remarque de PRomu@ld (deuxième post))

Qui correspond en gros à :

Code:

---

1 2 3 4 5 6 7 8 9 10

Procédure permutationAleatoire(Tableau t de taille 1 à n) Pour i = 1 à n t[i] <- i   Pour i = n à 1 faire j <- tirer aléatoirement entre 1 et i permute <- t[i] t[i] <- t[j] t[j] <- permute

---

Ainsi, tu disposes d'un tableau d'élève à choisir l'un après l'autre.

salut

je crois que cette methode ne serras pas optimal

si j´ai bien compris c de tirer sur la liste des eleves un au hasard

j´avais aussi utiliser cette methode mais la solution obtenue n´etais pas suffisant

c.a.d choisir un etudiant au hasard naturelement sans doublons et voir si son premier choix est encore libre si oui on l´attribue le projet sinon le 2 ieme ainsi de suite

je constituerais deux ensembles
demandes(étudiant,choix1,choix2,choix)
accords(étudiant,projet)

je constitue une boucle
classement des projets restant par nombre croissant de demande totales restantes
attribution des projets ayant une demande total à satisfaire<= 4
(par attribution j'entends ajout à la liste des accords, suppression de toutes les demandes de cet étudiant et si le projet a quatre accords, suppression du projet de la liste des demandes et retour à la boucle)
attribution des projets ou le nombre de choix 1 est égal on inférieur à
reste=4 -nb attribues pour ce projet
attribution des projets ou le nombre de choix 2 est égal on inférieur à reste
attribution des projets ou le nombre de choix 3 est égal on inférieur à reste

' a cette étape on a atteint un équilibre maximal demande/offre
tirage au sort des reste premiers choix 1 pour les projets restants
tirage au sort des reste premiers choix 2 pour les projets restants
tirage au sort des reste premiers choix 3 pour les projets restants
' à cette étape on a satisfait toutes les offres possibles sans mécontenter personne
fin boucle

à ce stade j'ai satisfait un maximum de demandes et d'étudiants et j'organise un tirage au sort des reliquats

je procède ainsi paceque que je suppose que certains sujets seront privilégiés

Bonjour,

Une méthode consiste à effectuer un tri des paires "éléves/projets" en fonction :
- critère 1 (croissant) : priorité du choix (1, 2 ou 3),
- critère 2 (croissant) : 0 si critère 3 = 1 ou critére 4=1, 1 sinon
- critère 3 (croissant) : nombre d'élève encore candidats pour le projet,
- critère 4 (croissant) : nombre de projets encore disponibles pour le candidat.

Retenir la paire la mieux classée, retirer les projets "pleins" et les élèves "traités", refaire le tri.

Itérer les opérations jusqu'à ce qu'il n'y ait plus d'étudiant ou de projet.

Question : que faut-il faire si tous les étudiants demandent les 3 mêmes projets ?

Bonjour à tous,

Il me semble que ton problème peut se modéliser sous la forme d'un problème d'affectation. Ce type de problème à été résolu en 1955 par Harold Kuhn (http://en.wikipedia.org/wiki/Hungarian_algorithm), il est donc dommage de réinventer la poudre :D .
Dans ton exemple, tu cherche à affecter les éléves aux places des projets. Connaissant la préférence des éléves vis à vis des projets, tu peux en déduire le coût d'affectation d'un éléve à une place d'un projet:
si la place correspond à son choix 1, le coût d'affectation est de 0
si la place correspond à son choix 2, le coût d'affectation est de 1
si la place correspond à son choix 3, le coût d'affectation est de 2
si la place correspond ne correspond à aucun de ses choix, le coût d'affectation est de 3.
En applicant l'algorithme Hongrois (résolvant le problème d'affectation en O(n^3)), tu obtiendras la matrice d'affectation des éléves vers les projets. Cette affectation est optimal au sens des de la matrice des couts (elle te donne l'affectation de coût minimum).

Bon courrage, si tu as besoins, j'ai codé l'algorithme en C.

Bonjour à tous,

Il me semble que ton problème peut se modéliser sous la forme d'un problème d'affectation. Ce type de problème à été résolu en 1955 par Harold Kuhn (http://en.wikipedia.org/wiki/Hungarian_algorithm), il est donc dommage de réinventer la poudre :D .
Dans ton exemple, tu cherche à affecter les éléves aux places des projets. Connaissant la préférence des éléves vis à vis des projets, tu peux en déduire le coût d'affectation d'un éléve à une place d'un projet:
si la place correspond à son choix 1, le coût d'affectation est de 0
si la place correspond à son choix 2, le coût d'affectation est de 1
si la place correspond à son choix 3, le coût d'affectation est de 2
si la place correspond ne correspond à aucun de ses choix, le coût d'affectation est de 3.
En applicant l'algorithme Hongrois (résolvant le problème d'affectation en O(n^3)), tu obtiendras la matrice d'affectation des éléves vers les projets. Cette affectation est optimal au sens des de la matrice des couts (elle te donne l'affectation de coût minimum).

Bon courrage, si tu as besoins, j'ai codé l'algorithme en C.

saut


merci a tout le monde pour vos tres bonne idées

Polo ca me ferait plaisir si me passais ton Code en C

moi je ne connais pour le moment que Java mais sa fait rien

tu p me le filer


Merci a tous et je suis toujours ouvert pour vos idée


Forum Super

C'est effectivement le problème d'affectation de coût minimal
Il serait bon de changer le titre de la discussion en "Problème d'affectation". Je n'avais personnellement jamais lu cette discussion à cause de son titre trop général.

Pour rentrer dans le cadre strict de l'algorithme hongrois, il faudra dupliquer tes projets en 4 instances différentes pour avoir une affectation 40 étudiants x 40 projets.

Si tu es curieux, tu peux aussi regarder du côté des problèmes de distribution (transportation problem, Hitchcock problem) et les problèmes de flots en général qui généralisent l'affectation 1x1.
http://en.wikipedia.org/wiki/Transportation_problem

Le probleme chez moi en fait il y a 40 Etudiants et seulement 10 Projets

et sur chaque projet la place pour 4 Etudiants donc je me demande si L`Algortihme Hongrois peut marcher


Merci

C'est ce que Francis disait: chacun de tes 10 projets correspond a 4 projets pour l'algo Hongroi.

salut


donc vous penser que ca p marcher avec cet algorithme hongrois?



Merci

Oui. A part que je donnerais un poids beaucoup plus eleve aux affectations qui ne correspondent pas a quelque chose de demande.

Oui pas de doute, l'algorithme hongrois est bien fait pour résoudre ton problème. Il y a aussi d'autres algorithmes.
Un lien parmi d'autres:
http://www.magiclogic.com/assignment.html

Si tu es plus intéressé par la solution que par la programmation, tu peux utiliser mathprog/glpk qui t'offre la possibilité de modéliser ton problème comme un programme linéaire.

Je crois qu'Excel peut aussi résoudre ce problème mais je n'ai pas trouvé sur le web de spreadsheet gratuite prête à l'emploi.

Tu peux aussi utiliser le package lpsolve (et lp.assign) du projet R.

Merci


Je voudrais juste savoir si kelk1 d´entre a un Code sur l´Algorithme Hongrois ou m´expliquer comment je pourrais resoudre mon probleme avec cet Algortithme je suis encore debutant en programmation et j´utilise le Language JAVA


Merci a l´avance

Bonne journée