Martin Andersen <dur@ikke.nu> writes:
> On 15-10-2010 11:05, Torben Ægidius Mogensen wrote:
>> Mogens<myname@mysite.dk> writes:
>>
>>> Har brug for at finde ud af hvor mange flasker der kan være i
>>> forskellige standard kartonkasser. Findes der ikke et freeware program
>>> der kan lave en sådan simpel beregning?
>>
>> Den er nu langt fra simpel. Der er f.eks. ikke nogen formel for det
>> mindste kvadrat, der kan indeholde N cirkler, og der er kun fundet
>> beviseligt optimale værdier for op til N=30. Se
>> f.eks.
http://en.wikipedia.org/wiki/Circle_packing_in_a_square
>>
>>> Denne problematik er jo velkendt, eks. også hvor man skal optimere
>>> udskæringen af eks. en plade i komponenter. Men som nævnt er det i mit
>>> tilfælde relativt enkelt hvor man kender diameter på flaskerne, og
>>> længde+bredde af rektanglet, og så ville jeg gerne have den optimale
>>> fyldning, og gerne visualiseret.
>>>
>>> Har Googlet temmelig meget, men indtil nu uden resultat.
>>
>> Søg på "close packing of circles".
>
> Men i Mogens' eksempel er både kassens mål og flaskernes diameter
> givet på forhånd. Kun antallet er variabelt.
Hvid du kender den mindste kvadratiske kasse, der kan rumme N flasker
med diameter 1 (det problem, Wikipediaartiklen omtaler), så kan du også
se, hvor mange flasker med diameter X, der kan pakkes i en kvadratisk
kasse med sidelængde Y: I listen af mindste kvadrater for N flasker (fra
N=1 og opad), find det største kvadrat, der er mindre end eller lig med
Y/X. Så har du det maksimale andtal flasker.
Det hjælper selvfølgelig ikke for ikke-kvadratiske kasser, men da der
øjensynlig ikke er nogen nem måde at beregne det for kvadratiske kasser,
er der nok heller ikke for ikke-kvadratiske kasser, undtagen i specielle
situationer. F.eks. når den smalle led af kassen er mellem 1 og
1+sqrt(3)/2 = 1.866 gange diameteren af flasken. Der er den bedste
pakning et zig-zag mønster, hvor den første flaske sættes i et hjørne,
og de efterfølgende flasker sættes skiftevis i den ene eller den anden
side.
Hvis flaskerne har diameter 1 og den korte led af kassen er y, så vil
delta-x (dvs. afstanden mellem flaskerne på x-aksen) være sqrt(2y-y^2).
N flasker kræver 1+(N-1)*delta-x, altså x >= 1+(N-1)*sqrt(2y-y^2).
Eksempler:
Hvis y = 1 er x >= 1+(N-1)*sqrt(2-1) = N (oplagt nok).
Hvis y = 3/2 er x >= 1+(N-1)*sqrt(3-9/4) = 1+(N-1)*sqrt(3)/2
Hvis y = 1+sqrt(3)/2 er
x >= 1+(N-1)*sqrt(2(1+sqrt(3)/2)-(1+sqrt(3)/2)^2)
= 1+(N-1)*sqrt(2+sqrt(3)-1-3/4-sqrt(3))
= 1+(N-1)*sqrt(1/4)
= 1+(N-1)/2
= (N+1)/2
Hvis y > 1+sqrt(3)/2, bliver det langt mere kompliceret.
Torben