Rucksackproblem

Knapsack-Problem, Ladungsproblem. 1. Begriff: Binäres Optimierungsproblem der Form:

2. Interpretation: Ein Bergsteiger steht vor dem Problem, für eine Bergtour seinen Rucksack so mit Proviant zu füllen, daß der (Gesamt-)Nährwert x0 der eingepackten Lebensmittel möglichst groß wird. Insgesamt stehen die (unteilbaren) Lebensmittel 1, 2, ... , n mit den (Einzelnährwerten) c1, c2, ... , cn und den Gewichten a1, a2, ... , an zur Verfügung, der Bergsteiger kann aber höchstens b Kilogramm tragen. Welche der Lebensmittel sollen unter diesen Bedingungen eingepackt werden? - 3. Lösungsverfahren: Grundsätzlich sind alle Verfahren der binären Optimierung anwendbar. Trotz großer Erfolge bei der Reduzierung des Rechenzeitaufwands ist man bei vielen Rucksackproblem der Praxis noch auf den Einsatz heuristischer Verfahren angewiesen. - 4. Ökonomische Anwendung: Varianten des Rucksackproblem kommen v. a. bei der Planung von Investitionsprogrammen bzw. von Wertpapierportefeuilles zum Einsatz. Darüber hinaus ergeben sich häufig Rucksackproblem als Unterprobleme bei der Lösung großer linearer Optimierungsprobleme, z. B. bei Verschnittproblemen.

<< vorheriger Begriff

nächster Begriff>>

Rückruf

Rückscheck