Somme maximale contrainte dans un tableau

[Jeff504]

Bonjour à tous,

Aujourd'hui je fais face à un problème qui me semblait évident. Pourtant après plusieurs heures de réflexion je bute toujours dessus... :hum:

Pour rendre ce problème un peu plus ludique, je vous propose de vous mettre dans la peau d'un manager sportif. :zen:

Vous avez à votre disposition K sportifs et vous souhaitez participer à une compétition comportant N épreuves (dans la pratique K <= N).
Comme vous avez entrainé vos sportifs, vous connaissez pour chaque épreuve j (1 <= j <= N) le résultat de n'importe lequel de vos sportifs i (1 <= i <= K). Le score d'un sportif donné pour une épreuve donnée est donc toujours connu et c'est une constante.
On dispose en fait d'un tableau constant de taille NxK.

Comment attribuer les épreuves aux sportifs pour maximiser le score final avec connaissance du nombre d'épreuves imposé à chaque sportif?

Exemple :
Soient 10 épreuves (E1, E2,...E10) et 3 sportifs (S1, S2 et S3) on a connaissance de tous les résultats possibles: R(Ej,Si).
Trouver quelles épreuves doit réaliser chaque sportif sachant que S1 doit participer à 2 épreuves, S2 à 3 et S3 à 5 pour que l'équipe obtienne le score maximal.
rq: on a bien 2+3+5=nb total d'épreuves

information complémentaire :
:id: Il me semble que dans le cas où le manager dispose uniquement de 2 sportifs S1 et S2, la solution est facile à trouver.
Il suffit pour chaque épreuve d'obtenir l'écart de résultat des deux joueurs R(Ej,S1)-R(Ej,S2) et de trier ces valeurs. Puis pour le nombre d'épreuves autorisées à S1 on récupère les épreuves pour lesquelles l'écart calculé est le plus important. Le reste des épreuves est ensuite attribué à S2

Bon courage à tous et merci pour votre aide

[godzylla]

il y a trois joueurs, dix épreuves, S1' à deux qualifications, S2' à trois qualification, S3' à 5 qualifications.

exemple:
S1 S2 S3
XXO (6,13,18)
XXO (15,13,16)
XXO (14,13,18)
XOX (10,13,8)
XOX (12,13,5)
XOX (10,13,12)
XOX (10,13,8)
XOX (12,13,5)
XOX (10,13,12)
XOX (10,13,12)

il faut la meilleure note possible pour les 10 épreuves noté sur 20.
donc cela me fait une note sur 200.
une note sur 100 sur 60 et sur 40.
je vais y reflechir.

[fatal_error]

slt,

on peut resoudre par prog lineaire nombre entiers:
on note a_ij qui vaut 0 ou 1, i le ieme joueur, j l'epreuve.
m_ij le score que sait faire le joueur i à l'épreuve j.
le ieme joueur joue k_i etapes.
donc somme des a_ij=k
l'objectif etant:
maximiser somme a_ijm_ij
sous contraintes
somme_j a_ij = k_i
somme_j a_ij<=1 (deux joueurs ne jouent pas la meme epreuve)

[Jeff504]

Merci de vous pencher sur le pb :we:

De mon côté j'ai regardé pas mal de chose sur le problème du sac à dos et la programmation dynamique

Le soucis c'est que je ne maitrise pas assez ces sujets et que je ne sait pas encore si c'est vraiment dans cette direction qu'il faut chercher et si oui comment prendre en compte les contraintes :mur:

bon courage

[fatal_error]

logiciel octave fonction gplk
http://www.gnu.org/software/octave/doc/interpreter/Linear-Programming.html

il gere les contraintes lineaires

[Jeff504]

Merci c'est super intéressant!

Je pense que je peux obtenir la solution numérique à mon pb. Mais j'ai besoin d'une démonstration mathématique. En fait je doit absolument faire comprendre à mon client toutes les étapes du raisonnement qui garantisse l'obtention de la solution.

(le problème a été mis sous forme ludique, mais c'est un pb industriel... d’où la besoin d'une preuve construite et compréhensible)