Nombre de cercles dans un carré

[Logarithme ne paye rien]

Bonjour à tous,

Je sollicite votre aide concernant le problème suivant :

Je dispose d'un carré de côté L.
A l'intérieur de ce carré, je dois mettre le maximum de cercles de rayon r.
(les cercles ne doivent pas déborder et ils doivent rester entier)

Il s'agit en réalité d'un problème tout à fait concret de packaging :
je dois mettre des tuyaux de différents diamètres (de 60 à 500 mm) dans un boite en carton de côté 700 mm. Je cherche donc une formule que je pourrais "dérouler" dans un tableau excel.

Merci par avance pour votre aide.

Baptiste.

[nodjim]

Tu cites d'abord des cercles de rayon r et ensuite tu dis qu'ils sont de diamètre différent....

[Logarithme ne paye rien]

Hum je vois que ce n'est pas très clair.

Il s'agit toujours du même problème : cercles de rayon r dans un carré de côté L.
Je cherche une formule à appliquer dans le cas général pour pouvoir faire ensuite varier r.

C'est mieux ?

[Dlzlogic]

Bonsoir,
Je crois que c'est un problème difficile.
Genre de question qui pourrait être posée :
1- dans un même carton, ne met-on que des tuyaux de même diamètre ?
2- les diamètres sont-ils normalisés ?
Il y a eu un problème de ce genre, je l'explique de mémoire.
"Dans une boite rectangulaire de largeur 4r on range des disques de rayon r. Donc les disques sont superposée 2 à 2.
Quelle doit être la longueur L de la boite pour pouvoir mettre 1 disque de plus ?"
Pour votre problème, je vais y réfléchir. Faites un petit "up" dans deux jours pour si jamais j'ai oublié.

[Logarithme ne paye rien]

Dlzlogic,

1/ On ne met que des tuyaux de même diamètre dans un même carton

2/ Les diamètres sont normalisés

Pour l'exemple, on peut prendre r = 50 et L = 600

[Dlzlogic]

Bonjour,
Finalement, j'ai eu un peu moins de difficulté que je ne craignais, je ne suis peut-être pas encore trop rouillé :zen: .
Voila le programme. C'est écrit en C, mais je suppose que vous n'aurez pas trop de mal à le transposer dans votre tableur préféré.
Mais je peux aussi faire un petit outil avec saisie, visualisation graphique, bref, tout ce qu'on veux (même le poids de l'ensemble), mais je ne vous ferai pas la feuille Excel.

Petit souci, je reviendrai.

[Logarithme ne paye rien]

Je suis impatient de voir le programme !
Le plus simple sera de le transposer en VBA pour utilisation dans excel.

Baptiste

[Dlzlogic]

Bonjour,
Je n'ai pas oublié ce problème. J'avais trouvé ce que je croyais être une solution, mais c'est probablement (encore) plus compliqué que ça.
Il n'y a pas eu d'autre réponse ?
Je devais terminer un truc, je m'y remet, mais je ne suis pas sûr du tout d'y arriver.
Si les diamètres de tuyaux sont normalisés ainsi que la dimension du carton, alors on peut résoudre le problème pour tous les cas possibles. Par contre, le faire dans je cas général, je n'ai pas encore la solution.

[nodjim]

Le problème se ramène donc à celui là: Quel carré minimal peut contenir n cercles de diamètre unité ?

[Dlzlogic]

Bonjour nojjim,
C'est pas si simple que ça, en tout cas à mon avis.
Cas simple, soit, les tuyaux sont rangés de telle sorte que leurs axes sont suivant un maillage carré, soit ils sont rangés suivant un maillage triangulaire équilatéral.
D'autre part, suivant que la première rangée, au fond, est paire ou impaire, et suivant l'intervalle qui reste ça peut changer l'optimisation.
Jetez un coup d'oeil sur la rangement de cercles dans un boite rectangulaire que j'ai cité, à partir de combien on peut rajouter 1 cercle. Je vous garanti que la solution n'est pas évidente. Dans le cas présent, je crois que cette situation doit arriver, donc il faut en tenir compte.

[Dlzlogic]

Bonjour,

Voila le programme.

Code: Tout sélectionner

int main()
{
/* le but est de calculer le nombre de tuyaux qu'on peut ranger dans
un espace de section carrée.
*/
  FILE *ecr = fopen("Tyau_Carré.txt","wt");
  float L; // côté du carré
  float R; // rayon des tuyaux
  int NbH; // nombre de tuyaux sur la couche la plus basse
  int NbC; // nombre de couches.
  int Ntot = 0;
// le nombre total est soit NbH * NbC
// soit NbH * (NbC/2) + (NbH-1) * (NbC/2)  Mais j'en suis pas sûr

// Nombre de tuyaux sur la première couche
  L=600;
  for (R=20.; R R) // On peut caser une demi-boule
    {
// Chaque rangée a le même nombre de tuyaux, décalés
// l'espace entre-axe est R*sqrt(3)
// on retire un rayon pour le haut et un tayon pour le bas et on rajoute un rang.
      NbC = (L - R*2) / floor(R*sqrt(3)) +1;
      Ntot= NbH * NbC;
      fprintf(ecr,"R=%.0fmm Rangement décalé  Ntot = %d \n",R,Ntot);
    }
    else // if ( reste  Ntot)
      {
        fprintf(ecr,"R=%.0fmm On décale 1 rang sur 2 Ntot = %d au lieu de %d\n",
                     R,NtotD,Ntot);
      }
      else
      {
        fprintf(ecr,"R=%.0fmm On garde %d par rang  Ntot = %d \n",R,NbH,Ntot);
      }
    }
  }
//  system("pause");
  fclose(ecr);
}


Vous me direz comment ça a marché.

[Quenton999]

Bonjour,

Je me permets de remettre cette conversation en haut de la file parce que, quelques années plus tard, je rencontre un problème similaire...

Il s'agit pour moi d'optimiser l'envoi de produits dans un container de 20 pieds ou 40 pieds dont voici les dimensions intérieures en mm (c'est surtout la quinconce en 2D qui m'intéresse) :

Container 20 pieds
Longueur : 5 867
Largeur : 2 330

Container 40 pieds
Longueur : 11 998
Largeur : 2 330

Les produits sont dans des sacs cylindriques. Je souhaite naturellement envoyer le plus grand nombre de sacs possibles dans un container en fonction du rayon du sac, qui peut être amené à changer.

Mon intuition me laisse penser qu'il faut écarter le plus possible les sacs dans le sens de la largeur mais est ce toujours vrai ?

Je butte, en regrettant l'époque de la prépa où j'aurais certainement été capable de venir à bout d'un tel exo... Un avis sur la question ?

Merci beaucoup de votre aide en tous cas !
Et très bonne journée !

[Ben314]

Salut,
Dans un espace supposé "infini", et avec des cercles de même rayon, le mieux que l'on puisse faire est un empilement "hexagonal" de ce style :

(piqué sur wiki ...)
Et, ça doit rester à peu prés l'optimum lorsque le rayon des cercles est "petit" par rapport à la dimension du "rangement" où on doit les mettre, mais je n'ai pas trop d'idée à priori du "petit comment" pour que ça soit à peu prés optimal...
Si on part sur le principe que le rangement doit être de ce type (hexagonal) on peut sans trop de problème calculer combien en faire rentrer dans un rectangle donné.

Par contre, dans le cas de cercles de rayon différent, je ne suis pas sûr qu'il y ait de solution théorique : je pense qu'il faut aller regarder du coté des algo. informatiques pour voir ce qui c'est fait dans ce domaine là (ça a surement été étudié)

[Cliffe]

C'est des problèmes de recherche opérationnelle ça non ? Tu n'obtiendra pas de formule mathématiques toutes faites.

[Cliffe]

Données :
[INDENT] - Soit le nombre de cercles.
- Soit , le rayon du i-ème cercle.
- Soit la largeur du cadre et la hauteur.[/INDENT]

Variables :
[INDENT] - On note le couple de variables indiquant la position du centre du i-ème cercle.[/INDENT]

Formulation du problème :
[INDENT] 1. On s'assure que le centre de chaque cercle est situer dans le cadre :[/INDENT]

[CENTER][/CENTER]

[INDENT] 2. On s'assure que les cercles ne se coupent pas :[/INDENT]

[CENTER] [/CENTER]



Tu peux utiliser un solveur pour résoudre. Excel peut le faire si tu n'a pas trop de variables (200 max).

Cette manière de modéliser le problème ne prend pas en compte la gravité. A toi de caler les sacs pour que sa tienne ^^ (ou alors il faut ajouter des contraintes).

[chan79]

En respectant les dimensions du container 20 pieds et en mettant des sacs tous de rayon 100, on peut en mettre 371. Je ne sais pas si on peut faire mieux .... :hum:

[Cliffe]

Les rayons sont différents

[Quenton999]

Rebonjour à tous et surtout merci pour toutes vos réponses !

Effectivement c'est un problème d'excellence opérationnelle, et il est de taille pour notre projet donc vaut mieux pas se planter ^^

Alors à priori le rayon sera identique pour tous les sacs, mais je dois le déterminer en faisant une étude comparative prenant notamment en compte l'espace occupé (critère principal). Donc plus on diminue le rayon, plus on va occupé d'espace mais d'autres problèmes, autres que mathématique, apparaîtront.

Imaginons le cas d'un sac de rayon 255mm (c'est tordu mais c'est directement un cas appliqué !). En largeur, on peut mettre 4 sacs et il restera 2330 - 4 * 255*2 = 290mm. Je me disais donc qu'il valait mieux répartir ces 290mm entre les sacs [Ligne 1] pour pouvoir "avancer" la Ligne 2.

Mais je ne parviens pas à calculer la position du centre des sacs en ligne 2, puis des autres.

J'espère avoir été clair.... sinon n'hésitez pas à me demander des précisions !

Et encore merci pour votre aide précieuse !

[Cliffe]

Moi je pige pas. Tous les sacs d'un même container ont le même rayon ? Si oui alors y'a rien de compliqué, tu peux trouver une formule mathématique. Si non alors c'est un problème de packing et tu dois utiliser l'informatique pour le résoudre.


Je pense à ça moi :

[CENTER] [/CENTER]

[chan79]

Container 20 pieds et rayon 255
On peut en mettre "au moins" 55(on a de la chance car les deux de droite "logent")