Quelle est la meilleure combinaison ?

Olympiades mathématiques, énigmes et défis
ZAZALAFLECHE
Messages: 2
Enregistré le: 27 Fév 2013, 11:10

Quelle est la meilleure combinaison ?

par ZAZALAFLECHE » 27 Fév 2013, 11:15

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 ?



Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6554
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 27 Fév 2013, 11:46

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
la vie est une fête :)

hammana
Membre Relatif
Messages: 477
Enregistré le: 24 Avr 2012, 22:26

par hammana » 27 Fév 2013, 18:04

fatal_error a écrit: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
Messages: 2
Enregistré le: 27 Fév 2013, 11:10

par ZAZALAFLECHE » 27 Fév 2013, 18:30

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
Membre Relatif
Messages: 477
Enregistré le: 24 Avr 2012, 22:26

par hammana » 27 Fév 2013, 19:51

ZAZALAFLECHE a écrit: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

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6554
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 27 Fév 2013, 21:26

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.
la vie est une fête :)

joel76
Membre Relatif
Messages: 230
Enregistré le: 11 Fév 2013, 17:31

par joel76 » 28 Fév 2013, 18:45

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]

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6554
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 28 Fév 2013, 22:08

( Je précise 10 min pour coder (la solution est donnée immédiatement) )
la vie est une fête :)

joel76
Membre Relatif
Messages: 230
Enregistré le: 11 Fév 2013, 17:31

par joel76 » 01 Mar 2013, 00:45

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

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6554
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 01 Mar 2013, 02:57

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)
la vie est une fête :)

joel76
Membre Relatif
Messages: 230
Enregistré le: 11 Fév 2013, 17:31

par joel76 » 01 Mar 2013, 10:40

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

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6554
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 01 Mar 2013, 10:45

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
la vie est une fête :)

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite