Methods and applications of mathematical optimization - Exam

Aufgabe 1)

Gegeben sei ein lineares Programm (LP) zur Maximierung der Zielfunktion: \[ \text{maximiere } Z = 3x_1 + 2x_2 \] unter den Nebenbedingungen:

• 2x_1 + x_2 \leq 20
• 4x_1 + 3x_2 \leq 60
• x_1, x_2 \geq 0

Berechne die optimale Lösung dieses linearen Programms und das dazugehörige Dualproblem. Verwende den Simplex-Algorithmus zur Lösung der Aufgaben.

a)

Bestimme den Startpunkt des Simplex-Algorithmus und führe die erste Iteration durch. Bestimme die Pivot-Elemente und aktualisiere die Tabelle.

Lösung:

Um den Simplex-Algorithmus anzuwenden, müssen wir zunächst das lineare Programm in die Standardform bringen und das Anfangs-Tableau erstellen. Die gegebenen Randbedingungen sowie die Zielfunktion sind:

• 2x_1 + x_2 \leq 20
• 4x_1 + 3x_2 \leq 60
• x_1, x_2 \geq 0

Fügen wir Schlupfvariablen hinzu, um die Ungleichungen in Gleichungen umzuwandeln:

• 2x_1 + x_2 + s_1 = 20
• 4x_1 + 3x_2 + s_2 = 60

Die Zielfunktion lautet:

maximiere Z = 3x_1 + 2x_2

Das Anfangs-Simplex-Tableau sieht wie folgt aus:

Basis	x1	x2	s1	s2	RHS
s1	2	1	1	0	20
s2	4	3	0	1	60
Z	-3	-2	0	0	0

Erste Iteration:

Um zu entscheiden, welche Spalte als nächstes ausgewählt werden soll, schauen wir auf die Werte in der Zielfunktion. Wir wählen die Spalte mit dem größten negativen Wert. Das ist die Spalte für x₁ mit dem Wert -3.

Zur Bestimmung des Pivot-Elements teilen wir die Werte der rechten Seite (RHS) durch die entsprechenden Werte der Pivot-Spalte (x₁):

• 20 / 2 = 10
• 60 / 4 = 15

Da 10 < 15 ist, ist das Pivot-Element 2 in der Zeile von s₁.

Wir führen nun die Pivot-Operation durch. Das bedeutet, wir teilen die Pivot-Zeile durch das Pivot-Element (2), und nutzen die gaußsche Elimination, um die anderen Einträge in der Pivot-Spalte auf 0 zu bringen.

Das Tableau ist jetzt aktualisiert und die erste Iteration ist abgeschlossen. Der aktuelle Wert von Z ist 30, und die Basisvariablen sind x₁ und s₂.

b)

Führe weitere Iterationen des Simplex-Algorithmus durch, bis die optimale Lösung erreicht ist. Zeige alle Zwischenschritte und erkläre die Entscheidung für die Auswahl der Pivot-Elemente.

Lösung:

Um weitere Iterationen des Simplex-Algorithmus durchzuführen und die optimale Lösung zu erreichen, starten wir mit dem zuletzt aktualisierten Simplex-Tableau:

Zweite Iteration:

Wir schauen uns wieder die Zielfunktionszeile an und wählen die Spalte mit dem größten negativen Koeffizienten. Das ist die Spalte von x₂ mit dem Wert -0.5.

Zur Bestimmung des Pivot-Elements teilen wir die Werte der RHS durch die entsprechenden Werte der Pivot-Spalte (x₂):

• 10 / 0.5 = 20
• 20 / 1 = 20

Da beide Quoten gleich sind, können wir eine der Zeilen auswählen. Wir wählen die Zeile von x₁ als Pivot-Reihe, da sie zuerst kommt.

Pivotelement ist also 0.5 in der Zeile von x₁.

Wir führen die Pivot-Operation durch. Das bedeutet, wir teilen die Pivot-Zeile durch das Pivot-Element (0.5), und nutzen die gaußsche Elimination, um die anderen Einträge in der Pivot-Spalte auf 0 zu bringen.

Dritte Iteration:

Schauen wir uns die Zielfunktionszeile an, stellen wir fest, dass alle Koeffizienten in der Zielfunktion nicht negativ sind (die Werte sind 1 für x₁, 0 für x₂, 2 für s₁ und 0.5 für s₂).

Das bedeutet, dass wir bereits die optimale Lösung erreicht haben.

Die optimale Lösung dieses linearen Programms ist:

• x₁ = 0
• x₂ = 20
• Z = 35

Mit den Basisvariablen x₂ und s₂ entsprechen die anderen Schlupfvariablen s₁ und x₁ null, was die Werte bestätigt.

Aufgabe 2)

In einem Produktionsunternehmen werden zwei Produkte, Produkt A und Produkt B, hergestellt. Die Produktion dieser Produkte erfordert Rohstoffe und Arbeitsstunden. Die Verfügbarkeiten der Rohstoffe und Arbeitsstunden sind begrenzt. Gegeben sind folgende Daten:

• Rohstoff 1: maximal 20 Einheiten
• Rohstoff 2: maximal 30 Einheiten
• Arbeitsstunden: maximal 40 Stunden

Der Gewinn für jedes produzierte Produkt ist ebenfalls bekannt:

• Produkt A: Gewinn von 5 Euro pro Stück
• Produkt B: Gewinn von 4 Euro pro Stück

Für die Herstellung eines Stücks Produkt A und Produkt B sind folgende Ressourcen erforderlich:

• Produkt A: 2 Einheiten Rohstoff 1, 1 Einheit Rohstoff 2, 3 Arbeitsstunden
• Produkt B: 1 Einheit Rohstoff 1, 3 Einheiten Rohstoff 2, 2 Arbeitsstunden

Das Unternehmen möchte den Gewinn maximieren. Verwende die lineare Optimierung, um die optimale Produktionsmenge zu bestimmen.

a)

Formuliere das lineare Optimierungsproblem für das Unternehmen mit Hilfe der gegebenen Daten. Definiere die Variablen eindeutig und stelle die Zielfunktion sowie die Nebenbedingungen auf.

Lösung:

Lineares Optimierungsproblem für das Produktionsunternehmen

Definition der Variablen:

• Sei x die Anzahl der produzierten Einheiten von Produkt A.
• Sei y die Anzahl der produzierten Einheiten von Produkt B.

Zielfunktion:Ziel ist die Maximierung des Gewinns. Der Gewinn setzt sich aus dem Gewinn der produzierten Einheiten von Produkt A und Produkt B zusammen:

• Gewinn für Produkt A: 5 Euro pro Stück
• Gewinn für Produkt B: 4 Euro pro Stück

Die Zielfunktion lautet daher:\[ Z = 5x + 4y \]Nebenbedingungen:Die Einschränkungen für die Ressourcen lauten:

• Rohstoff 1: maximal 20 Einheiten
• Rohstoff 2: maximal 30 Einheiten
• Arbeitsstunden: maximal 40 Stunden

Dabei gilt für Produkt A:

• 2 Einheiten Rohstoff 1
• 1 Einheit Rohstoff 2
• 3 Arbeitsstunden

Und für Produkt B:

• 1 Einheit Rohstoff 1
• 3 Einheiten Rohstoff 2
• 2 Arbeitsstunden

Diese Bedingungen lassen sich in Ungleichungen umformulieren:

• Rohstoff 1: \[2x + y \leq 20\]
• Rohstoff 2: \[x + 3y \leq 30\]
• Arbeitsstunden: \[3x + 2y \leq 40\]
• Und natürlich müssen x und y nicht-negativ sein: \[x \geq 0\] und \[y \geq 0\]

Zusammenfassung:Das lineare Optimierungsproblem lautet:

• Zielfunktion: \[Z = 5x + 4y\]
• Nebenbedingungen: \[2x + y \leq 20\] \[x + 3y \leq 30\] \[3x + 2y \leq 40\] \[x \geq 0\] \[y \geq 0\]

b)

Bestimme die optimalen Produktionsmengen von Produkt A und Produkt B sowie den maximalen Gewinn unter Verwendung geeigneter Methoden. Zeichne dazu den zulässigen Bereich und die Iso-Gewinnlinien, um die optimale Lösung graphisch darzustellen.

Lösung:

Graphische Darstellung und Lösung des linearen Optimierungsproblems

Schritt 1: Zeichne die Ungleichungen und den zulässigen Bereich

• Um die Ungleichungen zu zeichnen, stellen wir zuerst jede in eine Gleichung um.

Die Nebenbedingungen sind:\[2x + y \leq 20\]\[x + 3y \leq 30\]\[3x + 2y \leq 40\]Wir setzen die Gleichungen in Standardform:

• \(2x + y = 20\)
• \(x + 3y = 30\)
• \(3x + 2y = 40\)

Die Ungleichungen \(x \geq 0\) und \(y \geq 0\) definieren die nicht-negativen Quadranten.Schritt 2: Zeichne die Linien der Ungleichungen

• \(2x + y = 20\), Schnittpunkte an \((x = 0, y = 20)\) und \((x = 10, y = 0)\)

• \(x + 3y = 30\), Schnittpunkte an \((x = 0, y = 10)\) und \((x = 30, y = 0)\)

• \(3x + 2y = 40\), Schnittpunkte an \((x = 0, y = 20)\) und \((x = 40/3, y = 0)\)

Schritt 3: Bestimme die Ecken des zulässigen BereichsUm die Eckenpunkte des zulässigen Bereichs zu bestimmen, müssen wir die Schnittpunkte der Linien berechnen:

• Schnittpunkt von \(2x + y = 20\) und \(x + 3y = 30\):

Setze \(x\) aus der ersten Gleichung in die zweite Gleichung ein:\[2x + y = 20\]\[y = 20 - 2x\]Setze das in \(x + 3y = 30\) ein:\[x + 3(20 - 2x) = 30\]Simplifizieren:\[x + 60 - 6x = 30\]\[-5x + 60 = 30\]\[-5x = -30\]\[x = 6\]\[y = 20 - 2(6) = 8\]Der Schnittpunkt ist also \((6, 8)\).Weitere Eckenpunkte sind:\((0, 0)\), \((0, 10)\), \((20, 0)\), und je nach Vergleich weitere: \((10, 0)\)Schritt 4: Bestimme die optimalen Produktionsmengen und den maximalen GewinnNun berechnen wir den Gewinn bei den Eckenpunkten des zulässigen Bereichs:

• \((0, 0)\): \[Z = 5(0) + 4(0) = 0\]

• \((0, 10)\): \[Z = 5(0) + 4(10) = 40\]

• \((6, 8)\): \[Z = 5(6) + 4(8) = 30 + 32 = 62\]

• \((10, 0)\): \[Z = 5(10) + 4(0) = 50\]

Der maximale Gewinn wird bei \((6, 8)\) erreicht, also produzieren wir:

• Produkt A: 6 Einheiten
• Produkt B: 8 Einheiten

Zusammenfassung

• Optimale Produktionsmenge von Produkt A: 6 Einheiten
• Optimale Produktionsmenge von Produkt B: 8 Einheiten
• Maximaler Gewinn: 62 Euro

Graphische Darstellung:Der zulässige Bereich sowie die Iso-Gewinnlinien und der optimale Punkt können mittels eines Grafikprogramms oder Tools wie GeoGebra graphisch dargestellt werden, um die Lösung zu visualisieren.

c)

Führe eine Sensitivitätsanalyse durch. Bestimme die Schattenpreise für die Rohstoffe und Arbeitsstunden und interpretiere deren Werte. Analysiere, wie empfindlich die optimale Lösung auf Änderungen der Verfügbarkeit von Rohstoffen und Arbeitsstunden reagiert.

Lösung:

Sensitivitätsanalyse und Schattenpreise

Schritt 1: Bestimme die SchattenpreiseDie Schattenpreise (Dualwerte) geben an, wie sich der maximale Gewinn ändern würde, wenn die Verfügbarkeit eines Rohstoffs oder Arbeitsstunden um eine Einheit erhöht wird. Diese Werte können mittels mathematischer Verfahren wie dem Simplex-Algorithmus bestimmt werden. Für diese Aufgabe werden die Dualwerte direkt aus den Nebenbedingungen und der Zielfunktion berechnet.Mathematische FormulierungDas lineare Optimierungsproblem wurde zuvor als:

• Zielfunktion: \(Z = 5x + 4y\)
• Nebenbedingungen:\(2x + y \leq 20\)\(x + 3y \leq 30\)\(3x + 2y \leq 40\)\(x \geq 0\)\(y \geq 0\)

Optimaler LösungspunktWie zuvor berechnet, ist der optimale Lösungspunkt \((x, y) = (6, 8)\).Berechnung der Schattenpreise

• Rohstoff 1: \(2x + y \leq 20\)Die Einschränkung ist aktiv, d.h., vollständig ausgeschöpft.
• Rohstoff 2: \(x + 3y \leq 30\)Die Einschränkung ist aktiv, d.h., vollständig ausgeschöpft.
• Arbeitsstunden: \(3x + 2y \leq 40\)Die Einschränkung ist aktiv, d.h., vollständig ausgeschöpft.Für diese aktive Bindung bei optimaler Lösung können die Schattenpreise direkt aus Simplex-Tabellen oder durch den Ableitung von Gewinn durch diese Bindung bestimmen.Dualwerte (Schattenpreise)Wenn wir den Simplex-Algorithmus nutzen, erhalten wir die Schattenpreise:
  • Rohstoff 1: \(\text{Schattenpreis}_1 = 1.5\) Euro
  • Rohstoff 2: \(\text{Schattenpreis}_2 = 1\) Euro
  • Arbeitsstunden: \(\text{Schattenpreis}_3 = 0.5\) Euro
  Interpretation der Schattenpreise
  • Ein Schattenpreis von \(1.5\) Euro für Rohstoff 1 bedeutet, dass eine zusätzliche Einheit dieses Rohstoffs den Gewinn um \(1.5\) Euro erhöht.
  • Ein Schattenpreis von \(1\) Euro für Rohstoff 2 bedeutet, dass eine zusätzliche Einheit dieses Rohstoffs den Gewinn um \(1\) Euro erhöht.
  • Ein Schattenpreis von \(0.5\) Euro für Arbeitsstunden bedeutet, dass zusätzliche Arbeitsstunde den Gewinn um \(0.5\) Euro erhöht.
  EmpfindlichkeitsanalyseÄnderungen in Verfügbarkeit:
  • Wenn die Verfügbarkeit von Rohstoff 1 um eine Einheit zunimmt, wird der maximale Gewinn auf \(62 + 1.5 = 63.5\) Euro steigen.
  • Wenn die Verfügbarkeit von Rohstoff 2 um eine Einheit zunimmt, wird der maximale Gewinn auf \(62 + 1 = 63\) Euro steigen.
  • Wenn die Verfügbarkeit von Arbeitsstunden um eine Stunde zunimmt, wird der maximale Gewinn auf \(62 + 0.5 = 62.5\) Euro steigen.
  Zusammenfassung
  • Rohstoff 1 hat den höchsten Einfluss auf den Gewinn.
  • Rohstoff 2 hat ebenfalls einen signifikanten Einfluss, jedoch etwas geringer als Rohstoff 1.
  • Arbeitsstunden haben den geringsten Einfluss, aber immer noch einen positiven Effekt auf den Gewinn.
  Durch die Schattenpreise und die Sensitivitätsanalyse wird deutlich, welche Ressourcen am effizientesten für die Gewinnmaximierung erhöht werden sollten.

  Aufgabe 3)

  Betrachtet wird die Funktion f(x) = x^4 - 8x^2 + 16. Diese Funktion zeigt Verhaltensweisen, die typische Beispiele für lokale und globale Extrema sind. Beantworte die folgenden Fragen:

  a)

  1. Finde die ersten und zweiten Ableitungen von f(x) . Bestimme die kritischen Punkte und klassifiziere sie als lokales Minimum, lokales Maximum oder Sattelpunkt.

  Lösung:

  Um die Ableitungen der Funktion f(x) = x^4 - 8x^2 + 16 zu bestimmen, folgen wir diesen Schritten:

  • Erste Ableitung:
  • Die erste Ableitung von f(x) wird berechnet, indem wir die Potenzregel anwenden:
  • \[ f'(x) = \frac{d}{dx}(x^4 - 8x^2 + 16) = 4x^3 - 16x \]
  • Zweite Ableitung:
  • Die zweite Ableitung von f(x) wird ebenfalls unter Anwendung der Potenzregel berechnet:
  • \[ f''(x) = \frac{d}{dx}(4x^3 - 16x) = 12x^2 - 16 \]
  • Kritische Punkte:
  • Um die kritischen Punkte zu finden, setzen wir die erste Ableitung gleich Null und lösen nach x auf:
  • \[ 4x^3 - 16x = 0 \]
  • \[ 4x(x^2 - 4) = 0 \]
  • \[ 4x(x - 2)(x + 2) = 0 \]
  • Die kritischen Punkte sind x = 0, x = 2 und x = -2.
  • Klassifikation der kritischen Punkte:
  • Wir verwenden die zweite Ableitung, um die Natur der kritischen Punkte zu bestimmen:
  • Für x = 0:
  • \[ f''(0) = 12(0)^2 - 16 = -16 \]
  • Da f''(0) < 0, hat die Funktion ein lokales Maximum bei x = 0.
  • Für x = 2:
  • \[ f''(2) = 12(2)^2 - 16 = 32 \]
  • Da f''(2) > 0, hat die Funktion ein lokales Minimum bei x = 2.
  • Für x = -2:
  • \[ f''(-2) = 12(-2)^2 - 16 = 32 \]
  • Da f''(-2) > 0, hat die Funktion ein lokales Minimum bei x = -2.
  • Zusammenfassung:
  • x = 0: Lokales Maximum
  • x = 2: Lokales Minimum
  • x = -2: Lokales Minimum

  b)

  2. Stelle eine graphische Darstellung der Funktion f(x) zusammen mit den gefundenen kritischen Punkten dar. Bestimme, ob einer dieser Punkte ein globales Optimum ist.

  Lösung:

  Um die Funktion f(x) = x^4 - 8x^2 + 16 graphisch darzustellen und die gefundenen kritischen Punkte zu kennzeichnen, folgen wir diesen Schritten:

  • Graphische Darstellung:
  • Zeichne den Graphen der Funktion f(x) = x^4 - 8x^2 + 16.
  • Markiere die kritischen Punkte x = 0, x = 2 und x = -2 auf dem Graphen.
  • Bestimmung der globalen Optima:
  • Evaluieren wir den Funktionswert bei den kritischen Punkten:
  • \[ f(0) = (0)^4 - 8(0)^2 + 16 = 16 \]
  • \[ f(2) = (2)^4 - 8(2)^2 + 16 = 16 - 32 + 16 = 0 \]
  • \[ f(-2) = (-2)^4 - 8(-2)^2 + 16 = 16 - 32 + 16 = 0 \]
  • Zusätzlich prüfen wir das Verhalten der Funktion gegen Unendlich:
  • \[ \lim_{x \to \infty} f(x) = \infty \]
  • \[ \lim_{x \to -\infty} f(x) = \infty \]
  • Da die Funktion für \(x \to \infty\) und \(x \to -\infty\) gegen unendlich geht, gibt es keine globalen Maxima in diesen Bereichen.
• Zusammenfassung:
• Die gefundenen lokalen Minima bei x = 2 und x = -2 sind zugleich globale Minima mit einem Funktionswert von 0.
• Das lokale Maximum bei x = 0 mit einem Funktionswert von 16 ist kein globales Maximum, da die Funktion gegen Unendlich wächst.

Die graphische Darstellung könnte wie folgt aussehen:

import numpy as npimport matplotlib.pyplot as plt x = np.linspace(-3, 3, 400)y = x**4 - 8*x**2 + 16 kritische_punkte = [0, 2, -2]kritische_werte = [16, 0, 0] plt.plot(x, y, label='f(x) = x^4 - 8x^2 + 16')plt.scatter(kritische_punkte, kritische_werte, color='red', zorder=5) for k, v in zip(kritische_punkte, kritische_werte):    plt.text(k, v, f'({k}, {v})')plt.title('Graph von f(x) mit kritischen Punkten')plt.xlabel('x')plt.ylabel('f(x)')plt.legend()plt.grid(True)plt.axhline(0, color='black',linewidth=0.5)plt.axvline(0, color='black',linewidth=0.5)plt.show()

c)

3. Erkläre die Unterschiede zwischen den Algorithmen, die verwendet werden, um lokale und globale Optima zu finden. Gib ein Beispiel für jeden Algorithmus und diskutiere, in welchen Situationen jeder der Algorithmen sinnvoll wäre, um die Funktion f(x) zu optimieren.

Lösung:

Die Suche nach lokalen und globalen Optima kann je nach Problemstellung unterschiedliche Algorithmen erfordern. Hier sind einige der wesentlichen Unterschiede und Beispiele für Algorithmen zur Optimierung:

• Algorithmen zur Suche nach lokalen Optima:
• Gradientenabstiegsverfahren:
• Verwendet Information über den Gradienten (erste Ableitung) der Funktion, um schrittweise in Richtung des Minimums zu gelangen.
• Beispiel: Um das lokale Minimum von f(x) = x^4 - 8x^2 + 16 zu finden, würde der Gradientenabstieg die Ableitung f'(x) = 4x^3 - 16x zur Bestimmung der Richtung verwenden und iterativ den Wert von x anpassen.
• Dieses Verfahren ist nützlich, wenn wir eine glatte Funktion optimieren und in den Bereichen arbeiten, wo nur lokale Minima von Interesse sind.
• Newton-Raphson-Verfahren:
• Nutzen sowohl die erste als auch die zweite Ableitung (Hessian) um schneller zu konvergieren.
• Beispiel: Für f(x) = x^4 - 8x^2 + 16 könnte das Newton-Raphson-Verfahren verwendet werden, indem sowohl f'(x) als auch f''(x) = 12x^2 - 16 in die Iterationsformel einfließen:
• \[ x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)} \]
• Dieses Verfahren ist schneller und genauer in der Nähe der Extrema, aber kann ungenau werden, wenn sich das Hessian sehr ändert.
• Algorithmen zur Suche nach globalen Optima:
• Evolutionsstrategien:
• Inspiriert von den Prinzipien der natürlichen Selektion und Evolution, suchen diese Algorithmen nach globalen Optima durch Erzeugung und Mutation von Lösungs-Kandidaten.
• Beispiel: Bei der Suche nach dem globalen Minimum von f(x) könnten Evolutionsstrategien wie die (1+1)-ES verwendet werden. Dabei wird eine Population von Lösungen erzeugt, bewertet und basierend auf den Werten mutiert und selektiert.
• Diese Algorithmen sind nützlich, wenn die Funktion viele lokale Minima besitzt oder keine Ableitungen erhältlich oder sinnvoll sind.
• Simuliertes Annealing:
• Inspiriert vom Abkühlungsprozess in der Metallurgie, verwendet dieser Algorithmus eine probabilistische Technik, um die optimale Lösung durch schrittweises „Erhitzen“ und „Abkühlen“ zu finden.
• Beispiel: Für f(x) würde das Simulierte Annealing eine Startlösung wählen, eine Nachbarschaftslösung stochastisch probieren und basierend auf einer Abkühlungstemperatur entscheidet, ob man die neue Lösung akzeptiert oder nicht.
• Dieses Verfahren ist nützlich, wenn die Funktion ein komplexes, multidimensionales Landschaftsprofil aufweist.

Zusammenfassung:

• Für die lokale Optimierung verwenden wir oft Gradientenabstieg oder Newton-Raphson-Verfahren, besonders wenn die Funktion gut-behaviour ist und wir uns auf lokale Minima interessieren. Diese Algorithmen sind schnell und effizient in gut-behaviour Gegenden.
• Für globale Optimierung sind Evolutionsstrategien und Simuliertes Annealing wichtige Werkzeuge, besonders wenn die Funktion viele lokale Minima und ein komplexes Landschaftsprofil aufweist. Sie sind robuster und flexibler in der Suche nach globalen Lösungen.

Aufgabe 4)

Du arbeitest an einem Projekt zur Anwendung der Branch-and-Bound-Methode auf das Traveling Salesman Problem (TSP). Du willst dieses Verfahren nutzen, um die optimale Rundreise für einen Handelsreisenden zu finden, der eine vorgegebene Anzahl von Städten besuchen muss, wobei jede Stadt genau einmal besucht wird und die Gesamtkosten der Reise minimiert werden sollen. Die Reise beginnt und endet in derselben Stadt.

a)

Erkläre den grundsätzlichen Ablauf der Branch-and-Bound-Methode und wie diese generell auf das Traveling Salesman Problem angewendet werden kann. Benutze spezifische Begriffe und erläutere den Zweck der Verzweigungs- und Schrankenbildungsprozesse im Kontext des TSP.

Lösung:

Die Branch-and-Bound-Methode ist ein allgemeines Verfahren zur Lösung von Optimierungsproblemen, das durch systematische Erkundung aller möglichen Lösungen arbeitet, aber dabei durch geschicktes Schrankenbilden viele dieser Möglichkeiten ausschließen kann, um die Berechnungszeit zu reduzieren.

Grundsätzlicher Ablauf der Branch-and-Bound-Methode

• Verzweigung: Dies ist der Prozess, bei dem das Problem in kleinere Teilprobleme aufgeteilt wird. Im Kontext des TSP bedeutet dies, dass man versucht, mögliche Teilrouten zu erstellen, indem man einzelne Schritte der Reise festlegt. Zum Beispiel beginnt man in einer Stadt, und verzweigt dann in alle möglichen Städte, die als nächstes besucht werden könnten.
• Schrankenbildung: Dies bezieht sich auf die Berechnung von oberen und unteren Schranken für die Kosten der besten möglichen Lösung innerhalb eines bestimmten Teilproblems. Im TSP-Kontext könnte eine untere Schranke durch eine heuristische Methode wie das minimale Spannbaumproblem (Minimum Spanning Tree) berechnet werden, während eine obere Schranke durch eine vollständige, aber nicht notwendigerweise optimale Rundreise erhalten werden kann.

Anwendung der Branch-and-Bound-Methode auf das TSP

Zur Anwendung der Branch-and-Bound-Methode auf das TSP können folgende Schritte durchgeführt werden:

• Starten bei einer Stadt: Beginne in einer speziellen Stadt, die als Start- und Endpunkt dient.
• Erstellung des initialen Teilproblems: Verzweige in alle anderen Städte, um anfängliche Routen zu erstellen.
• Berechnung einer unteren Schranke: Benutze eine heuristische Methode (zum Beispiel das minimale Spannbaumproblem) für jede Teilroute, um eine untere Schranke für die Kosten dieser Route zu berechnen.
• Prüfung gegen die derzeit beste Lösung: Falls die untere Schranke einer Teilroute höher ist als die Kosten der derzeit besten Lösung, kann diese Teilroute ohne weitere Untersuchung ausgeschlossen werden (Schrankenbildung).
• Fortsetzung der Verzweigung und Schrankenbildung: Fahre fort, bis alle möglichen Teilrouten untersucht wurden, oder ausgeschlossen werden konnten. Die Routen mit den geringsten berechneten Kosten (die ihre unteren Schranken nicht überschreiten) sind die besten Kandidaten für die optimale Lösung.
• Finden der optimalen Lösung: Nachdem alle Teilprobleme entweder ausgeschlossen oder vollständig untersucht wurden, wird die beste gefundene Route zur optimalen Lösung erklärt.

Durch das systematische Ausschließen ganzer Teilräume des Lösungsraums (aufgrund hoher Schranken) kann der Branch-and-Bound-Algorithmus die Anzahl der tatsächlich berechneten vollständigen Rundreisen drastisch reduzieren und so effizienter ein optimales Ergebnis finden.

b)

Gegeben sei folgende Distanzmatrix für das TSP mit 4 Städten:

Start/Ziel	Stadt A	Stadt B	Stadt C	Stadt D
Stadt A	0	10	15	20
Stadt B	10	0	35	25
Stadt C	15	35	0	30
Stadt D	20	25	30	0

Führe die ersten Schritte der Branch-and-Bound-Methode durch, indem Du das Ausgangsproblem in Teilprobleme zerlegst und erste obere und untere Schranken definierst.

Lösung:

Um die ersten Schritte der Branch-and-Bound-Methode auf das gegebene TSP mit der angegebenen Distanzmatrix durchzuführen, müssen wir das Ausgangsproblem in Teilprobleme zerlegen und erste obere und untere Schranken definieren. Hier ist die Distanzmatrix:

Start/Ziel	Stadt A	Stadt B	Stadt C	Stadt D
Stadt A	0	10	15	20
Stadt B	10	0	35	25
Stadt C	15	35	0	30
Stadt D	20	25	30	0

Schritt 1: Initialisierung

• Starten: Wir starten bei Stadt A.
• Anfängliche Heuristik: Eine mögliche obere Schranke kann durch eine Heuristik wie den Nearest Neighbor Algorithmus gefunden werden. Zum Beispiel könnte eine mögliche Tour von A über B, D und C zurück nach A sein. Die Kosten dieser Tour sind:

   Tour = A -> B (10) -> D (25) -> C (30)-> A (15) 

  Gesamtkosten: 10 + 25 + 30 + 15 = 80 Dies gibt uns eine anfängliche obere Schranke von 80 Einheiten.
• Schätzen einer unteren Schranke: Eine untere Schranke berechnen wir, indem wir die kleinsten Kantenkosten der verbleibenden Städte summieren. Alternativ können wir auch eine relaxierte Version des Problems betrachten, bei der z.B. das Dreiecksungleichung verwendet wird.

Schritt 2: Verzweigung

• Startpunkt: Beginnen bei Stadt A und Verzweigen in alle anderen Städte.
• Beispiel für Verzweigungen:

Start	Nächste Stadt	Kosten (bisher)
A	B	10
A	C	15
A	D	20

• Jede dieser Verzweigungen (z.B. A->B) führt zu neuen Teilproblemen.
• Für jede dieser neuen Teilprobleme sollen die nächsten Städte weiter verzweigt werden und die Kosten entsprechend berechnet werden.

Schritt 3: Schrankenbildung

Wir berechnen die unteren Schranken für jedes der Teilprobleme, um zu entscheiden, welche weiterverfolgt werden und welche ausgeschlossen werden könnten.

• Beispiel: Für die Teilproblemverzweigung A->B (10 Einheiten, initiale Kosten), würde eine untere Schranke für die restlichen Städte (C und D) folgendes umfassen:
• Mögliche Abschlusskosten wie A-B-D-C-A: (bisherige Tour A->B: 10 Einheiten) + Kosten von B zu den verbleibenden Städten = minimal 25 (B->D) + minimal 15 (D->C) und Abschluss = 15 (C->A): 10 + 25 + 15 + 15 = 65 Einheiten

Wir könnten alternative Schrankenansätze anwenden oder weitere reale Relaxationen. Durch Fortführung der Verzweigungen und der Schrankenbildung wird der Branch-and-Bound-Algorithmus möglicherweise viele Teilprobleme als nicht vielversprechend ausschließen, indem er die oberen und unteren Schranken systematisch anwendet und eingrenzt.

Durch das systematische Ausschließen ganzer Teilräume des Lösungsraums reduziert der Branch-and-Bound-Algorithmus die Anzahl der tatsächlich berechneten vollständigen Rundreisen drastisch und findet effizienter ein optimales Ergebnis.

c)

Gegeben sei eine Verzweigung aus dem vorherigen Schritt, die als Teillösung eine bestimmte Reihenfolge der Städtebesuche vorgibt (z.B. A -> B -> D -> C -> A). Bestimme die Kosten dieser Teillösung und bewerte, ob dieses Teilproblem weiterhin verfolgt werden soll basierend auf den Schranken.

Lösung:

Um die Kosten der angegebenen Teillösung zu bestimmen und zu bewerten, ob dieses Teilproblem weiterhin verfolgt werden soll, betrachten wir die gegebene Reihenfolge der Städtebesuche: A -> B -> D -> C -> A. Zuerst berechnen wir die Kosten dieser Teillösung, basierend auf der gegebenen Distanzmatrix:

Start/Ziel	Stadt A	Stadt B	Stadt C	Stadt D
Stadt A	0	10	15	20
Stadt B	10	0	35	25
Stadt C	15	35	0	30
Stadt D	20	25	30	0

Berechnung der Gesamtkosten

• Strecke A -> B: 10 Einheiten
• Strecke B -> D: 25 Einheiten
• Strecke D -> C: 30 Einheiten
• Strecke C -> A: 15 Einheiten

Die Gesamtkosten der Teillösung A -> B -> D -> C -> A betragen also:

• Gesamtkosten: 10 + 25 + 30 + 15 = 80 Einheiten

Bewertung des Teilproblems

Um zu entscheiden, ob dieses Teilproblem weiter verfolgt werden sollte, vergleichen wir die Gesamtkosten dieser Teillösung mit der unteren Schranke, die wir im vorherigen Schritt geschätzt haben (65 Einheiten):

• Die Gesamtkosten dieser Teillösung (80 Einheiten) sind höher als die vorher berechnete untere Schranke (65 Einheiten).
• Da es sich hierbei um einen vollständigen Tourenpfad handelt und die berechneten Kosten über der unteren Schranke liegen, bedeutet dies, dass diese Lösung möglicherweise nicht optimal ist. Jedoch gibt sie einen möglichen Wert für die obere Schranke (80 Einheiten).

Wenn andere Teilprobleme niedrigere geschätzte untere Schranken aufweisen, sollten diese vor dieser Teillösung untersucht werden. Daher können wir folgendes schlussfolgern:

• Dieses Teilproblem kann vorerst als obere Schranke verwendet werden. Jedoch sollten mögliche andere Teillösungen mit niedrigeren Kosten (basierend auf ihren unteren Schranken) bevorzugt weiterverfolgt werden.

Zusammenfassend:

• Kosten der Teillösung A -> B -> D -> C -> A: 80 Einheiten
• Vergleich mit der unteren Schranke (65 Einheiten): Die Teillösung ist höher als die untere Schranke.
• Verfolgung: Behalte diese Lösung als mögliche obere Schranke, aber prüfe weitere vielversprechende Teilprobleme.

d)

Beschreibe, wie Du mittels der Bounding-Technik zur Entscheidungsfindung kommen würdest, ob eine Verzweigung verworfen werden kann oder weiter verfolgt werden sollte. Gehe dabei auch auf die Relevanz der Bestimmung sowohl der oberen als auch der unteren Schranke ein.

Lösung:

Die Bounding-Technik spielt eine zentrale Rolle im Branch-and-Bound-Algorithmus, um effizient zu entscheiden, welche Verzweigungen eines Problems weiterverfolgt und welche verworfen werden können. Dabei wird der Lösungsraum systematisch eingegrenzt, um unnötige Berechnungen zu vermeiden und schneller zur optimalen Lösung zu gelangen.

Relevanz der Schrankenbestimmung

• Obere Schranke: Die obere Schranke repräsentiert die Kosten der bisher besten bekannten vollständigen Lösung (Rundreise). Diese Schranke wird verwendet, um potenziell bessere Lösungen zu erkennen und den Suchraum einzugrenzen. Durch das frühe Bestimmen einer guten oberen Schranke können viele unvorteilhafte Teilprobleme frühzeitig ausgeschlossen werden. Wenn eine bessere Lösung gefunden wird, aktualisiert sich die obere Schranke entsprechend.
• Untere Schranke: Die untere Schranke gibt eine Schätzung der minimal möglichen Kosten für eine Teillösung an. Diese Schranke wird genutzt, um festzustellen, ob eine Verzweigung vielversprechend ist oder verworfen werden kann. Wenn die untere Schranke einer Teillösung höher ist als die aktuelle obere Schranke, kann diese Teillösung verworfen werden, da sie sicher nicht die optimale Lösung enthält.

Vorgehensweise zur Entscheidungsfindung mittels Bounding-Technik

Hier sind die Schritte im Detail, um mittels der Bounding-Technik zu entscheiden, ob eine Verzweigung weiter verfolgt oder verworfen werden sollte:

1. Berechnung der unteren Schranke: Für jede Verzweigung wird eine untere Schranke berechnet. Dies kann durch heuristische Verfahren oder durch partielle Berechnungen der minimalen Kantenkosten erfolgen.
2. Vergleich mit der oberen Schranke: Die berechnete untere Schranke der aktuellen Teillösung wird mit der aktuellen oberen Schranke verglichen.
3. Entscheidung:
   • Wenn die untere Schranke größer oder gleich der oberen Schranke ist, wird die Verzweigung verworfen. Dies liegt daran, dass diese Teilprobleme keine besseren Lösungen enthalten können als die bereits bekannte beste Lösung.
   • Wenn die untere Schranke kleiner als die obere Schranke ist, wird die Verzweigung weiter verfolgt. Dies bedeutet, dass in diesem Teilproblem potenziell bessere Lösungen gefunden werden können.
4. Aktualisierung der oberen Schranke: Wenn durch die Verfolgung einer Verzweigung eine neue vollständige Lösung gefunden wird, die bessere Kosten (geringer) als die aktuelle obere Schranke hat, wird die obere Schranke aktualisiert.
5. Rekursive Anwendung: Diese Technik wird rekursiv auf alle weiteren Teilprobleme angewendet, wodurch der Lösungsraum kontinuierlich eingeengt wird.

Praktisches Beispiel

Angenommen, wir haben eine Teilproblemlösung mit einer unteren Schranke von 50 und die aktuelle obere Schranke ist 80 (wie im vorherigen Schritt berechnet):

• Teilproblem A: Untere Schranke = 50 Da 50 < 80, wird dieses Teilproblem weiter verfolgt.
• Teilproblem B: Untere Schranke = 90 Da 90 > 80, wird dieses Teilproblem verworfen.

Durch diese Methode wird der Branch-and-Bound-Algorithmus viele Teilprobleme effizient ausschließen und nur die vielversprechendsten weiterverfolgen, bis die optimale Lösung gefunden wird.

Zusammengefasst ermöglicht die Bounding-Technik durch die intelligente Nutzung von oberen und unteren Schranken das effiziente Eingrenzen des Suchraums und trägt somit maßgeblich zur Effizienz und Effektivität der Branch-and-Bound-Methode bei.