Branch-and-Bound

Anwendung auf Probleme der ganzzahligen linearen Optimierung

Das allgemeine ganzzahlige lineare Optimierungsproblem hat die Gestalt

• Maximiere   G = a*x
• unter der Nebenbedingung
  Ax ≤ b
  x ≥ 0 und x ganzzahlig
• mit
• A: n*m -Matrix
• x: n-dimensionaler Vektor
• a: n-dimensionaler Vektor
• b: m-dimensionaler Vektor
• a*x: skalares Produkt, lineare Funktion mit n Variablen, reeller Wert
• Ax : m-dimensionaler Vektor, der aus der Multiplikation der Matrix A mit dem n-dimensionalen Vektor x entsteht.

Durch Vernachlässigung der Ganzzahligkeitsbedingungen erhält man die stetigeRelaxation, die mit dem Simplexverfahren gelöst werden kann. Wegender geforderten Ganzzahligkeit gehört das Ausgangsproblem aber nicht zu denlinearen Optimierungsproblemen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Branch-and-Bound aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung