Challenge

[Médiat]

Bonjour,

Suite à la discussion : Optimisation sous contraintes (version appliquée) (futura-sciences.com), je vous propose le challenge suivant :

On dispose d'une boite de 10cm par 15cm, on doit diviser cette boite en cases dont la surface doit être proportionnelle aux nombres de machins dans chaque catégorie (de A à J), l'épaisseur des cloisons est considéré comme nulle, les nombres de machins dans chaque catégorie sont :

A 111
B 159
C 8
D 70
E 86
F 126
G 150
H 45
I 195
J 50

Pour évaluer une disposition, on multiplie, pour chaque case le quotient du grand côté par le petit.

Trouverez-vous une disposition des cases, meilleure que celle de Excel (*) (dont le score est de 157) ?

 Cliquez pour afficher

On peut

(*) Qu'il n'est pas nécessaire de connaître.
-----

[Liet Kynes]

Je me suis lancé et le déplacement des rectangles me fait penser au générique de Chapi-Chapo ( https://www.youtube.com/watch?v=-OMyXgn9NUQ )

[Médiat]

Un petit mot supplémentaire : la pire solution donne un score de l'ordre de 10^13 aussi, je pense que la bonne mesure du score est le log (base 10) de la définition précédente, ce qui donne

Pour Excel : 2.20
La pire : 13

[Liet Kynes]

J'ai fait un positionnement mais j'ai arrondi majoritairement au rang inférieur, du coup je pense que je n'ai pas saisi ce qu'il faut chercher..

Sans nom 1.jpg

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Il faudrait faire le calcul du score, vérifier que vos cases s'intègre bien dans la boîte et éliminer les places vides

[BrainMan]

C'est finalement assez simple...???

Voici en tous cas ma solution (en fait une des 10*9*8*7*6*5*4*3*2 solutions évidentes) :

 Cliquez pour afficher

Il est question de diviser un rectangle de 10*15 cm de manière à pouvoir caser 1000 objets de différentes catégories (dont on ne sait rien).

Je vais donc pour me simplifier la vie, saucissonner le rectangle (de haut en bas pour imager) dans la direction du plus grand côté (celui qui fait 15cm).
On obtient donc des bandes verticales, apposées les unes aux autres par leur longueur (pour lesquelles on choisit bien sûr 15 de longueur), de largeurs égales au nombre d'objets de la catégorie (1 bande, 1 catégorie).
Par exemple :
Bande A : Largeur 10 cm * 111 / 1000 = 1.11 cm
Bande B : 1.59 cm
Bande C : 0.08 cm
Bande D : 0.70 cm
Bande E : 0.86 cm
Bande F : 1.26 cm
Bande G : 1.50 cm
Bande H : 1.45 cm
Bande I : 1.95 cm
Bande J : 0.50 cm

La somme des largeurs fait 10 cm
Et la hauteur bien sûr des bandes, fait 15 cm.

Reste à placer les bandes les unes par rapport aux autres.

L'ordre A/B/C...J est une possibilité, mais on peut permuter comme on veut, soit le nombre de possibilités 10! évoquées plus haut.

[Médiat]

Trouver une solution est trivial, en trouver une bonne beaucoup moins, avez-vous calculé votre score (sauf erreur de ma part vous avez la solution que j'ai appelé "la pire"

[BrainMan]

Trouver une solution est trivial, en trouver une bonne beaucoup moins, avez-vous calculé votre score (sauf erreur de ma part vous avez la solution que j'ai appelé "la pire"

Je l'aurais fait si j'avais la formule exprimée clairement pour ce faire...
Sinon, mis à part cette histoire de score, il est évident que la "réponse triviale" est la plus adaptée quant à la question posée dans le lien fourni en message #1.
Restreindre la solution à "des boites" qui ressemblent le plus à ce qu'on croit savoir des boites, reflète un manque d'imagination (compensé par un travail acharné, certes).

[Médiat]

Je l'aurais fait si j'avais la formule exprimée clairement pour ce faire...

Désolé, je n'avais pas anticipé que

Pour évaluer une disposition, on multiplie, pour chaque case le quotient du grand côté par le petit.

puisse être trop compliqué pour certains.

Quant à votre avis sur l'adéquation de votre "solution" au problème original, regardez ce que celui qui a posé la question a réalisé !

[Liet Kynes]

Bonjour,

J'ai repris mon positionnement qui a consisté à prendre la valeur paire de surface la plus proche de celle donnée par les proportions
A = 111/1000 soit 11.1% de 150 donne 16.65 cm² -> j’arrondis à 16
B= 15.9/1000 soit 11.1% de 150 donne 23.85 cm² -> j’arrondis à 24
En procédant ainsi il me reste 3 cases vides et j'ajuste donc C à 2 au lieu de 1 et H à 8 au lieu de 6.
Le calcul des écarts entre surfaces théoriques des cases et surface obtenues et disposées dans le rectangle 15*10 donne 5.3 en valeur absolue: je ne sais pas si je suis dans les clous avec cette méthode le score serait de 150+5.3=155.3 ? ( la somme des multiplications des côtés de mes cases donnant 150)

Sans nom c.jpg

Une autre variante et de prendre des cases de 3 de côté (les surfaces obtenues avec les proportions étant toutes multiples de 3) puis de les opposer de façon à être au plus proche de 10.
Dans ce cas l’écart absolu est de 0.7:

Sans nom c2.jpg

[Médiat]

Bonjour,

Pourquoi arrondir ?
Votre score pour le premier est de 4752 (ou 3.68 avec le log)

[polo974]

Les cases doivent-elles être rectangulaires ? ? ?

[Médiat]

Oui, d'ailleurs c'est le plus simple pour remplir un rectangle

Je précise que j'ai choisi 10 cases car c'est possible à la main, à partir de 15 il faut écrire un programme

[Liet Kynes]

J'ai enfin compris le calcul du score merci pour l'indication.

On cherche au final à obtenir une solution pour laquelle la proportion des rectangles soit telle que le rapport côté/côté (non opposés) de chaque rectangle soit au plus proche de 1 tout en respectant le pourcentage de surface correspondant à leur proportion en tant que machins ?

Si j'ai compris le problème, je vais tester quelques trucs car le résultat de excel me semble basé sur une règle qui peut ne pas être vraie si la relation entre les surfaces des rectangles permet certaines combinaisons.

[Médiat]

On cherche au final à obtenir une solution pour laquelle la proportion des rectangles soit telle que le rapport côté/côté (non opposés) de chaque rectangle soit au plus proche de 1 tout en respectant le pourcentage de surface correspondant à leur proportion en tant que machins ?

Oui, c'est bien cela, en faisant toujours le quotient du plus grand par le plus petit, chaque case a un score individuel >= 1, et on fait le produit de tous les scores individuels

[Liet Kynes]

Il faut multiplier par 100 pour les dimensions des rectangles pour faire des tests graphiques mais j'imagine bien que "à la main" qui est indiqué doit être un calcul.
Pour trouver plus rapidement que sur le tableur les facteurs et diviseurs d'un nombre j'utilise ce site https://fr.numberempire.com/1665

Je comprends mieux le titre challenge..

[Liet Kynes]

Quand on arrive là ou cela se corse, c'est là que le vrai problème se pose: il y a au départ dans le choix des n rectangles les plus favorables à un score bas quelque chose à trouver en lien avec les hypoténuses?

[Médiat]

quelque chose à trouver en lien avec les hypoténuses?

Pas que je sache, je précise que la réponse tient plus dans l'algorithmique que dans les mathématiques

[polo974]

Quand on arrive là ou cela se corse, c'est là que le vrai problème se pose...

La Palice, sort de ce corps ! ! !

[Liet Kynes]

J'ai les deux premiers rectangles, je les propose pour vérifier si j'ai vraiment compris l'idée:

 Cliquez pour afficher

1.5*3.7 et 4.5*5.3

[Médiat]

Chaque rectangle doit avoir une aire proportionnelle à ce qu'il doit contenir, par exemple (4.5*5.3/150)*1000 = 159, c'est bon, mais pour le premier non.

Surtout, je ne comprends pas votre démarche : les dimensions de chaque rectangle ne sont valides que si les cases forment un puzzle de taille 10x15.

Choisir les tailles d'une seule case n'a pas de sens (d'ailleurs dans ce cas, 4.88365 x 4.88365 serait bien meilleur, avec un score de 1)

[Liet Kynes]

Oui je me suis trompé en rédigeant pour le premier rectangle 4.5*3.7

J'ai une démarche par élimination en me basant sur les diviseurs, je ne sais pas si je peux aboutir mais je réduit déjà au maximum les pièces possibles du puzzle.

[Médiat]

En aucun cas cela peut avoir quelque chose à voir avec des diviseurs (on est dans IR pour les calculs)

[Liet Kynes]

J'ai bien fait de poser ma question.
Je suis parti sur l'idée que l'on pouvait construire le "puzzle" avec les cases d'un tableur, du coup j'ai multiplié par 100 les surfaces obtenues à partir des proportions de machins pour obtenir des entiers.
Ainsi mon rectangle devient 100*150.
Avec 23.85 qui est la surface pour 159 machins -> * 100=2385 et diviseurs 1,3,5,9,15,45,53,159,265,477,7 95,2385 -> les couples (1,2385),(3,795),(5,477),(9,26 5),(9,265),(15,159) ne peuvent tenir du fait d'une longueur de 150 max reste donc 45*53 éligible, de là si 45*53 est dans le rectangle alors les longueurs et hauteurs maxi possible sont 150-45 et 100-45 -> ce qui me permet de ne conserver qu'un couple pour la surface de 1665 (16.65 pour 111 machins) à savoir 45*37.

La conversion consiste à diviser par 10 chaque côté obtenu d'ou 4.5*3.7 et 5.3*4.5.

Mais je comprends que la solution ne se trouvera pas forcement (sauf coup de bol) dans les couples permis en multipliant les surfaces par 100 et c'est pour cela que je me dit que j'ai bien fait de poser la question

[Liet Kynes]

Après 25 posts j'ai compris ce qu'il fallait faire, en lisant trop vite je suis parti sur un autre problème (qui me parait aussi intéressant à étudier pour certaines applications pratiques).

[polo974]

je trouve un score de 18,457
il y a une petite astuce pour caser la plus petite case...
(c'est une solution numérique, donc avec arrondi au millième...)

 Cliquez pour afficher

cellule	machin	hauteur	largeur	k	surf ctrl	surf
A	111	4,810	3,461	1,390	16,650	16,65
B	159	4,492	5,310	1,182	23,850	23,85
C	8	1,373	0,874	1,572	1,200	1,20
D	70	4,242	2,475	1,714	10,500	10,50
E	86	3,437	3,754	1,092	12,900	12,90
F	126	6,563	2,880	2,279	18,900	18,90
G	150	5,190	4,335	1,197	22,500	22,50
H	45	2,727	2,475	1,102	6,750	6,75
I	195	5,508	5,310	1,037	29,250	29,25
J	50	3,030	2,475	1,224	7,500	7,50
				18,457	150,000	150,00

colonne k = rapport grand/petit coté

rectangle en mode paysage (h 10, l 15):
1 colonne contenant B et I (largeur 5,310)
1 colonne contenant D, H et J (largeur 2,475)
les 5 derniers avec C "au milieu"
presque colonne contenant F et E (dans cet ordre)
C coincé dans le décrochement entre F et E
presque colonne contenant G et A (dans cet ordre)

[Médiat]

Bonjour,

Je ne vois pas comment vos cases s'emboitent (pour B, I, J, H et D, je vois mais les autres non)

[polo974]

ci joint un placement (approximatif)

 Cliquez pour afficher

edit: argh, il les mets partout...

[polo974]

en mode texte:

 Cliquez pour afficher

+--------+------------+
|        |            |
|        |            |
|        |            |
|        |     G      |
|   F    |            |
|        |            |
|        |            |
|        +--+---------|
|        |C |         |
+--------+--+---------|
|           |         |
|           |         |
|     E     |    A    |
|           |         |
|           |         |
+-----------+---------+

[Médiat]

Bravo !
Cela me paraît difficile à battre.

Pourriez-vous décrire un algorithme faisant cela dans tous les cas de figure ?