Quelle est la meilleure combinaison ?

[ZAZALAFLECHE]

Bonjour,

Voici mon problème. Je passe actuellement de nombreux concours pour rentrer dans l'administration.
Si quelqu'un a une idée, je suis preneur :
J'ai 17 équipes en vente :
Équipe 1 : 44M
Équipe 2 : 37.5M
Équipe 3 : 30.8M
Équipe 4 : 29.5M
Équipe 5 : 29.1M
Équipe 6 : 28.5M
Équipe 7 : 23M
Équipe 8 : 20.6M
Équipe 9 : 20.5M
Équipe 10 : 18.9M
Équipe 11 : 15.3M
Équipe 12 : 14.1M
Équipe 13 : 13.4M
Équipe 14 : 11.1M
Équipe 15 : 9.5M
Équipe 16 : 8M
Équipe 17 : 6.5M
Je dois choisir exactement 6 équipes(Pas plus - Pas moins).
L'équipe 1 est la + chère et donc a le plus de chance de terminer 1ère. L'équipe 2 : 2ème. L'équipe 3 : 3 ème .....
Le but est d'atteindre le maximum de point avec un budget de 121M :
1er : 100 Points
2ème : 80 Points
3ème : 60 Points
4ème : 48 Points
5ème : 44 Points
6ème : 40 Points
7ème : 36 Points
8ème : 32 Points
9ème : 28 Points
10ème : 24 Points
11ème : 20 Points
12me : 16 Points
13ème : 12 Points
14ème : 8 Points
15ème : 6 Points
Quelles sont les 6 équipes qu'il faut choisir pour atteindre le maximum de points sans dépasser les 121 M ?

[fatal_error]

en tant bete (idem sans chercher dastuce) on peut reecrire le probleme sous forme doptimisation lineaire en nombre entiers:

z(x) = a_1x_1+a_2x_2...+a_17x_17
avec a_i qui vaut 0 ou 1 pour i=1..17
et x_1=100, x_2=80...

sous contraintes
a_1+...+a_17=6
a_1<=1
...
a_17<=1
a_1*44+a_2*37.5+...a_17*6.5<71

[hammana]

en tant bete (idem sans chercher dastuce) on peut reecrire le probleme sous forme doptimisation lineaire en nombre entiers:

z(x) = a_1x_1+a_2x_2...+a_17x_17
avec a_i qui vaut 0 ou 1 pour i=1..17
et x_1=100, x_2=80...

sous contraintes
a_1+...+a_17=6
a_1<=1
...
a_17<=1
a_1*44+a_2*37.5+...a_17*6.5<71

On peut approcher la solution idéale en calculant le prix du point pour chaque équipe et en cherchant la combinaison de 6 équipes dont le prix approche 121M, en choisissant en priorité celles dont le prix par point est le plus petit. Le plus simple est de tester toutes les combinaisons possibles (il y en a moins de 13000) ce qui demande moins d'une seconde (et 1/2 heurre de programmation). J'ai complété le tableau de points en affectant 5 points pour l'équipe 16 et 4 points pour l'équipe 17.
J'obtiens la meilleure combinaison avec les équipes 1,2,11,15,16,17
pour un total de 215 points et un coût de 120.8M (sauf erreur)

[ZAZALAFLECHE]

J'ai regardé de mon coté.
Si je part sur un budget de maximum 118 M.
je tombe sur les équipes :
1,2,14,15,16,17 (203 points Avec un budget de 116.6 M)
1,3,10,15,16,17 (199 points Avec un budget de 117.7 M)

Je pense ne pas me tromper ?

[hammana]

J'ai regardé de mon coté.
Si je part sur un budget de maximum 118 M.
je tombe sur les équipes :
1,2,14,15,16,17 (203 points Avec un budget de 116.6 M)
1,3,10,15,16,17 (199 points Avec un budget de 117.7 M)

Je pense ne pas me tromper ?

Bonsoir!

Je trouve aussi que la meilleure combinaison est
1,2,14,15,16,17 (203 points Avec un budget de 116.6 M),
quelle méthode as-tu suivi

[fatal_error]

Code: Tout sélectionner

maxBudget=116.6;
c = [100 80 60 48 44 40 36 32 28 24 20 16 12 8 6 5 4];
% z(x) = a_1x_1+a_2x_2...+a_17x_17
A(1,1:length(c))=1;
b(1)=6;
ctype(1)="S";
A(2,1:length(c))=[44 37.5 30.8 29.5 29.1 28.5 23 20.6 20.5 18.9 15.3 14.1 13.4 11.1 9.5 8 6.5];
b(2)=maxBudget;
ctype(2)="U";
s=-1;
lb=c*0;
ub=c*0+1;
vartype(1:length(c))="I";
param.msglev = 0;
param.itlim = 100;
[x, fmin] = glpk (c, A, b, lb, ub, ctype, vartype, s, param);
vSolution=x'
totalBudget = A(2,:)*x
totalPoints = c*x



Code: Tout sélectionner

vSolution =

   1   1   0   0   0   0   0   0   0   0   0   0   0   1   1   1   1

totalBudget =  116.60
totalPoints =  203


10minutes!

et encore chui sur en prolog c'est plus succint.

[joel76]

Effectivement Prolog va plus vite

?- time(meilleure_composition(L, Budget, Score)).
% 65,792,177 inferences, 8,518 CPU in 8,588 seconds (99% CPU, 7724213 Lips)
L = [1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1],
Budget = 120.8,
Score = 215 .

Voici le code en SWI-Prolog

Code: Tout sélectionner

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

meilleure_composition(L, TTS1, Score) :-    
        length(L, 17),    
        L ins 0..1,    
        sum(L, #=, 6),
    Prix = [440,375,308,295,291,285,230,206,205,189,
       153,141,134,111,95,80,65],    
        Valeur = [100,80,60,48,44,40,36,32,28,24,20,16,12,8,6,5,4],

    % Calcul du prix
    foldl(\X1^X2^Y^Z^(Z #= Y + X1*X2), L, Prix, 0, TTS),
    1210 #>= TTS,

     % Calcul du score
   foldl(\X3^X4^Y1^Z1^(Z1 #= Y1 + X3*X4), L, Valeur, 0, Score),

        % calcul des valeurs
    append(L, [Score, TTS], L1),
   labeling([max(Score)],L1),    
        TTS1 is TTS/10.

[EDIT] Code simplifié par rapport au précédent, variable Min inutile ! [/EDIT]

[fatal_error]

( Je précise 10 min pour coder (la solution est donnée immédiatement) )

[joel76]

Ah, OK, mais la solution semble fausse. C'est écrit dans quel langage ?

[fatal_error]

non je pense pas que la solution soit fausse. Plutot qu'on a pas les même critères.
Par ex: mes critères sont :

maxBudget=116.6;

alors que tu trouves un buget de 120.8 (jimagine max a 1210). donc c'est juste qu'on a pas la même "config".

Sinon c'est du matlab (octave)

[joel76]

D'accord, tu ne pouvais pas mettre comme moi un max à 121 ?

[fatal_error]

ben déjà j'ai un peu répondu avant. Donc ca devrait etre toi qui t'alignes sur les params.
Et je me suis aligné sur ceux de hammana, qui justement répondais avant...

Sinon pour 121

Code: Tout sélectionner

vSolution =

   1   1   0   0   0   0   0   0   0   0   1   0   0   0   1   1   1

totalBudget =  120.80
totalPoints =  215