Branch-and-Bound-Techniken zur Lsung von BIP-Problemen

Studienarbeit aus dem Jahr 2008 im Fachbereich BWL - Unternehmensforschung, Operations Research, Note: 1,0, Martin-Luther-Universitt Halle-Wittenberg (Wirtschaftswissenschaftliche Fakultt), Veranstaltung: Seminar Operations Research, 11 Quellen im Literaturverzeichnis, 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 Lsung 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, gelst. Im
Vordergrund der Modelle stehen allerdings kontinuierliche Entscheidungsvariablen
innerhalb linearer Zielfunktionen. In der Realitt hat man es aber oft mit
Problemen zu tun, die teilweise (MIP) oder sogar ausschlielich (PIP) mit Hilfe
ganzzahliger Entscheidungsvariablen modelliert werden mssen. Die Einplanung
verschiedener unteilbarer Produktionsfaktoren ist ein Beispiel dafr. Als Spezialfall der
ganzzahligen Programmierung (IP) existiert die binre ganzzahlige Programmierung
(BIP). BIP-Modelle beruhen auf binren Entscheidungsvariablen, die man als
Ja-Nein-Entscheidungen interpretieren kann. Bei der Lsung dieser Modelle ergeben
sich allerdings Probleme bezglich der Komplexitt. Man bentigt deshalb
Lsungsverfahren, die sich dieser Problematik annehmen und zu einer mglichst
optimalen Lsung in vertretbarer Zeit fhren. Ein mgliches Lsungsverfahren ist der
Branch-and-Bound (B&B) Algorithmus, wobei sich zustzlich verschiedene Techniken
anwenden lassen.

[...]