Problème de maximisation avec contraintes
Bonjour,
D'abord merci d'avance pour votre aide.
Je vous présente le problème aussi clairement que possible:
- Je dois choisir 9 coureurs cyclistes (pas un de plus, pas un de moins
) - Les coureurs ont chacun reçu une valeur (colonne D). La valeur total de mon équipe ne peut pas dépasser 175.
- Le but est de maximiser le score total de mon équipe de 9 coureurs. Le score obtenu par les coureurs est donné dans la colonne I.
Merci
Bonjour,
Une solution au hasard ?
18.2 - 18.3 - 18.7 - 18.8 - 19.5 - 19.6 - 19.8 - 19.8 - 22.3
ou encore :
17.9 - 18.2 - 18.3 - 18.7 - 18.8 - 19.5 - 19.6 - 19.8 - 24.2
Les solutions semblant si nombreuses qu'il ne semble pas utile de chercher une formule ou une macro... ( en l'absence d'autre contrainte)
[EDIT]
Finalement comme je suis un peu curieux, j'ai quand même testé un début de macro (limité à 30 000 boucles) et j'ai déjà une soixantaine de résultats différents, mais j'ai zappé près de la moitié des coureurs sinon le temps de calcul aurait été astronomique :
il y a quand même 446 098 010 817 800 combinaisons possible...
Une partie des réponses obtenues :
9.1 9.9 17.8 17.9 21 22.8 24.2 25.1 27.2
9.2 9.3 10 12.4 21.3 22.8 24.6 29.9 35.5
9.2 10.9 12.8 15 21 24.3 25.1 25.2 31.5
9.2 11.4 15 18.2 18.7 22 23.2 26.5 30.8
9.2 11.7 12 18.2 19.6 21.9 23.2 27.7 31.5
9.2 12.3 16.7 17 17.6 21 21.2 27.2 32.8
9.2 12.4 15 17 17.7 21.2 22 27.7 32.8
9.2 12.4 15 17 17 17.8 21.2 29.9 35.5
9.2 13.2 14.8 17.7 19.5 21 22 22.1 35.5
9.5 9.6 15.3 17.8 22.8 23.1 23.2 26.5 27.2
9.5 10 13.2 16.6 17.7 24.2 24.6 27.7 31.5
9.5 10.1 17 17.5 21.3 22.3 23.1 26.5 27.7
9.5 10.6 11.4 12.6 21.9 22 26.5 27.7 32.8
9.5 10.6 17.7 17.8 18.7 18.8 22 27.1 32.8
9.5 10.7 17.7 17.9 18.8 19.5 21 27.1 32.8
9.5 10.8 11.2 17.5 17.9 22 25.4 29.9 30.8
9.5 13.2 16.7 17.8 17.8 19.8 23.1 24.3 32.8
9.5 13.5 15 17.6 22.1 22.8 22.8 25.2 26.5
9.5 15 17.5 17.9 19.6 19.8 22 26.5 27.2
9.6 10.7 17.6 17.7 19.5 22.1 22.8 24.2 30.8
9.6 13.7 14.9 17.8 22 22.8 23.1 24.2 26.9
9.9 12 15.7 17.5 17.8 23.1 24.2 27.1 27.7
10 11.4 17.7 18.7 19.8 21 22.3 26.9 27.2
10 11.8 13.5 13.6 22.3 22.8 23.1 27.1 30.8
10 12 15 15.3 18.7 24.3 24.6 25.2 29.9
10 12.8 13.3 17 18.8 21.2 21.2 29.9 30.8
10.1 11.7 18.2 18.7 18.8 21.9 22 22.8 30.8
10.1 15.7 17 17.9 19.8 22 23.1 24.2 25.2
10.7 11.4 16.3 16.7 17.7 19.5 22 29.9 30.8
10.7 12 12.1 18.8 19.6 19.8 22.3 24.2 35.5
10.8 11.1 12 17.5 17.9 22 25.2 27.7 30.8
10.8 13.6 15 17.5 17.7 22 24.2 26.5 27.7
10.9 11.4 11.4 17 17.9 18.3 19.8 32.8 35.5
10.9 12.4 12.8 16.3 17.7 21 26.9 27.1 29.9
11.1 15 17.8 17.8 19.5 19.6 23.1 24.6 26.5
11.2 12.8 15 21 21.3 22 22.1 24.2 25.4
11.2 12.9 14.8 15.3 17.8 24.2 25.2 26.5 27.1
11.2 12.9 15.2 19.5 21.2 21.9 22.3 24.3 26.5
11.2 14.8 15.3 17.9 18.2 21 24.2 25.2 27.2
11.4 13.2 15.7 16.3 21.3 22 22.8 25.2 27.1
11.5 13.2 15 15.9 21.9 22.1 23.1 25.2 27.1
11.5 13.2 15.7 16.3 21 21.9 23.1 25.2 27.1
11.7 12 12.9 13.6 21.3 21.9 23.1 27.7 30.8
11.7 12 13.1 17 17.5 21.2 22.8 26.9 32.8
11.7 12.3 15.2 17.5 21.2 23.1 23.2 24.3 26.5
12 12.3 13.2 17.7 21.2 21.9 23.1 26.5 27.1
12 15.3 15.9 17 17.5 21.3 23.1 25.2 27.7
12.1 12.9 16.6 17.5 17.9 22.3 25.1 25.2 25.4
12.6 12.8 13.6 17.5 18.2 22.1 22.8 24.6 30.8
12.8 13.2 13.5 13.7 19.8 19.8 24.6 27.7 29.9
12.8 15.7 17 17.5 18.7 21 22.3 22.8 27.2
13.1 14.2 15.3 19.6 19.8 21 22.3 22.8 26.9
13.2 13.5 15 17.6 17.8 18.8 22.1 24.2 32.8
13.2 13.5 17.7 17.9 18.8 21 22.1 24.3 26.5
13.7 14.8 18.2 18.8 19.5 19.8 21.9 23.1 25.2
14.2 15 15.9 16.3 19.8 22 22.1 23.2 26.5
17.9 18.2 18.3 18.7 18.8 19.5 19.6 19.8 24.2
18.2 18.3 18.7 18.8 19.5 19.6 19.8 19.8 22.3
A noter que si on intègre les coureurs qui ont 9 pts et moins le nombre de combinaisons possibles croit considérablement car une combinaison qui accepterait 3.0 permettrait d'intégrer potentiellement 10 coureurs différents...
10 coureurs ont entre 6.6 et 6.8
10 coureurs ont entre 7.3 et 7.5
A+
Bonjour à tous
Bonjour galopin
Pour Galopin :
Je me permets d’intervenir car j’ai passé un bon moment à chercher une solution au problème posé sans y parvenir.
Mais je n’ai pas compris la même chose que toi.
Il me semble qu’il faut trouver l’équipe
• qui combine 9 joueurs
• dont le total des valeurs ne dépassent pas 175
• dont le total des scores est le plus grand possible
Il ne doit pas y en avoir tant que cela.
Mais si, comme tu dis, il faut examiner et comparer 446 098 010 817 800 combinaisons de joueurs, je renonce…
Bye !
Nombre de combinaisons de 9 parmi 179 :
=COMBIN(179;9) = 423 793 110 276 910
Bonjour,
Oui, oui... C'est bien ce que j'ai fait : Je ne me suis occupé que des points... j'ai considéré qu'a chaque total correspondait un coureur.
Chaque ligne fait 175 points. Après pour le nom du coureur tu peux faire un RECHERCHEV par exemple, mébon c'est pas le plus intéressant... En plus dus au fait que certains coureurs ont le même nombre de points il y a quelques doublons mais ça on peux le faire visuellement ou avec des formules. Une fois triés horizontalement et verticalement ça saute aux yeux.
Bon j'ai fait comme ça parce que c'est le total de 175 qui m'intéressait mais comme j'ai fait un dico avec comme item le nbre de points j'aurais pu sortir le dossard du coureur en même temps
Ensuite c'est pas sorcier, tu as ton dico avec tous les dossard comme clefs et les points comme item ensuite tu fais une boucle à 10 000 ou 50 000 (ou plus si affinité...)
YAPUKA tirer les 8 premiers au hasard (ou presque...) ensuite tu fais la différence du total des points avec 175 et tu regardes si tu as un quidam qui fais la différence. Si oui c'est le neuvième coureur si non tu continues ta boucle.
Selon mon expérience si on prend les coureurs qui ont moins de 9 points on a énormément de déchet.. avec les 100 meilleurs on a un rendement par boucle de 1 % environ ce qui est relativement acceptable avec les dico on arrive à traiter 100 000 boucles en 2 minutes environ. (à la louche...)
Après c'est juste un problème de tri et de dédoublonnage. Curieusement je trouve + de doublons que je ne m'y attendais...
Je vais rebosser dessus pour rapprocher les N° de dossard des points et je donnerai le classeur définitif...
A+
Quel courage !
@gallopin il faut trouver la combinaison de 9 coureurs qui aura le plus de points mais qui coute moins de 175 en fait !
J'ai trouvé quelque chose comme 1987 points par essai erreur. Je crois que j'avais pris les 6 ou 7 meilleurs coureurs (Sagan, Froome ect) plus le meilleurs pas cher (un coureurs proche de 3.0) et adam yates.
Je souhaiterai apprendre à le faire en utilisant un outil de excel
Merci d'avance !
Bonjour à tous,
Devant le nombre de possibilités un essai en force brute.
Tirage au hasard le plus rapide possible pour en tester le maximum.
Arrêt si score atteint ou t > 1 min
Chez moi une équipe à 175 point trouvée en 1/2 s en moyenne
eric
La meilleure solution inclura Peter Sagan vu son score 15.9 points par million investis! Les coureurs sont triés dans l'ordre du meilleur au moins bons en terme de points par million investi. Le problème c'est que le budget ne permet pas de prendre les 9 meilleurs alors je me demandais comment trouvé la meilleur combinaison(en terme de points) en respectant le budget.
J'espère que je suis plus clair.
@eric woua c'est super ce que vous avez fait !
Mais je me suis mal expliqué. Trouvé un équipe qui utilise tout le budget n'est pas l'objectif. En fait on n'est pas obligé de l'utiliser entièrement. On ne peut juste pas le dépasser. Le but est d'avoir l’équipe qui fera le plus de points. Les points de chaque coureurs sont dans la colonne i.
Voici la meilleure solution par essai erreur que j'ai trouvé:
Sagan38,0
Froome 35.5
Clement 7.0
deGendt 17.6
Majka 21.2
Greipel 27.2
Mclay 5.4
Yates 19.8
Tosatto 3.0
Total 174.7 budget respecté.
Score obtenu : 2088 points
Voilà j'aurai aimé apprendre à le faire avec un outil excel et pas par essai erreur et peut être trouvé une meilleure combinaison
Merci
@GMB la solution est sans aucun doute une combinaison parmi les 30 meilleurs coureurs. Les autres ne rapportent définitivement pas assez de points par million investi pour faire parti de la meilleure équipe.
pfff... Je suis toujours effaré quand je tripote un peu les dico :
En fait j'arrive à tester 100 000 boucles, tri horizontaux, tris verticaux, dédoublonnage et toutes vérifications comprises en moins d'une minute...
Bon je donne là mon classeur de travail j'ai un peu testé les "petits points" : c'est pas plus compliqué, mais ça demande plus de temps car il y a beaucoup plus de déchets au lieu d'un rendement de 1% on passe allègrement à 1/1000 et plus...
Si on veut traiter aussi les "petits points", il faut faire du "hasard dirigé" (pas plus de 2 tirages en dessous de 10 pts par exemple...)
On revient à la problématique initiale : c'est presque trop simpliste comme contraintes...
Si on veut une équipe avec que des cracs "façon Qatar" on va éliminer les petits scores, si on contraire on veut un "patron" et une équipe d'esclaves on donnera la part un peu plus belle aux "petits pts..."
A+
Mais je me suis mal expliqué. Trouvé un équipe qui utilise tout le budget n'est pas l'objectif.
Non, c'est moi qui ai mal lu
@gallopin j'ai compris pourquoi je ne vous comprenais pas ! En fait ce que vous appelez points c'est en fait la valeur du coureur. Les points réalisé par chaque coureurs sont dans la colonne i
je pensais avoir été clair
merci quand même ça reste intéressant !!
bonsoir,
Ah Bah... Y serait temps de se réveiller ! Grasse mat du Dimanche hein !
Heu... Là c'est moi qui comprend plus parce que avec la colonne D c'était chouette mais avec la colonne I ça va pas âtre la même musique...
Bon c'est pas grave YAKA changer le barême et mettre la barre un peu moins haut., mais là tu vas pas avoir l'équipe du QATAR hein !
On va déjà pouvoir éliminer tous ceux qui dépasse les 175 ça en fera une douzaine en moins.
Je vais même éliminer Joaquim Rodriguez parce que ce serait pas un cadeau à lui faire que de le mettre qu'avec des zéros...
Bon ça tombe bien j'ai justement trouvé un algo un peu plus performant... Je reviens après la pause casse croute...
A+
Je ne sais plus comment expliquer ahah vous n'avez toujours pas compris !
Bon...
Qu'est-ce que j'ai pas compris ? Je te l'ai fait avec les points de la colonne i. C'est quoi le problème ?
Je t'ai refait ça aux petits oignons avec mon nouvel algo, c'est un poil plus long mais pour le coup je travaille sur la totalité des N° (sauf la douzaine de hors concours.
Pour le coup c'est un petit peu plus long, et il y a un petit bug d'affichage à cause des nombreux zéros, j'ai corrigé manuellement : Pas le temps de chercher le loup.
Bon il te reste encore 11 000 combinaisons possible. ça devrait t'occuper un moment...
A+
tony qu'est ce que tu m'as fais ? tu me donnes toutes les combinaison qui utilise exactement 175 credit? c'est pas du tout ce que j'ai demandé ahaha merci pour ton investissement en temps malgré tout. j'espère que tu y as pris du plaisir !!:)
Ben...
Alors il va falloir que tu t'expliques mieux parce que je te l'ai fais avec la colonne D, avec la colonne I
Je te l'ai bien fait avec 9 coureurs cyclistes (pas un de plus, pas un de moins).
Si le but est de maximiser le score total de mon équipe de 9 coureurs, je comprend qu'il faut qu'il soit si possible égal à 175 puisque c'est le maximum...
C'est vrai que je commence à me faire un peu vieux, j'ai les neurones un peu poussiéreux OK mébon...
A+
En fait les 175 c'est un budget que tu possèdes . tu peux dépenser moins mais pas plus. Les coureurs ont une valeur (la colonne D). tu achètes 9 coureurs en respectant le budget. tu sais déjà le score que vont faire les coureurs. tu veux le maximiser. j'ai proposé une solution plus haut.
c'est clair comme ça ?
Bien que ce ne soit pas le type de problème où le solveur excelle j'ai tenté un modèle.
Le point de départ est J vide (sélection).
Comment j'ai fait :
lancer le solveur et ensuite tu le relances 2-3 fois jusqu'à ce qu'il n'y ait plus de progression.
Ensuite je garde les 2-3 premiers de l'équipe et je relance le solveur etc...
Tu peux ainsi lui indiquer coureurs pour lui donner un point de départ
Si ça peut te dépanner en attendant qq chose de plus efficient .
Je ne sais pas à combien tu en étais mais en le relançant plusieurs fois je suis arrivé à une équipe à 1809.
J'ai sauvegardé à partir de O qq résultats.