Advertisement
Published in:
2018 | OriginalPaper | Chapter
8. Ganzzahlige Probleme
Authors : Andreas Koop, Hardy Moock
Published in: Lineare Optimierung – eine anwendungsorientierte Einführung in Operations Research
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Zusammenfassung
Probleme mit ganzzahligen Variablen sind weitaus schwieriger zu lösen als Probleme mit reellen Variablen. Bei ganzzahligen Problemen kann mit wachsender Anzahl von Variablen der Lösungsaufwand, d. h. der Speicherplatzbedarf und die Laufzeit, exponentiell ansteigen. Für viele Probleme reicht es aus, wenn man sich auf das Berechnen einer reellen Lösung beschränkt, auch wenn die Variablen streng genommen ganzzahlig sein sollten. Man rundet dann einfach auf die nächste ganze Zahl und erhält so eine zwar nicht exakte, aber dennoch zufriedenstellende Lösung. Für andere Probleme, z. B. das Knapsack-Problem, ist die Bedingung der Ganzzahligkeit unabdingbar. In diesem Abschnitt wollen wir diesen Sachverhalt etwas genauer untersuchen und ein Verfahren zur Lösung ganzzahliger Probleme vorstellen.