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
 

B&B-Verfahren

Branch and Bound (B&B)-Verfahren dienen zur Lösung von kombinatorischen und ganzzahligen Optimierungsmodellen. B&B-Verfahren bestehen aus den zwei Komponenten Verzweigung (Branching) sowie Schrankenberechnung und Ausloten (Bounding). Sobald alle im B&B-Baum entstehenden Teilprobleme vollständig verzweigt oder ausgelotet sind, hat das Verfahren eine optimale Lösung gefunden oder festgestellt, dass keine zulässige Lösung existiert.

Ein Beispiel verdeutlicht die Vorgehensweise: Gegeben ist ein Knapsack- Problem mit Nutzenwerten uj und Gewichten gj der Gegenstände j = 1, 2, 3: Das maximale Gesamtgewicht des Rucksacks beträgt ... sie zeigt den B&B-Baum, der sich bei Anwendung des wie folgt ausgestalteten B&B-Verfahrens ergibt:

Bounding: LP-Relaxation zur Berechnung lokaler oberer Schranken, anfängliche globale untere Schranke LB = 0 (keine zulässige Lösung bekannt)

Branching: Verzweigung in zwei Teilprobleme durch Setzen von und

Branching-Regeln: Auswahl jeweils des Gegenstands h (d.h. der Variablen xh), der in der Lösung der LPRelaxation nur unvollständig in den Rucksack passt; Anwendung der LIFO-Regel Für die Berechnung der oberen Schranke UB0 = 17 im Ausgangsproblem P0 s. LP-Relaxation. In P1 wird eine erste zulässige Lösung mit LB = 13 gefunden. Nach Verzweigen von P2 ergibt sich in P3 eine bessere zulässige Lösung mit LB = 14. P4 wird ausgelotet, da UB4 nicht größer als dieser beste bis dahin bekannte Zielfunktionswert ist. Da nun alle Knoten vollständig verzweigt oder ausgelotet sind, endet das Verfahren. Als optimal wurde damit die in P3 gefundene beste zulässige Lösung erkannt.

Vorhergehender Fachbegriff: B | Nächster Fachbegriff: B-Marke



  Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

   
 
 

   Weitere Begriffe : Administrationssystem | Einkommenseffekt der Investition Multiplikatoranalyse | Antitrust-Politik

   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


     © 2023-2024 Wirtschaftslexikon24.com       All rights reserved.      Home  |  Datenschutzbestimmungen  |  Impressum  |  Rechtliche Hinweise
Aktuelles Wirtschaftslexikon