Gleichmäßige Verteilung von Studenten auf Plätze

Wissenschaft Mathematik
#1

Hallöchen,

also mein Problem ist das folgende.
Ich suche eine Möglichkeit Studenten, oder Objekte oder sonstwas auf einem vordefinierten Raster (Sitzplätze/Tische/Podeste) ideal zu verteilen.

Sprich ich habe n Objekte und k Plätze die aufgebaut sind nach : A Reihen und B Spalten.

Leider finde ich meistens nur den simplen - Weg wurzel aus ((A*B)/n )

also die Fläche/Reihen/Spalten als Fläche zu betrachten und diese dann in gleichgroße Quadrate aufzuteilen.

Jedoch ist das natürlich nicht wirklich so möglich.

Es soll je nach vorhandenem Platz, dieser natürlich optimal genutzt werden.

Wenige Objekte --> mehr Reihen können Platz gelassen werden
Mehr Objekte --> die Objekte müssen enger zusammen rücken

Gibt es für soetwas eine Möglichkeit dies zu berechnen?

#2

Hi Benjamin,

ich hab dein Problem ehrlich gesagt nicht verstanden, vielleicht hilfst du mir (uns) auf die Sprünge? Kann es sein, dass es um etwas in dieser Art in zwei Dimensionen geht?
http://de.wikipedia.org/wiki/Theorie_der_endlichen_K…
Wazu brauchst du das Raster?

#3

Hi also das konkrete Problem ist folgendes :

Ich habe eine variable Anzahl an Studenten die in einen Raum sollen Zwecks Prüfung.

Der Algorithmus, bzw meine Nährungsformel soll nun also den Abstand zwischen 2 Studenten berechnen.
Also wieviel Plätze zwischen 2 Studenten in einer Reihe und wieviele Reihen zwischen „besetzten“ Reihen Platz gelassen werden sollen.

Also hab ich mir eine Matrix gedacht in der jeder Stuhl sozusagen ein Matrix Element wäre.

Nun brauche ich also eine Rechnungsmethode die mir eine ideale Verteilung der n Studenten in einem Raum mit x Reihen und y Spalten ausgibt, bzw die Abstände die einzuhalten sind.

Hoffe das ist etwas deutlicher oder verständlicher… sorry, sonst fragt ruhig nochmal weiter ^^

#4

Moin, Benjamin,

eine gleichmäßige Verteilung lässt sich offensichtlich nur dann erreichen, wenn die Anzahl der Studenten im richtigen Verhältnis zur Anzahl der Plätze steht. Ein einfaches Beispiel: 7 Studenten auf 9 Plätzen oder, noch schlimmer: 5 auf 8, wobei sogar die Geometrie egal ist.

Es soll je nach vorhandenem Platz, dieser natürlich optimal
genutzt werden.

Optimierung heißt, (mindestens) ein Minumum oder ein Maximum zu suchen, und das setzt immer eine Zielfunktion voraus. Wenn die sich nicht formulieren lässt, schaut es schlecht aus. Von der Formulierung der Randbedingungen möchte ich in diesem Fall gar nicht erst anfangen.

Gibt es für soetwas eine Möglichkeit dies zu berechnen?

Nicht auszuschließen, aber mir ist kein Verfahren bekannt.
Allergröbste Annäherung an die Fragestellung: Ganzzahl (Anzahl Plätze / Anzahl Studenten) gibt die Schrittweite zum Besetzen an, dann sind die Plätze wenigstens in einer Dimension gleich weit voneinander entfernt (bis auf den Rest).

Gruß Ralf

#5

Hallo Ralf.

eine gleichmäßige Verteilung lässt sich offensichtlich nur
dann erreichen, wenn die Anzahl der Studenten im richtigen
Verhältnis zur Anzahl der Plätze steht.

Klar!

Optimierung heißt, (mindestens) ein Minumum oder ein Maximum
zu suchen, und das setzt immer eine Zielfunktion voraus. Wenn
die sich nicht formulieren lässt, schaut es schlecht aus.

Das läßt sich machen: Ich gehe von einem rechteckigen Raum aus und benenne die Anzahl der Reihen mit A und die Anzahl der Stühle in jeder Reihe mit B. Weiter
benenne ich die Anzahl der besetzten Reihen mit a und die Anzahl der Studenten in jeder besetzten Reihe mit b. Dann gibt es pro besetzte Reihe x = (A-a)/a freie Reihe und pro besetzten Stuhl y = (B-b)/b freie Stühle. Das Optimierungsproblem besteht nun darin, das Minimum min(x,y) zu maximieren.

Ich vermute (ohne Gewähr!), dass dafür einfach x=y gilt, weil die beiden Größen ja so gekoppelt sind, dass eine schrumpft, wenn die andere wächst. Darauf folgte dann schnell

a = \sqrt{\frac{AN}{B}}

wobei N=ab die Zahl der Studenten im Raum ist.

Liebe Grüße,

The Nameless

der Formulierung der Randbedingungen möchte ich in diesem Fall
gar nicht erst anfangen.

Stimmt, das habe ich auch nicht eingebaut. Und natürlich bin ich stillschweigend davon ausgegangen, dass alle Divisionen aufgehen. Ansonsten muss der Benutzer halt die nächstpassenden natürlichen Zahlen wählen. :smile:

#6

Wenn ich das richtig sehe hast du damit aber keine exakte Sitzverteilung! Du weißt wie viele Reihen und Stühle frei sind, aber werden die Studenten in einem rechteckigen oder bespielweise hexagonalem Gitter angeeordnet? Das Problem ist, dass die Zielfunktion immernoch nicht klar formuliert ist.
Ich spekulier mal: man möchte, dass in einem möglichst großen Radius um jeden Studenten keine weitere Stundenten sind. Anders formuliert: ich habe eine feste Anzahl von Kreisen, die ich (überschneidungsfrei) so anordnen möchte, dass sie den Raum maximal ausfüllen. Die Antwort ist eine Sechserpackung oder hexagonale Anordnung.
Das Problem bleibt, dass der Raum rechteckig und die Stuhlverteilung vermutlich fest ist. Wie skaliert/dreht/verschiebt man das hexagonale Gitter, damit der Raum optimal ausgefüllt wird (hat ein bisschen was von einem Verschnittproblem). Das wird mir grad zu kompliziert, einfacher wäre es vermutlich ein Programm zu schreiben (ich hab grad leider nicht die Zeit dafür), dass nach folgender Idee funktioniert:
Man steckt (schlaffe) Luftballons in einen Kasten und lässt sie sich aufpusten. Wenn sie aneinander stoßen schieben sie sich beiseite bis jeder Luftballon die Position hat in der er maximal groß ist und der Raum optimal ausgefüllt wird. Ist zwar nicht sehr mathematisch, aber solangs funktioniert… vielleicht hab ich nächste Woche Zeit das zu testen (falls Interesse besteht) :smile:

#7

Hallo zurück, Du grußloser Poster!

Wenn ich das richtig sehe hast du damit aber keine exakte
Sitzverteilung!

Du weißt wie viele Reihen und Stühle frei
sind, aber werden die Studenten in einem rechteckigen oder
bespielweise hexagonalem Gitter angeeordnet?

Der Fragesteller spricht von einem vordefinierten Raster, das er sich als Matrix vorstellt. Von daher dürfen wir wohl annehmen, dass als Nebenbedingung ein
einfach-kubisches Gitter vorgegeben ist.

Liebe Grüße!

#8

Hallo,

endschuldige, war etwas in Eile und habs vergessen :smile: Wie gesagt lässt un sder Fragesteller allgemein etwas im Dunkeln, aber so wie ichs verstanden hab sieht das Problem so aus:
Einfaches Beispiel, 9 Studenten auf 7 x 7 Plätze:

O X X O X X O
X X X X X X X
X X X X X X X
O X X O X X O
X X X X X X X
X X X X X X X
O X X O X X O

schön rechtwinklig, alles wunderbar. Ein Student wird krank:

O X X O X X O
X X X X X X X
X X X X X X X
X O X X X O X
X X X X X X X
X X X X X X X
O X X O X X O

Der Abstand zwischen jedem Student kann jetzt vergrößert werden, aber dann hat man keine rechtwinklige sondern eher eine hexagonale Anordnung. Das im Detail mathematisch durchzukauen halte ich für mühselig, darum mein Vorschlag mit dem Programm :smile: