Optimierungsproblem

wenn der nutzen mit konusum einer weiteren einheit nicht abnimmt, dann einfach nutzen/preis und für das produkt mit dem besten verhältnis das ganze geld verpulvern.
aber so einfach wirds wohl nicht sein

Ach so, ich darf jedes Gut nur maximal einmal kaufen.
Füg ich oben nochmal mit ein

excel solver könnte dir helfen zum einstieg

schau z.b. mal hier rein

bis auf die Einschränkung, das genau 10 Güter verlangt werden ist das ja ein sog. Rucksackproblem. Das ist NP_Schwer, also nicht in polynomieller Zeit lösbar. Vllt. gibt es dazu im Internet Algorithmen für Näherungslösungen

Mit dem Solver hab ich auch schon rumgespielt. Bekomme aber immer Fehlermeldungen, dass entweder die Linearitätsbedingung nicht erfüllt ist oder dass keine Lösung gefunden wurde, die alle Bedingungen erfüllt, obwohl das finden einer gültigen Lösung ja eigentlich trivial sein sollte. Zudem ist der Solver auch auf 200 Güter beschränkt, darüber hinaus bräuchte ich also eh was anderes.

finde das problem total interessant, für was brauchst du das, studium?

welche rechenschritte lässt du das programm ausführen um zu einer lösung zu kommen?

nach welchem thema muss ich googeln um literatur zu finden wo es um die problematik geht?

das ist das knapsack problem, und das ist np-schwer. insofern, schau, was du bei wiki rausziehen kannst, ansonsten sind meine vorschläge:
- code einen greedy algorithmus
- benutze einen genetischen algorithmus a la "nsga 2"
- benutze "simulated annealing"
- benutze "particle swarms"
- formuliere es als integer linear problem und benutze einen solver wie "lpsolve"

ich persönlich würde wohl einen greedy algorithmus coden, und dann lpsolve benutzen. bei genetischen algorithmen oder particle swarms ist das komplizierte vernünftige regeln zu formulieren, wie die lösungen "mutieren".

aja, "nsga 2" und "lpsolve" sind freeware, aber du brauchst dann halt noch nen c/c++-compiler. soweit ich weiß gibt s in python auch genetische algorithmen, und ziemlich sicher gibt s in python auch nen lp-solver.

ok, hier gibt s nen lp-solver für python.

thx! mal auf die schelle einlesen geht anscheinend nicht, aber werd mal bisschen schmökern..

Hab den Excel-Solver jetzt doch zum Laufen gebracht. Hatte zunächst mit Summewenn statt mit Summenprodukt gearbeitet, um den Gesamtnutzen einer Auswahl zu berechnen, damit kam der Solver anscheinend nicht klar. Also für bis zu 200 Güter kann ich das Problem damit lösen. Damit kann ich erstmal leben

Vllt. dein benötigter Gedankenanstoss?

Hab aber nur kurz gegoogelt... mag die BWL fächer nich so.

Gruß cuPsn (4. Semester Wirtschaftsingenieurwesen)

Original von cuPsn

Gruß cuPsn (4. Semester Wirtschaftsingenieurwesen)

Am besten lässte dir das tättowieren,dann sparste dir im rL diesen Satz

Original von Samy89

Original von cuPsn

Gruß cuPsn (4. Semester Wirtschaftsingenieurwesen)

Am besten lässte dir das tättowieren,dann sparste dir im rL diesen Satz

Am besten überlegst du dir mal, ob du es verdient hast unter der Fahne von PS.de son Dünnpfiff hier abzugeben?

no offense cuPsn, aber die letzte klammer in verbindung mit deinen posts kommt schon merkwürdig rüber.

in dem "mathe-formel"-thread https://forums.pokerstrategy.com/de/forum/thread.php?postid=15124106#post15124106 war ich mir zunächst auch nicht sicher, ob das einfach ein "besserwisser-post" ist, nach dem motto "lol, das weiss sogar ich, obwohl ich nur viertes semester bin"

deine antworten sind dazu für die threadersteller kaum bis nicht hilfreich. die brauchen keine neuen ähnlichen aufgaben (ohne lösungsweg) oder die empfehlung excel zu lernen. das verstärkt den eindruck noch.

vermutlich bedeutet die letzte klammer einfach gar nix in den zusammenhängen, aber du wirst auch festgestellt haben, dass sonst im forum niemand sowas an eine grußformel anhängt.

samys humor ist da wohl nicht so ganz rübergekommen, dass er die klammer überflüssg findet.

Original von tranceactor
no offense cuPsn, aber die letzte klammer in verbindung mit deinen posts kommt schon merkwürdig rüber.

in dem "mathe-formel"-thread https://forums.pokerstrategy.com/de/forum/thread.php?postid=15124106#post15124106 war ich mir zunächst auch nicht sicher, ob das einfach ein "besserwisser-post" ist, nach dem motto "lol, das weiss sogar ich, obwohl ich nur viertes semester bin"

deine antworten sind dazu für die threadersteller kaum bis nicht hilfreich. die brauchen keine neuen ähnlichen aufgaben (ohne lösungsweg) oder die empfehlung excel zu lernen. das verstärkt den eindruck noch.

vermutlich bedeutet die letzte klammer einfach gar nix in den zusammenhängen, aber du wirst auch festgestellt haben, dass sonst im forum niemand sowas an eine grußformel anhängt.

samys humor ist da wohl nicht so ganz rübergekommen, dass er die klammer überflüssg findet.

Danke für dein Feedback.

Original von Rho0
das ist das knapsack problem, und das ist np-schwer. insofern, schau, was du bei wiki rausziehen kannst, ansonsten sind meine vorschläge:
- code einen greedy algorithmus
- benutze einen genetischen algorithmus a la "nsga 2"
- benutze "simulated annealing"
- benutze "particle swarms"
- formuliere es als integer linear problem und benutze einen solver wie "lpsolve"

ich persönlich würde wohl einen greedy algorithmus coden, und dann lpsolve benutzen. bei genetischen algorithmen oder particle swarms ist das komplizierte vernünftige regeln zu formulieren, wie die lösungen "mutieren".

aja, "nsga 2" und "lpsolve" sind freeware, aber du brauchst dann halt noch nen c/c++-compiler. soweit ich weiß gibt s in python auch genetische algorithmen, und ziemlich sicher gibt s in python auch nen lp-solver.

ok, hier gibt s nen lp-solver für python.

Sehr gute Antwort!

Am einfachsten ist es wohl direkt einen LP-Solver daher zunehmen, den du mit deiner zusätzlichen Nebenbedingung fütterst.
Diese nutzen dann schon alle Tricks, die es gibt (Branch & Bound, LP Relaxation, Schnitte,...)

Wenn du dann die Formulierung aus dem pdf nimmst, dann fehlt noch

\sum_{i=0}^n x_i = 10

Wenn du nur kleine Instanzen hast, kannst du es damit optimal lösen.
Wenn es größere Probleme werden, empfehle ich auf die Optimalität zu verzichten und eine 1+\epsilon - Approximation zu nehmen.
Es ist dann fast egal, wie klein \epsilon ist - das Problem wird dann ziemlich zügig gelöst, da es polynomiell wird.