Kombinatorik- / Optimierungs-Problem

Das Problem interessiert mich…

Wenn ich das richtig verstehe, sind bei einer Variable 3 Attribute relevant, die sind mit der Tabelle mit "WAHR" tituliert.

Ich verstehe nur nicht was das Ziel sein soll. Kannst du ein Beispiel-Ziel für ein überschaubares Beispiel geben?

Ich habe das Gefühl, dass das Ganze im Prinzip mit Methoden aus der Digitaltechnik lösbar sein sollte.

verstehe das Problem nicht richtig glaube ich
meinst du mit optimieren, dass die Variablen mit den gleichen attributen untereinander stehen etc? oder wie genau stellt du dir eine optimierung vor? was meinst du mit übererfüllt? kann eine variable mehr als 3 attribute haben?

Moin,

wie ichs verstanden habe:
in deinem Bild müssen in jede Zeile 3 "Wahrs".
In jeder Spalte soll nun die Anzahl an "Wahrs" dem gesuchten Zielwert entsprechen.
Ziel ist es nun, dass Ganze mit so wenig Zeilen wie möglich hinzukriegen.

Passt das?
Wenn ja, hätte man schon mal einfache Grenzen für die Anzahl an benötigten Variablen.
Anzahl an Variablen >= Summe der Zielwerte /3
Anzahl an Variablen >= größter Zielwert

Dein Beispiel im Bild kriegt man mit 17 Variablen hin. Ob die Grenzen immer erfüllbar sind, weiß ich grad nicht. (wohl eher nicht).

Guten Morgen

ja, waren evtl etwas wenig Angaben, aber ABKaliasHORST hat es ganz gut getroffen!

Es geht darum mit wenig möglichen Zeilen die geforderten Werte in der Spalte zu erreichen - ist denke ich einfacher ausgedrückt als wenn man mit Variablen und Attributen hantiert. Hier mal ein Beispiel mit nur 4 Attributen. In jeder Zeile sind dann 1 oder 2 Attribute vorhanden.
Im zweiten Step habe ich manuell soweit die Zeilen gelöscht, die nur einen WAHR-Wert hatten und bin dann bei Attribut 3 an die untere Grenze gestoßen. Im letzten Step habe ich dann weiter gelöscht um auf das minimum zu kommen (wobei dann bei Attribut 1 eines mehr erfüllt wurde als benötigt).

Bei wenigen Attributen ist das bestimmt noch durch zuordnen machbar, aber desto mehr Variablen und Attribute man hat, desto ungenauer wird der manuelle Ansatz.

Ich habe für mich die Variablen soweit zusammen gestrichen, das nur noch Variablen mit 3 WAHR-Attributen enthalten sind, die mit 1 oder 2 Attributen habe ich raus gelassen, da ich min 2x so viele Variablen mit den benötigten Attributen habe als ich benötige (teilweise sogar mehr als das 6x)

Danke schon mal fürs mitdenken

AK

Ich finde das auch interessant. Könntest du eventuell ein paar Worten schreib, wofür du das brauchst bzw. worum es dabei geht?

Sind die Variablen vorgegeben oder kannst du die selber erstellen? Wenn du alle möglichen Variablenkombinationen hast, kannst du die Zielvorgaben ja immer exakt erfüllen.

Suchst du die bestmögliche Lösung oder reicht es dir, wenn es wenig genug Variablen sind, auch wenn es eventuell noch bessere Lösungen geben könnte?

Hi,

in diesem konkreten Beispiel geht es um ein Spiel Man benötigt verschiedene Charaktere mit diversen Elemente auf einem bestimmten Level um weiter zu kommen (denke da habe ich mit manuelles herum schieben schon eine sehr gute Lösung).

Aber ursprünglich kam ich vor ein paar Wochen mit der Problemstellung zum ersten mal in Berührung. Ich war von der Arbeit aus auf einer SixSigma-Schulung. Hier ging es zum einen um Einflussfaktoren zu einem Problem (da kann man das von oben auch ziemlich gut verwenden um die Komplexität des Problems darzulegen) und zum anderen um die Zusammenstellung des Teams.
Dieser zweite Punkt ist exakt nun auch mein Beispiel von oben und interessiert mich ....
Als Projektleiter hat man einen Mitarbeiterpool zur Verfügung, bei dem jeder seine speziellen Fähigkeiten / Erfahrungen mitbringt. Um hier dann möglichst Ressourcensparend das Team zusammen zu stellend wäre die Matrix von oben der Schlüssel zum Erfolg (in der Schulung war das recht vereinfacht dargestellt >> ein Logistiker, ein Mechaniker usw. dazu gab es halt dann noch ein oder zwei weitere Faktoren (Fremdsprache, Erfahrung etc) also im Prinzip war das Team mit 4 - 6 Personen zu füllen und da es meist sehr spezielle Fähigkeiten gab auch die Auswahl sehr übersichtlich).
Aber wenn ich mir das nun für ein komplexes Projekt vorstelle, bei dem im Mitarbeiterpool 30 - 50 Personen zur Verfügung stehen und ich ein Team aus 5 - 10 Personen zusammenstellen kann, bei dem sich Fähigkeiten (oder Verfügbarkeiten -> ist der Mitarbeiter überhaupt bereit x Wochen zb im Ausland zu Arbeiten) auch überlappen könnten, dann wäre eine "optimale" Teamzusammenstellung so ohne mathematische Hilfe eben nicht mehr möglich.

Also
Variablen = Mitarbeiter
Attribute = Fähigkeiten / Verfügbarkeit (frei definierbar)
Zielwerte = wie viele Fähigkeiten benötige ich für die Aufgabe

Denke eine Näherung wäre für den Anfang nicht schlecht, aber es müsste doch auch eine optimale Lösung für so ein Problem geben oder? Als Endergebnis stelle ich mir eben eine Matrix mit n-Zeilen und x-Spalten vor mit der ich dann die Optimale Belegung des Teams zusammen stellen könnte (ähnlich einer C&E-Matrix).

AK

Die optimale Lösung kannst du so finden:

1. die minimal benötigte Anzahl an Variablen bestimmen (hier: Summe der angeforderten Attribute / Attribute pro Mitarbeiter.

2. Prüfen, ob eine Kombination mit der Zahl an MA existiert, die die Voraussetzungen erfüllt
Wenn keine Lösung existiert, dann das ganze für einen Mitarbeiter mehr.

Nachteil ist, dass du schlimmstenfalls alle Kombinationen durchgehst.

Hi,

Danke für den Input - das muss ich mir mal ansehen wie ich das ggf in Excel (mit / ohne VBA) umsetzen könnte. Ich bin gerade dabei das mit dem Solver von Excel zu bearbeiten, aber nicht sicher ob es funktioniert. Es läuft nun seit gut fünf Minuten (10 Zeilen auf 4 Spalten) - naja ich lass den mal nun so weiter laufen und geh noch was anderes Arbeiten

AK

Ein Mathematiker würde dein Problem wahrscheinlich folgendermaßen beschreiben.
Definiere einen Vektor x mit Komponenten xi e {0,1}, i=1,2,3,…,n. Dabei ist n die Anzahl der Mitarbeiter. Der Vektor x beschreibt die Mitarbeiter, die du für deinen Task aussuchst, wenn also die i-te Komponente eine 1 ist, dann wird der Mitarbeiter ausgewählt, wenn die i-te Komponente eine 0 ist, dann eben nicht. Zudem definiere eine Funktion f(x)=s, wobei s ein Vektor ist, dessen Komponenten sj e N, j=1,2,3,…,m die Spaltensummen für einen bestimmten Vektor x wiedergeben. Dein Optimierungsproblem ist jetzt eher ein Mehrzieloptimierungsproblem, da du möglichst wenig Mitarbeiter auswählen möchtest (norm(x)), aber gleichzeitig dein Zielvektor s* erreichen willst (norm(s*-s)). Suche also einen Vektor x der J=norm(x)+norm(s*-s) minimiert.
Beispiel (bezieht sich auf die ersten 4 Spalten und Zeilen deines Beispiels):
Die Anzahl der Mitarbeiter ist n=4 (A,B,C,D) und die Anzahl der Attribute ist m=4. Dein Zielvektor ist s* mit Komponenten s1*=3, s2*=3, s3*=3, s4*=4. Der Vektor x hat ebenfalls die Dimension 4 mit Komponenten x1-x4 und gibt an, ob du einen Mitarbeiter mitnimmst oder nicht (0-nein und 1-ja). Die Funktion f(x)=s gibt die Spaltensummen wieder (Summe der Attribute) und sieht folgendermaßen aus:
S1=x1+x4
S2=x2+x3
S3=x1+x3
S4=x2+x3
Um das Problem zu lösen, kannst du jetzt alle Kombinationen von x ausprobieren (also [0,0,0,1],[0,0,1,0],…) und das x speichern, das den kleinsten Wert für J generiert.

P.S. Schau dir mal das Salesman Problem an (geht in eine ähnliche Richtung), https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Danke für den Input!
Das Problem des Handlungsreisenden kenne ich (also mehr oder weniger), hab schon befürchtet das es auf so etwas ähnliches hinaus läuft. Die Mathematik die du anbringst muss ich mich erst mal einarbeiten (ist alles schon etwas her bei mir ;)).
Ich wollte es mit dem Excel-Solver lösen:

Geändert werden die Zahlen unter "Auswahl" wenn eine 0, dann ist der Mitarbeiter überall mit 0 hinterlegt. Dazu wird die Gesamtprüfung als Bedingung genommen (hier wird geprüft ob in den einzelnen Spalten immer die das Ziel erreicht wurde --> Möglichkeiten >= Ziel). Ziel des Solvers ist es die Anzahl der Variablen zu minimieren. (oben im Bild ist mein manueller Versuch)

Entweder habe ich da irgendwie noch einen Denkfehler oder es läuft wirklich so ewig lange....

Wähl mal den EA-Solver als Lösungsmethode, die Anderen werden dein Problem nicht lösen können.

Hab ich, ist nur im Bild noch nicht umgestellt. Hab auch meine Nebendefinitionen umgestellt, denke da lag auch der Fehler das er zu keinem Ergebnis kam.
Nun läuft es noch mal durch - Ergebnis werde ich dann noch Posten

läuft und ist auch entsprechend schnell - muss nur noch sehen wie ich das noch mit der Automatisierung mache - kommen ja doch leicht unterschiedliche Ergebnisse raus (also andere Variablen werden gewählt)

Falls Interesse besteht stelle ich die Datei online - Danke für den Input!

AK

Das ist ein klassischer Anwendungsfall für Integer Linear Programming. Ist auf jedenfall NP-Vollständig. Es ähnelt eher dem Knapsack Problem als dem Salesman Problem. Dafür sollte es eigentlich gute Algorithmen geben. Ich weiß nicht, ob das noch akutuell ist. Ich könnte auf jeden Fall noch mehr Input geben, wenn das gewünscht ist.

Achja: Falls die Problemgröße sich im Rahmen hält, sollte das eigentlich sich leicht rekursiv lösen lassen. Das sind so 10 Zeilen in Python...

Hi,

danke schon mal für den Input. Gerade einen Bericht zum Rucksackproblem gelesen - sehr interessant, aber meine Zeit wird es aktuell nicht zulassen mich da wirklich mal rein zu arbeiten In Python bin ich auch recht blank (VBA in Kombi mit Excel, da fühle ich mich wohl ), aber Danke für dein Angebot!

Mein eigentliches Problem habe ich jetzt mit Hilfe des Solvers sehr gut gelöst bekommen. Dazu bin ich gerade noch etwas am basteln um eine flexible Tabelle zu bekommen mit der ich dann bzw auch andere ihre Parameter eingeben und dann die Lösung per Knopfdruck bekommen, ohne sich mit dem Solver und Bedingungen zu beschäftigen.

AK