Optimisation sous contraintes (version appliquée)

[thomas.trautenberger]

Bonjour à tout le monde !

Je m'appelle Thomas. J'ai 24 ans.
Je suis aujourd'hui avec vous pour partager un petit problème d'optimisation sous contraintes.

Voilà, je fais du tri dans mes composants électroniques et à vrai dire ça déborde de partout. Là j'attaque les condensateurs non polarisés.
Du coup comme j'aime concevoir des choses, j'ai fait mes boites de rangement moi-même à l'aide de carton et d'une graveuse laser ! (voir photo ci-jointe)

Cependant, comme vous le constatez sur la photo. En faisant des volumes équivalents pour toutes les valeurs, on se retrouve avec des emplacements remplis à bloc tandis que d'autres sont vides !

J'aimerais donc concevoir une boite avec des volumes correspondant à la fréquence d'apparition des valeurs de condensateurs. Comme ça quand un emplacement est plein, le reste des emplacements n'est pas loin de l'être !
Pour ce faire j'ai pris le reste des condensateurs que je n'ai pas encore trié et je les ai trié par valeur. J'ai compté combien j'en ai de chaque et consigné ça dans un petit tableau Excel que je vous joins également.

Mon problème est donc le suivant :

J'aimerais faire deux boites qui puissent accueillir chacune 12 valeurs de composant ( voir série normalisée E12). Le but est que ces boites se remplissent de manière à peu près homogène.
J'aimerais donc arriver à trouver des dimensions optimales qui me permettent d'achever ça sachant que la boîte peut faire jusqu'à 20*30cm (taille max de la zone de gravure laser).
Pour la hauteur j'aimerais ne pas dépasser 5 cm pour éviter que ça soit impossible de pêcher un composant à la main.
Surtout, j'aimerais que ça s'assemble pour qu'il n'y ai pas de volume mort ! c'est à dire que la somme des côtés qui sont extérieurs fasse par exemple jusqu'à 20cm d'un côté et 30cm de l'autre !

Le but final sera de faire un tableur qui me donne les dimensions des boîtes. Comme ça, je peux ensuite utiliser ça dans ma cao !

Je sais ce que je veux. Mais je ne sais pas comment y arriver. En cours, on avait vu les fonctions d'optimisations sous contraintes mais malheureusement pas de manière aussi abouti que ça.

Voilà ! Je sais que j'en demande beaucoup mais si vous avez des pistes je suis preneur. Je pense aussi que ça peut être utile si d'autres personnes souhaitent bénéficier des ressources dégagées par la discussion.

Merci d'avance !

Amicalement.
-----

[obi76]

Bonjour,

problème sympa !
Il existe une méthode pour décomposer l'espace en rectangles, connaissant le % de surface totale qu'occupe chaque rectangle :

Vous pouvez vous en inspirer : vous regroupez les surfaces en deux blocs à peu près égaux, vous pouvez couper l'espace en deux. Vous réitérez dans chacun des rectangle généré, et à la fin vous obtenez ça.

Vous voyez ?

[thomas.trautenberger]

Bonjour
et tout d'abord merci de votre réponse

donc en fait si je comprends bien il existe une méthodequi est capable de découper une surface en sous surface en fonction un pourcentage de celle ci
il me suffit donc de faire en sorte que la somme des pourcentages fasse 100% pour que j'utilise l'ensemble de la surface !
pour les % je fais gross modo volume occupé sur volume total fois 100 dans mon tableau !

Pouvez vous me donner le nom de cette méthode ou la procédure de mise en œuvre ?

Merci d'avance !

[obi76]

Bonjour
et tout d'abord merci de votre réponse

donc en fait si je comprends bien il existe une méthodequi est capable de découper une surface en sous surface en fonction un pourcentage de celle ci
il me suffit donc de faire en sorte que la somme des pourcentages fasse 100% pour que j'utilise l'ensemble de la surface !
pour les % je fais gross modo volume occupé sur volume total fois 100 dans mon tableau !

C'est ça. La méthode est celle que je vous ai donné : vous séparez les surfaces en deux groupes d'importance à peu près égale de matière itérative.

Par exemple :
On a 6 rectangles, chacun d'entre eux occupe respectivement P1, P2... P6 % de la surface totale. Imaginons :
P1 = 5%
P2 = 10%
P3 = 27 %
P4 = 5%
P5 = 3%
P6 = 50 %

1° étape : on regroupe les blocs en 2 parties. On va avoir d'un côté :
(P1, P2, P3, P4) = 47%
(P5, P6) = 53%

Vous séparez votre boite en deux parties, selon une verticale à 47% de la hauteur.

Capture d’écran du 2021-04-15 10-34-03.png

2° étape : pour la partie haute, on recommence, on sépare P1, P2... P4 en deux parties à peu près égales : (P1, P2) et (P3, P4). On coupe horizontalement à (P1+P2)/(P1+P2+P3+P4) % = 15/47 = 0.31 de la largeur

Capture d’écran du 2021-04-15 10-34-09.png

Pour la partie basse, on coupe à P5/(P5+P6) = 3/53 = 0.06 de la largeur

Capture d’écran du 2021-04-15 10-34-15.png

3° étape, etc. : on continue le même principe tant que chaque rectangle n'a pas sa partie réservée (ici en haut à gauche et en haut à droite)

Capture d’écran du 2021-04-15 10-34-22.png

Et voilà !

Et pour info : ce n'est pas de l'optimisation sous contrainte pour moi

Pouvez vous me donner le nom de cette méthode ou la procédure de mise en œuvre ?

Elle a sûrement un nom mais je ne le connais pas...

[A voir en vidéo sur Futura]

[Médiat]

Bonjour

Obi, est-ce que ce ne serait pas un tout petit plus pratique si au lieu d'alterner découpe verticale et découpe horizontale on découpait systématiquement dans la dimension la plus longue ?

[obi76]

Obi, est-ce que ce ne serait pas un tout petit plus pratique si au lieu d'alterner découpe verticale et découpe horizontale on découpait systématiquement dans la dimension la plus longue ?

Oui effectivement ça donnerait des choses plus homogènes, j'y ai pas pensé sur le coup

[Médiat]

Voilà ce que cela donne :



La découpe de p1, p2, p3, p4 en (p1, p2, p4) et (p3) serait plus équilibré, mais j'ai suivi to découpage.

[obi76]

La découpe de p1, p2, p3, p4 en (p1, p2, p4) et (p3) serait plus équilibré, mais j'ai suivi to découpage.

J'étais entrain de le refaire, merci

Oui pour les découpages on peut toujours faire différemment (pas forcément les prendre à la suite, etc.). Enfin après pour trouver où se trouvent les condensateurs de telle ou telle valeur, ça va vite finir par devenir compliqué

[Médiat]

Voilà ce que j'obtiens en découpant les quantités dans le rapport longueur/largeur plutôt que 1/2 systématiquement :

[obi76]

C'est encore plus propre ^^

[thomas.trautenberger]

Ah mais c'est super ! Du coup ma question c'est quel logiciel utilisez vous pour réaliser ce découpage ? Est ce fait manuellement ?
Je pense avoir compris le principe, il reste plus qu'à l'appliquer

[Médiat]

Est ce fait manuellement ?

Manuellement, si le nombre de case était trop important, il suffirait d'écrire un petit programme, sinon, cela n'en vaut pas le coup

[thomas.trautenberger]

Re,

Bon j'ai une bonne nouvelle, j'ai trifouillé un petit peu dans Excel et j'ai trouvé un type de graphique qui fait le boulot à ma place

Du coup je vous repartage le résultat (qui n'est pas au résultat final mais juste pour montrer). Effectivement du coup ça reprends cette fameuse astuce pour découper les rectangles.

Je pense être arrivé au résultat voulu, qu'en pensez vous ?

[Médiat]

C'est clairement pas le même algorithme, mais cela paraît pas mal

[thomas.trautenberger]

Bonsoir

afin de clore l'aventure je vous montre juste ce que ça a donné en image !
Merci encore pour vos réponses et conseils 😊

[Médiat]

Merci d'avoir posté le résultat

[obi76]

Merci !

Et je suis curieux de savoir s'ils vont se remplir aussi rapidement les uns que les autres

[thomas.trautenberger]

Hum c'est une bonne question, je pense que ça va principalement dépendre de la pertinence statistique de mon analyse ( est ce que les fréquences de mon échantillon sont représentatives ? ) et du coup de si ma formule empirique pour connaitre le volume occupé par les différentes valeurs de condensateurs est bonne ou non !

Malheureusement, comme j'ai fait la boite assez grande, on ne le saura probablement que dans quelques années quand elle sera pleine.