Branch-and-Bound-Techniken zur Lösung von BIP-Problemen

Studienarbeit aus dem Jahr 2008 im Fachbereich BWL - Unternehmensforschung, Operations Research, Note: 1,0, Martin-Luther-Universität Halle-Wittenberg (Wirtschaftswissenschaftliche Fakultät), Veranstaltung: Seminar Operations Research, Sprache: Deutsch, Abstract: Reale Entscheidungsprobleme bilden den Hintergrund des Fachgebietes ¿Operations

Research¿ (OR). Die Abbildung dieser Probleme als Modelle und die Entwicklung

bzw. Anwendung von Algorithmen zu deren Lösung sind die Hauptaufgaben des

OR im weiten Sinne. Dabei ist die lineare Programmierung (LP) ein bedeutendes

Teilgebiet des OR. Die betrachteten deterministischen Modelle werden durch den

Simplex-Algorithmus, als wichtigstes Verfahren innerhalb der LP, gelöst. Im

Vordergrund der Modelle stehen allerdings kontinuierliche Entscheidungsvariablen

innerhalb linearer Zielfunktionen. In der Realität hat man es aber oft mit

Problemen zu tun, die teilweise (MIP) oder sogar ausschließlich (PIP) mit Hilfe

ganzzahliger Entscheidungsvariablen modelliert werden müssen. Die Einplanung

verschiedener unteilbarer Produktionsfaktoren ist ein Beispiel dafür. Als Spezialfall der

ganzzahligen Programmierung (IP) existiert die binäre ganzzahlige Programmierung

(BIP). BIP-Modelle beruhen auf binären Entscheidungsvariablen, die man als

Ja-Nein-Entscheidungen interpretieren kann. Bei der Lösung dieser Modelle ergeben

sich allerdings Probleme bezüglich der Komplexität. Man benötigt deshalb

Lösungsverfahren, die sich dieser Problematik annehmen und zu einer möglichst

optimalen Lösung in vertretbarer Zeit führen. Ein mögliches Lösungsverfahren ist der

Branch-and-Bound (B&B) Algorithmus, wobei sich zusätzlich verschiedene Techniken

anwenden lassen.

[...]