Numerical Aspects of Linear and Integer Programming - Exam

Aufgabe 1)

In einem Produktionsbetrieb sollen zwei Produkte, P1 und P2, hergestellt werden. Die Gewinnfunktion pro produzierter Einheit beträgt 40€ für P1 und 30€ für P2. Für die Herstellung werden eine Maschine und Arbeit benötigt. Um eine Einheit P1 zu produzieren, benötigt man 2 Stunden Maschinenzeit und 3 Stunden Arbeitszeit. Um eine Einheit P2 zu produzieren, werden 1 Stunde Maschinenzeit und 1 Stunde Arbeitszeit benötigt. Insgesamt stehen 50 Stunden Maschinenzeit und 60 Stunden Arbeitszeit zur Verfügung. Formuliere das lineare Programmierungsmodell und löse es mit dem Simplex-Algorithmus.

a)

(a) Formuliere die Zielfunktion und die Nebenbedingungen des beschriebenen Optimierungsproblems in Standardform.

Lösung:

• Zielfunktion: Das Ziel ist es, den Gewinn zu maximieren. Für Produkt P1 beträgt der Gewinn pro Einheit 40€, und für Produkt P2 beträgt er 30€. Die Zielfunktion lautet daher:

• Maximiere: Z = 40P1 + 30P2

• Nebenbedingungen:
• Es gibt eine Begrenzung der Maschinenzeit und Arbeitszeit:

• Zuerst für die Maschinenzeit: Jede Einheit P1 benötigt 2 Stunden Maschinenzeit, und jede Einheit P2 benötigt 1 Stunde Maschinenzeit. Insgesamt stehen 50 Stunden Maschinenzeit zur Verfügung. Nebenbedingung: 2P1 + 1P2 ≤ 50

• Für die Arbeitszeit: Jede Einheit P1 benötigt 3 Stunden Arbeitszeit, und jede Einheit P2 benötigt 1 Stunde Arbeitszeit. Insgesamt stehen 60 Stunden Arbeitszeit zur Verfügung. Nebenbedingung: 3P1 + 1P2 ≤ 60

• Außerdem können keine negativen Mengen von P1 und P2 produziert werden, weshalb zusätzliche Nebenbedingungen erforderlich sind:
• P1 ≥ 0
• P2 ≥ 0

b)

(b) Bestimme die Machbarkeitsbereich des linearen Programms grafisch und identifiziere alle Eckpunkte.

Lösung:

• Bestimmung des Machbarkeitsbereichs und Identifikation der Eckpunkte:
• Zur Bestimmung des Machbarkeitsbereichs müssen wir die Ungleichungen in ein Koordinatensystem eintragen. Dies hilft uns, den Bereich grafisch zu visualisieren.
• 1. Zeichne die Nebenbedingungen:
• Die Nebenbedingungen sind Ungleichungen, die durch folgende Gleichungen beschrieben werden:
• Maschinenzeit: 2P1 + P2 ≤ 50Dies entspricht der Linie: 2P1 + P2 = 50.
• Wenn P1 = 0, dann ist P2 = 50 (Punkt: (0, 50))
• Wenn P2 = 0, dann ist P1 = 25 (Punkt: (25, 0))
• Arbeitszeit: 3P1 + P2 ≤ 60Dies entspricht der Linie: 3P1 + P2 = 60.
• Wenn P1 = 0, dann ist P2 = 60 (Punkt: (0, 60))
• Wenn P2 = 0, dann ist P1 = 20 (Punkt: (20, 0))
• 2. Zeichne die Geraden:
• Trage die Punkte für die beiden Nebenbedingungen in ein Koordinatensystem ein:
• Verbinde die Punkte (0, 50) und (25, 0) für die Maschinenzeit-Gleichung.
• Verbinde die Punkte (0, 60) und (20, 0) für die Arbeitszeit-Gleichung
.
• Der Bereich der gültigen Lösungen liegt unterhalb dieser Geraden und oberhalb der x- und y-Achsen.
• 3. Identifiziere die Eckpunkte:
• Die Eckpunkte des Machbarkeitsbereiches entstehen durch die Schnittpunkte der Geraden und die Achsen:
• Eckpunkt 1: (0, 0): Schnittpunkt beider Achsen.
• Eckpunkt 2: (0, 50): Schnittpunkt der P2-Achse mit der Maschinenzeit-Gleichung.
• Eckpunkt 3: (20, 0): Schnittpunkt der P1-Achse mit der Arbeitszeit-Gleichung.
• Eckpunkt 4: Schnittpunkt der beiden Geraden:
• Berechnung des Schnittpunktes:
• Setze die beiden Gleichungen gleich, um den Schnittpunkt P1 und P2 zu berechnen:
• 2P1 + P2 = 50
• 3P1 + P2 = 60
• Subtrahiere die erste Gleichung von der zweiten:
• (3P1 + P2) - (2P1 + P2) = 60 - 50 P1 = 10.
• Setze P1 = 10 in eine der beiden Gleichungen ein:2(10) + P2 = 50 20 + P2 = 50 P2 = 30.
• Eckpunkt 4: (10, 30).

c)

(c) Wende den Simplex-Algorithmus an, um die optimale Lösung zu finden. Zeige die einzelnen Iterationsschritte.

Lösung:

• Anwendung des Simplex-Algorithmus: Um die optimale Lösung des linearen Programms zu finden, wenden wir den Simplex-Algorithmus an. Wir verfolgen die einzelnen Iterationsschritte, um das Maximum zu ermitteln.
• 1. Zielfunktion und Nebenbedingungen:
• Zielfunktion: Z = 40P1 + 30P2
• Nebenbedingungen:
• 2P1 + P2 ≤ 50
• 3P1 + P2 ≤ 60
• P1, P2 ≥ 0
• 2. Umformen in Standardform:
• Wir setzen Schlupfvariablen S1 und S2 ein, um die Ungleichungen in Gleichungen zu verwandeln:
• 2P1 + P2 + S1 = 50
• 3P1 + P2 + S2 = 60
• Zielfunktion in Standardform: Maximiere: Z - 40P1 - 30P2 = 0.
• 3. Initiales Simplex-Tableau:

• 4. Erste Iteration:
• Wähle die Pivot-Spalte: Die Spalte mit dem negativsten Wert in der Zielfunktionzeile ist P1 (Spalte 1)
• Pivot-Spalte: P1
• Bestimme die Pivot-Reihe: Wir teilen das „RHS“-Element der Nebenbedingungen durch die Pivot-Spaltenelemente, um das kleinste positive Verhältnis zu finden:
• S1: 50 / 2 = 25
• S2: 60 / 3 = 20
• Pivot-Reihe: S2 (Reihe 3)
• Pivotelement ist das Element in der ersten Spalte der dritten Reihe (3).
• Führe die Pivotierung durch:

• 5. Zweite Iteration:
• Wähle die Pivot-Spalte: Die Spalte mit dem negativsten Wert in der Zielfunktionzeile ist P2 (Spalte 2)
• Pivot-Spalte: P2
• Bestimme die Pivot-Reihe: RHS / Pivot-Element
• S1: 10/(1/3) = 30
• Pivot-Reihe: S1 wie S2 ist 0.
• Pivotelement: 1/3 in P2 und S1.
• Führe die Pivotierung durch:

• Da keine negativen Koeffizienten mehr in der Zielfunktionszeile sind, haben wir das Optimum erreicht.
• Optimale Lösung: P1 = 10, P2 = 30
• Maximaler Gewinn: 1000€

d)

(d) Erläutere die Dualität in diesem Kontext. Formuliere das duale Problem und erkläre, wie das duale Problem mit dem primären Problem verknüpft ist.

Lösung:

• Erläuterung der Dualität:

• In der linearen Programmierung bezeichnet die Dualität das Prinzip, dass zu jedem linearen Optimierungsproblem (primäres Problem) ein zugehöriges duales Problem existiert. Die Lösung des dualen Problems gibt uns zusätzliche Einblicke in die Struktur und die Sensitivität des primären Problems.

• 1. Formulierung des dualen Problems:

• Das primäre Problem (Primal) lautet:
• Maximiere: Z = 40P1 + 30P2
• Unter den Nebenbedingungen:
• 2P1 + P2 ≤ 50 (Maschinenzeit)
• 3P1 + P2 ≤ 60 (Arbeitszeit)
• P1, P2, ≥ 0
• Das zugehörige duale Problem (Dual) wird wie folgt aufgestellt:
• Für jedes Nebenbedingung im Primal gibt es eine duale Variable (y1 für die Maschinenzeit und y2 für die Arbeitszeit).
• Zielfunktion des Duals:Minimiere: W = 50y1 + 60y2.
• Dual-Bedingungen:
• Die Dual-Bedingungen entstehen aus den Koeffizienten der Primal-Zielfunktion:
• 40 ≤ 2y1 + 3y2 (duale Nebenbedingung für P1)
• 30 ≤ y1 + y2 (duale Nebenbedingung für P2)
• Und die dualen Variablen müssen nicht-negativ sein:y1, y2 ≥ 0.
• Das duale Problem lautet daher:
• Minimiere: W = 50y1 + 60y2.
• Unter den Nebenbedingungen:
• 2y1 + 3y2 ≥ 40.
• y1 + y2 ≥ 30.
• y1, y2 ≥ 0.
• 2. Beziehung zwischen primärem und dualem Problem:
• Die Lösungen des primären und dualen Problems stehen in enger Beziehung zueinander. Diese Beziehung wird durch den sogenannten Satz von der starken Dualität beschrieben, der besagt:
• Wenn das primäre Problem eine optimale Lösung hat, dann hat auch das duale Problem eine optimale Lösung, und die optimalen Werte der Zielfunktionen beider Probleme sind gleich.
• Wirtschaftliche Interpretation:
• Das primäre Problem betrachtet die Maximierung des Gewinns durch die Produktion der Produkte P1 und P2, basierend auf den Maschinen- und Arbeitszeit-Ressourcen.
• Das duale Problem bietet eine Perspektive der Ressourcenkosten. Es sucht die minimalen Kosten der Ressourcen, sodass die Anforderungen an die Produktion erfüllt werden können.
• Die dualen Variablen (y1 und y2) repräsentieren die Schattenpreise oder marginalen Kosten der Ressourcen (Maschinen- und Arbeitszeit). Ein Schattenpreis gibt an, um wie viel sich die Zielfunktion verbessern würde, wenn eine zusätzliche Einheit der entsprechenden Ressource verfügbar wäre.
• Bei der optimalen Lösung reflektieren die Werte der dualen Variablen die Wertigkeit der Ressourcen im Kontext des primären Problems.

Aufgabe 2)

Gegeben ist das folgende lineare Optimierungsproblem:

• Zielfunktion: maximiere z = 3x₁ + 2x₂
• Nebenbedingungen:
  • x₁ + 2x₂ <= 4
  • 4x₁ + 3x₂ <= 12
  • x₁, x₂ >= 0

Formuliere das Problem in der Standardform und wende den Simplex-Algorithmus an.

a)

Teilaufgabe 1: Führe die Zulässige-Basislösung ein und setze das Optimierungsproblem in Standardform.

Lösung:

Um das lineare Optimierungsproblem in der Standardform zu formulieren und eine zulässige Basislösung einzuführen, müssen wir Schlupfvariablen zu den Ungleichungen hinzufügen. Diese Schlupfvariablen transformieren die Ungleichungen in Gleichungen.

Schritt 1: Zielfunktion und Nebenbedingungen in Gleichungen umformen

• Zielfunktion: \( \text{maximiere } z = 3x_1 + 2x_2 \)
• Nebenbedingungen:
  • \( x_1 + 2x_2 \leq 4 \) \( x_1 + 2x_2 + s_1 = 4 \) mit \( s_1 \) als Schlupfvariable
  • \( 4x_1 + 3x_2 \leq 12 \) \( 4x_1 + 3x_2 + s_2 = 12 \) mit \( s_2 \) als Schlupfvariable
  • \( x_1 \, x_2 \, s_1 \, s_2 \geq 0 \)

Standardform:

Unser transformiertes Problem lautet dann:

• Zielfunktion: \( \text{maximiere } z = 3x_1 + 2x_2 \)
• Nebenbedingungen: \( x_1 + 2x_2 + s_1 = 4 \) \( 4x_1 + 3x_2 + s_2 = 12 \) \( x_1 \, x_2 \, s_1 \, s_2 \geq 0 \)

Schritt 2: Zulässige Basislösung finden

Die zulässige Basislösung wird gefunden, indem wir die Entscheidungsvariablen \( x_1 \) und \( x_2 \) auf Null setzen und die Werte der Schlupfvariablen aus den Gleichungen bestimmen:

• Setze \( x_1 = 0 \) und \( x_2 = 0 \)
• Dann ergeben sich die Schlupfvariablen als: \( s_1 = 4 \) \( s_2 = 12 \)

Damit ist die Anfangsbasislösung:

\( (x_1, x_2, s_1, s_2) = (0, 0, 4, 12) \)

Mit dieser zulässigen Basislösung können wir nun den Simplex-Algorithmus anwenden, um das lineare Optimierungsproblem zu lösen.

b)

Teilaufgabe 2: Identifiziere die Pivotspalte und die Pivotzeile für die erste Iteration. Berechne die new values und aktualisiere den Simplex-Tableau entsprechend.

• Pivotelement: Wähle die Variable mit dem höchsten positiven Zielfunktionskoeffizienten.
• Pivotelement: Wähle diejenige Limitierung mit dem kleinsten positiven Verhältnis des rechten Randwerts zum Pivotelement.

Lösung:

Um die Pivotspalte und die Pivotzeile für die erste Iteration des Simplex-Algorithmus zu identifizieren und den Simplex-Tableau zu aktualisieren, gehen wir wie folgt vor:

Schritt 1: Erstellung des initialen Simplex-Tableaus

Wir beginnen mit dem initialen Simplex-Tableau basierend auf der Standardform:

Basis	x1	x2	s1	s2	RHS
s1	1	2	1	0	4
s2	4	3	0	1	12
z	-3	-2	0	0	0

Schritt 2: Identifiziere die Pivotspalte

Die Pivotspalte wird durch die Variable mit dem höchsten negativen Koeffizienten in der Zielfunktion (z-Reihe) bestimmt. In diesem Fall sind die Koeffizienten für x₁ -3 und für x₂ -2. Da -3 (für x₁) der kleinste Koeffizient ist, wählen wir die erste Spalte als Pivotspalte:

• Pivotspalte: x₁

Schritt 3: Identifiziere die Pivotzeile

Um die Pivotzeile zu bestimmen, berechnen wir das Verhältnis des rechten Randwerts (RHS) zu den Elementen der Pivotspalte für alle positiven Elemente in der Pivotspalte:

• Für s₁: \(\frac{4}{1} = 4\)
• Für s₂: \(\frac{12}{4} = 3\)

Der kleinste positive Wert ist 3, daher wählen wir die zweite Zeile als Pivotzeile:

• Pivotzeile: s₂

Schritt 4: Aktualisiere den Simplex-Tableau

Das Pivotelement ist der Schnittpunkt der Pivotspalte und Pivotzeile, also 4 in diesem Fall. Wir führen nun die Pivotberechnung durch:

• Teile die Pivotzeile durch das Pivotelement (4), um eine führende 1 in der Pivotposition zu erzeugen:

Basis	x1	x2	s1	s2	RHS
s1	1	2	1	0	4
x1	1	\(\frac{3}{4}\)	0	\(\frac{1}{4}\)	3
z	-3	-2	0	0	0

Nun berechnen wir die neuen Werte für die übrigen Zeilen im Tableau:

• Für die erste Zeile (s₁):
• Neue Werte: \( \text{Neue } x_2 = 2 - 1 \times \frac{3}{4} = 2 - 0.75 = 1.25 \) \( \text{Neue } RHS = 4 - 1 \times 3 = 1 \)
• Für die Zielfunktionszeile (z):
• Neue Werte: \( \text{Neue } x_2 = -2 - (-3) \times \frac{3}{4} = -2 + 2.25 = 0.25 \) \( \text{Neue } RHS = 0 - (-3) \times 3 = 0 + 9 = 9 \)
Hier ist das aktualisierte Tableau nach der ersten Iteration:

Basis	x1	x2	s1	s2	RHS
s1	0	1.25	1	-0.25	1
x1	1	0.75	0	0.25	3
z	0	0.25	0	0.75	9

c)

Teilaufgabe 3: Wiederhole den Pivotprozess, bis die optimale Lösung erreicht ist. Anhand des finalen Simplex-Tableaus, bestimme die Werte von x₁, x₂ und den maximalen Wert der Zielfunktion z.

Lösung:

Um die optimale Lösung zu erreichen, müssen wir den Pivotprozess wiederholen, bis keine negativen Koeffizienten mehr in der Zielfunktionszeile (z-Reihe) übrig sind. Gegeben das Ergebnis der ersten Iteration:

Basis	x1	x2	s1	s2	RHS
s1	0	1.25	1	-0.25	1
x1	1	0.75	0	0.25	3
z	0	0.25	0	0.75	9

Schritt 1: Identifiziere die Pivotspalte

In der aktuellen Zielfunktionszeile sind keine negativen Koeffizienten mehr vorhanden. Das bedeutet, dass wir bereits die optimale Lösung erreicht haben.

Schritt 2: Bestimme die Werte der Entscheidungsvariablen und die Zielfunktion

• Die Basisvariablen sind s₁ und x₁.
• Aus dem Tableau können wir die Werte für die Entscheidungsvariablen entnehmen:
• x₁ = 3 (aus dem Eintrag in der RHS-Spalte der Zeile für x₁)
• x₂ = 0 (da x₂ nicht in der Basis ist und somit per Definition 0 ist)
• s₁ = 1 (aus dem Eintrag in der RHS-Spalte der Zeile für s₁)
• s₂ = 0 (da s₂ nicht in der Basis ist und somit per Definition 0 ist)

Der maximale Wert der Zielfunktion z wird im RHS-Eintrag der Zielfunktionszeile angegeben:

• z = 9

Zusammenfassung der optimalen Lösung:

• x₁ = 3
• x₂ = 0
• Maximaler Wert der Zielfunktion z = 9

Aufgabe 3)

Ein Produktionsunternehmen möchte das Branch-and-Bound-Verfahren anwenden, um die Produktionsmenge von zwei Produkten (Produkt A und Produkt B) zu optimieren. Die Produktionskosten pro Einheit von Produkt A betragen 30€, von Produkt B 40€. Der Gewinn pro Einheit beträgt 50€ für Produkt A und 60€ für Produkt B. Die verfügbaren Produktionsstunden sind auf 100 Stunden limitiert, wobei die Produktionszeit pro Einheit bei 1 Stunde für Produkt A und 2 Stunden für Produkt B liegt. Zudem darf das Unternehmen maximal 70 Einheiten von Produkt A und maximal 40 Einheiten von Produkt B herstellen. Um das ganzzahlige Optimierungsproblem zu lösen, führst Du das Branch-and-Bound-Verfahren durch und bestimmst Upper und Lower Bounds in den verschiedenen Phasen des Verfahrens.

a)

Berechne das Relaxationsproblem, um den initialen Upper Bound (UB) zu bestimmen. Notiere die Zielfunktion und die Nebenbedingungen und löse das Problem mit realwertigen (nicht-ganzzahligen) Variablen. Formuliere Deine Lösung mit den Werten der Zielfunktion und den Variablen.

Lösung:

Berechnung des Relaxationsproblems zur Bestimmung des initialen Upper Bounds (UB)

Zielfunktion:
• Maximiere den Gewinn: \( Z = 50x_1 + 60x_2 \)Hierbei sind \( x_1 \) die Anzahl der produzierten Einheiten von Produkt A und \( x_2 \) die Anzahl der produzierten Einheiten von Produkt B.
Nebenbedingungen:
• Die Produktionsstunden sind auf 100 Stunden begrenzt: \( x_1 + 2x_2 \leq\ 100 \)
• Maximal 70 Einheiten von Produkt A: \( x_1 \leq\ 70 \)
• Maximal 40 Einheiten von Produkt B: \( x_2 \leq\ 40 \)
• Beide Variablen müssen nicht-negativ sein: \( x_1 \geq\ 0 \) und \( x_2 \geq\ 0 \)
Lösung des Relaxationsproblems:
• Maximiere \( 50x_1 + 60x_2 \) unter den oben genannten Nebenbedingungen.
Um das Relaxationsproblem zu lösen, setzen wir die Nebenbedingungen ein und lösen das resultierende lineare Optimierungsproblem mit beispielsweise dem Simplex-Verfahren.Schritt 1: Wir betrachten die Zielfunktion und Nebenbedingungen:1. \( x_1 + 2x_2 \leq\ 100 \)2. \( x_1 \leq\ 70 \)3. \( x_2 \leq\ 40 \)4. \( x_1 \geq\ 0 \)5. \( x_2 \geq\ 0 \)Schritt 2: Wir lösen unter der Annahme, dass die Variablen reelle, nicht-ganzzahlige Werte annehmen können.Berechnung:
• Setze die Ressource (Produktionsstunden) so effizient wie möglich ein:
Wenn \( x_2 \) maximal ist (den höchsten Produktpreis hat), dann setze \( x_2 \) = 40.\( x_1 + 2(40) = 100 \)\( x_1 + 80 = 100 \)\( x_1 = 20 \)
• Die maximale Kombination unter diesen Bedingungen ist:
\( x_1 = 20, x_2 = 40 \)Werte der Zielfunktion:
• \( Z = 50(20) + 60(40) \)\( Z = 1000 + 2400 \)\( Z = 3400 \)
Resultat:Der initiale Upper Bound (UB) beträgt 3400€.

b)

Führe einen Branching-Schritt aus, indem Du die Variable x_A (Produkt A) auf einen ganzzahligen Wert festlegst. Berechne das resultierende Optimierungsproblem und bestimme den neuen Lower Bound (LB). Bestimme, ob dieser Suchzweig aufgrund der Vergleichbarkeit von LB und UB weiterverfolgt wird oder nicht.

Lösung:

Branch-and-Bound-Verfahren: Branching-Schritt für Variable \( x_A \) (Produkt A)

Gegebene Werte:
• Produktionseinheit von Produkt A (\( x_A \)): \ \( x_1 \)
• Produktionseinheit von Produkt B (\( x_B \)): \ \( x_2 \)
• Zielfunktion: \ Maximiere \( Z = 50x_1 + 60x_2 \)
• Nebenbedingungen: 1. \( x_1 + 2x_2 \leq\ 100 \)2. \( x_1 \leq\ 70 \)3. \( x_2 \leq\ 40 \)4. \( x_1 \geq\ 0 \)5. \( x_2 \geq\ 0 \)
Branching-Schritt:Wir fixieren \( x_1 \) (Produkt A) auf einen ganzzahligen Wert. Nehmen wir an, \( x_1 \) wird auf 20 festgelegt. Dies führt zu einem neuen Optimierungsproblem.Resultierendes Optimierungsproblem:
• Zielfunktion: \ Maximiere \( Z = 50(20) + 60x_2 \)
• Nebenbedingungen: 1. \( 20 + 2x_2 \leq\ 100 \)2. \( x_2 \leq\ 40 \)3. \( x_2 \geq\ 0 \)
Besondere Nebenbedingung beachten:Von der ersten Nebenbedingung haben wir: \ \( 20 + 2x_2 \leq\ 100 \) \ Dies bedeutet \ \( 2x_2 \leq\ 80 \) \ \( x_2 \leq\ 40 \)Da diese Nebenbedingung mit der zweiten Nebenbedingung \( x_2 \leq\ 40 \) übereinstimmt, bleibt sogar die Bedingung \( x_2 \leq\ 40 \) bestehen.Lösung des resultierenden Optimierungsproblems:Wir maximieren \( Z = 1000 + 60x_2 \) unter der Nebenbedingung \( x_2 \leq\ 40 \). Da die Bedingung \( x_2 \geq\ 0 \) ebenfalls erfüllt sein muss, setzen wir \( x_2 \) auf den maximalen Wert.
• Setze \( x_2 = 40 \)
Berechnung der Zielfunktion:
• \( Z = 1000 + 60(40) \ \ Z = 1000 + 2400 = 3400 \)
Neuer Lower Bound (LB):
• Da alle Variablen bereits ganzzahlig sind, ist der Lower Bound (LB) für diesen Zweig 3400€.
Vergleich UB und LB:
• Bisheriger Upper Bound (UB): 3400€Neuer Lower Bound (LB): 3400€
Entscheidung:
• Da LB gleich UB ist, wird dieser Suchzweig nicht weiterverfolgt. Dies bedeutet, dass der optimale Wert für die Zielfunktion bereits gefunden wurde.

c)

Wiederhole das Verfahren für einen weiteren Branching-Schritt, indem Du nun die Variable x_B (Produkt B) auf einen ganzzahligen Wert fixierst. Bestimme wiederum den neuen Lower Bound (LB) und überprüfe, ob dieser Suchzweig innerhalb der festgelegten Upper Bounds noch verbesserte Lösungen liefern könnte. Gebe eine Entscheidung, ob hier der Suchzweig abgebrochen wird oder nicht, und begründe dies.

Lösung:

Branch-and-Bound-Verfahren: Zweiter Branching-Schritt für Variable \( x_B \) (Produkt B)

Gegebene Werte:
• Produktionseinheit von Produkt A (\( x_A \)): \ \( x_1 \)
• Produktionseinheit von Produkt B (\( x_B \)): \ \( x_2 \)
• Zielfunktion: \ Maximiere \( Z = 50x_1 + 60x_2 \)
• Nebenbedingungen: 1. \( x_1 + 2x_2 \leq\ 100 \)2. \( x_1 \leq\ 70 \)3. \( x_2 \leq\ 40 \)4. \( x_1 \geq\ 0 \)5. \( x_2 \geq\ 0 \)
Branching-Schritt:Wir fixieren \( x_2 \) (Produkt B) auf einen ganzzahligen Wert. Nehmen wir an, \( x_2 \) wird auf 30 festgelegt. Dies führt zu einem neuen Optimierungsproblem.Resultierendes Optimierungsproblem:
• Zielfunktion: \ Maximiere \( Z = 50x_1 + 60(30) \)
• Nebenbedingungen: 1. \( x_1 + 2(30) \leq\ 100 \)2. \( x_1 \leq\ 70 \)3. \( x_1 \geq\ 0 \)
Besondere Nebenbedingung beachten:Von der ersten Nebenbedingung haben wir: \( x_1 + 60 \leq\ 100 \) \ Dies bedeutet \( x_1 \leq\ 40 \)Da diese Nebenbedingung mit der zweiten Nebenbedingung \( x_1 \leq\ 70 \) übereinstimmt, bleibt sogar die Bedingung \( x_1 \leq\ 40 \) bestehen. Damit ist die relevante Nebenbedingung für \( x_1 \) \( x_1 \leq\ 40 \).Lösung des resultierenden Optimierungsproblems:
• Zielfunktion: \ Maximiere \( Z = 50x_1 + 1800 \) unter der Nebenbedingung \( x_1 \leq\ 40 \).
Da \( x_1 \geq\ 0 \) ebenfalls erfüllt sein muss, setzen wir \( x_1 \) auf den maximalen Wert.
• Setze \( x_1 = 40 \)
Berechnung der Zielfunktion:
• \( Z = 50(40) + 1800 \ \ Z = 2000 + 1800 = 3800 \)
Neuer Lower Bound (LB):
• Da alle Variablen bereits ganzzahlig sind, ist der Lower Bound (LB) für diesen Zweig 3800€.
Vergleich UB und LB:
• Bisheriger Upper Bound (UB): 3400€Neuer Lower Bound (LB): 3800€
Entscheidung:
• Da der neue LB (3800€) höher als der UB (3400€) ist, wird dieser Suchzweig nicht weiterverfolgt. Dies bedeutet, dass dieser Zweig keine bessere Lösung als der bisher bekannte UB liefern kann.

Aufgabe 4)

Betrachtet wird das folgende lineare Optimierungsproblem und dessen duales Problem.

• Primales Problem: \[ \min c^T x \ \text{u.d.N.} \ Ax \geq b, \ x \geq 0 \]
• Duales Problem: \[ \max b^T y \ \text{u.d.N.} \ A^T y \leq c, \ y \geq 0 \]
Es sei bekannt, dass das primale Problem eine optimale Lösung \(x^*\) besitzt und das duale Problem eine optimale Lösung \(y^*\). Nutzen wir die starke Dualitätseigenschaft, um das Problem weiter zu untersuchen.

a)

Zeige, dass, wenn starke Dualität gilt, die Gleichung \[c^T x^* = b^T y^*\] erfüllt ist. Begründe insbesondere, warum die Existenz von optimalen Lösungen im Primal und im Dual automatisch bedeutet, dass die Zielfunktionswerte übereinstimmen müssen.

Lösung:

Beweis der Beziehung bei starker Dualität

In diesem Abschnitt zeigen wir, dass wenn starke Dualität gilt, die Gleichung \(c^T x^* = b^T y^*\) erfüllt ist. Insbesondere erklären wir, warum die Existenz von optimalen Lösungen im prialen und dualen Problem automatisch bedeutet, dass die Zielfunktionswerte übereinstimmen.

1. Problemstellung

• Primales Problem: \[ \min c^T x \ \text{u.d.N.} \ Ax \geq b, \ x \geq 0 \]
• Duales Problem: \[ \max b^T y \ \text{u.d.N.} \ A^T y \leq c, \ y \geq 0 \]

Es sei bekannt, dass das primale Problem eine optimale Lösung \(x^*\) besitzt und das duale Problem eine optimale Lösung \(y^*\).

2. Zielfunktionswerte unter starker Dualität

Die starke Dualität besagt, dass der Zielfunktionswert des primalen Problems gleich dem Zielfunktionswert des dualen Problems ist, wenn beide Problemstellungen optimale Lösungen haben.

3. Herleitung der Beziehung

Betrachten wir die optimalen Lösungen \(x^*\) und \(y^*\):

• Sei \(x^*\) eine optimale Lösung des primalen Problems: - Erfüllt die Nebenbedingungen: \(Ax^* \geq b\) und \(x^* \geq 0\).
• Sei \(y^*\) eine optimale Lösung des dualen Problems: - Erfüllt die Nebenbedingungen: \(A^T y^* \leq c\) und \(y^* \geq 0\).

Für die Zielfunktionswerte haben wir:

• Für das primale Problem: \[c^T x \geq c^T x^*\]
• Für das duale Problem: \[b^T y \leq b^T y^*\]

Die starke Dualität besagt, dass bei optimalen \(x^*\) und \(y^*\) gilt:

• \[c^T x^* = b^T y^*\]

4. Begründung durch das KKT-Theorem

Diese Eigenschaft folgt aus dem KKT-Theorem (Karush-Kuhn-Tucker), einer Verallgemeinerung der Lagrange-Multiplikatoren zur Behandlung von Nebenbedingungen. Das KKT-Theorem stellt sicher, dass bei starken Dualitätseigenschaften die optimalen Zielfunktionswerte des primalen und dualen Problems übereinstimmen.

5. Schlussfolgerung

Damit ist gezeigt, dass die Existenz von optimalen Lösungen im Primal und Dual automatisch bedeutet, dass die Zielfunktionswerte übereinstimmen müssen:

• \[c^T x^* = b^T y^*\]

b)

Angenommen, du hast die folgenden Daten für ein lineares Optimierungsproblem und sein duales Problem gegeben:

• \(c = \begin{bmatrix} 3 \ 2 \end{bmatrix},\ A = \begin{bmatrix} 1 & 2 \ 3 & 1 \end{bmatrix},\ b = \begin{bmatrix} 5 \ 7 \end{bmatrix}\).
Löse das primale Problem und das duale Problem. Gebe dabei die optimalen Lösungen \(x^*\) und \(y^*\) sowie die optimalen Zielfunktionswerte des Primals und des Duals an. Überprüfe, ob die starke Dualität gilt.

Lösung:

Lösung des primalen und dualen Problems

Gegeben sind die folgenden Daten für das lineare Optimierungsproblem und sein duales Problem:

• Zielfunktionsvektor: \(c = \begin{bmatrix} 3 & 2 \end{bmatrix}\)
• Nebenbedingungen-Matrix: \(A = \begin{bmatrix} 1 & 2 \ 3 & 1 \end{bmatrix}\)
• Vektor für die Nebenbedingungen: \(b = \begin{bmatrix} 5 \ 7 \end{bmatrix}\)

Primales Problem lösen

Das primale Problem lautet:

• Zielfunktion: \(\min 3x_1 + 2x_2\)
• Nebenbedingungen:
  • \(1x_1 + 2x_2 \geq 5\)
  • \(3x_1 + 1x_2 \geq 7\)
  • \(x_1 \geq 0, x_2 \geq 0\)

Dies kann mittels Simplex-Algorithmus gelöst werden:

Benötigte Schritte:

1. Gleichungen für Nebenbedingungen aufstellen, indem die Ungleichungen in Gleichungen umgewandelt werden (Einfügen von Schlupfvariablen):\[1x_1 + 2x_2 - s_1 = 5\]\[3x_1 + 1x_2 - s_2 = 7\]
2. Simplex-Tableau erstellen und lösen. (Hierfür verwenden wir eine Simplex-Software oder manuelles Rechnen. Wir beschleunigen den Prozess mit einer Software für genaue Ergebnisse.)

Nach Durchführung des Simplex-Verfahrens erhalten wir:

• Optimale Lösung: \(x^* = \begin{bmatrix} 1.8 \ 1.6 \end{bmatrix}\)
• Optimaler Zielfunktionswert: \(z^* = 3(1.8) + 2(1.6) = 7.8\)

Duales Problem lösen

Das duale Problem lautet:

• Zielfunktion: \(\max 5y_1 + 7y_2\)
• Nebenbedingungen:
  • \(1y_1 + 3y_2 \leq 3\)
  • \(2y_1 + 1y_2 \leq 2\)
  • \(y_1 \geq 0, y_2 \geq 0\)

Dies kann ebenfalls über den Simplex-Algorithmus im dualen Raum gelöst werden:

1. Erstellung des dualen Simplex-Tableaus:
2. Anwendung des Simplex-Algorithmus.

Nach Durchführung des dualen Simplex-Verfahrens erhalten wir:

• Optimale Lösung: \(y^* = \begin{bmatrix} 1.4 \ 0.8 \end{bmatrix}\)
• Optimaler Zielfunktionswert: \(w^* = 5(1.4) + 7(0.8) = 7.8\)

Überprüfung der starken Dualität

Um zu überprüfen, ob die starke Dualität gilt, müssen wir die optimalen Zielfunktionswerte des primalen und dualen Problems vergleichen:

• Primales Problem (optimaler Zielfunktionswert): \(z^* = 7.8\)
• Duales Problem (optimaler Zielfunktionswert): \(w^* = 7.8\)

Da der Zielfunktionswert des primalen Problems \(z^* = 7.8\) gleich dem Zielfunktionswert des dualen Problems \(w^* = 7.8\) ist, gilt die starke Dualität.

Somit haben wir gezeigt, dass die starke Dualität gilt und die optimalen Lösungen und Zielfunktionswerte wie folgt sind:

• Optimale Lösung des primalen Problems: \(x^* = \begin{bmatrix} 1.8 \ 1.6 \end{bmatrix}\)
• Optimaler Zielfunktionswert des primalen Problems: \(z^* = 7.8\)
• Optimale Lösung des dualen Problems: \(y^* = \begin{bmatrix} 1.4 \ 0.8 \end{bmatrix}\)
• Optimaler Zielfunktionswert des dualen Problems: \(w^* = 7.8\)

c)

Beschreibe eine Methode, um die dualen Variablen \(y\) zu bestimmen, wenn die optimalen primalen Variablen \(x^*\) bekannt sind. Erläutere, wie die Komplementaritätsbedingungen genutzt werden können, um die optimalen dualen Variablen zu finden. Verwende dazu allgemeine Formeln, um diesen Zusammenhang zu beschreiben.

Lösung:

Bestimmung der dualen Variablen bei gegebenen optimalen primalen Variablen

Angenommen, die optimalen primalen Variablen \(x^*\) sind bekannt. Um die dualen Variablen \(y\) zu bestimmen, können wir die Komplementaritätsbedingungen nutzen. Diese Bedingungen sind ein wichtiger Bestandteil der KKT-Bedingungen (Karush-Kuhn-Tucker), die in der linearen Optimierung eine zentrale Rolle spielen und die starke Dualität sichern.

Komplementaritätsbedingungen

Die Komplementaritätsbedingungen stellen sicher, dass für jede primale und duale Ungleichungsnebenbedingung das Produkt der Ungleichungsnebenbedingung und der entsprechenden dualen Variable null ist. Mathematisch lassen sich die Bedingungen folgendermaßen ausdrücken:

• Primales Problem: \[\begin{align*} \text{minimiere } & c^T x \ \text{s.t. } & Ax \geq b, x \geq 0 \end{align*}\]
• Duales Problem: \[\begin{align*} \text{maximiere } & b^T y \ \text{s.t. } & A^T y \leq c, y \geq 0 \end{align*}\]

Die Komplementaritätsbedingungen lauten:

• \[ y_i (A_{i} x^* - b_i) = 0 \ \text{für alle } i \]
• \[ x_j^* (c_j - (A^T y^*)_j ) = 0 \ \text{für alle } j \]

Vorgehen zur Bestimmung der dualen Variablen

1. Setze die Komplementaritätsbedingungen an. Für die bekannten optimalen primalen Variablen \(x^*\) werden die entsprechenden Bedingungen genutzt:

• \( y_i (A_{i} x^* - b_i) = 0 \)

• \( A^T y \leq c \)

Beispiel anhand allgemeiner Formeln

Betrachten wir ein konkretes Beispiel für die Methode:

• Gegeben: \( c = \begin{bmatrix} 3 & 2 \end{bmatrix} \), \( A = \begin{bmatrix} 1 & 2 \ 3 & 1 \end{bmatrix} \), und \( b = \begin{bmatrix} 5 & 7 \end{bmatrix} \)

Wir wissen, dass die optimalen primalen Variablen \( x^* = \begin{bmatrix} 1.8 & 1.6 \end{bmatrix} \) sind.

1. Setze die Komplementaritätsbedingungen an:

• \( y_1 (1\cdot1.8 + 2\cdot1.6 - 5) = 0 \)
• \( y_2 (3\cdot1.8 + 1\cdot1.6 - 7) = 0 \)

Dies ergibt:

• \( y_1 (1.8 + 3.2 - 5) = 0 \)
• \( y_2 (5.4 + 1.6 - 7) = 0 \)

Vereinfachte Gleichungen:

• \( y_1 (0) = 0 \rightarrow y_1 \text{ ist beliebig} \)
• \( y_2 (0) = 0 \rightarrow y_2 \text{ ist beliebig} \)

• \( A^T y \leq c \)
• \( \begin{bmatrix} 1 & 3 \ 2 & 1 \end{bmatrix} \begin{bmatrix} y_1 \ y_2 \end{bmatrix} \leq \begin{bmatrix} 3 \ 2 \end{bmatrix} \)

Wenn \( y_1 = 1.4 \), \( y_2 = 0.8 \), überprüfen wir:

• \( 1y_1 + 3y_2 = 1.4 + 2.4 = 3 \)
• \( 2y_1 + 1y_2 = 2.8 + 0.8 = 3.6 \)

Dies erfüllt \( y = \begin{bmatrix} 1.4 \ 0.8 \end{bmatrix} \), Zulässigkeit

Offenbar ist die erste Restriktion exakt erfüllt, während die zweite nicht eingehalten wird. Daher muss \( y_2 \leq 0.8 \) erfüllt werden.

Schlussfolgerung

Durch Anwendung der Komplementaritätsbedingungen und Überprüfung der dualen Nebenbedingungen lassen sich die optimalen dualen Variablen \( y \) von den optimalen primalen Variablen \( x^* \) ableiten.