Discrete optimization II - Exam

Aufgabe 1)

Simplex-Algorithmus: Du bist als Praktikant in einem Unternehmen tätig, das lineare Optimierungsprobleme löst. Heute besteht Deine Aufgabe darin, ein vorgegebenes Problem mit dem Simplex-Algorithmus zu lösen.

• Startet in einer Ecke des zulässigen Bereichs, bewegt sich entlang der Kanten
• Ziel ist die Minimierung oder Maximierung einer linearen Zielfunktion
• Benutzt Pivot-Operationen zur Verbesserung der Zielfunktion in jedem Schritt
• Erzeugt eine Folge von Basislösungen: Jede Lösung entspricht einem Eckpunkt
• Terminiert, wenn keine weitere Verbesserung möglich ist
• Mathematische Formulierung: Maximiere \( c^T x \) unter den Nebenbedingungen \( Ax \leq b \) und \( x \geq 0 \)

a)

Betrachte das folgende lineare Optimierungsproblem: Maximiere \( z = 3x_1 + 2x_2 \) unter den Nebenbedingungen:

x_1 + x_2 \leq 4 \ 2x_1 + x_2 \leq 5 \  x_1, x_2 \geq 0

Wandle das Problem in ein gleichwertiges Simplex-Tableau um.

Lösung:

Simplex-Algorithmus:Wie beschrieben, besteht deine Aufgabe darin, ein lineares Optimierungsproblem zu lösen. Zunächst wandelst du dein Problem in ein entsprechendes Simplex-Tableau um. Betrachten wir die gegebenen Bedingungen und Optionen:Optimierungsproblem:Maximiere \( z = 3x_1 + 2x_2 \)Unter den Nebenbedingungen:

x_1 + x_2 \leq 4 \ 2x_1 + x_2 \leq 5 \  x_1, x_2 \geq 0

Hier sind die Schritte, die du ausführen musst, um das Simplex-Tableau zu erstellen:

• Schritt 1: Füge Schlupfvariablen hinzu, um die Ungleichungen in Gleichungen zu verwandeln:

x_1 + x_2 + s_1 = 4 \ 2x_1 + x_2 + s_2 = 5

Hier sind \( s_1 \) und \( s_2 \) als Schlupfvariablen hinzugefügt.

• Schritt 2: Erstelle basierend auf diesen Gleichungen das initiale Simplex-Tableau:

Initiales Simplex-Tableau:

Basis	x_1	x_2	s_1	s_2	b
s_1	1	1	1	0	4
s_2	2	1	0	1	5
Z	-3	-2	0	0	0

Stelle sicher, dass du die korrekten Werte für jede Zeile und Spalte notierst.

• Schritt 3: Initialisiere die Basislösungen: \( s_1 \) und \( s_2 \) sind die Basisvariablen mit den zugehörigen rechten Seitenwerten als Anfangslösungen.
• Für die Zielfunktion z: Trage die Koeffizienten der Entscheidungsvariablen \( x_1 \) und \( x_2 \) mit negativem Vorzeichen ein.

Zusammenfassung:Du hast dein Problem nun erfolgreich in ein Simplex-Tableau umgewandelt. Als nächstes folgt der iterative Prozess des Simplex-Algorithmus, wobei in jedem Schritt Verbesserungen durch Pivot-Operationen vorgenommen werden, bis keine weiteren Verbesserungen möglich sind.

b)

Führe eine Pivot-Operation auf das erste Simplex-Tableau durch, um die optimalste Basislösung zu finden. Beschreibe detailliert die Schritte, die Du unternimmst, und berücksichtige dabei alle relevanten Berechnungen.

Lösung:

Simplex-Algorithmus:Der nächste Schritt besteht darin, eine Pivot-Operation auf das initiale Simplex-Tableau durchzuführen. Ziel ist es, eine optimalere Basislösung zu finden. Wir gehen durch den Prozess Schritt für Schritt:Initiales Simplex-Tableau:

Basis	x_1	x_2	s_1	s_2	b
s_1	1	1	1	0	4
s_2	2	1	0	1	5
Z	-3	-2	0	0	0

Schritt 1: Identifiziere die Pivot-Spalte. Dies ist die Spalte mit dem negativsten Zielfunktionskoeffizienten in der Z-Zeile. In diesem Fall ist es die Spalte mit dem Koeffizienten -3, also die Spalte für \( x_1 \).Schritt 2: Bestimme die Pivot-Zeile, indem du das kleinste Verhältnis \( \frac{b_i}{a_{ij}} \) berechnest, wobei \( a_{ij} \) das Element in der Pivot-Spalte und \( b_i \) die rechte Seite ist. Für die erste Zeile: \( \frac{4}{1} = 4 \) Für die zweite Zeile: \( \frac{5}{2} = 2.5 \) Der kleinste Wert ist 2.5, also ist die Pivot-Zeile die zweite Zeile. Der Pivot ist somit die Zahl 2 in der zweiten Zeile, ersten Spalte.Schritt 3: Führe die Pivot-Operation durch.

• Teile die Pivot-Zeile durch den Pivot-Wert, um die neue Pivot-Zeile zu erhalten.
• Passe die anderen Zeilen an, sodass alle anderen Elemente in der Pivot-Spalte zu Null werden.

Teile die Pivot-Zeile durch 2:

Neue Pivot-Zeile: (s_2 geworden x_1) [1, 0.5, 0, 0.5, 2.5]

Passe die erste Zeile an:

Neue s_1-Zeile: (s_1) [0, 0.5, 1, -0.5, 1.5]

Passe die Z-Zeile an:

Neue Z-Zeile: (Z) [0, -0.5, 0, 1.5, 7.5]

Neues Simplex-Tableau:

Basis	x_1	x_2	s_1	s_2	b
s_1	0	0.5	1	-0.5	1.5
x_1 (Pivot)	1	0.5	0	0.5	2.5
Z	0	-0.5	0	1.5	7.5

Zusammenfassung:Nach der Pivot-Operation haben wir eine neue Basislösung gefunden. Bevor wir den Simplex-Algorithmus fortsetzen, prüfen wir, ob weitere Verbesserungen möglich sind, indem wir die aktuelle Z-Zeile analysieren. In diesem Fall hat die Spalte \( x_2 \) noch einen negativen Koeffizienten, daher müssen wir mindestens eine weitere Pivot-Operation durchführen.

c)

Überprüfe, ob die von Dir gefundene Basislösung optimal ist. Wenn dies der Fall ist, gib die Lösung des Optimierungsproblems an. Falls nicht, führe weitere Pivot-Operationen durch, bis die optimale Lösung erreicht ist.

Lösung:

Simplex-Algorithmus:Nachdem wir die erste Pivot-Operation durchgeführt haben, prüfen wir, ob die gefundene Basislösung bereits optimal ist. Hier sind die bisherigen Schritte und das neue Simplex-Tableau:Neues Simplex-Tableau nach der ersten Pivot-Operation:

Basis	x_1	x_2	s_1	s_2	b
s_1	0	0.5	1	-0.5	1.5
x_1 (Pivot)	1	0.5	0	0.5	2.5
Z	0	-0.5	0	1.5	7.5

Überprüfung auf Optimalität:Eine Lösung ist optimal, wenn alle Einträge in der Z-Zeile (außer dem rechten Wert 'b') größer oder gleich null sind. In unserem Tableau haben wir noch einen negativen Koeffizienten in der Z-Zeile bei \( x_2 \) (nämlich -0.5). Das bedeutet, dass die aktuelle Lösung noch nicht optimal ist.Schritt 1: Identifiziere die Pivot-Spalte. In diesem Fall ist es die Spalte von \( x_2 \), da sie den negativsten Wert in der Z-Zeile enthält.Schritt 2: Bestimme die Pivot-Zeile, indem du das kleinste Verhältnis \( \frac{b_i}{a_{ij}} \) berechnest. Hier vergleichen wir:Für die erste Zeile: \( \frac{1.5}{0.5} = 3 \) Für die zweite Zeile: (nicht anwendbar, da 0.5 im Pivot-Element der Pivot-Zeile, also keine Division durch 0 möglich)Das kleinste Verhältnis von 3 zeigt, dass die erste Zeile die Pivot-Zeile ist. Der Pivot-Element ist 0.5.Schritt 3: Führe die Pivot-Operation durch.

• Teile die Pivot-Zeile durch den Pivot-Wert
• Passe die anderen Zeilen an

Teile die Pivot-Zeile durch 0.5:

Neue Pivot-Zeile: (s_1 wird x_2) [0, 1, 2, -1, 3]

Passe die zweite Zeile an:

Neue x_1-Zeile: [1, 0, -1, 1, 1]

Passe die Z-Zeile an:

Neue Z-Zeile: [0, 0, 1, 1, 9]

Neues Simplex-Tableau:

Basis	x_1	x_2	s_1	s_2	b
x_2 (Pivot)	0	1	2	-1	3
x_1	1	0	-1	1	1
Z	0	0	1	1	9

Überprüfung auf Optimalität:Nun hat die Z-Zeile keine negativen Koeffizienten mehr. Das bedeutet, dass wir die optimale Lösung erreicht haben.Optimale Lösung:\( x_1 = 1 \)\( x_2 = 3 \)\( z = 9 \)Die optimale Lösung des Optimierungsproblems ist daher \( x_1 = 1 \) und \( x_2 = 3 \) mit maximalem \( z = 9 \).

Aufgabe 2)

Gegeben sei das folgende lineare Programm (Primärproblem):

min:      3x1 + 2x2subject to: x1 + x2 >= 4                 2x1 + x2 >= 5                 x1, x2 >= 0

Leite das zugehörige Dualproblem her und löse sowohl das Primär- als auch das Dualproblem.

a)

a) Leite das Dualproblem aus dem gegebenen Primärproblem her und formuliere es vollständig. Stelle sicher, dass alle Bedingungen korrekt umgewandelt werden.

Lösung:

Um das Dualproblem abzuleiten, müssen wir das Primärproblem in eine standardisierte Form umwandeln und dann die dualen Variablen einführen. Das Dualproblem entspricht dann einem Maximierungsproblem, bei dem die Rollen der Zielfunktionskoeffizienten und der rechten Seiten der Ungleichungen vertauscht werden.

Primärproblem:

min:      3x_1 + 2x_2subject to: x_1 + x_2 >= 4                 2x_1 + x_2 >= 5                 x_1, x_2 >= 0

Um das Dualproblem zu formulieren, gehen wir Schritt für Schritt vor:

• Schreibe das Primärproblem in eine standardisierte Form:

Zielfunktion:

min: 3x_1 + 2x_2

Restriktionen:

x_1 + x_2 >= 42x_1 + x_2 >= 5x_1, x_2 >= 0

• Einfügen der dualen Variablen y_1 und y_2 für die Restriktionen des Primärproblems:

Dualproblem:

max:    4y_1 + 5y_2subject to:       y_1 + 2y_2 <= 3       y_1 + y_2 <= 2       y_1, y_2 >= 0

• Die Koeffizienten der Zielfunktion des Primärproblems (3 und 2) werden zu den Schranken der Ungleichungen im Dualproblem.
• Die Konstanten auf der rechten Seite der Restriktionen des Primärproblems (4 und 5) werden zu den Koeffizienten in der Zielfunktion des Dualproblems.

Das vollständig umgewandelte Dualproblem lautet:

max:    4y_1 + 5y_2subject to:       y_1 + 2y_2 <= 3       y_1 + y_2 <= 2       y_1, y_2 >= 0

b)

b) Verwende die Schwache Dualität zur Kontrolle, ob eine gefundene Lösung für das Primärproblem optimal ist. Berechne die Lagrange-Multiplikatoren (y-Werte) und den Zielfunktionswert für das Dualproblem.

Lösung:

Um die Schwache Dualität zu verwenden und zu prüfen, ob eine gefundene Lösung für das Primärproblem optimal ist, gehen wir wie folgt vor:

• Finde zuerst eine Lösung für das Primärproblem.
• Leite dann die zugehörigen Lagrange-Multiplikatoren (y-Werte) ab.
• Berechne den Zielfunktionswert für das Dualproblem.

Primärproblem:

min: 3x_1 + 2x_2subject to: x_1 + x_2 >= 4                 2x_1 + x_2 >= 5                 x_1, x_2 >= 0

Das Primärproblem ist minimiert worden, indem wir die Randbedingungen beachten. Angenommen, die optimale Lösung für das Primärproblem ist (x_1, x_2) = (2, 2), dann ist der Zielfunktionswert:

Z_P = 3x_1 + 2x_2 = 3*2 + 2*2 = 6 + 4 = 10

Jetzt betrachten wir das Dualproblem:

max: 4y_1 + 5y_2subject to: y_1 + 2y_2 <= 3                  y_1 + y_2 <= 2                  y_1, y_2 >= 0

Angenommen, wir finden die optimale Lösung für das Dualproblem bei (y_1, y_2) = (1, 1). Dann ist der Zielfunktionswert für das Dualproblem:

Z_D = 4y_1 + 5y_2 = 4*1 + 5*1 = 4 + 5 = 9

Nach der Schwachen Dualität wissen wir, dass für jede zulässige Lösung des Primärproblems und des Dualproblems der Zielfunktionswert des Dualproblems nicht größer als der des Primärproblems sein kann:

Z_D <= Z_P

Mit Z_P = 10 und Z_D = 9 ist diese Bedingung erfüllt. Daher können wir schließen, dass die gefundene Lösung für das Primärproblem optimal ist, wenn beide Bedingungen der Schwachen Dualität und der Zielfunktion erfüllt sind.

Die Lagrange-Multiplikatoren bzw. y-Werte sind somit y_1 = 1 und y_2 = 1.

c)

c) Demonstriere die Starke Dualität durch den Vergleich der Optimallösungen beider Probleme. Berechne die optimalen Werte von x und y sowie die entsprechenden zielfunktionalen Werte und überprüfe deren Gleichheit.

Lösung:

Um die Starke Dualität zu demonstrieren, müssen wir die optimalen Lösungen sowohl für das Primär- als auch das Dualproblem berechnen und die entsprechenden Zielfunktionswerte vergleichen. Laut dem Satz der Starken Dualität sind beide Zielfunktionswerte gleich, wenn beide Probleme optimal gelöst sind.

Primärproblem:

min: 3x_1 + 2x_2subject to: x_1 + x_2 >= 4                 2x_1 + x_2 >= 5                 x_1, x_2 >= 0

Wir lösen das Primärproblem optimal, indem wir die Randbedingungen beachten:

• Gegeben die Restriktionen, betrachten wir die Punkte auf den Randgeraden:
• Für x_1 + x_2 = 4:

x_2 = 4 - x_1

Für 2x_1 + x_2 = 5:

x_2 = 5 - 2x_1

Durch gleichsetzen der beiden Ausdrücke für x_2 erhalten wir:

4 - x_1 = 5 - 2x_1x_1 = 1x_2 = 4 - 1 = 3

Wir erhalten die Lösung (x_1, x_2) = (1, 3).

Der Zielfunktionswert des Primärproblems ist daher:

Z_P = 3x_1 + 2x_2 = 3*1 + 2*3 = 3 + 6 = 9

Dualproblem:

max: 4y_1 + 5y_2subject to: y_1 + 2y_2 <= 3                  y_1 + y_2 <= 2                  y_1, y_2 >= 0

Wir lösen das Dualproblem optimal:

• Aus den Restriktionen:

y_1 + 2y_2 <= 3y_1 + y_2 <= 2

Setzen wir mögliche Werte für y_1 und y_2 ein:

Gegeben die Restriktionen, erhalten wir (y_1, y_2) = (1, 1).

Der Zielfunktionswert des Dualproblems ist daher:

Z_D = 4y_1 + 5y_2 = 4*1 + 5*1 = 4 + 5 = 9

Da Z_P = Z_D = 9, demonstriert dies die Starke Dualität. Beide Zielfunktionalwerte sind gleich, und somit sind die optimalen Werte für x und y gefunden. Die optimalen Werte sind:

Primärproblem Lösung (x_1, x_2) = (1, 3)Zielfunktionswert Z_P = 9

Dualproblem Lösung (y_1, y_2) = (1, 1)Zielfunktionswert Z_D = 9

Die Gleichheit der Zielfunktionswerte bestätigt, dass beide Lösungen optimal sind und die Starke Dualität erfüllen.

Aufgabe 3)

Das Branch-and-Bound Verfahren wird häufig verwendet, um kombinatorische Optimierungsprobleme effizient zu lösen. Ein klassisches Problem, das mit Branch-and-Bound gelöst werden kann, ist das Rucksackproblem, bei dem eine Menge von Gegenständen gegeben ist, von denen jeder ein bestimmtes Gewicht und einen bestimmten Wert hat. Das Ziel ist es, eine Auswahl von Gegenständen zu finden, die den Rucksack mit einer maximalen Kapazität so füllen, dass der Gesamtwert maximiert wird. Im Branch-and-Bound Verfahren teilt man das Problem in kleinere Teilprobleme auf (Branching) und berechnet Schranken (Bounding) für die Kosten der Lösungen in diesen Teilräumen, um unlohnende Teilräume auszuschließen.

a)

Teilaufgabe 1: Gegeben sei ein Rucksackproblem mit den folgenden Gegenständen:

• Gegenstand 1: Gewicht 3, Wert 25
• Gegenstand 2: Gewicht 2, Wert 20
• Gegenstand 3: Gewicht 1, Wert 15
• Gegenstand 4: Gewicht 4, Wert 30
• Gegenstand 5: Gewicht 5, Wert 40

Die maximale Kapazität des Rucksacks beträgt 7. a. Erkläre die Schritte des Branch-and-Bound Verfahrens für dieses Problem anhand eines prägnanten Beispiels. Beginne mit der Berechnung einer initialen oberen Schranke, branchen der Entscheidungsvariablen und Bestimmen der Schranken für die Teilprobleme. b. Führe die Berechnungen durch und finde die optimale Lösung für dieses Rucksackproblem mit dem Branch-and-Bound Verfahren. Dokumentiere die Schritte und die Berechnung der Schranken detailliert. Vergiss nicht, Heuristiken zu verwenden, die die Effizienz des Verfahrens verbessern können.

Lösung:

Teilaufgabe 1: Gegeben sei ein Rucksackproblem mit den folgenden Gegenständen:

• Gegenstand 1: Gewicht 3, Wert 25
• Gegenstand 2: Gewicht 2, Wert 20
• Gegenstand 3: Gewicht 1, Wert 15
• Gegenstand 4: Gewicht 4, Wert 30
• Gegenstand 5: Gewicht 5, Wert 40

Die maximale Kapazität des Rucksacks beträgt 7.

a. Erkläre die Schritte des Branch-and-Bound Verfahrens für dieses Problem anhand eines prägnanten Beispiels.

Das Branch-and-Bound Verfahren gliedert sich in drei hauptschritte: Branching, Bounding und das Ausschließen von unvorteilhaften Teilproblemen.

• Initialisierung: Berechne eine initiale obere Schranke. Eine übliche Methode dafür ist ein Heuristikverfahren wie die Greedy-Methode.
• Branching: Teile das Problem in kleinere Teilprobleme auf, indem man Entscheidungen darüber trifft, ob ein Gegenstand in den Rucksack aufgenommen wird oder nicht.
• Bounding: Berechne Schranken für die Teilprobleme, um festzustellen, ob sie potentielle Lösungen enthalten können, die besser sind als die aktuell beste gefundene Lösung. Falls nicht, werden sie ausgeschlossen.

Beispiel:

1. Sortiere die Gegenstände nach Wertdichte (Wert/Gewicht):

• Gegenstand 3: Wertdichte 15 (15/1)
• Gegenstand 2: Wertdichte 10 (20/2)
• Gegenstand 1: Wertdichte 8,33 (25/3)
• Gegenstand 4: Wertdichte 7,5 (30/4)
• Gegenstand 5: Wertdichte 8 (40/5)

2. Berechne eine heuristische obere Schranke, indem alle Gegenstände nach Wertdichte in den Rucksack gepackt werden, bis zur maximalen Kapazität.

• Gegenstand 3 (Gewicht 1, Wert 15) → verbleibendes Gewicht 6
• Gegenstand 2 (Gewicht 2, Wert 20) → verbleibendes Gewicht 4
• Gegenstand 1 (Gewicht 3, Wert 25) → verbleibendes Gewicht 1
• Gegenstand 4 (teilweise, Gewicht 1, Wert 7.5)

Obere Schranke: 15 + 20 + 25 + 7.5 = 57.5

b. Führe die Berechnungen durch und finde die optimale Lösung für dieses Rucksackproblem mit dem Branch-and-Bound Verfahren.

• Erstelle den Suchbaum und beginne mit dem Wurzelknoten, der für den leeren Rucksack steht.
• Level 1: Betrachte Entscheidung gegenständlich 1: Inklusive / Exklusive
• Inklusive: Gesamtgewicht 3, verbleibendes Gewicht 4, Teilsumme Wert 25, verbleibende Obere Schranke: Wertdichte der restlichen Gegenstände (Gegenstand 2,3,4,5) = 75. Total = 100
• Exklusive: Teilsumme Wert 0, Obere Schranke 57.5
• Fortfahren: Wiederhole das Verfahren für jedes Teilproblem, indem die Entscheidungsvariablen weiter aufgeteilt werden und die Schranken berechnet werden.
• Pfad: Gegenstände 1, 2 einpacken, Gegenstand 3 zu klein → Teilsumme 45.
• Gegenstand 4 oder 5 kann das Gewicht überschreiten, daher Teilsumme: 45
• Optimale Lösung: Gegenstand 1, 2 und 3 packen, verbleibendes Gewicht = 1, übriger Gegenstand 4 , 5 kapazitätsüberschreitend.
• Gesamtwert: 25 + 20+15= 60

b)

Teilaufgabe 2: Erweitere das vorherige Rucksackproblem, indem Du annimmst, dass die Gegenstände teilbar sind, d.h. es handelt sich um das continuous knapsack problem. Berechne: a. Die optimale Lösung ohne Berücksichtigung der Ganzzahligkeit mit Hilfe einer geeigneten Fraktionierungsmethode. Gib den maximalen Wert und die Zusammensetzung des Rucksacks an. b. Vergleiche die Lösungen des diskreten und des kontinuierlichen Rucksackproblems in Bezug auf den maximalen Gesamtwert und die Elemente, die in den Rucksack aufgenommen werden. Diskutiere anhand der Ergebnisse, wann und warum die eine oder andere Problemvariante in der Praxis bevorzugt werden könnte.

Lösung:

Teilaufgabe 2: Erweitere das vorherige Rucksackproblem, indem Du annimmst, dass die Gegenstände teilbar sind, d.h. es handelt sich um das continuous knapsack problem. Berechne:

a. Die optimale Lösung ohne Berücksichtigung der Ganzzahligkeit mit Hilfe einer geeigneten Fraktionierungsmethode. Gib den maximalen Wert und die Zusammensetzung des Rucksacks an.

1. Die Gegenstände nach ihrer Wertdichte sortieren (Wert/Gewicht):

• Gegenstand 3: Wertdichte 15 (15/1)
• Gegenstand 2: Wertdichte 10 (20/2)
• Gegenstand 1: Wertdichte 8,33 (25/3)
• Gegenstand 4: Wertdichte 7,5 (30/4)
• Gegenstand 5: Wertdichte 8 (40/5)

2. Starten mit dem Gegenstand mit der höchsten Wertdichte und den Rucksack so viel wie möglich füllen, bis die maximale Kapazität erreicht ist:

• Gegenstand 3 (Gewicht 1, Wert 15) → verbleibendes Gewicht 6
• Gegenstand 2 (Gewicht 2, Wert 20) → verbleibendes Gewicht 4
• Gegenstand 1 (Gewicht 3, Wert 25) → verbleibendes Gewicht 1
• Gegenstand 4 (teilweise, Gewicht 1, Wert 7.5) → verbleibendes Gewicht 0

Maximaler Wert: 15 + 20 + 25 + 7.5 = 67.5

Zusammensetzung des Rucksacks:

• Gegenstand 3: 1 Gewichtseinheit, Wert 15
• Gegenstand 2: 2 Gewichtseinheiten, Wert 20
• Gegenstand 1: 3 Gewichtseinheiten, Wert 25
• Gegenstand 4: 1 Gewichtseinheit, Wert 7.5

b. Vergleiche die Lösungen des diskreten und des kontinuierlichen Rucksackproblems in Bezug auf den maximalen Gesamtwert und die Elemente, die in den Rucksack aufgenommen werden. Diskutiere anhand der Ergebnisse, wann und warum die eine oder andere Problemvariante in der Praxis bevorzugt werden könnte.

Vergleich:

• Diskretes Rucksackproblem:
• Maximaler Wert: 60
• Zusammensetzung des Rucksacks: Gegenstand 1 (Gewicht 3, Wert 25), Gegenstand 2 (Gewicht 2, Wert 20), Gegenstand 3 (Gewicht 1, Wert 15)
• Kontinuierliches Rucksackproblem:
• Maximaler Wert: 67.5
• Zusammensetzung des Rucksacks: Gegenstand 3 (Gewicht 1, Wert 15), Gegenstand 2 (Gewicht 2, Wert 20), Gegenstand 1 (Gewicht 3, Wert 25), teilweise Gegenstand 4 (Gewicht 1, Wert 7.5)

Diskussion:

In der Praxis gibt es Szenarien, in denen das kontinuierliche Rucksackproblem bevorzugt wird, und andere, in denen das diskrete Rucksackproblem realistischer ist. Die Entscheidung hängt von der Beschaffenheit der Gegenstände und den praktischen Anforderungen ab.

• Diskretes Rucksackproblem: Wenn die Gegenstände unteilbar sind (z.B. Personen auf einem Boot oder Geräte in einem Lager), dann muss das diskrete Problem gelöst werden.
• Kontinuierliches Rucksackproblem: Wenn die Gegenstände teilbar sind (z.B. Flüssigkeiten, Materialien oder andere teilbare Ressourcen), dann ist das kontinuierliche Problem bevorzugt, da es zu einer optimaleren Ausnutzung der Kapazität führt.

Das kontinuierliche Rucksackproblem erzielt in der Regel einen höheren Wert, weil es die Flexibilität bietet, Gegenstände zu teilen und somit die Kapazität des Rucksacks optimal auszunutzen.

Aufgabe 4)

Kontext des Cutting-Plane Verfahrens:Betrachten wir ein Ganzzahloptimierungsproblem, das durch Lineare Programmierung (LP) gelöst wird, indem wiederholt Ungleichungen (Schnittebenen) zu einem LP-Relaxationsproblem hinzugefügt werden. Ausgangspunkt ist die LP-Relaxation des Ganzzahlproblems. Eine Schnitt-Ebene ist eine Ungleichung, die lösungsausschließende Teile des LP-Polyeders wegschneidet, aber alle ganzzahligen Punkte behält. Ziel ist es, alle nicht-ganzzahligen Lösungen auszuschließen und eine ganzzahlige Lösung zu finden. Ein Beispiel für Schnitte sind Gomory-Schnitte.

a)

Gegeben sei das folgende LP-Relaxationsproblem eines Ganzzahlproblems:

• Minimiere: \(z = 3x_1 + 2x_2\)
• Unter den Einschränkungen:
• \( -x_1 + 2x_2 \leq 4 \)
• \( 3x_1 + x_2 \leq 6 \)
• \( x_1 \geq 0 \ , x_2 \geq 0 \)

Finde die optimale Lösung der LP-Relaxation. Bestimme anschließend eine Gomory-Schnitt-Ebene und füge diese hinzu. Löse das resultierende LP-Relaxationsproblem, um die Wirkung der Schnitt-Ebene zu überprüfen. Gibt es nun eine ganzzahlige Lösung? Wenn keine ganzzahlige Lösung gefunden ist, wiederhole den Prozess einmal und überprüfe erneut.

Lösung:

Lösung des gegebenen Subproblems:Gegeben sei das folgende LP-Relaxationsproblem eines Ganzzahlproblems:

• Minimiere: \( z = 3x_1 + 2x_2 \)
• Unter den Einschränkungen:
• \( -x_1 + 2x_2 \leq 4 \)
• \( 3x_1 + x_2 \leq 6 \)
• \( x_1 \geq 0 \, , x_2 \geq 0 \)

Schritte zur Lösung:

• 1. Bestimme die optimale Lösung der LP-Relaxation:Wir lösen das LP-Problem zunächst ohne die Ganzzahligkeitsbedingung. Dies kann durch Simplex-Verfahren oder andere LP-Löser erfolgen.

  b)

  Präsentiere den iterativen Prozess des Cutting-Plane-Verfahrens für das obige Problem graphisch. Zeichne die ursprünglichen Einschränkungen und zeige die Schnittebenen an. Falls der endgültige Schnittgraf keine ganzzahlige Lösung hervorbringt, erläutere, warum der Algorithmus endet und welche ganzzahligen Lösungen ausgeschlossen wurden. Beschreibe kurz, wie eine globale optimale ganzzahlige Lösung gefunden werden kann, falls mehrere Iterationen notwendig sind.

  Lösung:

  Lösung des gegebenen Subproblems:1. Graphische Darstellung der ursprünglichen Einschränkungen:Wir zeichnen die linearen Ungleichungen und die Zielfunktion im \(x_1, x_2\)-Koordinatensystem.

  • Die erste Einschränkung \( -x_1 + 2x_2 \leq 4 \) wird als Linie eingezeichnet.
  • Die zweite Einschränkung \( 3x_1 + x_2 \leq 6 \) wird als Linie eingezeichnet.
  • Die Nichtnegativitätsbedingungen \( x_1 \geq 0 \) und \( x_2 \geq 0 \) begrenzen das zulässige Gebiet im ersten Quadranten.
  Das resultierende zulässige Gebiet wird von diesen Ungleichungen begrenzt.2. Bestimme die optimale Lösung der LP-Relaxation:Die optimale Lösung der LP-Relaxation kann mit dem Simplex-Algorithmus oder einem anderen LP-Löser gefunden werden. Angenommen, wir erhalten die folgende optimale Lösung: \(x_1 = 1.5\), \(x_2 = 1.5\). Der Zielfunktionswert ist \( z = 3(1.5) + 2(1.5) = 7.5 \).3. Hinzufügen einer Gomory-Schnitt-Ebene:Die Gomory-Schnitt-Ebene wird von der nicht-ganzzahligen Lösung abgeleitet. Angenommen, wir haben eine Gomory-Schnitt-Ebene erhalten: \( x_1 - x_2 \leq 0\).4. Aktualisiere das LP-Problem und lösen es erneut:Mit der hinzugefügten Schnitt-Ebene lautet unser aktualisiertes LP-Problem:
  • Minimiere: \( z = 3x_1 + 2x_2 \)
  • Unter den Einschränkungen:
  • \( -x_1 + 2x_2 \leq 4 \)
  • \( 3x_1 + x_2 \leq 6 \)
  • \( x_1 - x_2 \leq 0 \)
  • \( x_1 \geq 0 \ , x_2 \geq 0 \)
  Das aktualisierte zulässige Gebiet wird grafisch dargestellt.5. Überprüfe, ob eine ganzzahlige Lösung gefunden wurde:Wir lösen erneut das LP-Problem. Falls die neue optimale Lösung immer noch nicht ganzzahlig ist, wird der Prozess wiederholt, und eine weitere Gomory-Schnitt-Ebene wird hinzugefügt.Ende des Algorithmus:Falls nach mehreren Iterationen keine ganzzahlige Lösung gefunden wurde, bedeutet dies, dass alle möglichen ganzzahligen Lösungen ausgeschlossen wurden. Das ist ein Hinweis darauf, dass das ursprüngliche Problem möglicherweise keine zulässige ganzzahlige Lösung hat.Globale optimale ganzzahlige Lösung:Falls mehrere Iterationen notwendig sind, wird jede Iteration den zulässigen Bereich weiter einschränken, bis eine ganzzahlige Lösung gefunden wird. Um die globale optimale Lösung zu finden, sollten alle möglichen ganzzahligen Punkte innerhalb des ursprünglichen zulässigen Bereichs überprüft werden, um sicherzustellen, dass die beste Lösung ausgewählt wird.Zusammenfassend zeigt der Cutting-Plane-Algorithmus, wie durch schrittweises Hinzufügen von Schnitt-Ebenen eine ganzzahlige Lösung gefunden wird oder festgestellt wird, dass keine zulässige Lösung existiert.