Discussion :

[bonjour69]

Bonjour,

Je me dois de realiser pour une equipe sportive un fichier constituant une équipe susceptible d'etre la plus performante.
Je décris le probléme : chaque athléte a des compétences lié a plusieurs epreuves. Chaque epreuves rapporte un certain nombre de Points et donc chaque athléte rapporte un certain nombre de points. Le défi est d'organisé l'equipe la plus performante en nombres de points.
Chaque epreuve doit etre effectué par deux athlétes. il y a vingts epreuves. Un athléte peux faire au plus deux epreuves.
le nombre d'athlétes ne pose pas un probléme ( plus d'athlétes que de places )

Y a t'il une méthode miracle pour regler le probléme ?
j'avais pensé a generer tout d'abord une solution possible du probléme puis ensuite effectuer toutes les modifications possibles, et ensuite garder la trace de la meilleure performance. Mais ceci sera surement extremement trop long.. ?


ceci n'est que le probléme de base il y a d'autres contraintes a rajouter par la suite ( les horaires ( un athlete ne pouvant realiser deux epreuves en même temps ) , si le nombres d'athletes est inferieur aux nombres d'epreuves , mixer avec une equipe de filles etc.. )


Merci

[Graffito]

Bonjour,

Envisager toutes les solutions possible est effectivement difficile en un temps raisonnable. 20 epreuves un choix parmi n athletes, donc n*(n-1)*...*(n-19) combinaisons possibles (si n=30, plus de 100 Milliards de combinaisons).

Une idée d'algorithme
Sur la base d'un concept développé pour la planification de fréquences de diffusion radio
1) associer à chaque épreuve un coefficient de difficulté suivant qu'il y ou non beaucoup d'athlètes disponibles capable d'y gagner le maximum de points.

2) traiter les épreuves en prenant la plus "difficile" d'abord,

3) choisir pour cette épreuve le meilleur athlete disponible,

4) recalculer les coeff de difficulté avant de boucler sur l'étape 2).

Le point délicat est la spécification du coefficient de difficulté qui doit prendre en compte l'écart de compétence entre le meilleur candidat et l'ensemble de ses suivants. On peut prendre par exemple qqchose du genre
Coeff:=(score1-score2)+1/2(score1-score3)+1/3(score2-score3)+1/4(score1-score4)+1/5(score2-score4)

[bonjour69]

Bonjour,

Tout d'abord merci pour ta réponse,
en effet l'idée d'un coefficient ne me saurais pas trop parvenu pour l'etablissement d'une premiere liste pour suffir d'ebauche.

je vais essayer cela,je vous tient au jus.

Toutefois si vous avez d'autres idées ou des questions n'hésitez pas

merci
a+

[FrancisSourd]

La recherche opérationnelle s'intéresse à ce genre de questions. En fait, il s'agit d'un problème d'affectation (ici on affecte les athlètes aux épreuves). Comme un athlètes peut être affecté à plusieurs épreuves, on appelle plutôt cela un problème de transport qui peut être modélisé et résolu comme un problème de flot dans un graphe.

Cela peut également être modélisé et résolu efficacement par un programme linéaire. Cette modélisation a l'avantage d'être plus flexible, c'est-à-dire qu'elle pourra te permettre de modéliser relativement facilement les contraintes additionnelles que tu évoques à la fin de ta question. Il existe des solveurs (même libre: GLPK, lpsolve) pour résoudre de tels modèles.

Si tu ne connais pas ces méthodes, j'espère qu'elle te serviront de mots-clés dans tes recherches. Elles sont en général enseigner à partir des niveaux bac+3. N'hésite pas si tu as des questions.

[bonjour69]

Bonjour,

Tout d'abord merci pour cette deuxieme réponse.

J'ai donc effectué des recherches dans ce domaine de la programmation que je ne connaissais pas.

je suis tombé sur l'algorithme du simplexe, je me demandais s'il étais approprié :

j'ai ma fonction qui me permet de calculer la performance maximale :
en additionnant le nombres de points par epreuves * 20.

mes contraintes :
-Un athléte X ne peux faire que deux épreuves.

je ne trouve pas de contrainte en plus.

je ne sais pas si mon problémes est modélisable
Merci

[FrancisSourd]

Oui, le simplexe est fait pour résoudre de tels problèmes.

Pour modéliser:
On suppose qu'il y a n athlètes et m épreuves.

il faut introduire des variables x[i,j] telles que doit être égal à 0 ou à 1. x[i,j] vaut 1 si l'athlète i participe à l'épreuve j. Cela fait mn variables.

Il vaut maximiser la somme des c[i,j] x[i,j] (pour tous les i et tous les j). c[i,j] représentant le nombre de points que rapporterait l'athlète i à l'épreuve j.

Les contraintes qu'un athlète participe à au plus deux épreuves s'écrivent:
Pour chaque athlète i, x[i,1]+x[i,2]+...x[i,m] <= 2

Tu avais aussi dit qu'il y a au plus 2 athlètes pour chaque épreuve:
Pour chaque épreuve j, x[1,j]+x[2,j]+...x[n,j] <= 2

Normalement, il faut dire que x[i,j] est soit 0 soit 1. Pour ce type de problème, on sait qu'il suffit de dire que 0 <= x[i,j] <=1 pour obtenir une solution où les x[i,j] sont tous entiers (cette propriété est très utile car un Programme linéaire) sans contraintes d'intégrité est directement résolu par le simplexe.

[bonjour69]

Bonjour,


Merci pour cette réponse, en effet j'ai deja tout implementé , chargement des fichiers , definition des contraintes , etc..

Par contre pour le gros de la partie Algo , c'est la fonction Maximize qui me pose probléme, j'ai lu des documents attestant d'une technique de pivotage. Mais j'ai un peu de mal sur la chose.

Voila merci si vous avez des bonnes pistes.

A bientôt

[FrancisSourd]

Tout dépend s'il s'agit de programmer le simplexe ou d'utiliser une librairie implémentant déjà l'algorithme. Je conseillerai plutôt cette seconde solution (lpsolve ou glpk). C'est surtout utile en vue d'extension futures qui impliquerait des contraintes additionnelles et en particulier des contraintes d'intégrité sur les variables (dans ce cas le simplexe seul ne suffirait plus).

[bonjour69]

bonjour,

je vais donc m'essayer de m'attaquer a la librairie GLPK dont j'ai trouvé un exemple assez illustratif pour ce que sa interesse :

http://www-lih.univ-lehavre.fr/~bale...OR/TPglpk.html


Merci,

A bientot