Formel für kleinstmöglichen Kreis um Kreise ?

Wissenschaft Physik
#1

Hallo Mathematiker,

Ich habe folgendes Problem. Ich muß um kleine Kreise mit verschiedenen Durchmessern einen großen legen. Dieser sollte der kleinstmögliche sein. Gibt es hierfür eine Mathematische Lösung ?
Die Variablen sollten also sein: 1. Anzahl der verschiedenen kleiner Durchmesser. 2. Durchmesser dieser einzelnen kleinen Durchmesser. 3. Anzahl der gleichartigen Durchmesser. Als Ergebnis sollte der kleinstmögliche Kreisdurchmesser um alle diese kleinen Kreise herauskommen.
Z. Zt. habe ich nur die zeichnerische (und damit sehr ungenaue) Lösung, die mich verständlicherweise nicht befriedigt.
Für die Bearbeitung dieses Problems schon im Voraus vielen Dank
Ciao Matthias

#2

Die Variablen sollten also sein: 1. Anzahl der verschiedenen
kleiner Durchmesser. 2. Durchmesser dieser einzelnen kleinen
Durchmesser. 3. Anzahl der gleichartigen Durchmesser. Als
Ergebnis sollte der kleinstmögliche Kreisdurchmesser um alle
diese kleinen Kreise herauskommen.

Warum ist die Anzahl der gleichartigen Durchmesser eine eigenständige Variable? Stattdessen fehlt die Beziehung der Kreise zueinander (z.B. Mittelpunktsabstände). Oder berühren die sich alle, wenn ja wie?
Detailliere das doch bitte mal.

#3

Hallo CyMind,

Vielleicht wird das Problem klarer, wenn ich meine Anwendung beschreibe. Wir verlegen mit CATIA (3-D CAD-Programm) Kabelbündel in einem Verbindungsknoten der Raumstation. Diese Bündel bestehen wiederum aus verschiedenen Einzeldrähten. Wir müssen dem System die Büdeldurchmesser (und ihre Eigenschaften) vorgeben, was bedeutet, dass wir kleinstmögliche Bündel mit verschieden dicken Einzeldrähten berechnen müssen. Dies geschieht z.Zt. noch zeichnerisch (was, wie Du sicher nachvollziehen kannst, nicht nur recht ungenau, sondern auch sehr Zeitintensiv ist). Die kleinen Kreise, die ich beschrieben habe, sind also die Einzeldrähte (sie berühren sich also alle mehr oder weniger) und der große Kreis um diese kleinen Kreise ist dann der von mir zu ermittelnde kleinste Bündeldurchmesser.
Ich hoffe durch diese Beschreibung ist das Problem klarer geworden. Vielen Dank für Deine Bemühungen mir das Leben zu erleichtern.
Ciao Matthias

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

Ich weiß nicht, ob es dafür eine analytische Lösung gibt. Falls nicht oder aber doch (diese aber seeehr kompliziert ist), kann man für derartige Probleme Optimierungsalgorithmen (die man mit kleinen Computerprogrammen schnell durchführen kann). Ein verwandtes Problen, daß häufig beschrieben ist, ist das „Packproblem“, wo versucht wird, möglichst viele Kisten untersch. Größen in einen vorgegebenen Raum zu packen. Vielleicht sucht du mal in dieser Richtung.

Gruß Jo

#5

Hallo,

also doch ein Packungsproblem. Die schlechte Nachricht: Es ist NP-hart, d.h. es gibt keinen Algorithmus, der die optimale L"osung f"ur praxisrelevante Problemgr"ossen in vern"unftiger Zeit findet.

Die bessere Nachricht: Es gibt Algorithmen, die suboptimale L"osungen recht schnell finden, kenn ich allerdings keine Referenz zu.

Eine Hau-Drauf-Methode w"are folgende: Du bastelst Dir eine Fehlerfunktion, und zwar mit Summanden f"ur sich "uberlappende Dr"ahte, quadratisch in der L"ange der "Uberlappung und f"ur Dr"ahte, die ausserhalb eines variablen Radius r liegen. Nun startest Du in einer Situation mit Fehlerfunktion Null und steuerst r nach unten, und immer, wenn der Fehler gr"osser als Null ist, wird mit Gradientenverfahren oder … korrigiert.

Wenn keine Korrektur mehr m"oglich ist, dann ist ein lokales Optimum erreicht. Mehrere L"aufe mit verschiedenen Startsituationen f"uhren dann (hopefully) an das globale Optimum heran.

F"ur die … in den Abstiegsmethoden s. z.B. David G. Luenberger: Introduction to linear and nonlinear Programming

Ciao Lutz