Empfehlungen
A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z  
  Home Top 10 Fachbereiche News Hilfe & FAQ
 

Branch and Bound

Siehe auch: Entscheidungsbaum

Typ von Entscheidungsbaumverfahren der kombinatorischen
Optimierung, zur Klasse der
impliziten vollständigen Enumeration ge­hörend. Es wurde erstmals 1960 von Lana und Doig für Aufgaben der ganzzahligen Optimierung
entwickelt. Der Name wurde 1963 durch John D. C. Little u.a. im Zusam­menhang mit dem Traveling-Salesman
Pro­blem eingeführt.


Mit diesem Verfahren wird die Menge aller Lösungen systematisch in
Untermengen zer­legt (Branch), und die Untermengen werden bewertet (Bound) mit
dem bestmöglichen Wert der Zielfunktion, der gerade noch er­reichbar erscheint.
Dabei wird jeweils die Lösungsuntermenge mit dem günstigsten Zielfunktionswert (Bound)
weiter aufgespal­ten. Das Verfahren bricht ab, wenn in der zur weiteren
Aufspaltung ausgewählten Lösungs­untermenge eine vollständige Lösung bekannt
ist, deren Zielfunktionswert mit dem berech­neten Bound identisch ist.


Sowohl in der Organisation des Baumes als auch in der Terminologie
unterscheidet sich Branch and Bound von den prinzipiell ver­wandten Verfahren
der begrenzten Enume­ration und der dynamischen Optimierung.


Ein
typischer Entscheidungsbaum des Branch and Bound sei an einem Beispiel vom Typ Knapsack-Problem
dargestellt. Es stehe eine Finanzsumme von 30 Mio. DM zur Verfügung, die für
eine Auswahl aus den fünf Projekten A bis E zu verwenden sei. Der Nut­zen
dieser Projekte (z. B. in Form von Erlösen) und die erforderlichen Finanzmittel
(in Mio. DM) sind in der folgenden Tabelle ge­nannt. Gefragt ist, welche
Projekte auszuwäh­len sind, um mit den verfügbaren 30 Mio. DM eine maximale
Nutzensumme zu erzielen.


Der Lösungsprozeß ist als Baum der impli­ziten vollständigen
Enumeration dargestellt. Der Start-Knoten enthält sämtliche 2 = 32 (im einzelnen unbekannte) Lösungen. Diese Menge wird
schrittweise in Untermengen aller Lösungen zerlegt, die ein bestimmtes Projekt
enthalten (Buchstabe) bzw. nicht enthalten (Buchstabe mit Strich). Die Zweige A
und X repräsentieren disjunkte Untermengen mit jeweils 16 Lösungen. Die
Untermengen der Zweige AB und
AB
enthalten jeweils acht Lö­sungen,
die Zweige ABC und ABC jeweils vier Lösungen .


Die optimale Lösung lautet ABCDE mit der Nutzensumme von 94 und der
Auswahl der Projekte A, C und E. Diejenigen Zweige des Baumes mit kleineren
Nutzensummen als 94 brauchen nicht weiter betrachtet zu werden, da sie zu
keiner besseren als der gefundenen Lösung führen können.


Jeder
Zweig des Baumes wurde durch einen "Bound" (hinter dem Doppelpunkt) bewertet.
Dieser wurde durch die Lösung eines relaxier- ten Problems (Entscheidungsbaumverfah­ren)
bestimmt. Dazu wurde die Bedingung, daß nur ganze Projekte ausgewählt werden
können, ersetzt durch die weichere Bedin­gung, daß auch Projektteilungen
zulässig sind (Knapsack-Problem).
Zur Lösung eines so "relaxierten" Problems braucht man nur die Projekte in abnehmender
Reihenfolge des Quotienten "Nutzen/Finanzmittel" auszu­wählen, bis die
verfügbaren 30 Mio. DM ver­braucht sind, wobei das letztgewählte Projekt
gewöhnlich nur zu einem Teil realisiert wer­den kann, z.B. A ganz, B ganz und C
zu 90% mit einer Nutzensumme von 42 + 30 + 0,9 • 32 = 100,8, gerundet auf 100.
Für den Zweig AB führen A ganz, C ganz und 8/11 von D zu der Nutzensumme von
95,82, gerundet auf 95. Wenn die Lösung des relaxierten Pro­blems keine
geteilten Projekte enthält, liegt mit ihr für den entsprechenden Zweig des
Baumes die jeweilige Bestlösung des ur­sprünglichen Problems vor, so daß von
hier aus keine weitere Verzweigung mehr erforder­lich ist. Das gilt z. B. für
die Zweige Ä (B ganz, C ganz, D ganz) und ABC (A ganz, C ganz, E ganz).            


Literatur: Land,
A. H.IDoig, A. G., An
Automatic Method of Solving Discrete Programming Prob­lems, in: Econometrica,
28. Jg. (1960), S. 497ff. Little, J. D. C. u.a., An Algorithm for the Traveling Salesman
Problem, in: Operations Research, 11. Jg. (1963), S. 972ff.



Branch and Bound

 













Vorhergehender Fachbegriff: Brainwriting-Pool | Nächster Fachbegriff: Branch-and Cut-Algorithmen



  Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken




   
 
 

   Weitere Begriffe : CEMAC | Polypragmasie | Basiswahl bei der Indexbildung

   Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

  Marketing

  Definition

  Konditionenpolitik

   Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

  Investitionsrechnungen

  Marktversagen

  Umsatzsteuer

   Beliebte Artikel

Bestimmte Erklärungen und Begriffsdefinitionen erfreuen sich bei unseren Lesern ganz besonderer Beliebtheit. Diese werden mehrmals pro Jahr aktualisiert.

  Cash Flow

  Bausparen

  Fremdwährungskonto


     © 2017 Wirtschaftslexikon24.com       All rights reserved.      Home  |  Datenschutzbestimmungen  |  Impressum  |  Rechtliche Hinweise
Aktuelles Wirtschaftslexikon