Excel "Rätsel" - Optimale Teilnehmerzahl bei vorgegebenen Timeslots

wuerde das auch aehnlich angehen, summen der zeilen und aber auch summen der spalten machen und bei den kleinen mit wenig auswahl anfangen

ansonsten, da es noch ueberschaubar ist, kannste ansich auch nen kleines VBA schreiben was einfach alle permutationen durchgeht?

klingt nach einem fall für den excel solver (also hier dauerts mit dem solver vermutlich länger, aber so generell für optimierungsprobleme dieser art)

du hast ne zielfunktion: möglichst viele timeslots gefüllt und
eine menge nebenbedingungen (max. 1 teilnehmer pro slot und 1 teilnehmer soll max. 1mal teilnehmen, nehme ich an)

https://support.office.com/de-de/article/Definieren-und-L%C3%B6sen-eines-Problems-mit-dem-Solver-bdd10118-4133-4d09-b5fa-8a2841a33b10

Das mit dem Solver ist eine gute Idee, allerdings verändere ich ja keine variablenzellen?! Wie mach ich das denn am besten?

Kannst du das Problem noch mal näher erläutern? Was heißt: sodass am Ende möglichst viele teilnehmen?

edit: Achso, zu jedem Slot darf maximal 1 Teilnehmer? Dann sollte das das Heiratsproblem sein. Dafür könnte es schon fertige Matching-Algorithmen auch für VBA geben.

Sieh mal hier nach:

http://www.excel-easy.com/examples/assignment-problem.html

Hier hättest du sogar noch die Möglichkeit, die Leute ihre Präferenzen angeben zu lassen.

ich habe damit auch ewig nicht mehr gearbeitet (und damals auch nicht tief)

wie sind deine nebenbedingungen? nehmen teilnehmer max. 1 mal teil und max. 1 teilnehmer pro slot? falls sie anders sind, lass die entsprechenden bedingungen, die unten aufgeführt sind, weg

https://www.uni-marburg.de/fb02/statistik/studium/vorl/dynopt/excelsolver.pdf
ich würde dann quasi die ganze tabelle nochmal nebendran machen (leer), die zielbedingung in einer weiteren zelle definieren timeslot1 + timeslot 2 + ... -> max
(es bietet sich dafür an, eine spalte hinzuzufügen, die die zeilensummen enthält und am ende die summe der zeilensummen als zielzelle)
achtung: die folgenden bedingungen auf deine neue tabelle anpassen. die werte sind hier nie E3 bis L15, sondern entsprechend ab spalte M oder wo du auch immer mit der neuen tabelle beginnst. ich habe diese nur aus illustrationszwecken gewählt, damit du siehst, worauf sich die bedingungen genau beziehen.

nebenbedingungen sind dann
sum(E3:L3)<=1, sum(E4:L4)<=1 ... ,
sum(E3:E15)<=1, sum(F3:F15)<=1 ...

diese nebenbedingungen dürften soweit klar sein. sie garantieren, dass jeder teilnehmer max. 1 mal drankommt und jeder timeslot max. 1 mal genutzt wird

dann müssen wir ausschließen, dass jemand nicht kann.
ich bin nicht sicher, ob man direkt die veränderbaren zellbereiche auswählen kann (falls ja, wären es alle in denen bei dir in der ausgangstabelle eine 1 steht)

falls das nicht geht, als nebenbedingung alle zellen, in denen eine 0 steht als 0 definieren
F3+G3+H3+I3+J3+E4+G4+... =0

jetzt brauchen wir noch die nichtnegativitätsbedingung E3:L15>=0 und
die ganzzahligkeitsbedingung

dann sollten wir es "solven" können.

davon ab hat lego recht und es wäre besser die aufgabenstellung komplett (mit allen nebenbedingungen) zu posten;)

Danke für eure Ausführungen. Irgendwie komm ich aber nicht weiter.

nebenbedingungen sind dann
sum(E3:L3)<=1, sum(E4:L4)<=1 ... ,
sum(E3:E15)<=1, sum(F3:F15)<=1 ...

hab ich kapiert. Auch das Beispiel von Lego hab ich verstanden, aber keine Ahnung wie ich das jetzt auf meine Problemstellung übertragen kann. Mir fehlen hier doch komplett die "Veränderbaren Zellen", oder?

Wenn du das von mir gepostete nimmst, dann müsstest du eigentlich nur 0 und 1 aus deiner Tabelle tauschen und einsetzen, da er ja minimert. Bin mir nicht sicher, was du mit Veränderbaren Zellen meinst.

Wie meinst du das? Die 1 kann ich ja nicht durch die 0 ersetzen, schließlich sind das ja die Terminvorschläge der Personen. Diese sind nicht zu verschieben. So weit bin ich, allerdings hab ich das Gefühl, dass das nicht zielführend ist.

Original von MyLady17
Danke für eure Ausführungen. Irgendwie komm ich aber nicht weiter.

nebenbedingungen sind dann
sum(E3:L3)<=1, sum(E4:L4)<=1 ... ,
sum(E3:E15)<=1, sum(F3:F15)<=1 ...

hab ich kapiert. Auch das Beispiel von Lego hab ich verstanden, aber keine Ahnung wie ich das jetzt auf meine Problemstellung übertragen kann. Mir fehlen hier doch komplett die "Veränderbaren Zellen", oder?

Original von tranceactor
ich würde dann quasi die ganze tabelle nochmal nebendran machen (leer), die zielbedingung in einer weiteren zelle definieren timeslot1 + timeslot 2 + ... -> max
(es bietet sich dafür an, eine spalte hinzuzufügen, die die zeilensummen enthält und am ende die summe der zeilensummen als zielzelle)
achtung: die folgenden bedingungen auf deine neue tabelle anpassen. die werte sind hier nie E3 bis L15, sondern entsprechend ab spalte M oder wo du auch immer mit der neuen tabelle beginnst. ich habe diese nur aus illustrationszwecken gewählt, damit du siehst, worauf sich die bedingungen genau beziehen.

das hast du vermutlich überlesen.

die veränderbaren zellen sind dann alle zellen innerhalb der neuen (leeren) tabelle (v und vreal). tatsächlich sind aber später nur vreal veränderbar, weil wir alle v-zellen auf 0 definieren müssen, da der kandidat im entsprechenden timeslot ja keine zeit hat.

disclaimer: da nicht v und vreal reinschreiben^^ dient nur zur illustration genauso wie "zielfeld"

Mit VBA scheints ja auch zu gehen, aber damit kenn ich micht nicht aus. Ich weiß nicht, wie bekannt AMPL ist, aber ich musste das grade für die Uni lernen.
Habs mal eben damit modelliert, weils recht simpel ist. Weiß aber nicht, ob dir das hilft, wenn du das mit VBA und Excel machen musst und keinen Zugriff auf andere Programmiersprachen hast.

Muss man halt nur noch die Verfügbarkeiten eingeben, was auch bei einer viel größeren Teilnehmerzahl kein Problem wäre.

Original von MyLady17
Wie meinst du das? Die 1 kann ich ja nicht durch die 0 ersetzen, schließlich sind das ja die Terminvorschläge der Personen. Diese sind nicht zu verschieben. So weit bin ich, allerdings hab ich das Gefühl, dass das nicht zielführend ist.

Ich meinte dass dass du 0 und 1 tauschen müsstest wenn du minimerst. Also einfach deine Tabelle nehmen und ab jetzt soll 0: hat Zeit und 1: hat nicht Zeit heißen.

bin entweder zu dumm oder stehe auf dem Schlauch, aber das was ihr mir sagt, ist einfach nicht umsetzbar?!

sorry @trunxx, klingt zwar schlüssig, aber von anderen Programmiersprachen hab ich so gar keine Ahnung

ich habs mal fertig gemacht für ein 3x3-bsp. musst dann nur noch auf das größere anwenden. da ich kein excel habe, habe ich es mit dem solver in open office gemacht. läuft problemlos.

die erste bedingung garatntiert, dass der solver nur 0 oder 1 verwendet in den veränderbaren zellen.
die zweite, dass die spaltensummen nie größer 1 sind, d.h. ein teilnehmer wird max. ein mal vergeben.
die dritte, dass die werte in den veränderbaren zellen nie größer sind als die zugehörigen in der ausgangstabelle, also wenn ein teilnehmer nicht kann zu dem zeitpunkt, dieser zeitpunkt nicht an den teilnehmer vergeben wird.
die vierte, dass die zeilensummen nie größer 1 sind, d.h. ein slot wird max. ein mal vergeben.

die dritte ist mir obv. erst spät eingefallen, vereinfacht aber vieles ungemein

ergänzend, da man es auf dem screenshot nicht erkennt:
J7=Summe(J4:J6)
J4=Summe(G4:I4) (J5,J6 analog)
G7=Summe(G4:G6) (H7,I7 analog)

Vielen vielen Dank

Mit der dritten Bedingung läuft´s. Auf die bin ich einfach nicht gekommen

np

bin ja zunächst auch nicht darauf gekommen und wollte jede einzelne zelle als =0 bzw. <=1 definieren.
das würde übrigens auch gehen. man müsste dann bspw. in zelle G2 (oder wo auch immer) in meinem beispiel schreiben
G2=H4+I4+G5+I5+G6
(das summiert alle zellen auf, die 0 ausgeben sollen in der lösung, also die nicht 1 werden dürfen, weil der teilnehmer im entsprechenden slot keine zeit hat)

dann könnte man als dritte bedingung auch einfach G2=0 angeben und funktioniert genauso.

(erklärung: wenn die summe G2 null ist, dann ist auch jeder summand null, da sämtliche summanden wegen der binärbedingung nur 0 oder 1 sein können, aber wenn mind. einer 1 wäre, die summe nicht mehr null sein könnte. es wird also verhindert, dass ein teilnehmer in einen timeslot eingeteilt wird, in dem er nicht kann)

das ist etwas umständlicher gedacht, aber der gedanke gewisse zellen sicher "zu nullen" hilft dir evtl. für zukünftige probleme und funktioniert, wenn man die ideallösung (hier G4:I6<=B4:D6) nicht erkennt.

edit: gute ergänzung von frischi. diesen post deshalb bitte nur als alternativen denkansatz sehen, der einem evtl. hilft, falls man mal wieder auf dem schlauch steht

der vorteil an der formulierung der 3. NB von tranceactor ist, dass man die Ausgangstabelle einfach ändern kann, und so die ganze Klasse von Problemen lösen kann, bei der anderen Methode müsste man für jedes Problem die Formeln ändern.