Berechnung der Anzahl von Kombinationsmöglichkeiten von Projekten in Perioden |
| 02.06.2010, 18:05 | frame | Auf diesen Beitrag antworten » | ||||
| Berechnung der Anzahl von Kombinationsmöglichkeiten von Projekten in Perioden Hallo, momentan versuche ich, ein Verständnis von Algorithmen zur linearen Optimierung zu entwickeln(auf die Algorithmen soll im weiteren Verlauf nicht eingegangen werden). Dabei traf ich unter anderem auf folgende Problemstellung: 20 Projekte sollen innerhalb von 5 Perioden bearbeitet werden. Dabei ist es völlig egal in welcher Reihenfolge und Periode diese Bearbeitung erfolgt. Es sind hierbei keinerlei Restriktionen bzw. Nebenbedingungen zu beachten. Ein paar mögliche Lösungen (in diesem Fall 3 Projekte und 3 Perioden - analog zur eingangs gestellten Aufgabe) sollen dieses verdeutlichen: Es gilt: T(i) = Periode(i), i=1..3 P(i) = Projekt(i), i=1..3 1. [T1:{P1,P2,P3}] [T2:{/}] [T3:{/}] 2. [T1:{P1,P3,P2}] [T2:{/}] [T3:{/}] . . . . n. [T1:{P2,P3}] [T2:{P1}] [T3:{/}] . . bei T=5 und P=20 beträgt die Anzahl der möglichen Lösungen 2^100 Meine Frage lautet nun: Wie gelange ich auf die Anzahl der möglichen Lösungen bzw. was ist dabei zu berücksichtigen. Ich danke Ihnen vielmals und entschuldige mich bereits im Voraus für die laienhafte Darstellung. Meine Ideen: Da hier der Sachverhalt "Ziehen ohne zurücklegen" greift kann man bereits für jede Periode P! Kombinationsmöglichkeiten festhalten. Für jede Periode macht dieses P! * T. Wie ich auf den Rest komme ist mir jedoch schleierhaft. Mir schweben noch das Pascalsche Dreieck und eine Binomialkoeffizient(hier müsste es sich dann ja um sowas wie einen Polynomialkoeffizienten handeln? gibt es sowas?) vor, aber Stochastik war nie so meine Stärke 
. |
||||||
| 02.06.2010, 23:32 | ObiWanKenobi | Auf diesen Beitrag antworten » | ||||
Sehr verwirrend! Ich habe gerade echt 2 Stunden gebraucht um den Knoten aus meinem Gehirn zu bekommen! Dabei ist es eigentlich ganz einfach! Stell Dir vor du ordnest die Projekte in einer bestimmten Reihenfolge und verteilst sie dann auf die Perioden. Für eine gegebene Reihenfolge der Projekte kannst du nun die Periode "Ziehen mit zurücklegen" Wende also die Formel für Ziehen mit Zurücklegen ohne Beachtung der Reihenfolge für n Projekte und k Perioden an. Diesen Vorgang kannst du für jede beliebige Anordnung der Projekte durchführen. Multipliziere also das Ergebnis mit der Anzahl der Möglichen Anordnungen (Permutationen) der n Projekte. Welche algemeine Formel erhälst du? Edit 01:45 Uhr: Habe gerade festgestellt, dass immer ncoh ein Fehler drin ist, aber ich komme gerade nicht dahinter, wo genau der Fehler liegt. Ich lasse es mal als Denkanstoß stehen. Ich befasse mich morgen nochmal damit! |
||||||
| 03.06.2010, 03:47 | Zellerli | Auf diesen Beitrag antworten » | ||||
Ich glaube damit geht es: Du hast schon den richtigen Weg vorgegeben, ObiWan: Man nimmt die 20 Projekte in einer Reihe (z.B. als Murmeln). Permutiert sie. Und jetzt schiebt man an beliebiger Stelle 4 Platten ein, die die 20 Murmeln in 5 Bereiche (Perioden) unterteilen. Damit müsste man alle möglichen Fälle abdecken. Die Platten sind quasi nummeriert. Es gibt 21 Plätze (jeweils einen vor jedem Murmelplatz und einen hinter der letzten Murmel), wo eine Platte hin kann. Das kann man so an Sieb-Rekursions-42-Arthur weitergeben und es mit nicht nummerierten Platten machen. Da muss man dann aber gut aufpassen, was man alles einbauen muss, damit es eine eindeutige Darstellung für jede Anordnung gibt. Offenbar habe ich da bisher was vergessen, denn ich komme nicht auf das Ergebnis. Kommt da wirklich raus? Das riecht so nach , wobei die möglichen Teilmengen einer 20er Menge sind. |
||||||
| 03.06.2010, 09:37 | Mystic | Auf diesen Beitrag antworten » | ||||
Edit: Sorry, hier stand zuerst Unsinn... 
Momentan scheint mir der Ansatz von Zellerli am vielversprechendsten... Man hat 24 Objekte, nämlich die 20 Projekte und die 4 Platten, die man auf 24! Arten anordnen kann.. Da aber die 4 Platten ununterscheidbar sind, muss diese Anzahl noch durch 4! dividiert werden... |
||||||
| 03.06.2010, 11:02 | wisili | Auf diesen Beitrag antworten » | ||||
| RE: Berechnung der Anzahl von Kombinationsmöglichkeiten von Projekten in Perioden «20 Projekte sollen innerhalb von 5 Perioden bearbeitet werden. Dabei ist es völlig egal in welcher Reihenfolge und Periode diese Bearbeitung erfolgt. Es sind hierbei keinerlei Restriktionen bzw. Nebenbedingungen zu beachten.» Wenn ein Projekt also auch während mehrerer Perioden bearbeitet werden kann, aber auch liegen gelassen werden kann, dann stellt sich nur die Frage, wird das Projekt i in der Periode j bearbeitet, ja oder nein. Das gibt dann 2^(20*5) Möglichkeiten. |
||||||
| 03.06.2010, 11:25 | Mystic | Auf diesen Beitrag antworten » | ||||
RE: Berechnung der Anzahl von Kombinationsmöglichkeiten von Projekten in Perioden
Ja, wird wohl so gemeint sein, denn nur so kommt man dann doch noch auf die ominöse Anzahl ... 
Schade um diese Aufgabe... Sie könnte so interessant sein, wenn z.B. ein Projekt nur in genau einer Periode bearbeitet werden könnte und/oder es auch auf die Reihenfolge innerhalb einer Periode nicht ankäme ... So wird halt leider eine Trivialität daraus...
|
||||||
| Anzeige | ||||||
|
|
||||||
| 03.06.2010, 11:50 | ObiWanKenobi | Auf diesen Beitrag antworten » | ||||
Ach das ist wirklich ärgerich. Ich hatte das so verstanden, dass ein Prokekt nur einmal bearbeitet werden kann, was meines Erachtens auch Sinn machen würde. Dann ist es nämlich nicht ganz so trivial. Weil ich wirklich viele Stunden daran gearbeitet habe, möchte ich meine Lösung für diese "Abwandlung" der Aufgabenstellung doch noch präsentieren. Anzahl der Perioden: k Anzahl der Projekte: n Formel: Weil mir irgendwie nicht die "zündende Idee" kam habe ich mir die Lösung durch "probieren und extrapolieren" "erschummelt"! Siehe Anhang. |
||||||
| 03.06.2010, 12:44 | Mystic | Auf diesen Beitrag antworten » | ||||
Ja, so hatte ich das auch verstanden... In Anlehnung an Zellerlis "Platten" hätte man also n+k-1 Objekte, nämlich n Projekte und die k-1 Platten zu ihrer Aufteilung auf die k Perioden, welche man auf insgesamt (n+k-1)! Arten anordnen kann, wobei man aber je (k-1)! von diesen Anordnungen nachträglich wegen der Nichtunterscheidbarkeit der k-1 Platten identifizieren muss und so auf deine Formel kommt... Noch interessanter wird das Ganze, wenn man nicht zwischen verschiedenen Anordnungen der Projekte innerhalb der Perioden unterscheidet... Da kommen dann Stirlingzahlen zweiter Art ins Spiel, d.h., man verläßt endgültig den Bereich der elementaren Kombinatorik... 
|
||||||
| 03.06.2010, 13:10 | Zellerli | Auf diesen Beitrag antworten » | ||||
Dann habe ich die Frage aber auch falsch verstanden... Denn ich dachte (siehe Einführungsbeispiel): Es macht etwas aus, ob man in Periode1 Pro1,Pro2,Pro3 oder eben Pro2,Pro3,Pro1 in diesen Reihenfolgen behandelt. |
||||||
| 03.06.2010, 13:25 | Mystic | Auf diesen Beitrag antworten » | ||||
Ja, sein Beispiel ist der Prototyp eines schlechten Beispiels, indem es nicht alle potenziell möglichen Fälle exemplarisch aufzeigt... Das hat uns alle genarrt (mit Aunahme von wisili)
Übrigens habe ich die folgende Passage
auch nicht verstanden, denn es sind ja 24 Plätze, wo eine Platte hin kann, die restlichen 20 sind dann durch Projekte besetzt... |
||||||
| 03.06.2010, 14:07 | frame | Auf diesen Beitrag antworten » | ||||
Vielen Dank! Zu allererst möchte ich Ihnen für Ihre ausführlichen Antworten danken. Anscheinend habe ich die Problemstellung zu kompliziert interpretiert und deshalb ein leicht falsches Beispiel angeführt. |
||||||
| 03.06.2010, 15:28 | frame | Auf diesen Beitrag antworten » | ||||
Noch einmal überprüft - und es scheint so wie von wisili zuerst beschrieben. (Zu meiner Verteidigung muss ich sagen, dass die Problemstellung nicht beschrieben wurde, sondern nur "20 Projekte und 5 Perioden" welche zu 2^100 verschiedenen Varianten führen). Das Beispiel hätte ich mir besser sparen sollen, da es sich um meine eigene Interpretation des Problems handelte. Ich dachte zuerst, dass es sich hier wirklich um jede erdenkliche Kombination und nicht um die Berechnung der Kombinationen der Teilmengen handelte. |
||||||
| 03.06.2010, 17:23 | Zellerli | Auf diesen Beitrag antworten » | ||||
Sag "du" zu uns (so wie wir dreister Weise zu dir) 
Ist so üblich im Board. Schön, dass das Problem geknackt ist. Der wisili hat sich halt nicht verwirren lassen
@Mystic: Mit deiner Methode (24 Plätze, 20 Kugeln, 4 Platten) ist es einfacher. Dazu haben meine müden Zellen aber nichtmehr die Kapazität gehabt um die Uhrzeit
Ich habe mir halt 20 Kugeln vorgestellt und 21 potentielle Plattenplätze, die aber auch doppelt, dreifach und vierfach besetzt sein können. 4 Platten in 1 heißt, dass alle Projekte in Periode 5 liegen. 2 Platten in 1, 3 in 21 heißt, dass alle Projekte in Periode 3 liegen. In jedem Fall sollte das ebenfalls eindeutig sein. Nur eben blöder zu berechnen. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
