Ich grüble gerade an einem auf den ersten Blick einfachem
Optimierungsproblem, folgende Situation:
Gegeben ist ein Rechteck (Kantenlängen w und h) und ausserdem ein
Anzahl von Quadraten n. Nun soll die Seitenlänge der Quadrate s so
bestimmt werden, das die Fläche des Rechtecks optimal ausgenutzt wird.
n ist Ein Element natürlicher Zahlen von 1...m.
Zum Zeitpunkt der Bestimmung von s steht n natürlich fest.
Also z.B. w = 1000, h = 300, n = 7
Wie bestimmt man nun s so das der Platz im Rechteck optimal genutzt
wird?
Wie würden die Mathe-Gurus unter euch das lösen?
mit s=sqrt(w*h/n) erhält man den idealen Wert wenn man die Quadrate
teilen könnte. Damit die Quadrate passen muss man dafür sorgen, dass
diese an einer Seite anliegen:
w/(w/s aufgerundet) ergibt s, wenn die Quadrate an der rechten Seite
anliegen sollen. Das gleiche macht man mit h. Es kann aber vorkommen,
dass beim größeren s keine n Quadrate ins Rechteck passen. Ob dann das
kleinere s das optimale Ergebnis müsste man prüfen.
Ich denke, das Problem dürfte mit vernünftigem Aufwand nur durch massive
Rechenpower lösbar sein, immerhin kann man die Quadrate ja auch kippen
(???), und nicht alle im selben Winkel, da hat es dann schon einige
Freiheitsgrade
Samuel K. schrieb:> mit s=sqrt(w*h/n) erhält man den idealen Wert wenn man die Quadrate> teilen könnte.
Diese Formel war auch mein Ansatz. Sie resultiert aus der Restfläche
Arest = w*h - s*s*n . Leider funktioniert es so nicht, ein Beispiel:
w = 1000
h = 300
n = 8
s ergibt sich zu 193.64 ~ 194. Das passt aber niemals um 8 Quadrate
unterzubringen. Das Optimum dürfte irgend wo bei 150 liegen, damit wäre
h optimal ausgenutzt, in x-Richtung würde allerdings eine Fläche von
400*300 übrigbleiben...
Ich vermute mal man muß Randbedingungen festelegen, aber wie?
ich würde es so lösen:
alle möglichen "figuren" die es gibt durchprobieren
und immer eine Seite der Figur, auf die länge der Fläche anpassen (je
nachdem wie die "figur" passt, ist das w oder h)
ob man dass jetzt auch "berechnen" kann, (und beweisen dass das dann
immer stimm) wäre interessat
edit:
>Das Optimum dürfte irgend wo bei 150
also es kann nur entweder genau 150 (also 2 reihen)
oder 125 sein (1 reihe)
(die Lösung ist also genau 150...)
Mario Grafe schrieb:> Wie bestimmt man nun s so das der Platz im Rechteck> optimal genutzt wird?
Was heisst den für dich "optimal ausgenutzt" willst du die Fläche
einfach mit möglichst großen Rechtecken füllen? In dem Fall würde ich
das einfach in sinnvollen Schrittgrößen mich einer ersten Schätzung
annähern und dann in kleineren Schritten das optimum bestimmen.
Mario Grafe schrieb:> Samuel K. schrieb:>> mit s=sqrt(w*h/n) erhält man den idealen Wert wenn man die Quadrate>> teilen könnte.>> Diese Formel war auch mein Ansatz. Sie resultiert aus der Restfläche> Arest = w*h - s*s*n . Leider funktioniert es so nicht, ein Beispiel:>> w = 1000> h = 300> n = 8>> s ergibt sich zu 193.64 ~ 194.
Das ist nur die Hälfte meines Beitrags:
w/s aufgerundet = 6
h/s aufgerundet = 2
sx = w/(w/s) = 166.66
sy = h/(h/s) = 150
Der größere Wert für s passt nicht. Also prüft man ob es einen besseren
Wert für s gibt im Bereich 150 < s < 166.66:
h/s = 1000/166.66 gerundet = 1
w/n*(h/s) = 125
Dieser Wert ist kleiner als 150 -> Optimaler Wert s = 150
Robert L. schrieb:> also es kann nur entweder genau 150 (also 2 reihen)> oder 125 sein (1 reihe)> (die Lösung ist also genau 150...)
Für das Beispiel stimmt es, ich suche aber eine generelle Lösung für
z.B. n = 1...1000 und für mehr oder weniger beliebige w und h.
Es durchzuprobieren ist mir auch schon in den Sinn gekommen aber es muß
doch noch auch eine analytische Lösugn geben,oder?
Läubi .. schrieb:> Vermutlich könnte man das sogar in eine Extremwertaufgabe überführen...> hast du es den einfach schon mal versucht?
Ja habe ich aber genau da liegt der Hund begraben. Man muß geeignete
Randbedingungen festlegen. Man könnte der Formel Arest = w*h - s*s*n
ausgehen und entsprechend differentieren, aber ich weiß nicht wie ich
geeigente Randbedingungen definiere.
das ganze zu "Lösen" (mittels Software) ist jetzt glaub ich nicht so das
Problem..
in der Überschrift vom Thread steht "Mathematik"
deshalb GLAUBE ist, dass es nicht darum geht das "irgendwie" zu lösen,
sonder mit einer Formel..
Falls du den Code angeschaut hättest, wüsstest du, dass dieser eine
Formel mit ein paar Bedingungen enthält. Ich habe diesen Code
geschrieben um meine Idee zu testen, die ich oben erklärt habe. Bisher
habe ich keinen Fehler gefunden.
Bevor man sich Gedanken zum Algorithmus macht:
Erstmal Rahmenbedingungen: wie groß können w,h,n werden? Arbeiten wir im
ganzzahligen Bereich, oder im realen?
Und dein Code ist glaube ich nicht optimal Samuel. Es gibt Fälle wo ein
bisschen Verschnitt auf beiden Achsen besser ist als nur ein Verschnitt
auf einer Achse.
D. I. schrieb:> Und dein Code ist glaube ich nicht optimal Samuel. Es gibt Fälle wo ein> bisschen Verschnitt auf beiden Achsen besser ist als nur ein Verschnitt> auf einer Achse.
Ich denke man kann die Quadrate solange vergrößeren, bis sie an einer
Seite anliegen.
also ich habe jetzt folgenden Algorithmus als Lösung, er funktioniert,
aber ist sicher noch verbesserbar:
Das Problem ist das w,h,s und auch n ganze Zahlen (integer) sind. Daher
muß man den Wertebereich für s einschränken:
Schritt 1:
Bestimmen aller möglichen s für die x- und y-Richtung mit Hilfe der
Formeln sx[i=0..n-1] = w/i und sy[[i=0..n-1] = h/i
Schritt 2:
Gegencheck für die jeweils andere Richtung welche sx und sy gültig (d.h.
w udn h nicht überschreiten) sind mit Hilfe von hx[i=0..n-1]=(n/i)*sx
und wx[i=0..n-1]=(n/i)*sy, dabei fallen einige Werte schonmal raus. Der
Trick ist hierbei, das auch der Term (n/i) auf ganze Zahlen gerundet
werden muß, aber immer aufgerundet (falls bei (n/i) ein Rest bleibt.
Schritt 3:
Jetzt haben wir die "möglichen" s (sx und sy) ausgerecht und können die
gültigen Werte in die Formel für die Restflächenberechnung A = w*h -
s*s*n einsetzen. Der Wert s bei dem die Fläche minimal ist ist der
gesuchte Wert s!
Neben bei kann man noch die Anzahl der Elemente in x-Richtung (nx = w/s)
ausrechnen.
Naja, das ist jetzt wirklich Bruteforce und in dem Sinne kein wirklicher
Algorithmus. Wenn du ihn in c-ähnlichen Code fasst, könnte man ihn mit
meinem in einem bestimmten Wertebereich vergleichen.
Samuel K. schrieb:> Naja, das ist jetzt wirklich Bruteforce und in dem Sinne kein wirklicher> Algorithmus. Wenn du ihn in c-ähnlichen Code fasst, könnte man ihn mit> meinem in einem bestimmten Wertebereich vergleichen.
Ja ein echter analytischer Ansatz wäre mir auch lieber, aber man muß die
Randbedingungen beachten.
Wenn deine Zielfunktion eine Parabel ist (ist sie das wirklich?) dann
kannst du ternäre Suche anwenden um das Optimum zu finden. Dann muss man
auch nichts brute-forcen
D. I. schrieb:> Wenn deine Zielfunktion eine Parabel ist (ist sie das wirklich?) dann> kannst du ternäre Suche anwenden um das Optimum zu finden. Dann muss man> auch nichts brute-forcen
Nun ja, so einfach ist das nicht, da für s nur bestimmte Werte
zugelassen werden. Die Extremwerte der parabel bestimmen sich einfach,
aber man muß noch das nächstmöglich s finden.
Mir ist noch eine andere Lösung eingefallen, welche sich aus dem
Verhältnis von w und h ableitet.
Folgendes kann angenommen werden:
w nx
- ~ --
h ny
nx, ny ... Anzahl der Quadrate in x und y-Richtung
Schritt 1: Verhältnis von v = w/h ausrechnen
Schritt 2: nx = sqrt(v*n) und ny = sqrt(n/v) ausrechnen und aufrunden
Schritt 3: das jeweilige nx bzw. ny für beide Lösungen ausrechnen,
also nxy = n/nx und nyx = n/ny
Schritt 4: Für beide Fälle s ausrechnen, als sxx=w/nx, sxy=h/nxy,
syx=w/nyx, syy=h/ny
Schritt 5: für alle vier s... überprüfen ob die jeweilige Grenze (w, h)
überschritten wird.
Schritt 6: Den maximalen übrigbleibenden s-Wert nehmen
So in der Art würde ich es auch angehen
optimales N berechnen : x=abrunden(lange_seite/kurze_seite)
x>=N --> optimales s ist die kurze seite
x<N --> kurze_seite_neu=kurze_seite/2
x_neu=abrunden(2*(lange_seite/kurze_seite_neu)
x_neu>=N --> optimales s ist kurze_seite/2
usw und so fort...
Grüße Ert
Mario Grafe schrieb:> Ich grüble gerade an einem auf den ersten Blick einfachem> Optimierungsproblem, folgende Situation:>> Gegeben ist ein Rechteck (Kantenlängen w und h) und ausserdem ein> Anzahl von Quadraten n. Nun soll die Seitenlänge der Quadrate s so> bestimmt werden, das die Fläche des Rechtecks optimal ausgenutzt wird.>> [...]>> Wie würden die Mathe-Gurus unter euch das lösen?
Wenn ich's recht sehe ist das Euklid'scher Algorithmus aka. einfache
Kettenbruckentwicklung für das Seitenverhältnis w/l:
Zunächst bestimmt man
Q wird nicht sonderlich groß sein; zB ist
Q(200) = { 1, 2, 5, 10 }
Dann führt man den Euklid'schen Algorithmus für das Seitenverhältnis
durch und erhält damit eine rationale, teilerfremde (und in gewissem
Sinne optimale) Annäherung für das Seitenverhältnis, sei diese a:b.
Dann prüft man für alle q in Q, ob a·b <= n/q²
Ist das der Fall, berechnet man den Verschnitt
und sucht den besten Verschnitt v(q) über aller so gefunden q.
Da a und b geometrisch wachsen, ist entweder recht bald a·b > n und man
kann aufhören.
Oder w und h sind kommensurabel und die Kettenbruchentwicklung von w/h
also endlich. Hier kann der Fall auftreten, daß die
Kettenbruckentwicklung von w/h abbricht bevor a·b > n ist. In diesem
Fall hört man auch auf weiter zu entwickeln.
Beachte, daß Q nie leer ist und mindestens immer die 1 enthält.
Man setzt dann s(n) = a·b/q für die Seitenlänge und ist fertig.
Johann L. schrieb:> Wenn ich's recht sehe ist das Euklid'scher Algorithmus aka. einfache> Kettenbruckentwicklung für das Seitenverhältnis w/l:>
q ist also 0....n, aber was ist n', soll es das Seitenverhältnis w/h
sein?
Hagen Re schrieb:> Danke Johann, wieder was gelernt: inkommensurabel = teilerfremd
Nicht ganz, e und 1 sind inkommensurabel "teilerfremd" für reelle Zahlen
passt nicht wirklich. Am ehensten passt zu kommensurabel "stehen in
rationalem Verhältnis zueinander" oder "mit gleichem Maß messbar".
2.8 und 35 können zB beide mit einem Maß der Länge 0.7 (ganzzahlig)
ausgemessen werden; bei 1 und e geht das nicht.
Das ist doch eine Variationsaufgabe und zwar genau ein allgemeines
isoperimetrisches Problem. Die Randbedingungen sind die beiden
Längenparameter der xy-Achsen und die Anzahl der Quadrate, die
Extremwerte sind die Flächen. Wurde so schon im 9. Jh. v. Chr. gelöst
von Königin Dido bei der Landnahme von Karthago.
Damit sollte man das jetzt im 2. Semseter locker lösen können.
Also ein echt alter Hut welcher mathematisch richtig dann irgendwann von
Euler formuliert wurde.
Michael Lieter schrieb:> Johann L. schrieb:>> Sehe ich hier nicht. Das Problem ist doch diskret.>> Spielt keine Rolle - ist eben ein Spezialfall.
Das ist doch so, als wollte man eine Diophantische Gleichung oder ein
Faktorisierungproblem mittels Techniken der Differntial-, Integral- oder
Variationsrechnung lösen...
Es handelt sich aber um ein triviales Problem - welches natürlich mit
verschieden Verfahren lösbar ist - selbst in einem Vektorraum ist eine
Lösung formulierbar - ich rede mit Anfängern...
2. Semester?
Michael Lieter schrieb:> Es handelt sich aber um ein triviales Problem - welches natürlich mit> verschieden Verfahren lösbar ist - selbst in einem Vektorraum ist eine> Lösung formulierbar - ich rede mit Anfängern...>> 2. Semester?
Also so hat den Georg Johann auch noch keiner angefahren, wenn es um
Mathematik geht.
Du scheinst dir deiner Sache ja sicher zu sein.
Eure begrenzte Vorstellung der Mathematik erstaunt mich.
Ich stelle meinen Studenten in der 1. Vorlesung folgende Frage:
Was ist e?
Nur die Studenten welche im Geiste wie Euler sind, können über ihre
Beschreibung mitteilen das sie überhaupt nach dem verstehen dieser
Eintrittskarte die Befähigung besitzen sich selbst mit der Fähigkeit des
Nachdenkens die höheren Ebenen der Mathematik erschliessen können.
Es sind sehr Wenige.
Für einen Ingenieur mit einem Hammer besteht die Welt aus lauter Nägeln
;-)
Wie auch immer, da hier weniger Rumtheoretisieren denn eine praxisnahe
Antwort gefragt ist, anbei eine Lösung in C, bzw. genauer C99.
Kettenbrüche braucht man übrigens nicht; das Problem ist viel einfacher.
Um ein Variationsproblem reinzuprügeln muss man sich auch ziemlich
anstrengen; macht sich aber bestimmt ganz chic und beeindruckend ;-)
Mit GCC übersetzt man das Programm zB mit
> gcc quadrate.c -o quadrate.exe -std=c99 -Os -lm> .\quadrate.exe 1000 300 7> S = 150.00 (4 x 2, Verschnitt: 142500.0 = 47.50%, #Extra=5> .\quadrate.exe 1000 300 8> S = 150.00 (4 x 2, Verschnitt: 120000.0 = 40.00%, #Extra=4
"4 x 2" ist der Raster, in dem die Quadrate angeordnet werden.
"Extra" ist die Anzahl der Bonus-Quadrate, die man gratis aus dem
Verschnitt erhalten kann.
Winfried J. schrieb:> o weh>> s ist der gröste gemeinsame teiler von w und und h
Nein, ist es nicht. Beispiel: w = 1024, h = 1000 und n = 1200.
Lösung ist s = 200/7 ≈ 28.57 aber ggT (1024,1000) = 8
Johann L. schrieb:> Winfried J. schrieb:> o weh>> s ist der gröste gemeinsame teiler von w und und
hNein, ist es nicht. Beispiel: w = 1024, h = 1000 und n = 1200.Lösung ist s =
200/7 ≈ 28.57 aber ggT (1024,1000) = 8
Das ist ja wohl Blödsinn!
200/7 ist ein nichtperiodischer unendlicher Bruch (Teilbarrkeitsregeln)
es bleibt also ein wenn auch sehr kleiner Rest. Schon bei "≈" hättest du
drauf kommen sollen.
Mit GGT=8 125*128 = 16000 Einzelflächen bleibt Rest Null, also optimal
ausgenutzt bei gröstmöglicher Einzelfläche.
Winfried J. schrieb:> Johann L. schrieb:>> Winfried J. schrieb:>>> o weh>>> s ist der gröste gemeinsame teiler von w und und h>> Nein, ist es nicht. Beispiel: w = 1024, h = 1000 und n = 1200.>> Lösung ist s = 200/7 ≈ 28.57 aber ggT (1024,1000) = 8>> Das ist ja wohl Blödsinn!>> 200/7 ist ein nichtperiodischer unendlicher Bruch (Teilbarrkeitsregeln)Das ist auf jeden Fall Blödsinn> es bleibt also ein wenn auch sehr kleiner Rest. Schon bei "≈" hättest du> drauf kommen sollen.>> Mit GGT=8 125*128 = 16000 Einzelflächen bleibt Rest Null, also optimal> ausgenutzt bei gröstmöglicher Einzelfläche.
Enstpann dich erst mal und lies die Aufgabenstellung dann gaaanz
entspannt durch.
Mit den Zahlen von oben sind 1200 möglichst große Quadrate auf einem
1024 × 1000 großen Rechteck unterzubringen, und die Frage ist die nach
der besten Kantenlänge der Quadrate.
Ich behaupte immer noch: Diese Kantenlänge ist 200/7.
200/7 hat übrigens periodische Dezimalentwicklung:
@Samuel:
Für w=1, h=3 und n=5 liefert dein Programm s=0, was nicht sein kann.
Grund dafür ist die Integer-Division in
1
doubles=sqrt(w*h/n);
Wenn man sie durch eine Float-Division ersetzt, kommt s=0,5 heraus, was
aber immer noch nicht stimmt. Die richtige Lösung wäre s=0,6.
@Johann:
Auch dein Verfahren liefert für obige Eingabe s=0,5. Der Hund liegt hier
begraben:
1
a=sqrt((double)N*H/W);
2
b=sqrt((double)N*W/H);
3
4
for(intia=-1;ia<=1;ia++)
5
for(intib=-1;ib<=1;ib++)
6
{
7
doublesa,sb,s,v;
8
intaa=a+ia;
9
intbb=b+ib;
10
...
Es genügt nicht, nur die nächsten Nachbarn von a und b zu untersuchen.
Wenn ich mich nicht verrechnet habe, müsste folgende Formel das
Problem lösen:
Yalu X. schrieb:> @Johann:>> Auch dein Verfahren liefert für obige Eingabe s=0,5
Grrr. Danke für den Hinweis; lag aber an einem Denkfehler, nicht an
einem Rundungsfehler. Die Suche geht jetzt nur noch über 6 Kachelungen
anstatt über 9 wie zuvor.
>> quadrate.exe 1 3 5>> S = 0.60 (1 x 5, Verschnitt: 1.2 = 40.00%, #Extra=0> Wenn ich mich nicht verrechnet habe, müsste folgende Formel das> Problem lösen:
Sieht gut aus :-) Die gleiche Idee in eine Formel wo ich nur
durchprobiere...
Johann L. schrieb:> lag aber an einem Denkfehler, nicht an einem Rundungsfehler.
Ja, der Rundungsfehler war nur in Samuels Programm (zusätzlich zu einem
Denkfehler).
Dein jetziges Programm liefert aber immer noch Fehler, wenngleich
deutlich weniger als vorher. Beispiele:
1
H W N dein S mein S
2
——————————————————————————
3
3 1 5 0,5000 0,6000
4
5 3 29 0,6000 0,6250
5
19 6 5 3,1667 3,8000
6
——————————————————————————
Die Fehler scheinen aber nur noch für H>W aufzutreten.
optimierung.PNG
(987 Bytes)
