Combinatorial optimization - Exam

Aufgabe 1)

Du bist beauftragt, einen Greedy-Algorithmus für ein Netzwerk zu entwerfen. Dabei sind Dir folgende Informationen bekannt: Der Kruskal-Algorithmus wird verwendet, um einen minimalen Spannbaum für das Netzwerk zu finden, und der Dijkstra-Algorithmus hilft, die kürzesten Wege von einem Startknoten zu allen anderen Knoten zu berechnen. Im Netzwerk befinden sich 5 Knoten und 7 Kanten mit den folgenden Gewichten: (A-B: 4, A-C: 2, B-C: 1, B-D: 5, C-D: 8, C-E: 10, D-E: 2).Da beide Algorithmen auf dem Greedy-Prinzip basieren, triffst Du in jedem Schritt eine lokal optimale Wahl in der Hoffnung, dass diese zu einer global optimalen Lösung führt.

a)

a) Wende den Kruskal-Algorithmus auf das Netzwerk an, um den minimalen Spannbaum zu berechnen. Gib die Schritte und das finale Ergebnis an. Zeige die Reihenfolge der Kanten, die hinzugefügt werden, und erläutere, warum jede Kante hinzugefügt oder nicht hinzugefügt wurde.

Lösung:

Um den minimalen Spannbaum (Minimum Spanning Tree, MST) für das Netzwerk mit dem Kruskal-Algorithmus zu berechnen, folge bitte den folgenden Schritten:

• Sortiere die Kanten des Netzwerks in aufsteigender Reihenfolge ihrer Gewichte:
• A-C (2)
• B-C (1)
• D-E (2)
• A-B (4)
• B-D (5)
• C-D (8)
• C-E (10)
• Initialisiere eine leere Menge für den MST.
• Iteriere durch die sortierten Kanten und füge jede Kante hinzu, die keinen Zyklus bildet, bis der MST alle Knoten enthält.

Hier sind die Schritte:

• Schritt 1: Hinzufügen der Kante B-C (1), bildet keinen Zyklus. MST: {(B, C, 1)}
• Schritt 2: Hinzufügen der Kante A-C (2), bildet keinen Zyklus. MST: {(B, C, 1), (A, C, 2)}
• Schritt 3: Hinzufügen der Kante D-E (2), bildet keinen Zyklus. MST: {(B, C, 1), (A, C, 2), (D, E, 2)}
• Schritt 4: Hinzufügen der Kante A-B (4), bildet keinen Zyklus. MST: {(B, C, 1), (A, C, 2), (D, E, 2), (A, B, 4)}
• Schritt 5: Die Kante B-D (5) wird nicht hinzugefügt, da sie einen Zyklus bilden würde.
• Schritt 6: Die Kante C-D (8) wird nicht hinzugefügt, da sie einen Zyklus bilden würde.
• Schritt 7: Die Kante C-E (10) wird nicht hinzugefügt, da sie einen Zyklus bilden würde.

Finales Ergebnis des MST:

• Kanten: {(B, C, 1), (A, C, 2), (D, E, 2), (A, B, 4)}
• Kosten: 1 + 2 + 2 + 4 = 9

Wir haben also den minimalen Spannbaum für das Netzwerk mit den Kanten {(B, C, 1), (A, C, 2), (D, E, 2), (A, B, 4)} und den Gesamtkosten von 9 gefunden.

b)

b) Berechne die kürzesten Wege von Knoten A zu allen anderen Knoten im Netzwerk unter Anwendung des Dijkstra-Algorithmus. Gib die einzelnen Schritte und die finalen kürzesten Wege sowie deren Kosten an.

Lösung:

Um die kürzesten Wege von Knoten A zu allen anderen Knoten im Netzwerk zu berechnen, wenden wir den Dijkstra-Algorithmus an. Hier sind die Schritte:

• Initialisiert werden die Entfernungen zu allen Knoten mit unendlich, außer dem Startknoten A, der auf 0 gesetzt wird. Ein Besuchsknoten-Set wird initialisiert, um besuchte Knoten zu verfolgen.
• Schritt 1: Startknoten A hat eine Entfernung von 0. Von A aus erreichbare Knoten sind B (4) und C (2). Aktualisiere die Entfernungen:
  • Entfernung zu B: min(unendlich, 0 + 4) = 4
  • Entfernung zu C: min(unendlich, 0 + 2) = 2
  Besuchte Knoten: {A}
• Schritt 2: Der aktuelle Knoten mit der kürzesten Entfernung ist C (2). Von C aus erreichbare Knoten sind B (1), D (8), und E (10). Aktualisiere die Entfernungen:
  • Entfernung zu B: min(4, 2 + 1) = 3
  • Entfernung zu D: min(unendlich, 2 + 8) = 10
  • Entfernung zu E: min(unendlich, 2 + 10) = 12
  Besuchte Knoten: {A, C}
• Schritt 3: Der aktuelle Knoten mit der kürzesten Entfernung ist B (3). Von B aus erreichbare Knoten sind D (5). Aktualisiere die Entfernung:
  • Entfernung zu D: min(10, 3 + 5) = 8
  Besuchte Knoten: {A, B, C}
• Schritt 4: Der aktuelle Knoten mit der kürzesten Entfernung ist D (8). Von D aus erreichbare Knoten ist E (2). Aktualisiere die Entfernung:
  • Entfernung zu E: min(12, 8 + 2) = 10
  Besuchte Knoten: {A, B, C, D}
• Schritt 5: Der verbleibende Knoten ist E (10), aber da alle Knoten bereits besucht wurden, beenden wir hier.

Finale kürzeste Wege und deren Kosten:

• Kürzester Weg von A nach B: 3
• Kürzester Weg von A nach C: 2
• Kürzester Weg von A nach D: 8
• Kürzester Weg von A nach E: 10

Fazit: Der Dijkstra-Algorithmus liefert die kürzesten Wege von Knoten A zu allen anderen Knoten mit den Kosten:

• A nach B: 3
• A nach C: 2
• A nach D: 8
• A nach E: 10

c)

c) Diskutiere inwieweit die Greedy-Strategie der beiden verwendeten Algorithmen zum global optimalen Ergebnis führt. Erläutere die spezifischen Voraussetzungen, unter denen die Greedy-Methoden in diesen Beispielen erfolgreich sind und in welchen Situationen sie möglicherweise fehlschlagen könnten.

Lösung:

Die Greedy-Strategie basiert darauf, in jedem Schritt eine lokal optimale Wahl zu treffen, mit der Hoffnung, dass diese zu einer global optimalen Lösung führt. Lassen Sie uns im Kontext der beiden verwendeten Algorithmen — Kruskal und Dijkstra — diskutieren, wie diese Strategie zum global optimalen Ergebnis führt oder in welchen Situationen sie möglicherweise fehlschlägt.

Kruskal-Algorithmus

Der Kruskal-Algorithmus ist darauf ausgelegt, einen minimalen Spannbaum zu finden. Dies gelingt, indem Kanten in aufsteigender Reihenfolge ihres Gewichts hinzugefügt werden, solange sie keinen Zyklus bilden.

Erfolgsfaktoren:

• Lokale Optimalität: In jedem Schritt wird die leichteste verfügbare Kante gewählt, die keinen Zyklus erzeugt, was eine lokal optimale Auswahl ist.
• Globale Optimalität: Der Algorithmus führt immer zu einem minimalen Spannbaum, da die Auswahl der leichtesten Kanten das Gesamtkosten minimiert. Dieser Algorithmus wird immer zu einem global optimalen Ergebnis führen, sofern die Kanten sortiert und korrekt verarbeitet werden.

Fehlerquellen:

• Geteilte Graphen: Wenn der Graph nicht zusammenhängend ist, also nicht alle Knoten miteinander verbunden sind, kann der Algorithmus scheitern, da er keinen zusammenhängenden Spannbaum erzeugen kann.

Dijkstra-Algorithmus

Der Dijkstra-Algorithmus hilft, die kürzesten Wege von einem Startknoten zu allen anderen Knoten zu berechnen. Auch dieser Algorithmus trifft in jedem Schritt eine lokal optimale Wahl, indem er den unbesuchten Knoten mit der kleinsten bekannten Entfernung auswählt.

Erfolgsfaktoren:

• Lokale Optimalität: In jedem Schritt wird der Knoten mit der geringsten Entfernung vom Startknoten ausgewählt, was eine lokal optimale Entscheidung darstellt.
• Globale Optimalität: Der Algorithmus garantiert die kürzeste Entfernung zu jedem Knoten, sofern alle Kanten nichtnegative Gewichte haben. Er führt immer zu einem global optimalen Ergebnis, wenn diese Bedingung erfüllt ist.

Fehlerquellen:

• Negative Gewichte: Wenn der Graph negative Kantengewichte enthält, kann der Dijkstra-Algorithmus falsche Ergebnisse liefern, da die lokal optimale Wahl nicht garantiert global optimal ist. In solchen Fällen ist der Bellman-Ford-Algorithmus eine bessere Wahl.

Zusammenfassung

Die Greedy-Methoden der Kruskal- und Dijkstra-Algorithmen führen unter den richtigen Voraussetzungen zu global optimalen Ergebnissen. Der Kruskal-Algorithmus funktioniert hervorragend für zusammenhängende Graphen und führt immer zum minimalen Spannbaum. Der Dijkstra-Algorithmus ist optimal für Graphen mit nichtnegativen Gewichten, garantiert jedoch nicht das beste Ergebnis für Graphen mit negativen Gewichten. Durch das Verständnis der Voraussetzungen und Einschränkungen kann die Effektivität der Greedy-Algorithmen maximiert werden.

Aufgabe 2)

Ein Transportunternehmen muss Waren von einem Lagerhaus zu mehreren Kunden liefern. Die Lieferkosten zwischen den verschiedenen Punkten sind unterschiedlich und im Voraus bekannt. Das Unternehmen möchte die Route so planen, dass die gesamten Lieferkosten minimiert werden. Verwende die dynamische Programmierung, um dieses Problem zu lösen.

Du hast folgende Kostenmatrix für die Wege zwischen den Punkten:

    0   2   9  10    1   0   6   4   15   7   0   8    6   3  12   0

a)

Teilaufgabe 1: Entwickle eine rekursive Formel zur Bestimmung der minimalen Lieferkosten. Erkläre detailliert die Variablen und Parameter in dieser Formel. Welche grundlegenden Prinzipien der dynamischen Programmierung nutzt Du hierbei?

Lösung:

Um die minimalen Lieferkosten mit dynamischer Programmierung zu berechnen, betrachten wir das Problem als das „Travelling Salesman Problem“ (TSP, das Problem des Handlungsreisenden). Hier sind die Schritte zur Entwicklung einer rekursiven Formel zur Bestimmung der minimalen Lieferkosten:

• Variablen und Parameter:
• C(i, j): Kosten von Punkt i zu Punkt j
• dp[mask][i]: minimale Lieferkosten für die Route, die die Punkte abdeckt, die in mask vorhanden sind, und in i endet
• mask: eine Bitmaske, die anzeigt, welche Punkte besucht wurden (1 bedeutet besucht, 0 bedeutet nicht besucht)
• n: Anzahl der Punkte
• Unser Ziel ist es, eine rekursive Formel zu entwickeln, die die minimalen Kosten für die Route berechnet.

Rekursive Formel:

dp[mask][i] = min(dp[mask ^ (1 << i)][j] + C(j, i) for all j, where mask[j] is true and j ≠ i)

• Hierbei ist:
• dp[mask ^ (1 << i)][j]: der Minimalkostenwert für die Teilroute ohne den Punkt i, die in j endet
• C(j, i): die Kosten vom Punkt j zum Punkt i

Diese Rekursion basiert auf der Tatsache, dass das Problem durch Unterprobleme gelöst werden kann, indem für jede mögliche Endstation die besten vorherigen Endstationen und deren Kosten verglichen werden, um die minimalen Lieferkosten zu berechnen.

Wir nutzen hierbei die folgenden grundlegenden Prinzipien der dynamischen Programmierung:

• Optimalteilstruktur: Das Problem kann in kleinere, überlappende Teilprobleme zerlegt werden, die jeweils optimal gelöst werden müssen. Dies wird genutzt, indem wir die Kosten für kürzere Routen speichern und diese zur Berechnung längerer Routen verwenden.
• Memoization: Zwischenresultate werden gespeichert, um mehrfaches Berechnen derselben Werte zu vermeiden und somit die Gesamtrechenzeit zu reduzieren.

b)

Teilaufgabe 2: Implementiere einen Algorithmus in Python unter Verwendung der zuvor entwickelten rekursiven Formel. Der Algorithmus soll die minimalen Lieferkosten zwischen allen Punkten berechnen. Stelle sicher, dass Du Memoisierung verwendest, um die Berechnungseffizienz zu maximieren.

def minimize_delivery_cost(cost_matrix):    n = len(cost_matrix)    memo = {}    def recur(i, j):        if (i, j) in memo:            return memo[(i, j)]        if i == j:            result = cost_matrix[i][j]        else:            result = min(recur(i-1, j), recur(i, j-1)) + cost_matrix[i][j]        memo[(i, j)] = result        return result    return recur(n-1, n-1)# Beispielkostenmatrixcost_matrix = [    [0, 2, 9, 10],    [1, 0, 6, 4],    [15, 7, 0, 8],    [6, 3, 12, 0]]print(minimize_delivery_cost(cost_matrix))

Lösung:

Um die minimalen Lieferkosten mithilfe dynamischer Programmierung zu berechnen, können wir die rekursive Formel, die wir in Teilaufgabe 1 entwickelt haben, implementieren. Wir nutzen Memoisierung, um sicherzustellen, dass die Berechnungseffizienz maximiert wird. Hier ist der Python-Code zur Lösung des Problems:

def minimize_delivery_cost(cost_matrix):    n = len(cost_matrix)    memo = {}    def tsp(mask, pos):        if (mask, pos) in memo:            return memo[(mask, pos)]        if mask == (1 << n) - 1:  # Alle Punkte besucht            return cost_matrix[pos][0]  # Zurück zum Start        min_cost = float('inf')        for city in range(n):            if mask & (1 << city) == 0:  # Wenn die Stadt nicht besucht wurde                new_cost = cost_matrix[pos][city] + tsp(mask | (1 << city), city)                min_cost = min(min_cost, new_cost)        memo[(mask, pos)] = min_cost        return min_cost    return tsp(1, 0)  # Startposition bei Punkt 0 mit besuchter Bitmaske 1# Beispielkostenmatrixcost_matrix = [    [0, 2, 9, 10],    [1, 0, 6, 4],    [15, 7, 0, 8],    [6, 3, 12, 0]]print(minimize_delivery_cost(cost_matrix))

In diesem Algorithmus:

• Wir verwenden memo, ein Dictionary, um die bereits berechneten Routen mit ihren entsprechenden Kosten zu speichern.
• Die Funktion tsp(mask, pos) berechnet die minimalen Lieferkosten für die Route, die die in der Bitmaske mask angegebenen Punkte besucht hat und bei pos endet.
• Wenn alle Punkte besucht wurden (mask == (1 << n) - 1), kehrt die Funktion zum Startpunkt zurück und summiert die entsprechenden Kosten.
• Die Schleife for city in range(n) versucht, alle möglichen nächsten Ziele hinzuzufügen, die noch nicht besucht wurden, und aktualisiert die minimalen Kosten entsprechend.
• Bei jedem rekursiven Aufruf wird das Ergebnis in memo gespeichert, um doppelte Berechnungen zu vermeiden.

Mit diesem Algorithmus kann das Transportunternehmen die minimalen Lieferkosten effizient berechnen.

Aufgabe 3)

Gegeben sei das folgende Optimierungsproblem eines Unternehmens, das eine Produktionslinie für zwei Produkte steuern möchte. Die Produktionslinie kann entweder Produkt A oder Produkt B pro Zeiteinheit produzieren, jedoch nicht beide gleichzeitig. Das Unternehmen möchte den Gewinn maximieren, wobei der Gewinn pro Einheit von Produkt A 50€ beträgt und für Produkt B 40€. Die Produktionskapazität für A und B pro Woche ist durch die Arbeitsstunden der Maschinen beschränkt: mindestens 10 Stunden für A (jedoch nicht mehr als 40 Stunden) und mindestens 20 Stunden für B (jedoch nicht mehr als 60 Stunden). Insgesamt stehen pro Woche 70 Produktionsstunden zur Verfügung.

a)

Teilaufgabe 1: Formuliere das Problem als lineares Optimierungsproblem (LP). Definiere die Entscheidungsvariablen, die Zielfunktion sowie die Nebenbedingungen.

Lösung:

Hier ist die Lösung für Teilaufgabe 1: Formuliere das Problem als lineares Optimierungsproblem (LP):

• Entscheidungsvariablen:

Lass uns die Stunden, die pro Woche für die Produktion von Produkt A und Produkt B aufgewendet werden, als Entscheidungsvariablen definieren:

• \(x \text{ = Anzahl der Stunden pro Woche für die Produktion von Produkt A}\)
• \(y \text{ = Anzahl der Stunden pro Woche für die Produktion von Produkt B}\)

• Zielfunktion:
• Der Gewinn, den das Unternehmen maximieren möchte, beträgt 50€ pro Stunde für Produkt A und 40€ pro Stunde für Produkt B. Die Zielfunktion ist daher:

\(\text{Maximiere } P = 50x + 40y\)

• Nebenbedingungen:
• 1. Gesamtproduktionsstunden: \(x + y \leq 70\)
• 2. Minimale Produktionsstunden für Produkt A: \(x \geq 10\)
• 3. Maximale Produktionsstunden für Produkt A: \(x \leq 40\)
• 4. Minimale Produktionsstunden für Produkt B: \(y \geq 20\)
• 5. Maximale Produktionsstunden für Produkt B: \(y \leq 60\)
• 6. Nicht-Negativitätsbedingung: \(x \geq 0\), \(y \geq 0\)

Zusammengefasst ist das lineare Optimierungsproblem (LP) wie folgt:

Maximiere \(P = 50x + 40y\) unter den Nebenbedingungen:

• \(x + y \leq 70\)
• \(x \geq 10\)
• \(x \leq 40\)
• \(y \geq 20\)
• \(y \leq 60\)
• \(x \geq 0\), \(y \geq 0\)

b)

Teilaufgabe 2: Löse das entspanntes Problem (wo die Variablen keine Ganzzahligkeitseinschränkung haben) und bestimme die optimale Lösung. Berechne dazu die Zielfunktion und vergleiche die Ergebnisse verschiedenster Produktionsaufteilungen.

Lösung:

Hier ist die Lösung für Teilaufgabe 2: Löse das entspannte Problem (wo die Variablen keine Ganzzahligkeitseinschränkung haben) und bestimme die optimale Lösung. Berechne dazu die Zielfunktion und vergleiche die Ergebnisse verschiedenster Produktionsaufteilungen.

• Gegeben:

Das lineare Optimierungsproblem (LP) ist wie folgt definiert:

• Zielfunktion:

Maximiere \(P = 50x + 40y\)

• Nebenbedingungen:
• \(x + y \leq 70\)
• \(x \geq 10\)
• \(x \leq 40\)
• \(y \geq 20\)
• \(y \leq 60\)
• \(x \geq 0\), \(y \geq 0\)
• Schritt-für-Schritt-Lösung:
• 1. Plotten der Nebenbedingungen:
• Die Gleichung \(x + y = 70\) repräsentiert die Gesamtproduktionsgrenze.
• Die Ungleichungen \(x \geq 10\) und \(x \leq 40\) begrenzen die Produktionszeit für Produkt A.
• Die Ungleichungen \(y \geq 20\) und \(y \leq 60\) begrenzen die Produktionszeit für Produkt B.
• 2. Bestimmen der Eckpunkte:
• Um die optimale Lösung zu finden, müssen wir die Eckpunkte des zulässigen Bereichs berechnen:
• \(x = 10\) und \(y = 60 - 10 = 50\)
• \(x = 10\) und \(y = 20\)
• \(x = 40\) und \(y = 70 - 40 = 30\)
• \(x = 40\) und \(y = 20\)
• 3. Berechnung der Zielfunktion an den Eckpunkten:
• Punkt (10, 60): \(P = 50(10) + 40(60) = 500 + 2400 = 2900\)
• Punkt (10, 20): \(P = 50(10) + 40(20) = 500 + 800 = 1300\)
• Punkt (40, 30): \(P = 50(40) + 40(30) = 2000 + 1200 = 3200\)
• Punkt (40, 20): \(P = 50(40) + 40(20) = 2000 + 800 = 2800\)
• Optimale Lösung:

Aus den berechneten Werten sehen wir, dass die Produktionsaufteilung von 40 Stunden für Produkt A und 30 Stunden für Produkt B den maximalen Gewinn von \(3200€\) ergibt:

• Optimale Produktionsaufteilung: 40 Stunden für Produkt A und 30 Stunden für Produkt B
• Maximaler Gewinn: 3200€

c)

Teilaufgabe 3: Nutze die Branch-and-Bound Methode, um die optimale Lösung zu finden, wenn die Produktionszeiten für Produkt A und Produkt B Ganzzahlen sein müssen. Beschreibe den Prozess des Branching, Bounding und das Ausschließen unbrauchbarer Lösungen und leite die optimale Ganzahrlösung ab.

Lösung:

Hier ist die Lösung für Teilaufgabe 3: Nutze die Branch-and-Bound Methode, um die optimale Lösung zu finden, wenn die Produktionszeiten für Produkt A und Produkt B Ganzzahlen sein müssen. Beschreibe den Prozess des Branching, Bounding und das Ausschließen unbrauchbarer Lösungen und leite die optimale Ganzahrlösung ab.

• Schritt 1: Lineares Entspanntes Problem Lösen

Im vorherigen Schritt haben wir bereits das entspannte Problem gelöst. Die optimale Lösung ohne Ganzzahligkeitseinschränkung ist:

• \(x = 40\)
• \(y = 30\)
• mit einem maximalen Gewinn von \(3200€\).
• Schritt 2: Branching

Da \(x = 40\) und \(y = 30\) bereits ganzzahlig sind, brauchen wir in diesem Fall kein Branching durchzuführen, aber wir prüfen dennoch, ob diese Lösung wirklich die beste ist, indem wir die umliegenden Ganzzahlen untersuchen.

• Schritt 3: Bounding

Für Bounding bewerten wir die Zielfunktion in den Bereichen, die Ganzzahlen enthalten, und nutzen unsere Einschränkungen:

• 1. Lösung: \(x = 40\) (im Bereich), \(y = 30\) (im Bereich)
• Berechnung: \(P = 50(40) + 40(30) = 2000 + 1200 = 3200\)
• 2. Lösung: \(x = 41\) oder \(x = 39\)
• Diese Lösungen sind nicht innerhalb der zulässigen Bereiche (\(x \leq 40\)), daher werden sie ausgeschlossen.
• 3. Lösung: \(y = 31\) oder \(y = 29\)
• Versuchen wir diese Kombinationen:
• \(x = 40\), \(y = 29\)
• \(P = 50(40) + 40(29) = 2000 + 1160 = 3160\)
• Der Gewinn hier ist kleiner als 3200€.
• Maximaler Gewinn bleibt 3200€.
• Schritt 4: Vergleichen und Überprüfen

Da die ursprüngliche Lösung ganzzahlige Werte enthält, sind keine weiteren Iterationen notwendig.

• Ergebnis
• Optimale ganzzahlige Lösung: \(x = 40\), \(y = 30\)
• Maximaler Gewinn: 3200€

Aufgabe 4)

Ein Fertigungsunternehmen plant die Produktion von drei Produkten A, B und C. Die Produktion ist durch die Verfügbarkeit von Rohstoffen sowie durch die Kapazitäten der Maschinen eingeschränkt. Es existieren folgende Beschränkungen und Gewinnfunktionen:

• Produkt A benötigt 2 Einheiten Rohstoff R1 und 3 Einheiten Maschinenkapazität M1 pro Einheit
• Produkt B benötigt 1 Einheit Rohstoff R1 und 2 Einheiten Maschinenkapazität M2 pro Einheit
• Produkt C benötigt 3 Einheiten Rohstoff R2 und 1 Einheit Maschinenkapazität M2 pro Einheit
• Die Verfügbarkeit beträgt 100 Einheiten für R1, 150 Einheiten für R2, 100 Einheiten für M1 und 160 Einheiten für M2
• Der Gewinn ist 30 Euro für A, 20 Euro für B und 50 Euro für C pro Einheit
Formuliere ein lineares Programm zur Maximierung des Gewinns und löse dies mit Hilfe des Simplex-Algorithmus.

a)

1. Modellformulierung: Formuliere das lineare Programm zur Maximierung des Gewinns unter Berücksichtigung der gegebenen Beschränkungen. Stelle die Zielfunktion und die Nebenbedingungen explizit auf.

Nutze hierzu die Variablen x1, x2 und x3 für die Anzahl an produzierten Einheiten von A, B und C entsprechend.

Lösung:

• Um das lineare Programm zur Maximierung des Gewinns zu formulieren, definieren wir zunächst die Variablen:
• Variablen:
  • x1: Anzahl der produzierten Einheiten von Produkt A
  • x2: Anzahl der produzierten Einheiten von Produkt B
  • x3: Anzahl der produzierten Einheiten von Produkt C
• Zielfunktion:Wir möchten den Gewinn maximieren, daher ergibt sich die Zielfunktion zu: \(Max Z = 30x1 + 20x2 + 50x3\)
• Nebenbedingungen:
  • Rohstoff R1: \(2x1 + 1x2 \leq 100\)
  • Rohstoff R2: \(3x3 \leq 150\)
  • Maschinenkapazität M1: \(3x1 \leq 100\)
  • Maschinenkapazität M2: \(2x2 + 1x3 \leq 160\)
• Zusätzlich müssen wir die Nichtnegativitätsbedingungen berücksichtigen: \(x1 \geq 0, x2 \geq 0, x3 \geq 0\)

Zusammengefasst:Zielfunktion:

• \(Max Z = 30x1 + 20x2 + 50x3\)
Nebenbedingungen:
• \(2x1 + 1x2 \leq 100\)
• \(3x3 \leq 150\)
• \(3x1 \leq 100\)
• \(2x2 + 1x3 \leq 160\)
• \(x1 \geq 0, x2 \geq 0, x3 \geq 0\)

b)

2. Initialisierung und Simplex-Tableau: Starte mit einer geeigneten Basislösung und erstelle das anfängliche Simplex-Tableau.

Nutze hierfür die Werte aus der Aufgabe und zeige den Prozess der Initialisierung des Simplex-Algorithmus.

Lösung:

• Um den Simplex-Algorithmus zu starten, benötigen wir eine geeignete Basislösung und das anfängliche Simplex-Tableau. Diese Schritte helfen bei der Initialisierung:
• 1. Einführen der Schlupfvariablen:Um die Ungleichungen in Gleichungen umzuwandeln, führen wir Schlupfvariablen ein.
• \(2x_1 + 1x_2 + s_1 = 100\)
• \(3x_3 + s_2 = 150\)
• \(3x_1 + s_3 = 100\)
• \(2x_2 + 1x_3 + s_4 = 160\)
• Schlupfvariablen: \(s_1, s_2, s_3, s_4 \geq 0\)
• 2. Standardisierung der Zielfunktion:Wir wandeln die Zielfunktion in die Standardform um.
• \(Max Z = 30x_1 + 20x_2 + 50x_3\)
• Gleichung in Gleichung umwandeln und negative Zielkoeffizienten hinzufügen:
• \(Z - 30x_1 - 20x_2 - 50x_3 = 0\)
• 3. Erstellen des anfänglichen Simplex-Tableaus:

| Basis | x1 | x2 | x3 | s1 | s2 | s3 | s4 | rechte Seite ||-------|----|----|----|----|----|----|----|--------------|| s1    |  2 |  1 |  0 |  1 |  0 |  0 |  0 |     100      || s2    |  0 |  0 |  3 |  0 |  1 |  0 |  0 |     150      || s3    |  3 |  0 |  0 |  0 |  0 |  1 |  0 |     100      || s4    |  0 |  2 |  1 |  0 |  0 |  0 |  1 |     160      || Z     |-30 |-20 |-50 |  0 |  0 |  0 |  0 |      0       |

Erklärung: Jede Zeile in diesem Tableau entspricht einer der Gleichungen der Nebenbedingungen. Die letzte Zeile stellt die Zielfunktion dar. Die Schlupfvariablen \(s_1, s_2, s_3, s_4\) bieten eine Anfangsbasislösung.

Beim Simplex-Algorithmus müssen wir Pivotelemente identifizieren und das Tableau iterativ aktualisieren, um eine Optimalitätslösung zu finden.

c)

3. Pivot-Operationen und Lösung: Führe die notwendigen Pivot-Operationen durch, bis die optimale Lösung erreicht ist.

Veranschauliche jeden Schritt des Verfahrens und erkläre die Auswahl der Pivot-Elemente. Zeige schrittweise, wie die Ziellösung maximiert wird, und berechne den maximalen Gewinn.

Lösung:

• Um die notwendigen Pivot-Operationen durchzuführen und die optimale Lösung zu erreichen, werden wir die Schritte des Simplex-Algorithmus im Detail durchlaufen.

• Ausgehend vom anfänglichen Simplex-Tableau:

| Basis | x1 | x2 | x3 | s1 | s2 | s3 | s4 | Rechte Seite ||-------|----|----|----|----|----|----|----|--------------||  s1   |  2 |  1 |  0 |  1 |  0 |  0 |  0 |     100      ||  s2   |  0 |  0 |  3 |  0 |  1 |  0 |  0 |     150      ||  s3   |  3 |  0 |  0 |  0 |  0 |  1 |  0 |     100      ||  s4   |  0 |  2 |  1 |  0 |  0 |  0 |  1 |     160      ||  Z    |-30 |-20 |-50 |  0 |  0 |  0 |  0 |      0       |

• Schritt 1: Auswahl des Pivot-Elements:Wir wählen die Variable mit dem negativsten Koeffizienten in der Zielzeile: \(x3\) (Koeffizient -50). Diese wird unsere Eingangsvariable.

• Bestimme die Pivot-Reihe: Wir schauen uns das Verhältnis der rechten Seite zu den positiven x3-Koeffizienten an:
• Für s2: \(\frac{150}{3} = 50\)
• Für s4: \(\frac{160}{1} = 160\)
• Das kleinere Verhältnis ist 50, daher wird s2 unsere Ausgangsvariable und das Pivot-Element ist 3.

• Schritt 2: Pivot-Operation:Wir teilen die Pivot-Reihe (Zeile s2) durch 3, um eine Eins in der Pivot-Spalte x3 zu bekommen:

| Basis | x1 | x2 | x3  | s1 | s2  | s3 | s4 | Rechte Seite ||-------|----|----|---- |----|-----|----|----|--------------||  s1   |  2 |  1 |  0  |  1 |  0  |  0 |  0 |     100      ||  x3   |  0 |  0 |  1  |  0 | 1/3 |  0 |  0 |      50      ||  s3   |  3 |  0 |  0  |  0 |  0  |  1 |  0 |     100      ||  s4   |  0 |  2 |  0  |  0 | -1  |  0 |  1 |     110      ||  Z    |-30 |-20 |  0  |  0 | 50/3|  0 |  0 |    2500      |

• Als nächstes eliminieren wir x3 aus den anderen Zeilen durch entsprechende Zeilenoperationen:
• Für die Zielzeile Z: \(Z_neu = Z + 50 \times (Zeile_{x3})\)
• Für s1: \(s1_{neu} = s1 - 0 \times (Zeile_{x3})\) (keine Änderung notwendig)
• Für s3: \(s3_{neu} = s3 - 0 \times (Zeile_{x1})\) (keine Änderung notwendig)
• Für s4: \(s4_{neu} = s4 - 0 \times (Zeile_{x3})\) (keine Änderung notwendig)

• Schritt 3: Wiederhole die Pivot-Operationen:Wir wiederholen das Verfahren mit den verbleibenden negativen Koeffizienten in der Zielfunktion.

• Wir sehen, dass x1 den negativsten Koeffizienten hat und wählen x1 als die Eingangsvariable und bestimmen die Pivot-Reihe:

• Für s1: \(\frac{100}{2} = 50\)
• Für s3: \(\frac{100}{3} = 33.33\)
• Das kleinere Verhältnis ist 33.33, daher wird s3 zur Ausgangsvariablen und x1 kommt in die Basis.

| Basis | x1  | x2 | x3  | s1 | s2  | s3 | s4 | Rechte Seite ||-------|-----|----|---- |----|-----|----|----|--------------||  s1   | 0.67| 1  |  0  |  1 |  0  | -0.33|  0 |     66.67  ||  x3   |  0  |  0 |  1  |  0 | 1/3 |  0  |  0 |     50      ||  x1   |  1  |  0 |  0  |  0 |  0  |  0.33|  0 |     33.33  ||  s4   |  0  |  2 |  0  |  0 | -1  | -1  |  1 |     76.67   ||  Z    |  0  |-20 |  0  |  0 | 50/3| 10  |  0 |    3500      |

• Nun führen wir die gleiche Operation für x2 durch. Das Verhältnis der rechten Seite zu den positiven x2-Koeffizienten:
• Für s1: \(\frac{66.67}{1} = 66.67\)
• Für s4: \(\frac{76.67}{2} = 38.33\)
• Das kleinere Verhältnis ist 38.33, daher wird s4 zur Ausgangsvariablen und x2 kommt in die Basis.

| Basis | x1 | x2 | x3  | s1 | s2  | s3 | s4 | Rechte Seite ||-------|----|----|---- |----|-----|----|----|--------------||  s1   |0.67|  0 |  0  |  1 |0.5  | -0.33|-0.5|   13.34    ||  x3   |  0 |  0 |  1  |  0 | 1/3 |  0  |  0 |     50      ||  x1   |  1 |  0 |  0  |  0 | 0.33| 0.33|  0 |   33.33    ||  x2   |  0 |  1 |  0  |  0 |-0.5 | -0.5|  1 |   38.33    ||  Z    |  0 |  0 |  0  |  0 |  0  |  0  |  0 |   4000      |

Das Tableau zeigt nun, dass die optimale Lösung gefunden wurde, da keine negativen Koeffizienten in der Zielfunktion mehr existieren. Maximale Gewinn beträgt 4000 Euro.