Diskrete Optimierung: Branch-and-Bound Methode

Jul 9, 2024

Diskrete Optimierung: Branch-and-Bound Methode

Überblick

  • Diskrete Optimierung mit der Branch-and-Bound Methode
  • Ein Optimierungsproblem mit einer Zielfunktion und Nebenbedingungen
  • Unterschiedliche Arten von Variablen: kontinuierlich und diskret

Vorgehensweise

Startzustand

  • Zielfunktion: Minimieren
    • 7 Variablen, davon x5, x6 und x7 kontinuierlich, x1, x2 und x3 diskret
  • Entscheidungsbaum als Hilfsmittel
    • Alle Variablen zunächst als kontinuierlich behandeln und das kontinuierliche Optimierungsproblem lösen
    • Erhalten der Werte für die Optimierungsvariablen und Zielfunktionswert (f)
    • Startknoten (Knoten 0) als kontinuierliche Lösung

Schritte der Branch-and-Bound Methode

  1. X1 Diskret Setzen

    • x2, x3, x5, x6 und x7 bleiben kontinuierlich
    • X1 in diskrete Werte setzen: 1, 2, 4, 5
    • Berechnung der Optimierungsvariablen und Zielfunktionswerte für jede gesetzte diskrete Variable
    • Liefert den niedrigsten Zielfunktionswert (z.B. 66.16)

  2. Restwerte Diskret Setzen

    • Fortsetzen an der Stelle mit niedrigstem Zielfunktionswert
    • Beispiel: X1 = 2, X2 diskret setzen in 1, 2, 4, 5
    • Berechnung der Optimierungsvariablen und Zielfunktionswerte
    • Niedrigster Zielfunktionswert aussuchen (z.B. 66.85)
    • Fortführen bis alle diskreten Werte der Variablen durchlaufen sind

Finalisierung der Lösung

  • Finden des endgültigen minimalen Zielfunktionswertes nach Durchlaufen aller Knoten im Entscheidungsbaum
  • Vergleich der Werte zur Identifikation der besten Lösung:
    • Z.B.: X1 = 4, X2 = 4, X3 = 5, X4 = 5 führt zu Zielwert = 68.33
    • Überprüfung aller möglichen Knoten für niedrigeren Wert

Zusammenfassung

  • Branch-and-Bound Methode als Tool zur diskreten Optimierung
  • Systematische Testung aller diskreten Kombinationen zur Minimierung der Zielfunktion
  • Verwendung Matlab zur Berechnung der kontinuierlichen Optimierungsprobleme

Abschluss

  • Endlösung: exakte Kombination der diskreten und kontinuierlichen Variablen
  • Zielfunktionswert: 68.33
  • Video-Abschluss Hinweise: Abonnieren für weitere Inhalte rund um die Optimierung

Danke fürs Zuschauen und bis zum nächsten Mal!

Full transcript