Gewinnbringenste Kombination von Aktivitäten in Zeitraum ermitteln

[Guybrush Threepwood]

Angenommen ich habe ein Liste von Aktivtäten welche eine Dauer und einen Gewinn beinhalten. Jetzt möchte ich irgendwie ermitteln welche dieser Aktivitäten ich durchführen muss um den höchsten Gewinn zu erzielen wenn ich nur einen begrenzten Zeitraum zur Verfügung habe (also nicht genug Zeit um alle Aktivitäten durchzuführen).

Gibt es für sowas bestimmte Algorithemen mit denen man das lösen kann?

[geloescht_Newlukai]

Du könntest natürlich alle gültigen Kombinationen durchrechnen und das Minimum/Maximum suchen. Würde aber wahrscheinlich bei langen Listen ewig dauern.

Ich schätze, daß Problem dürfte NP-vollständig sein, weshalb Du am besten zufällige Kombinationen erstellst und davon das Minimum/Maximum nimmst. Wenn Du zusätzlich noch eine obere sowie untere Schranke erstellst, kannst Du auch eine ungefähre Fehlerwahrscheinlichkeit mit angeben.

[Lizzy]

Das Problem ist in der Tat NP-vollstaendig. In der theoretischen Informatik besser als "Rucksackproblem" bekannt.

Algorithmisch natuerlich durch "ausprobieren" loesbar, wie Newlukai schon angemerkt hat allerdings mit exponentiellem Aufwand, also nur fuer kleine Listen von Aktionen wirklich anwendbar.

Gibt verschiedene Verfahren (z.B. genetische/evolutionaere Algorithmen oder Simulated annealing), um auch bei grossen Listen gute Ergebnisse zu erzielen. Allerdings finden diese per Definition nicht unbedingt die optimale Loesung.

Gruesse,

Lizzy

[Guybrush Threepwood]

hmm Danke, das liefert mir zumindest schonmal einen Ansatz wonach ich suchen muss. Weil ausprobieren ist ja jetzt nicht so dolle

[Bubble]

Spontan könntest Du z.B. probieren:

1. "greedy".

2. Zufällige Kombinationen auswählen, die besten Ausgangskombinationen versuchen lokal weiter zu optimieren.

3. Genetischer Algorithmus.

Das Optimum wirst Du nur duch eine vollständige Suche sicher finden können.

her finden können.

[Lizzy]

Spontan könntest Du z.B. probieren:

1. "greedy".

Bravo! Was ein Vorschlag fuer ein Optimierungsproblem. *kopfschuettel*

[Bubble]

Bravo! Was ein Vorschlag fuer ein Optimierungsproblem. *kopfschuettel*

Zu dem Tonfall: Kommentare in einem derart aggressiv-dümmlichen Tonfall bitte zukünftig erst gar nicht abschicken. Danke.

Zum Problem: Es ist eine einfache Lösung, rasch umzusetzen, zwar selten eine wirklich gute, kann je nach Situation aber auch akzeptabel sein. Über die Art der zu erwartenden Daten ist uns bisher übrigens nichts bekannt.

[Lizzy]

Zu dem Tonfall: Kommentare in einem derart aggressiv-dümmlichen Tonfall bitte zukünftig erst gar nicht abschicken. Danke.

Entschuldigung fuer diesen Ausrutscher. Auf eine Besserung moechte ich mich jetzt allerdings nicht verbindlich festlegen.

Es gibt da uebrigens auch noch einen Unterschied zwischen Sarkasmus und einem "aggresiv-duemmlichen Tonfall". Aber damit muessen wir diesen Thread auch nicht kuenstlich belasten.

Zum Problem: Es ist eine einfache Lösung, rasch umzusetzen, zwar selten eine wirklich gute, kann je nach Situation aber auch akzeptabel sein. Über die Art der zu erwartenden Daten ist uns bisher übrigens nichts bekannt.

Es ging hier von Anfang an nicht um eine rasche Loesung. Einen greedy Algorithmus wie z.b. ASAP umzusetzen sollte fuer Guybrush kein Problem sein. Alleine der Fokus auf die Gewinnmaximierung schliesst jegliche greedy Algorithmen aus.

[Bubble]

Alleine der Fokus auf die Gewinnmaximierung schliesst jegliche greedy Algorithmen aus.

Es hängt von seinen Aktivitäten ab, je nach Situation kann er durchaus erstmal gierig vorgehen und akzeptable Resultate erzielen. Ob das bei ihm sinnvoll ist, ist spekulativ, wir wissen nicht, was er als typische Eingabedaten erwartet. Möglich ist es jedoch. Das globale Maximum findet er eh nur durch eine vollständige Suche.

[Crash2001]

Angenommen ich habe ein Liste von Aktivtäten welche eine Dauer und einen Gewinn beinhalten. Jetzt möchte ich irgendwie ermitteln welche dieser Aktivitäten ich durchführen muss um den höchsten Gewinn zu erzielen wenn ich nur einen begrenzten Zeitraum zur Verfügung habe (also nicht genug Zeit um alle Aktivitäten durchzuführen).[...]

Sind diese denn voneinander abhängig oder unabhängig?

Falls sie nicht voneinander abhängig sind, sollte das doch nicht kein Problem sein...

Oder ist das eher so was, dass man z.B. erst etwas herstellen muss, was in einem weiteren Schritt dann benötigt wird?

[Guybrush Threepwood]

Falls sie nicht voneinander abhängig sind, sollte das doch nicht kein Problem sein...

Achsooo das wußte ich natürlich nicht das das kein Problem ist, dann ist natürlich alles klar und die Frage hätte ich mir sparen können

@Topic

hmm also die Art der Daten sollte dafür doch relativ unwichtig sein. Wichtig ist doch nur die Anforderung an das Ergebnis bzw. das Verhältnis zwischen Performance und Genauigkeit. Also ob ich jetzt immer komplett alle Kombinationen durchprobiere, was lange dauert aber immer das optimale Ergebnis liefert oder ob ich es mit einem Algorithmus schneller mache aber dafür evtl. ein nicht ganz so optimales Ergebnis erziele.

Das muss ich aber dann mal schauen, die Stichpunkte von Lizzy haben mir (wie bereits gesagt) auf jeden Fall schonmal einen guten Ansatz gegeben.

[Pointerman]

Moinsen!

Ich denke für solche Probleme kann man den Simplex-Algorithmus gut verwenden.

Simplex-Verfahren - Wikipedia

Nicht von der komischen Grafik abschrecken lassen

Bei einer schnellen und oberflächlichen google-Suche hab ich dies Programm gefunden:

Simplex 2.2 Deutsch, Download im heise Software-Verzeichnis

Vielleicht hilft Dir das ja weiter.

Viel Erfolg wünsch ich noch!

[Crash2001]

@Guybrush Threepwood:

Eine sinnvolle Antwort auf meine Frage hast du aber nicht gegeben. Nur eine sarkastische Antwort ohne wirkliche Aussage.

Wenn die Aktivitäten nicht voneinander abhängig sind, kann man doch jede einmal für einen bestimmten Zeitraum durchlaufen lassen und schauen, welches in diesem Zeitraum den grössten Gewinn bringt. Dieser wird dann einfach in der zur Verfügung stehenden Zeit durchgehend ausgeführt und fertig.

Wenn sie voneinander abhängig sind, sieht das schon anders aus. Da gäbe es dann ja je nach Anzahl der Optionen zig verschiedene Möglichkeiten, die es sehr lange brauchen würde, alle durchzurechnen.

[Guybrush Threepwood]

Joa passend zur Aussage halt, außerdem kannst du jede Aktivität natürlich nur einmal durchführen.

@Pointerman

Danke werds mir mal anschauen.

[Bubble]

Eigentlich wollte ich ja nichts mehr hierzu schreiben...

Wenn Dauer und Gewinn für jede Aktivität vorab bekannt sind und die Aktivitäten nicht voneinander abhängig sind (so verstehe ich die Fragestellung zumindest), dann kann kann man sie in ein Verhältnis setzen und Gewinn/Zeit für jede Aktivität ausrechnen. Dann sortiert man danach (und nach der Dauer als zweites Kriterium) und beginnt mit mit dem Abarbeiten. Ist eine Aktivität für die verbleibende Zeit zu lang, dann geht man die Liste weiter durch, bis eine möglichst gewinnbringende Aktivität gefunden ist, die noch in die Zeitlücke passt. Dies wäre die einfache "greedy" Variante.

Wenn die Dauer aller Aktivitäten im Verhältnis zur gesamten verfügbaren Zeit kurz ist und die Unterschiede im Gewinn/Aktivität für die Aktivitäten keine hohen Sprünge machen, dann führt dies zu einem vermutlich erst einmal brauchbaren Ergebnis.

Wenn dies nicht gegeben ist, oder man höhere Ansprüche an das Ergebnis stellt, muss man zu einem aufwendigeren Verfahren greifen. Hier kann man aber schnell viel Zeit investieren, sowohl beim Umsetzen, als auch später in der für die Ausführung erforderlichen Rechenzeit.

[Guybrush Threepwood]

hmm ja wäre sicherlich eine einfache Möglichkeit das umzusetzten. Ich glaub das müßte man dann einfach ausprobieren was sich da rentiert.

Ich hab gestern mal einen Algorithmus anhand des Rucksackproblems (Nach)programmiert welcher mit wenigen Elementen gute Ergebnisse erziehlt. Bei ner halben Millionen oder mehr Elementen (glaub zwar nicht das es auch nur annähernd so viele werden) wirds aber je nach dem schon schwer bzw. dauernd extrem lange. Außerdem ist es dann auch irgendwie schwer zu testen ob das Ergebnis so stimmt

[Der Kleine]

Wenn Dauer und Gewinn für jede Aktivität vorab bekannt sind und die Aktivitäten nicht voneinander abhängig sind (so verstehe ich die Fragestellung zumindest), dann kann kann man sie in ein Verhältnis setzen und Gewinn/Zeit für jede Aktivität ausrechnen. Dann sortiert man danach (und nach der Dauer als zweites Kriterium) und beginnt mit mit dem Abarbeiten. Ist eine Aktivität für die verbleibende Zeit zu lang, dann geht man die Liste weiter durch, bis eine möglichst gewinnbringende Aktivität gefunden ist, die noch in die Zeitlücke passt. Dies wäre die einfache "greedy" Variante.

Natürlich ins Verhältnis setzen (Rentabilität), die besten Resultate so lange auswählen, bis die längste noch verbleibene Zeitdauer gerade noch realisierbar ist.

Dann den restlichen Zeitbedarf optimiert darstellen (auch durch alle möglichen Kombinationen), bzw. unrentable Objekte einfach eleminieren und somit weiter die verbleibenden Möglichkeiten reduzieren, bis ein eindeutig bgerechendares Ergebnis bleibt.

PS: Aus kaufmännischer Sicht verstehe ich das Problem nicht so richtig. (Kaufmännische Investitionsrechnung beschäftigt sich im Detail damit, nur das Geld und Gewinne auf ein Budget aufgeteilt werden müssen. Dazu braucht man nur nen Taschenrechner, keinen Computer)

Es ist natürlich davon abhängig, ob die Werte (Zeitdauer) alle ungefähr gleich lang sind, oder ob extrem lange Ausrutscher dabei sein können.

[Bubble]

Die "greedy" Variante kann bei geeigneten Ausgangssituationen durchaus gute Ergebnisse erzielen. Ihr Problem liegt aber darin, dass eine nicht nutzbare Restzeit übrig bleiben kann, in der keine weitere Aufgaben (oder nur wenig lohnende) abgearbeitet werden können. Es könnte nämlich durchaus sein, dass es weniger gut ist eine Aufgabe mit hohem Gewinn/Zeit Quotienten abzuarbeiten, bei der Zeit ungenutzt bleibt bzw. nur mit deutlich weniger lohnenden Aufgaben gefüllt werden kann, als z.B. zwei (oder mehrere) Aufgaben mit schlechterem Quotenten, die die verfügbare Zeit jedoch so viel besser ausnutzen, dass sich das Gesamtergebnis verbessert.

Aus kaufmännischer Sicht verstehe ich das Problem nicht so richtig.

Es ist kein rein kaufmännisches Problem. Ähnliche Fragestellungen treten z.B. auch dann auf, wenn es darum geht aus Papierrollen, mit möglichst wenig Verschnitt, bestimmte kleinere Papierformate zu gewinnen.

[Der Kleine]

Es ist kein rein kaufmännisches Problem. Ähnliche Fragestellungen treten z.B. auch dann auf, wenn es darum geht aus Papierrollen, mit möglichst wenig Verschnitt, bestimmte kleinere Papierformate zu gewinnen.

Das es ein rein kaufmännisches Problem ist, habe ich nicht gesagt. Mann kann es auf kaufmännische Fragestellungen übertragen, die dann Lösungsansätze bieten können.

PS: Papierrollen und Verschnitt ist aus kaufmännischer Sicht gesehen wiederum nur eine andere Variante der gleichen Fragestellung.

Eine vollständige Fallunterscheidung bzw. die Reduktion der Fragestellung durch logische Algorithmen kann durch eine Transformation auf die kaufmännische Sichtweise im vorherein auf eine mittels IT berechenbare Lösungsgröße transformiert werden.

Dementsprechend verstehe ich im Detail immer noch nicht das große (IT-)Problem aus kaufmännischer Sicht. Es sei denn, man hat es mit einer extremen Verteilung (und somit kaum mit realistischen Problemen) zu tun, also wenn die Zeitspannen doch extrem voneinander abweichen und nicht um einen Mittelwert (entsprechend irgendeiner statistischen Verteilung) schwankend sind.

[Bubble]

Mann kann es auf kaufmännische Fragestellungen übertragen, die dann Lösungsansätze bieten können.

Oder man überträgt kaufmännische Probleme auf andere, analoge ;-)

PS: Papierrollen und Verschnitt ist aus kaufmännischer Sicht gesehen wiederum nur eine andere Variante der gleichen Fragestellung.

Genau, deswegen brachte ich das Beispiel.

Eine vollständige Fallunterscheidung bzw. die Reduktion der Fragestellung durch logische Algorithmen kann durch eine Transformation auf die kaufmännische Sichtweise im vorherein auf eine mittels IT berechenbare Lösungsgröße transformiert werden.

??? Ich verstehe nicht ganz, was Du sagen willst. Die Übertragung auf kaufmännische Probleme führt jedenfalls zu keinem besseren Lösungsansatz, allenfalls auf eine analoge Problemstellung, die z.B. Dir vertrauter erscheint.

Dementsprechend verstehe ich im Detail immer noch nicht das große (IT-)Problem aus kaufmännischer Sicht.

Das theoretische Problem besteht darin, die optimale Lösung zu finden. Dies ist oft mit sehr hohem Aufwand verbunden und daher in der Praxis oft unrealistisch. Darum versucht man eine nährungsweise Lösung zu finden, eventuell ein lokales Optimum. Dies kann man bei dem Problem, über das wir hier sprachen, z.B. mit dem von mir oben beschriebenen und recht einfachen Verfahren tun. Das Verfahren hat jedoch prinzipbedingte Probleme und findet eben nicht grundsätzlich die bestmögliche Lösung, es kann hingegen sogar eine nur sehr schlechte Lösung vorschlagen. Es ist aber einfach umzusetzen und vergleichsweise schnell in der Ausführung (das Sortieren verursacht den größten Aufwand).

Es sei denn, man hat es mit einer extremen Verteilung (und somit kaum mit realistischen Problemen)

So extrem muss das gar nicht sein, man kann recht einfach ein Beispiel konstruieren, wo die einfache Herangehensweise nicht zur optimalen Lösung führt (ich mache gleich ein solches Beispiel). Trotzdem: Das Verfahren wird dadurch nicht automatisch unbrauchbar, man muss sich aber über die Grenzen im Klaren sein.

Nun zu einem Beispiel, wo es nicht klappt:

3 Aufträge (a, b, c), die verfügbare Zeitspanne besteht aus 40 Zeiteinheiten:

a) Gewinn: 30 / Zeitdauer: 24 / Verhältnis: 1.25

Gewinn: 20 / Zeitdauer: 20 / Verhältnis: 1

c) Gewinn: 20 / Zeitdauer: 20 / Verhältnis: 1

Mögliche Lösungen: Entwerder nur a) ausführen und 30 erhalten, oder und c) ausführen und 40 erhalten.

Das gierige Verfahren würde zuerst a) ausführen, da es so zuerst am meisten pro Zeiteinheit erreicht, danach aber feststellen müssen, dass weder für noch für c) genügend Zeit bleibt und aufhören.

Es wäre besser gewesen a) nicht auszuführen, sondern sich auf und c) zu beschränken.

Sähe die Ausgangslage anders aus, z.B. mit sehr vielen Aufträgen, die gemessen an der verfügbaren Zeit kurz sind (also beispielsweise 100 Aufträge mit jeweils 1-4 Zeiteinheiten Dauer und einem recht ausgeglichen Verhältnis aus Zeitbedarf und Gewinn), würde zwar am Ende vermutlich auch eine eher ungünstige Wahl getroffen werden, aber im Bezug auf den Gesamtgewinn würde es nicht mehr so stark ins Gewicht fallen.

Würde die Aufgabe a) aus dem Beispiel einen Gewinn von mehr als 40 abwerfen, dann wäre die Lösung des gierigen Verfahrens hingegen richtig, sogar optimal.

Es hängt also stark von den Eingabedaten ab wie gut die Lösung ist. Leider, und dies kann ein Problem sein, ist es nicht möglich festzustellen, wie gut oder schlecht die gefundene Lösung tatsächlich ist. Wenn die Eingabedaten aber gewisse Anforderungen immer einhalten, man keine optimale Lösung benötigt und man sich der Nachteile dieser Lösungsstrategie bewusst ist, dann kann das Verfahren auch eingesetzt werden.

Natürlich kann man das Verfahren noch beliebig verfeinern, meinetwegen die ersten 90% der Zeit "greedy" verbringen und danach mehrere Varianten ausprobieren. Man kann auch gleich völlig andere Herangehensweisen anwenden. Ob sich der Aufwand lohnt und wie man in der Praxis dann tatsächlich vorgeht, muss man abwägen.

Ich hoffe, die Erklärungen sind nachvollziehbar und haben Dir erstmal geholfen.

[Der Kleine]

??? Ich verstehe nicht ganz, was Du sagen willst. Die Übertragung auf kaufmännische Probleme führt jedenfalls zu keinem besseren Lösungsansatz, allenfalls auf eine analoge Problemstellung, die z.B. Dir vertrauter erscheint.

Nein, was ich sagen will, ist, dass viele probleme im kaufmännischen Bereichen bereits durchleuchtet und optimiert sind, die in der Mathematik so noch nicht gesehen wurden.

Nun zu einem Beispiel, wo es nicht klappt:

Dein Problem ist bereits ein reduziertes Problem, bei welchem um die restlichen knappen Ressourcen revalisiert wird.

Aber ich erkenne meinen Denkfehler (irgendwo): Verdopple deine Angebote und deine Zeitdauer. Dann wäre das Problem nicht mehr reduziert (auf den kläglichen Rest).

Der kaufmännische Ansatz müsste in die Richtung gehen, das Gewinnverhältnis auf die Zeitdauer zu beziehen und dabei den besten Ergebnisse Priorität einzuräumen.

(Aber ich muss nochmals genau an diesem Ansatz grübeln und in Ruhe rechnen, damit ich auch Begründungen liefern kann).