Management Science (MiM) - Exam

Aufgabe 1)

Ein Produktionsunternehmen stellt zwei Arten von Produkten her: Produkt A und Produkt B. Jedes Produkt muss durch zwei Maschinen gehen, Maschine 1 und Maschine 2. Die Zeit, die jede Maschine für jedes Produkt benötigt, ist in der folgenden Tabelle gegeben:

• Produkt A: Maschine 1: 2 Stunden, Maschine 2: 3 Stunden
• Produkt B: Maschine 1: 3 Stunden, Maschine 2: 2 Stunden

Es stehen insgesamt 120 Stunden für Maschine 1 und 100 Stunden für Maschine 2 zur Verfügung. Der Gewinn pro Produkt beträgt 40€ für Produkt A und 50€ für Produkt B. Das Unternehmen möchte den Gewinn maximieren.

a)

Identifiziere die Entscheidungsvariablen, die Zielfunktion und die Nebenbedingungen dieses Optimierungsproblems. Formuliere das Problem mathematisch.

Lösung:

Identifikation und Formulierung des Optimierungsproblems:Um das gegebene Optimierungsproblem mathematisch zu formulieren, müssen wir zunächst die Entscheidungsvariablen, die Zielfunktion und die Nebenbedingungen identifizieren und definieren. Hier ist eine Schritt-für-Schritt-Anleitung:

• Entscheidungsvariablen: Definiere die Variablen, die die Anzahl der herzustellenden Produkte darstellen:
  • \( x \rightarrow \text{Anzahl der hergestellten Einheiten von Produkt A} \)
  • \( y \rightarrow \text{Anzahl der hergestellten Einheiten von Produkt B} \)
• Zielfunktion: Die Zielfunktion ist der zu maximierende Gesamtgewinn, der sich aus der Anzahl der hergestellten Produkte und deren Gewinn pro Einheit ergibt:
  • \(\text{Maximiere}: Z = 40x + 50y \)
• Nebenbedingungen: Jede Maschine hat eine begrenzte Verfügbarkeit an Stunden, die auf die Zeit pro Produkt verteilt werden müssen:
  • Maschine 1: \( 2x + 3y \leq 120 \)
  • Maschine 2: \( 3x + 2y \leq 100 \)
  • Zusätzlich müssen beide Entscheidungsvariablen nicht-negativ sein:
    • \(x \geq 0\)
    • \(y \geq 0\)

Mathematische Formulierung des Problems:

• Entscheidungsvariablen: \( x, y \)
• Zielfunktion: \( \text{Maximiere}: Z = 40x + 50y \)
• Nebenbedingungen:
  • \( 2x + 3y \leq 120 \)
  • \( 3x + 2y \leq 100 \)
  • \( x \geq 0 \)
  • \( y \geq 0 \)

b)

Das Problem aus Teil a) soll nun mit Python unter Verwendung der Bibliothek 'PuLP' gelöst werden. Implementiere dabei die Zielfunktion und die Nebenbedingungen. Der resultierende Code könnte wie folgt aussehen:

'import pulp# Problem initialisierenproblem = pulp.LpProblem('Maximierung des Gewinns', pulp.LpMaximize)# Entscheidungsvariablenx_A = pulp.LpVariable('Produkt_A', lowBound=0, cat='Continuous')x_B = pulp.LpVariable('Produkt_B', lowBound=0, cat='Continuous')# Zielfunktionproblem += 40 * x_A + 50 * x_B, 'Gesamtgewinn'# Nebenbedingungenproblem += 2 * x_A + 3 * x_B <= 120, 'Maschine_1'problem += 3 * x_A + 2 * x_B <= 100, 'Maschine_2'# Problem lösenproblem.solve()print(f'Optimale Anzahl von Produkt A: {pulp.value(x_A)}')print(f'Optimale Anzahl von Produkt B: {pulp.value(x_B)}')print(f'Maximaler Gewinn: {pulp.value(problem.objective)}')'

Wie interpretiert man die Ergebnisse dieses Codes?

Lösung:

Interpretation der Ergebnisse des Codes:Der angegebene Python-Code löst das Optimierungsproblem mit der 'PuLP'-Bibliothek. Nachdem der Code ausgeführt wurde, liefert er die optimale Anzahl der herzustellenden Produkte A und B sowie den maximalen möglichen Gewinn. Hier ist eine detaillierte Interpretation der Ergebnisse:

• Optimale Anzahl von Produkt A:Der Ausdruck

  print(f'Optimale Anzahl von Produkt A: {pulp.value(x_A)}')

  gibt die optimale Anzahl von Einheiten an, die von Produkt A produziert werden sollten, um den Gewinn zu maximieren. Der Wert von pulp.value(x_A) ist die berechnete Menge von Produkt A.
• Optimale Anzahl von Produkt B:Der Ausdruck

  print(f'Optimale Anzahl von Produkt B: {pulp.value(x_B)}')

  gibt die optimale Anzahl von Einheiten an, die von Produkt B produziert werden sollten, um den Gewinn zu maximieren. Der Wert von pulp.value(x_B) ist die berechnete Menge von Produkt B.
• Maximaler Gewinn:Der Ausdruck

  print(f'Maximaler Gewinn: {pulp.value(problem.objective)}')

  gibt den maximalen Gewinn an, der erzielt werden kann, wenn die optimale Anzahl der Produkte A und B hergestellt wird. Der Wert von pulp.value(problem.objective) ist der berechnete maximale Gewinn.

Zusammengefasst liefert der Code also die optimale Produktionsmenge von Produkt A und Produkt B sowie den maximal erzielbaren Gewinn, basierend auf den gegebenen Maschinenzeiten und Produktionskapazitäten. Dies hilft dem Unternehmen, seine Ressourcen effizient zu nutzen und den Gewinn zu maximieren.

c)

Welche Limitationen hat der oben beschriebene Ansatz der linearen Optimierung, und wie könnten diese Limitationen in realen Herstellungsprozessen überwunden werden?

Lösung:

Limitationen des Ansatzes der linearen Optimierung und deren Überwindung in realen Herstellungsprozessen:Auch wenn der oben beschriebene Ansatz der linearen Optimierung sehr nützlich ist, um den Gewinn zu maximieren, gibt es einige Limitationen, die in realen Herstellungsprozessen beachtet werden müssen.

• Annahmen der Linearität: Der Ansatz nimmt an, dass alle Beziehungen zwischen den Variablen linear sind. In der Realität könnten jedoch Produktionszeiten, Kosten oder Gewinne nichtlinear sein. Überwindung: Verwendung von nichtlinearen Optimierungsmodellen, die eine nichtlineare Beziehung zwischen Variablen berücksichtigen.
• Statische Parameter: Die Methode geht davon aus, dass alle Parameter wie Produktionszeiten und Kapazitäten fest sind. In Wirklichkeit können diese jedoch variieren. Überwindung: Implementierung dynamischer Optimierungsmodelle, die Variationen in den Parametern berücksichtigen, oder Verwendung robuster Optimierungsansätze, die innerhalb eines bestimmten Unsicherheitsbereichs optimal sind.
• Vernachlässigung von Unsicherheiten: Der Ansatz berücksichtigt nicht mögliche Unsicherheiten und Störungen im Herstellungsprozess, wie Maschinenausfälle oder Lieferengpässe. Überwindung: Einführung stochastischer Optimierungsmodelle, die Unsicherheiten und Risiken in die Entscheidungsfindung einbeziehen, und Nutzung von Szenario-Analysen.
• Fehlende Feinheiten der Produktionslogistik: Der lineare Ansatz vernachlässigt oft logistische Feinheiten wie Lagerkapazitäten, Vorlaufzeiten und Sequenzierungsprobleme in der Produktion. Überwindung: Nutzung umfassenderer Modelle wie gemischt-ganzzähliger linearer Programmierung (MILP) oder simulationsbasierter Optimierungsansätze, die solche logistischen Details integrieren.
• Begrenzte Anpassungsfähigkeit an Änderungen: Änderungen am Modell erfordern oft eine vollständige Neuberechnung der Optimierung, was zeitaufwändig sein kann. Überwindung: Anwendung von Echtzeit-Optimierung und adaptiven Steuerungssystemen, die sich kontinuierlich an Änderungen anpassen.

Durch die Berücksichtigung dieser Limitationen und die Anwendung entsprechender fortgeschrittener Optimierungstechniken können reale Herstellungsprozesse effizienter und robuster gestaltet werden.

Aufgabe 2)

Gegeben ist folgendes lineare Optimierungsproblem:

• Zielfunktion: Maximiere Z = 3x₁ + 2x₂
• Unter den Nebenbedingungen:
  • 2x₁ + x₂ ≤ 20
  • 4x₁ + 3x₂ ≤ 42
  • 2x₁ + 5x₂ ≤ 30
  • x₁, x₂ ≥ 0

Verwende das Simplexverfahren, um das optimale Ergebnis zu bestimmen.

a)

Initialisiere das Simplexverfahren, indem Du die Nebenbedingungen in Gleichungen umwandelst, die Schlupfvariablen einführst und die Anfangsecke bestimmst. Stelle das erweiterte Tableau für die erste Iteration auf und identifiziere die Pivot-Spalte sowie die Pivot-Zeile.

Lösung:

Gegeben ist folgendes lineare Optimierungsproblem:

• Zielfunktion: Maximiere Z = 3x₁ + 2x₂
• Unter den Nebenbedingungen:
• 2x₁ + x₂ ≤ 20
• 4x₁ + 3x₂ ≤ 42
• 2x₁ + 5x₂ ≤ 30
• x₁, x₂ ≥ 0

Wir verwenden das Simplexverfahren, um das optimale Ergebnis zu bestimmen.

Um das Simplexverfahren zu initialisieren:

1. Wandel die Ungleichungen in Gleichungen um, indem Du Schlupfvariablen einführst.

Die Nebenbedingungen werden zu:

• 2x₁ + x₂ + S₁ = 20
• 4x₁ + 3x₂ + S₂ = 42
• 2x₁ + 5x₂ + S₃ = 30

Definiere die Schlupfvariablen S₁, S₂, und S₃ so, dass S₁, S₂, und S₃ ≥ 0 sind.

Die Anfangsecke (Startlösungen) wird bestimmt, wenn alle Schlupfvariablen ihren maximalen Wert annehmen und x₁ = x₂ = 0:

• x₁ = 0
• x₂ = 0
• S₁ = 20
• S₂ = 42
• S₃ = 30

Erweitertes Tableau für die erste Iteration:

|    Basis    |   x1  |  x2  |  S1  |  S2  |  S3  |  b  ||--------------|-------|-------|--------|--------|--------|----||    S1          |    2     |    1    |    1    |    0    |    0    |   20 ||    S2          |    4     |    3    |    0    |    1    |    0    |   42 ||    S3          |    2     |    5    |    0    |    0    |    1    |   30 ||--------------|-------|-------|--------|--------|--------|----||    Z              |   -3     |   -2   |    0     |    0    |    0    |    0  |

Identifizieren der Pivot-Spalte und Pivot-Zeile:

Pivot-Spalte:Die Pivot-Spalte ist die Spalte mit dem am stärksten negativen Wert in der Zielfunktion (Z-Zeile). Hier ist dies die Spalte für x₁, da der Koeffizient -3 ist.

Pivot-Zeile:Um die Pivot-Zeile zu bestimmen, berechnen wir das Verhältnis von b zu den Werten in der Pivot-Spalte (x₁):

• S₁: \(\frac{20}{2} = 10\)
• S₂: \(\frac{42}{4} = 10,5\)
• S₃: \(\frac{30}{2} = 15\)

Die geringste positive Ratio ist 10, daher ist die Pivot-Zeile die Zeile von S₁.

• Zusammengefasst:
• Pivot-Spalte: x₁
• Pivot-Zeile: S₁

Mit diesen Informationen können wir nun die erste Iteration des Simplex-Schritts durchführen.

b)

Führe die erste Pivot-Operation durch, um eine neue Basislösung zu erhalten. Erkläre jeden Schritt und zeige das neue Tableau nach der ersten Iteration. Bestimme, ob eine weitere Iteration notwendig ist oder ob die optimale Lösung erreicht wurde.

Lösung:

Gegeben ist folgendes lineare Optimierungsproblem:

• Zielfunktion: Maximiere Z = 3x₁ + 2x₂
• Unter den Nebenbedingungen:
• 2x₁ + x₂ ≤ 20
• 4x₁ + 3x₂ ≤ 42
• 2x₁ + 5x₂ ≤ 30
• x₁, x₂ ≥ 0

Wir verwenden das Simplexverfahren, um das optimale Ergebnis zu bestimmen.

Erste Iteration des Simplexverfahrens:

Das ursprüngliche Tableau lautet:

|    Basis    |   x1  |  x2  |  S1  |  S2  |  S3  |  b  ||--------------|-------|-------|--------|--------|--------|----||    S1          |    2     |    1    |    1    |    0    |    0    |   20 ||    S2          |    4     |    3    |    0    |    1    |    0    |   42 ||    S3          |    2     |    5    |    0    |    0    |    1    |   30 ||--------------|-------|-------|--------|--------|--------|----||    Z              |   -3     |   -2   |    0     |    0    |    0    |    0  |

Ermittlung der Pivot-Spalte und Pivot-ZeilePivot-Spalte: x₁ (der negativste Koeffizient in der Zielfunktion, Z = -3)

Pivot-Zeile: Finde das kleinste Verhältnis von b zu den Werten in der Pivot-Spalte (x₁):

• S₁: \( \frac{20}{2} = 10 \)
• S₂: \( \frac{42}{4} = 10.5 \)
• S₃: \( \frac{30}{2} = 15 \)

Die Pivot-Zeile ist S₁ (kleinstes positives Verhältnis, 10).

Pivot-Operation:

• Wir transformieren die Pivot-Zeile (S₁), indem wir durch das Pivot-Element (2) teilen.

|    Basis    |   x1  |  x2  |  S1  |  S2  |  S3  |  b  ||--------------|-------|-------|--------|--------|--------|-------||    x1          |    1     |    0.5  |    0.5  |    0    |    0    |   10 ||    S2          |    4     |    3    |    0    |    1    |    0    |   42 ||    S3          |    2     |    5    |    0    |    0    |    1    |   30 ||--------------|-------|-------|--------|--------|--------|-------||    Z              |   -3     |   -2   |    0     |    0    |    0    |    0  |

• Nun transformieren wir die anderen Zeilen so, dass die Einträge in der Pivot-Spalte 0 werden:
• Neue S₂-Zeile: Alte S₂-Zeile - 4 * transformierte S₁-Zeile
• Neue S₃-Zeile: Alte S₃-Zeile - 2 * transformierte S₁-Zeile
• Neue Z-Zeile: Alte Z-Zeile + 3 * transformierte S₁-Zeile

|    Basis    |   x1  |  x2  |  S1  |  S2  |  S3  |  b  ||--------------|-------|-------|--------|--------|--------|-------||    x1          |    1     |    0.5  |    0.5  |    0    |    0    |   10 ||    S2          |    0     |    1    |    -2   |    1    |    0    |    2 ||    S3          |    0     |    4    |    -1   |    0    |    1    |   10 ||--------------|-------|-------|--------|--------|--------|-------||    Z              |    0     |   -0.5 |    1.5  |    0    |    0    |   30 |

Bestimmen ob eine weitere Iteration notwendig ist:Eine weitere Iteration ist erforderlich, da es in der Zielfunktion noch negative Koeffizienten gibt (hier -0,5 in der x₂-Spalte).

Aufgabe 3)

Ein Unternehmen stellt zwei Produkte her, A und B. Produktionszeiten und Gewinne je Produkt sowie verfügbare Ressourcen sind folgende:

• Produkt A benötigt 1 Stunde pro Stück mit einem Gewinn von 10€.
• Produkt B benötigt 2 Stunden pro Stück mit einem Gewinn von 15€.
• Insgesamt stehen 8 Stunden Produktionszeit zur Verfügung.

Formuliere das primale lineare Programm (LP) zur Gewinnmaximierung und ermittle die Lösung mittels Simplex-Methode.

a)

Formuliere das zugehörige Dualproblem. Spezifizieren die Dualvariablen und ihre Bedeutung für das ursprüngliche Problem.

Lösung:

Um das Dualproblem eines linearen Programms zu formulieren, müssen die Einschränkungen und das Ziel des primären Problems (Primalproblem) in Variablen und Elemente des Dualproblems umgeschrieben werden. Hier ist die ursprüngliche Formulierung des Primärproblems:

• Primärproblem (Primal)

• Produkte A und B

• Gewinnmaximierung: Maximiere Z = 10A + 15B

• Einschränkungen: Nutzung der Produktionszeit: A + 2B ≤ 8 (Produktionszeitbeschränkung) 1. A ≥ 0 (Nichtnegativitätsbedingung)
• 2. B ≥ 0 (Nichtnegativitätsbedingung)

Das zugehörige Dualproblem basiert auf diesen Einschränkungen:

Dualproblem

Minimiere W = 8U

Einführung der Dualvariablen y, die der Einschränkung des Primärenproblems entsprechen:

Dualvariablen:

U = Dualvariable für die Produktionszeit

Dualbedingungen:

1. U ≥ 10 (für Produkt A)

2. U ≥ 7.5 (für Produkt B)

Zusammengefasst ist das Dualproblem:

Minimiere W = 8U Beschränkungen: 1. U ≥ 10 2.U ≥ 7.5

b)

Führe eine Sensitivitätsanalyse durch: Analysiere die Auswirkungen, wenn die Produktionskapazität von 8 auf 10 Stunden erhöht wird. Bestimme die neuen Schattenpreise und diskutiere die wirtschaftlichen Auswirkungen dieser Änderung.

Lösung:

Um eine Sensitivitätsanalyse durchzuführen, wenn die Produktionskapazität von 8 auf 10 Stunden erhöht wird, müssen wir zunächst das ursprüngliche primale lineare Programm (LP) lösen und die Schattenpreise bestimmen. Dies ermöglicht uns, die Auswirkungen der Änderung der Produktionskapazität zu verstehen.

Ursprüngliches Primalproblem (LP)

• Maximiere den Gewinn Z = 10A + 15B
• Unter den Einschränkungen:
• A + 2B ≤ 8
• A ≥ 0
• B ≥ 0

Wir müssen dieses Problem mit der Simplex-Methode lösen, um die optimale Lösung und die Schattenpreise zu bestimmen. Danach analysieren wir die Änderung der Produktionskapazität.

Schritt 1: Lösung des ursprünglichen Problems

Angenommen, die Lösung der Simplex-Methode ergibt: (A, B) = (0, 4) mit Z = 60.

Der Schattenpreis (oder dualer Wert) für die Produktionszeitbeschränkung (A + 2B ≤ 8) ist der Betrag, um den sich der Gewinn Z ändern würde, wenn die verfügbare Produktionszeit um eine Einheit erhöht wird. Angenommen, der Schattenpreis ist 7,5 Euro.

Schritt 2: Erhöhen der Produktionskapazität von 8 auf 10 Stunden

• Die neue Einschränkung lautet: A + 2B ≤ 10

Wir lösen jetzt das neue LP:

• Maximiere den Gewinn Z = 10A + 15B
• Unter den Einschränkungen:
• A + 2B ≤ 10
• A ≥ 0
• B ≥ 0

Durch Anwendung der Simplex-Methode auf dieses neue Problem erhalten wir eine neue optimale Lösung. Nehmen wir an, die neue Lösung ist (A, B) = (0, 5) mit Z = 75.

Neue Schattenpreise

Die Schattenpreise können sich ändern, da die Erhöhung der Ressourcenkapazität den marginalen Wert der Ressource beeinflusst. In diesem Fall müsste der Schattenpreis neu berechnet werden, was über erneute Anwendung der Dualitätsanalyse erfolgt.

Angenommen, der neue Schattenpreis beträgt 6 Euro.

Wirtschaftliche Auswirkungen der Änderung

• Der maximale Gewinn erhöht sich von 60 Euro auf 75 Euro, was eine direkte Folge der Erhöhung der Produktionskapazität ist.
• Der neue Schattenpreis von 6 Euro deutet darauf hin, dass der Wert einer zusätzlichen Produktionsstunde gesunken ist. Dies liegt daran, dass die Knappheit der Ressource (Produktionszeit) bei einer höheren Kapazität (10 Stunden) geringer ist.
• Die Produktionszeit ist nun weniger knapp, was wirtschaftlich bedeutet, dass die zusätzliche Kapazität weniger effektiv zur Gewinnsteigerung beiträgt als vorher.

Insgesamt zeigt die Sensitivitätsanalyse, dass die Erhöhung der Produktionskapazität zu höheren Gewinnen führt, jedoch den marginalen Nutzen zusätzlicher Produktionszeit verringert.

Aufgabe 4)

Gegeben sei ein zusammenhängender, ungerichteter Graph G = (V, E) mit Knoten V und Kanten E. Die Kanten haben Gewichte, die Entfernungen zwischen den Knoten darstellen. Dieser Graph soll analysiert werden, um sowohl den minimalen Spannbaum (MST) zu finden als auch die kürzesten Wege zwischen allen Knoten zu bestimmen.

a)

Wende den Prim-Algorithmus auf diesen Graphen an, um den minimalen Spannbaum zu finden. Erkläre jeden Schritt und berechne die Gesamtlänge des minimalen Spannbaums.

Lösung:

Um den Prim-Algorithmus auf den gegebenen Graphen G = (V, E) anzuwenden, um den minimalen Spannbaum (MST) zu finden, müssen wir folgende Schritte durchführen:

• Beginn mit einem beliebigen Startknoten.
• Füge den Startknoten zur Menge der bereits besuchten Knoten hinzu.
• Wähle die Kante mit dem geringsten Gewicht, die einen bereits besuchten Knoten mit einem noch nicht besuchten Knoten verbindet.
• Füge diese Kante und den neuen Knoten zum MST hinzu.
• Wiederhole die Schritte 3 und 4, bis alle Knoten besucht wurden.

Hier ist eine detaillierte Erklärung der Schritte am Beispiel eines hypothetischen Graphen:

 V = {A, B, C, D, E} E = { (A, B, 1), (A, C, 3), (B, C, 3), (B, D, 6), (C, D, 4), (C, E, 2), (D, E, 5) } 

1. Wir starten mit Knoten A. Der MST enthält bisher nur den Knoten A.
2. Von A aus sind die möglichen Kanten (A, B, 1) und (A, C, 3). Wähle die Kante mit dem geringsten Gewicht: (A, B, 1). Der MST enthält jetzt die Kanten {(A, B, 1)} und die Knoten {A, B}.
3. Nun betrachten wir die Kanten, die die Knoten A oder B mit einem neuen Knoten verbinden: (A, C, 3), (B, C, 3), und (B, D, 6). Wähle die Kante (A, C, 3). Der MST enthält jetzt die Kanten {(A, B, 1), (A, C, 3)} und die Knoten {A, B, C}.
4. Als nächstes betrachten wir die neuen möglichen Kanten: (B, D, 6), (C, D, 4), und (C, E, 2). Wähle die Kante (C, E, 2). Der MST enthält jetzt die Kanten {(A, B, 1), (A, C, 3), (C, E, 2)} und die Knoten {A, B, C, E}.
5. Jetzt sind die verbleibenden Kanten (B, D, 6) und (C, D, 4). Wähle die Kante (C, D, 4). Der MST enthält jetzt die Kanten {(A, B, 1), (A, C, 3), (C, E, 2), (C, D, 4)} und alle Knoten {A, B, C, D, E}.

Der Prim-Algorithmus ist nun abgeschlossen, da alle Knoten besucht wurden. Der minimale Spannbaum besteht aus den Kanten {(A, B, 1), (A, C, 3), (C, E, 2), (C, D, 4)}.

Die Gesamtlänge des minimalen Spannbaums ist die Summe der Gewichte dieser Kanten:

 1 + 3 + 2 + 4 = 10 

Der minimale Spannbaum hat also eine Gesamtlänge von 10.

b)

Nutze den Kruskal-Algorithmus, um denselben minimalen Spannbaum zu berechnen. Vergleiche die Schritte und Ergebnisse dieses Algorithmus mit dem Prim-Algorithmus.

Lösung:

Um den Kruskal-Algorithmus auf den gegebenen Graphen G = (V, E) anzuwenden, um den minimalen Spannbaum (MST) zu finden, müssen wir folgende Schritte durchführen:

• Sortiere alle Kanten nach zunehmendem Gewicht.
• Beginne mit einem leeren MST.
• Durchlaufe die sortierten Kanten und füge sie zum MST hinzu, solange sie keinen Zyklus bilden.
• Wiederhole den vorherigen Schritt, bis der MST alle Knoten verbunden hat.

Hier ist eine detaillierte Erklärung der Schritte am Beispiel desselben hypothetischen Graphen:

 V = {A, B, C, D, E} E = { (A, B, 1), (A, C, 3), (B, C, 3), (B, D, 6), (C, D, 4), (C, E, 2), (D, E, 5) } 

• Sortiere die Kanten nach Gewicht: (A, B, 1), (C, E, 2), (A, C, 3), (B, C, 3), (C, D, 4), (D, E, 5), (B, D, 6).
• Beginne mit einem leeren MST.
• Füge die kleinste Kante (A, B, 1) zum MST hinzu. Der MST enthält jetzt {(A, B, 1)}.
• Füge die nächste Kante (C, E, 2) hinzu. Der MST enthält jetzt {(A, B, 1), (C, E, 2)}.
• Die nächste Kante ist (A, C, 3). Da sie keinen Zyklus bildet, füge sie hinzu. Der MST enthält jetzt {(A, B, 1), (C, E, 2), (A, C, 3)}.
• Die nächste Kante ist (B, C, 3). Diese Kante würde einen Zyklus bilden, also überspringe sie.
• Füge die nächste Kante (C, D, 4) hinzu, da sie keinen Zyklus bildet. Der MST enthält jetzt {(A, B, 1), (C, E, 2), (A, C, 3), (C, D, 4)}.
• Die verbleibenden Kanten (D, E, 5) und (B, D, 6) würden in jedem Fall einen Zyklus bilden, also überspringe sie.

Der Kruskal-Algorithmus ist nun abgeschlossen, da alle Knoten verbunden sind. Der minimale Spannbaum besteht aus denselben Kanten wie beim Prim-Algorithmus: {(A, B, 1), (C, E, 2), (A, C, 3), (C, D, 4)}.

Die Gesamtlänge des minimalen Spannbaums ist die Summe der Gewichte dieser Kanten:

 1 + 3 + 2 + 4 = 10 

Die Schritte und Ergebnisse der beiden Algorithmen unterscheiden sich wie folgt:

• Prim-Algorithmus: Beginnt mit einem beliebigen Startknoten und erweitert den MST Schritt für Schritt, indem die Kanten hinzugefügt werden, die den geringsten Abstand zu den bereits hinzugefügten Knoten haben.
• Kruskal-Algorithmus: Sortiert alle Kanten nach Gewicht und fügt die kleinsten Kanten hinzu, solange sie keine Zyklen bilden, bis alle Knoten verbunden sind.

Beide Algorithmen führen zu demselben minimalen Spannbaum mit derselben Gesamtlänge.

c)

Bestimme mithilfe des Dijkstra-Algorithmus den kürzesten Weg von einem Startknoten zu allen anderen Knoten. Zeige deine Berechnungen und beschreibe den Algorithmus detailliert.

Lösung:

Um den Dijkstra-Algorithmus anzuwenden, um die kürzesten Wege von einem Startknoten zu allen anderen Knoten in einem zusammenhängenden, ungerichteten Graphen G = (V, E) zu bestimmen, folgen wir den folgenden Schritten:

• Initialisiere die Entfernungen: Setze die Entfernung des Startknotens zu sich selbst auf 0 und zu allen anderen Knoten auf unendlich.
• Füge alle Knoten in eine Prioritätswarteschlange ein, die nach den aktuellen Entfernungen sortiert ist.
• Wähle den Knoten mit der kleinsten Entfernung aus der Warteschlange.
• Aktualisiere die Entfernungen der benachbarten Knoten des gewählten Knotens.
• Wiederhole die Schritte 3 und 4, bis die Warteschlange leer ist.

Hier ist eine detaillierte Erklärung der Schritte am Beispiel eines hypothetischen Graphen:

 V = {A, B, C, D, E} E = { (A, B, 1), (A, C, 4), (B, C, 2), (B, D, 5), (C, D, 1), (D, E, 3) } 

Wir wählen A als Startknoten.

1. Initialisiere die Entfernungen:

    Dist(A) = 0 Dist(B) = ∞ Dist(C) = ∞ Dist(D) = ∞ Dist(E) = ∞  

2. Füge alle Knoten in eine Prioritätswarteschlange ein:

    {A(0), B(∞), C(∞), D(∞), E(∞)} 

3. Wähle den Knoten A (0) aus der Warteschlange.
4. Aktualisiere die Entfernungen der benachbarten Knoten von A:

    Dist(B) = Min(∞, 0+1) = 1 Dist(C) = Min(∞, 0+4) = 4 

   Die Prioritätswarteschlange ist jetzt:

    {B(1), C(4), D(∞), E(∞)} 

5. Wähle den Knoten B (1) aus der Warteschlange.
6. Aktualisiere die Entfernungen der benachbarten Knoten von B:

    Dist(C) = Min(4, 1+2) = 3 Dist(D) = Min(∞, 1+5) = 6 

   Die Prioritätswarteschlange ist jetzt:

    {C(3), C(4), D(6), E(∞)} 

7. Wähle den Knoten C (3) aus der Warteschlange.
8. Aktualisiere die Entfernungen der benachbarten Knoten von C:

    Dist(D) = Min(6, 3+1) = 4 

   Die Prioritätswarteschlange ist jetzt:

    {D(4), D(6), E(∞)} 

9. Wähle den Knoten D (4) aus der Warteschlange.
10. Aktualisiere die Entfernungen der benachbarten Knoten von D:

     Dist(E) = Min(∞, 4+3) = 7 

    Die Prioritätswarteschlange ist jetzt:

     {E(7)} 

11. Wähle den Knoten E (7) aus der Warteschlange. Die Prioritätswarteschlange ist jetzt leer, und der Algorithmus ist abgeschlossen.

Die kürzesten Entfernungen von A zu allen anderen Knoten sind:

 Dist(A) = 0 Dist(B) = 1 Dist(C) = 3 Dist(D) = 4 Dist(E) = 7 

Dies zeigt die durch den Dijkstra-Algorithmus gefundenen kürzesten Wege von A zu allen anderen Knoten im Graphen.

d)

Analysiere den gegebenen Graphen mithilfe des Bellman-Ford-Algorithmus. Überprüfe, ob negative Gewichtskreise existieren und erkläre, wie der Algorithmus darauf reagiert.

Lösung:

Um den Bellman-Ford-Algorithmus für die Analyse des gegebenen Graphen G = (V, E) zu verwenden, müssen wir folgende Schritte durchführen:

• Setze die Entfernung des Startknotens zu sich selbst auf 0 und zu allen anderen Knoten auf unendlich.
• Durchlaufe alle Kanten des Graphen V-1 Mal und aktualisiere die Entfernungen entsprechend.
• Überprüfe nach V-1 Durchläufen, ob es noch minimale Entfernungen über eine Kante gibt. Wenn ja, existiert ein negativer Gewichtskreis im Graphen.

Hier ist eine detaillierte Erklärung der Schritte am Beispiel eines hypothetischen Graphen:

 V = {A, B, C, D, E} E = {(A, B, 1), (A, C, 4), (B, C, -3), (B, D, 2), (D, C, 1), (D, E, 3)} 

Wir wählen A als Startknoten.

1. Initialisiere die Entfernungen:

    Dist(A) = 0 Dist(B) = ∞ Dist(C) = ∞ Dist(D) = ∞ Dist(E) = ∞  

2. Durchlaufe alle Kanten V-1 Mal (hier 4 Mal, da V = 5):

Erster Durchlauf:

• Aktualisiere Dist(B) über (A, B): Min(∞, 0+1) = 1
• Aktualisiere Dist(C) über (A, C): Min(∞, 0+4) = 4
• Aktualisiere Dist(C) über (B, C): Min(4, 1-3) = -2
• Aktualisiere Dist(D) über (B, D): Min(∞, 1+2) = 3
• Aktualisiere Dist(C) über (D, C): Min(-2, 3+1) = -2 (Dist wird hier nicht weiter aktualisiert)
• Aktualisiere Dist(E) über (D, E): Min(∞, 3+3) = 6

 Dist(A) = 0 Dist(B) = 1 Dist(C) = -2 Dist(D) = 3 Dist(E) = 6 

Zweiter Durchlauf bis vierter Durchlauf:

• Kein weiteres Update, da alle Pfeilableitungen bereits minimale Werte haben

Zum Schluss überprüfe auf negative Gewichtskreise:

1. Gehe alle Kanten einmal durch und checke, ob eine weitere minimale Distanz gefunden werden kann; z.B (B, C) Min (-2, 1 -3) nicht möglich und so iteriere weiter

 Dist(A) = 0 Dist(B) = 1 Dist(C) = -2 Dist(D) = 3 Dist(E) = 6 

Da keine weiteren Updates vorhanden war, kann man sicherstellen, dass keine negative Gewichtskreise existieren.

Wenn in der letzten Überprüfung eine Kanten noch Optimierung verfügbar wäre, würde dies auf einen negativen Gewichtskreis hinweisen und der Bellman-Ford-Algorithmus würde für negative Kreise nicht funktionieren.