Standardmodelltyp der — kombinatorischen Optimierung. Aus den Elementen j = 1, 2, ..., n ist eine solche Auswahl zu treffen, dass der Wert der —Zielfunktion minimiert wird und die n —Restriktionen vom Typ mit den Koeffizienten ai; = 0 oder 1 eingehalten werden. Dabei bedeuten der Variablenwert x; = 1 die Wahl, x; = 0 die Nichtwahl des Elementes j. Der Index i repräsentiert eine Liste von Eigenschaften, von denen jede mindestens einmal erfüllt werden muss. Der Index j steht für die Objekte, unter denen auszuwählen ist. Die Koeffizienten ai; = 1 kennzeichnen diejenigen Objekte j, die die Eigenschaft i besitzen. Zur Lösung eignen sich unterschiedliche Entscheidungsbaumverfahren, und zwar solche des -Branch and Bound, der begrenzten Enumeration und der dynamischen Optimierung, sowie —heuristische Verfahren. Gegenüber dem Knapsack-Problem handelt es sich hier jedoch um ein generell schwieriger zu lösendes Auswahlproblem der kombinatorischen Optimierung.
Vorhergehender Fachbegriff: Set Up | Nächster Fachbegriff: Set-Packing-Problem
Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken
|