Variante des Rucksackproblems < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:05 Mi 02.05.2012 | | Autor: | conman |
Ich habe folgende Problemstellung:
---
Es existieren mehrere Gruppen mit jeweils einem oder auch mehreren Projekten. Jedes der Projekte besitzt einen individuellen Nutzen und spezifische Projektkosten.
Es soll nun eine Auswahl getroffen werden, die den Gesamtnutzen maximiert und die Gesamtkosten im Rahmen eines Budgets hält, wobei aus jeder Gruppe nur maximal ein Projekt ausgewählt werden darf.
----
Nach etwas Recherche bin ich der Meinung, dass dem Ganzen ein 0-1 Knapsack Problem mit Multiple Choice Contraint zugrunde liegt ![[]](/images/popup.gif) (Nauss, 1978).
Allerdings ist dort das Problem so formuliert, dass exakt 1 Projekt aus jeder Gruppe ausgewählt wird. Gibt es eine Variante des Rucksackproblems, das perfekt auf meine Problembeschreibung passt?
Oder ist mein Problem eine Unterklasse des 0-1 Knapsack Problem mit Multiple Choice Contraint? Indem ich nämlich in jede Gruppe ein zusätzliches Projekt einführe, dessen Kosten und Nutzen null sind, repräsentiert dieses Projekt den Fall, dass einfach kein Projekt aus der Gruppe ausgewählt wurde. Kann ich das einfach so machen?
Danke!
Constantin
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:57 Do 03.05.2012 | | Autor: | Stoecki |
> Ich habe folgende Problemstellung:
>
> ---
>
> Es existieren mehrere Gruppen mit jeweils einem oder auch
> mehreren Projekten. Jedes der Projekte besitzt einen
> individuellen Nutzen und spezifische Projektkosten.
>
> Es soll nun eine Auswahl getroffen werden, die den
> Gesamtnutzen maximiert und die Gesamtkosten im Rahmen eines
> Budgets hält, wobei aus jeder Gruppe nur maximal ein
> Projekt ausgewählt werden darf.
>
> ----
>
> Nach etwas Recherche bin ich der Meinung, dass dem Ganzen
> ein 0-1 Knapsack Problem mit Multiple Choice Contraint
> zugrunde liegt
> (Nauss, 1978).
>
> Allerdings ist dort das Problem so formuliert, dass exakt 1
> Projekt aus jeder Gruppe ausgewählt wird. Gibt es eine
> Variante des Rucksackproblems, das perfekt auf meine
> Problembeschreibung passt?
>
> Oder ist mein Problem eine Unterklasse des 0-1 Knapsack
> Problem mit Multiple Choice Contraint? Indem ich nämlich
> in jede Gruppe ein zusätzliches Projekt einführe, dessen
> Kosten und Nutzen null sind, repräsentiert dieses Projekt
> den Fall, dass einfach kein Projekt aus der Gruppe
> ausgewählt wurde. Kann ich das einfach so machen?
ob es eine solche variante gibt, weiß ich nicht. aber das mit den dummies geht auf jeden fall.
>
> Danke!
> Constantin
>
>
Gruß Bernhard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:03 Fr 04.05.2012 | | Autor: | conman |
Danke für die Antwort.
Grüße
Constantin
|
|
|
|
