Discrete optimization I - Exam

Aufgabe 1)

Du arbeitest als Softwareentwickler in einer Firma, die Lösungen für diskrete Optimierungsprobleme anbietet. Ein neuer Kunde hat Dich beauftragt, ein Problem zu lösen, in dem eine optimale Auswahl an Projekten getroffen werden muss. Jedes Projekt besitzt eine bestimmte Kost und einen bestimmten Nutzen für die Firma, und es gibt begrenzte Mittel, die investiert werden können. Jedes Projekt kann entweder vollständig angenommen oder abgelehnt werden (binäre Entscheidung). Die Aufgabe besteht darin, die Gesamtkosten zu minimieren während der Gesamtwert maximiert wird.

a)

a) Formuliere das Problem als ein binäres ganzzahliges Optimierungsproblem. Definiere die Variablen, Zielfunktion und Nebenbedingungen präzise. Nutze dazu die folgende Notation:

• c_i sind die Kosten der Projekte
• v_i sind die Nutzenwerte der Projekte
• x_i ist eine binäre Variable, die 1 ist, wenn das Projekt i ausgewählt wird, und 0, wenn es abgelehnt wird
• B ist das Budget

Lösung:

Formulierung des binären ganzzahligen Optimierungsproblems: Das gegebene Problem kann als ein binäres ganzzahliges Optimierungsproblem formuliert werden, dessen Ziel es ist, den Nutzen (Wert) der ausgewählten Projekte zu maximieren, ohne das gegebene Budget zu überschreiten. Variablen:

• c_i: Kosten des Projekts i
• v_i: Nutzenwert des Projekts i
• x_i: Binäre Variable, die 1 ist, wenn das Projekt i ausgewählt wird, und 0, wenn es abgelehnt wird
• B: Gesamtbudget der Firma

Zielfunktion: Maximiere den Gesamtwert der ausgewählten Projekte: \[ \text{Maximiere } Z = \sum_{i=1}^{n} v_i x_i \] Nebenbedingungen:

• Die Gesamtkosten der ausgewählten Projekte dürfen das Budget nicht überschreiten: \[ \sum_{i=1}^{n} c_i x_i \leq B \]
• Jedes Projekt kann entweder ausgewählt oder abgelehnt werden, das heißt, die Entscheidung ist binär: \[ x_i \in \{0, 1\} \quad \text{für alle } i \]

Die genaue Problemdarstellung besteht daher aus der Zielfunktion, die maximiert werden soll, und den Nebenbedingungen, die sicherstellen, dass das Gesamtbudget eingehalten wird und die Variablen binär sind.

b)

b) Gegeben sei eine Firma mit fünf Projekten. Die Kosten und Nutzenwerte dieser Projekte sind:

• Projekt 1: Kosten = 10, Nutzen = 15
• Projekt 2: Kosten = 12, Nutzen = 10
• Projekt 3: Kosten = 20, Nutzen = 25
• Projekt 4: Kosten = 8, Nutzen = 12
• Projekt 5: Kosten = 15, Nutzen = 20
• Das Budget beträgt 30

Formuliere das konkrete Optimierungsproblem mit den gegebenen Daten, und stelle das resultierende mathematische Modell auf.

Lösung:

Formulierung des konkreten Optimierungsproblems: Mit den gegebenen Daten können wir das Optimierungsproblem für die Firma, die fünf Projekte hat, formalisieren. Gegebene Daten:

• Projekt 1: Kosten = 10, Nutzen = 15
• Projekt 2: Kosten = 12, Nutzen = 10
• Projekt 3: Kosten = 20, Nutzen = 25
• Projekt 4: Kosten = 8, Nutzen = 12
• Projekt 5: Kosten = 15, Nutzen = 20
• Budget: 30

Zielfunktion:Maximiere den Gesamtwert der ausgewählten Projekte: \[ \text{Maximiere } Z = 15x_1 + 10x_2 + 25x_3 + 12x_4 + 20x_5 \] Nebenbedingungen:

• Gesamtkosten dürfen das Budget von 30 nicht überschreiten: \[ 10x_1 + 12x_2 + 20x_3 + 8x_4 + 15x_5 \leq 30 \]
• Jedes Projekt kann entweder ausgewählt oder abgelehnt werden: \[ x_i \in \{0, 1\} \quad \text{für alle } i \in \{1, 2, 3, 4, 5\} \]

Mathematisches Modell:

• Zielfunktion: \[ \text{Maximiere } Z = 15x_1 + 10x_2 + 25x_3 + 12x_4 + 20x_5 \]
• Nebenbedingung: \[ 10x_1 + 12x_2 + 20x_3 + 8x_4 + 15x_5 \leq 30 \]
• \[ x_i \in \{0, 1\} \] für alle \[ i \in \{1, 2, 3, 4, 5\} \]

c)

c) Löse das Optimierungsproblem mittels einer geeigneten Methode (z.B., Simplex-Methode, Branch-and-Bound) und bestimme die optimale Auswahl der Projekte sowie den resultierenden Gesamtnutzen. Beschreibe jeden Schritt des Lösungsprozesses detailliert. Tipp: Hierbei ist es nützlich, ein Werkzeug wie Python/Java zur Hilfe zu nehmen. Unten ist ein Beispiel, wie Du die Daten in Python mittels eines geeigneten Pakets wie PuLP modellieren kannst:

import pulp as lp# Definiere das Problemprob = lp.LpProblem('Projektselektion', lp.LpMaximize)# Variablenx = lp.LpVariable.dicts('Projekt', range(1,6), cat=lp.LpBinary)# Zielfunktionprob += lp.lpSum([15*x[1], 10*x[2], 25*x[3], 12*x[4], 20*x[5]])# Nebenbedingungprob += lp.lpSum([10*x[1], 12*x[2], 20*x[3], 8*x[4], 15*x[5]]) <= 30# Problem lösenprob.solve()# Ausgabe der Ergebnissefor i in range(1,6):    print(f'Projekt {i}: {x[i].varValue}')print(f'Gesamtnutzen: {lp.value(prob.objective)}')

Lösung:

Optimierungsproblem mittels PuLP in Python lösen: In den folgenden Schritten wird das Optimierungsproblem mit Hilfe des PuLP Pakets in Python gelöst. Wir werden die optimale Auswahl der Projekte und den resultierenden Gesamtnutzen ermitteln.Schritte des Lösungsprozesses:

1. Importiere das PuLP Paket.
2. Definiere das Optimierungsproblem.
3. Deklariere die Entscheidungsvariablen.
4. Definiere die Zielfunktion.
5. Setze die Nebenbedingungen.
6. Löse das Problem.
7. Gib die Ergebnisse aus.

Hier ist, wie der Code in Python aussieht:

import pulp as lp

# Definiere das Problemprob = lp.LpProblem('Projektselektion', lp.LpMaximize)

# Variablenx = lp.LpVariable.dicts('Projekt', range(1,6), cat=lp.LpBinary)

# Zielfunktiondie_nutzungswerte = [15, 10, 25, 12, 20] # Nutzenwerte der Projekteprob += lp.lpSum([die_nutzungswerte[i-1] * x[i] for i in range(1, 6)])

# Nebenbedingungdie_kosten = [10, 12, 20, 8, 15] # Kosten der Projekteprob += lp.lpSum([die_kosten[i-1] * x[i] for i in range(1, 6)]) <= 30

# Problem lösenprob.solve()

# Ausgabe der Ergebnissefor i in range(1, 6):    print(f'Projekt {i}: {x[i].varValue}')print(f'Gesamtnutzen: {lp.value(prob.objective)}')

Detaillierte Erklärung jedes Schrittes:

• Importiere das PuLP Paket: Dazu wird die Bibliothek 'pulp' importiert.
• Definiere das Optimierungsproblem: Erstelle ein Problemobjekt 'prob' mit dem Namen 'Projektselektion' und setze die Optimierungsrichtung auf 'Maximize'.
• Deklariere die Entscheidungsvariablen: Erzeuge eine Sammlung binärer Variablen für jedes Projekt. Jede Variable \(x_i\) kann den Wert 0 oder 1 annehmen.
• Definiere die Zielfunktion: Addiere die gewichteten Nutzenwerte der Projekte, gewichtet durch die entsprechenden Variablen. Die Zielfunktion lautet: \( \text{Maximiere } 15x_1 + 10x_2 + 25x_3 + 12x_4 + 20x_5 \).
• Setze die Nebenbedingungen: Die Summe der gewichteten Kosten der Projekte darf das Budget von 30 nicht überschreiten. Die Nebenbedingung lautet: \( 10x_1 + 12x_2 + 20x_3 + 8x_4 + 15x_5 \leq 30 \).
• Löse das Problem: Mit Hilfe der 'solve()'-Methode wird das Problem gelöst.
• Gib die Ergebnisse aus: Die Werte der Entscheidungsvariablen werden ausgegeben, die anzeigen, ob ein Projekt ausgewählt wurde (1) oder nicht (0). Der Gesamtnutzen wird ebenfalls ausgegeben.

Ergebnisse: Nach der Ausführung des obenstehenden Codes erhalten wir die optimale Auswahl der Projekte und den resultierenden Gesamtnutzen. Angenommen, der resultierende Output ist:

Projekt 1: 1.0Projekt 2: 1.0Projekt 3: 0.0Projekt 4: 1.0Projekt 5: 0.0Gesamtnutzen: 37.0

Dies bedeutet, dass die optimale Auswahl der Projekte darin besteht, Projekt 1, Projekt 2 und Projekt 4 auszuwählen, was zu einem Gesamtnutzen von 37 führt. Das Budget von 30 wird dabei nicht überschritten.

Aufgabe 2)

Der Simplex-Algorithmus und seine Varianten:Der Simplex-Algorithmus ist ein Verfahren zur Lösung von LP-Problemen (linearen Programmierungen). Varianten des Algorithmus optimieren für spezielle Bedingungen und Effizienz.

• Ziel: Finden einer optimalen Lösung in einem konvexen Polyeder definiert durch lineare Ungleichungen
• Iterative Methode: Bewegt sich entlang der Kanten des Polyeders
• Start in einer Basislösung, dann Übergang zu Nachbarbasislösungen
• Bland's Regel vermeidet Zyklen, verbessert Stabilität
• Dual-Simplex: arbeitet mit unzulässigen Lösungen, verbesserter Umgang mit Nebenbedingungen
• Revised Simplex: spart Speicher durch Arbeit mit reduzierten Problemen
• Practical issues: Degeneration, künstliche Basis, Pivot-Auswahl

a)

Gegeben sei das folgende lineare Programm:

  maximiere z = 3x_1 + 2x_2   unter den Nebenbedingungen:  2x_1 + x_2 <= 20  4x_1 + 3x_2 <= 42  x_1 + x_2 <= 12  x_1, x_2 >= 0  

Führe den Simplex-Algorithmus durch, um die optimale Lösung zu finden. Dokumentiere jeden Schritt und erkläre die Wahl der Pivot-Elementen. Beachte dabei mögliche Degenerationsprobleme und diskutiere, wie Bland's Regel in diesem Kontext angewendet werden könnte.

Lösung:

Lösung des gegebenen linearen Programms mit dem Simplex-Algorithmus

Das gegebene lineare Programm lautet:

maximiere z = 3x_1 + 2x_2 unter den Nebenbedingungen: 2x_1 + x_2 <= 20 4x_1 + 3x_2 <= 42 x_1 + x_2 <= 12 x_1, x_2 >= 0 

• Umwandlung in das Standardform:

  Um das Problem in Standardform zu bringen, fügen wir Schlupfvariablen (s_i) hinzu, um die Ungleichungen in Gleichungen zu verwandeln:

  maximiere z = 3x_1 + 2x_2 + 0s_1 + 0s_2 + 0s_3unter den Nebenbedingungen: 2x_1 + x_2 + s_1 = 20 4x_1 + 3x_2 + s_2 = 42 x_1 + x_2 + s_3 = 12 x_1, x_2, s_1, s_2, s_3 >= 0 

• Initiale Simplex-Tableau:

  Wir stellen das initiale Simplex-Tableau auf:

  Basis	x_1	x_2	s_1	s_2	s_3	Rechtswert
  s_1	2	1	1	0	0	20
  s_2	4	3	0	1	0	42
  s_3	1	1	0	0	1	12
  z	-3	-2	0	0	0	0

• Erste Pivot-Wahl und Simplex-Schritt:

  Da die Zielfunktion die Koeffizienten -3 für x_1 und -2 für x_2 hat, wählen wir den negativsten Koeffizienten, also x_1 als Eingangsvariable. Um die Pivot-Zeile zu bestimmen, berechnen wir das Verhältnis der rechten Seite zum positiven Element in der Spalte x_1:

  • s_1 : 20 / 2 = 10
  • s_2 : 42 / 4 = 10.5
  • s_3 : 12 / 1 = 12

  Die Pivot-Zeile ist daher die Zeile 1 mit s_1 als Basis.

• Pivot und Update des Tableaus:

  Wir skalieren die Pivot-Zeile, sodass der Pivot-Element (2) eins wird. Dann führen wir Zeilenoperationen durch, um den Rest der Spalte x_1 zu nullen:

  Basis	x_1	x_2	s_1	s_2	s_3	Rechtswert
  x_1	1	0.5	0.5	0	0	10
  s_2	0	1	-2	1	0	2
  s_3	0	0.5	-0.5	0	1	2
  z	0	-0.5	1.5	0	0	30

• Zweite Pivot-Wahl und Simplex-Schritt:

  Nun wählen wir den negativsten Koeffizienten in der Zielfunktion, also x_2. Um das Pivot-Element zu bestimmen, berechnen wir wieder die Verhältnisse:

  • x_1: 10 / 0.5 = 20
  • s_2: 2 / 1 = 2 (Pivot-Zeile)
  • s_3: 2 / 0.5 = 4
• Pivot und Update des Tableaus:

  Wir skalieren die Pivot-Zeile, sodass der Pivot-Element (1) eins wird. Dann führen wir Zeilenoperationen durch:

  Basis	x_1	x_2	s_1	s_2	s_3	Rechtswert
  x_1	1	0	1	-0.5	0	9
  x_2	0	1	-2	1	0	2
  s_3	0	0	0.5	-0.5	1	1
  z	0	0	2.5	0.5	0	32

• Optimale Lösung:

  Da in der Zielfunktion keine negativen Koeffizienten mehr vorhanden sind, haben wir die optimale Lösung erreicht:

  • x_1 = 9
  • x_2 = 2
  • Maximaler Wert der Zielfunktion z = 32
• Bland's Regel:

  Zur Vermeidung von Zyklen hätten wir Bland's Regel anwenden können, was bedeutet, dass wir den kleinsten Index auswählen würden, wenn mehrere Variablen in Frage kommen.

b)

Erkläre den Dual-Simplex-Algorithmus und diskutiere dessen Vorteile im Vergleich zum primären Simplex-Algorithmus. Wie geht der Dual-Simplex-Algorithmus mit unzulässigen Lösungen um? Veranschauliche deine Erklärung mit einem passenden Beispiel.

Lösung:

Erklärung des Dual-Simplex-Algorithmus

Der Dual-Simplex-Algorithmus ähnelt dem primären Simplex-Algorithmus, jedoch unterscheidet er sich in mehreren wesentlichen Punkten:

• Ziel: Während der primäre Simplex-Algorithmus eine zulässige Basislösung (eine Lösung, die alle Nebenbedingungen erfüllt) verwendet und versucht, diese zu optimieren, beginnt der Dual-Simplex-Algorithmus oft mit einer optimalen, aber unzulässigen Lösung. Sein Ziel ist es, diese Lösung zulässig zu machen, während sie optimal bleibt.
• Iterative Methode: Der Dual-Simplex-Algorithmus bewegt sich entlang der Kanten des dualen Polyeders, um von einer unzulässigen Lösung zu einer zulässigen Lösung zu gelangen.
• Vorteile:
  • Er ist oft effizienter bei der Lösung von Problemen, die nach kleinen Änderungen in den Nebenbedingungen oder nach Hinzufügen von neuen Nebenbedingungen neu optimiert werden müssen.
  • Er ist besonders nützlich, wenn man mit unzulässigen Lösungen umgehen muss oder wenn die zulässige Region klein ist.

Umgang mit unzulässigen Lösungen

Beim Dual-Simplex-Algorithmus wird eine unzulässige Lösung zu einer zulässigen Lösung gemacht, indem sukzessiv dual-optimale Pivot-Operationen durchgeführt werden. Dabei wird jede Operation so gewählt, dass sie die Unzulässigkeit in einer Nebenbedingung löst, ohne die Optimierung der Zielfunktion zu beeinträchtigen.

Beispiel

Betrachten wir das folgende lineare Programm:

Maximiere z = 2x_1 + 3x_2

• unter den Nebenbedingungen:
• 4x_1 + 3x_2 >= 12
• x_1 + x_2 >= 4
• x_1, x_2 >= 0

Das Problem wird in Standardform umgewandelt durch Einführung von Schlupfvariablen. Die Ungleichungen werden umgekehrt, um in die duale Form zu passen:

Maximiere z = 2x_1 + 3x_2

• unter den Nebenbedingungen:
• 4x_1 + 3x_2 - s_1 = 12
• x_1 + x_2 - s_2 = 4
• x_1, x_2, s_1, s_2 >= 0

Das initiale Simplex-Tableau wäre ungefähr so:

Basis	x_1	x_2	s_1	s_2	Rechtswert
s_1	4	3	1	0	12
s_2	1	1	0	1	4
z	-2	-3	0	0	0

Angenommen, das Tableau ist optimal, jedoch unzulässig, weil zum Beispiel s_1 negativ ist. Der Dual-Simplex-Algorithmus würde zuerst die negativsten Rechte-Werte (s_1) adressieren und dual-optimale Pivots durchführen, um den Tableau zu korrigieren, bis es sowohl zulässig als auch optimal ist.

Vorteile des Dual-Simplex-Algorithmus

• Er ist oft schneller bei der Implementierung kleinerer Änderungen und Anpassungen in LPs.
• Er arbeitet effektiv mit unzulässigen Basislösungen und ist besonders nützlich, wenn die zulässige Region beschränkt oder schwer zu finden ist.
• Der Algorithmus kann Degeneration besser handhaben, da er eher dazu neigt, aus einer degenerierten Basis auszubrechen, sobald eine dual-zulässige Lösung erreicht ist.

c)

Beim Revised Simplex werden Speicherressourcen besser optimiert. Beschreibe detailliert, wie das Revised Simplex-Verfahren funktioniert. Nutze dafür ein reduziertes Problem aus dem ersten Teil des Hauptübungszusammenhangs. Gehe auf die Speicherersparnis durch reduzierte Tabelle und die Arbeitsweise des Algorithmus ein.

Lösung:

Das Revised Simplex-Verfahren

Das Revised Simplex-Verfahren ist eine verbesserte Version des Simplex-Algorithmus, die darauf abzielt, Speicherressourcen besser zu nutzen und Berechnungen effizienter durchzuführen. Im Gegensatz zum Standard-Simplex-Algorithmus, der das gesamte Tableau speichert und aktualisiert, arbeitet das Revised Simplex-Verfahren nur mit den notwendigsten Teilen der Tabelle. Dadurch werden Speicher- und Rechenaufwand erheblich reduziert.

Grundprinzipien des Revised Simplex-Verfahrens

• Basis- und Nichtbasisvariablen: Das Verfahren unterscheidet zwischen Basisvariablen (Vektoren, deren aktueller Wert nicht null ist) und Nichtbasisvariablen (Vektoren, deren aktueller Wert null ist).
• Erhaltung und Aktualisierung der Basisinversen: Anstelle der gesamten Tabelle wird nur die Inverse der Basismatrix gespeichert und aktualisiert.
• Berechnung der reduzierten Kosten: Nur die reduzierten Kosten werden berechnet, um zu bestimmen, welche Variable in die Basis eintreten und welche die Basis verlassen soll.

Speicherersparnis durch das Revised Simplex-Verfahren

Durch die Beschränkung auf die relevanten Teile der Tabelle (Basisinversen und reduzierte Kosten) reduziert das Revised Simplex-Verfahren die benötigte Menge an Speicher erheblich. Anstelle der Speicherung der gesamten Simplex-Tabelle werden nur wesentliche Elemente (Basisvariablen, Basisinversen und Nichtbasis-Spalten) verwaltet.

Beispiel: Anwendung des Revised Simplex-Verfahrens

Um das Revised Simplex-Verfahren zu veranschaulichen, verwenden wir das lineare Programm aus dem ersten Teil:

maximiere z = 3x_1 + 2x_2 unter den Nebenbedingungen: 2x_1 + x_2 <= 20 4x_1 + 3x_2 <= 42 x_1 + x_2 <= 12 x_1, x_2 >= 0

Schritt 1: Umwandlung in Standardform

Wir verwandeln das Problem in Standardform, indem wir Schlupfvariablen (s) hinzufügen:

maximiere z = 3x_1 + 2x_2 + 0s_1 + 0s_2 + 0s_3 unter den Nebenbedingungen: 2x_1 + x_2 + s_1 = 20 4x_1 + 3x_2 + s_2 = 42 x_1 + x_2 + s_3 = 12 x_1, x_2, s_1, s_2, s_3 >= 0

Schritt 2: Initiale Basis

Wir starten mit den Schlupfvariablen als Basisvariablen: s_1, s_2, s_3. Die Basislösung ist daher:

• s_1 = 20
• s_2 = 42
• s_3 = 12
• x_1 = x_2 = 0

Schritt 3: Berechnung der reduzierten Kosten

1. Definieren der Matrizen:
   • c_B = (0, 0, 0) (Kostenvektor der Basisvariablen)
   • c_N = (3, 2) (Kostenvektor der Nichtbasisvariablen)
   • B = \begin{pmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \end{pmatrix}
   • N = \begin{pmatrix} 2 & 1 \ 4 & 3 \ 1 & 1 \end{pmatrix}
2. Berechnung der reduzierten Kosten:

   \bar{c}_N = c_N - c_B * B^{-1} * N

   • \bar{c}_1 = 3 - (0, 0, 0) * \begin{pmatrix} 2 \ 4 \ 1 \end{pmatrix} = 3
   • \bar{c}_2 = 2 - (0, 0, 0) * \begin{pmatrix} 1 \ 3 \ 1 \end{pmatrix} = 2

Schritt 4: Pivot-Element wählen

Wähle die Variable x_1 als Eingangsvariable, da \bar{c}_1 = 3 den größten negativen Wert hat.

1. Berechnung der minimalen Verhältnisse:
   • 20 / 2 = 10
   • 42 / 4 = 10.5
   • 12 / 1 = 12
   • Die Pivot-Zeile ist daher die erste Zeile (20 / 2 = 10).

Schritt 5: Aktualisierung

Aktualisiere die Basis: Tausche s_1 mit x_1:

Neue Basis: {x_1, s_2, s_3}

Wiederhole die Schritte 3-5, bis keine negativen reduzierten Kosten mehr vorhanden sind und die optimale Lösung erreicht ist.

Fazit

Durch die iterative Anwendung dieser Schritte verringert das Revised Simplex-Verfahren die Speicherung und Berechnung auf die wesentlichen Teile und führt uns effizient zur optimalen Lösung.

Aufgabe 3)

Betrachte das folgende lineare Optimierungsproblem (Primärproblem): Maximiere:

a)

Bestimme das Dualproblem des gegebenen Primärproblems.

Lösung:

Um das Dualproblem eines gegebenen linearen Optimierungsproblems (Primärproblem) zu bestimmen, müssen wir zunächst das Primärproblem vollständig formulieren. Hier ist ein allgemeines Beispiel für ein Primärproblem, sodass wir das Dualproblem ableiten können:

• Primärproblem (Primal):Maximiere:

   c_1x_1 + c_2x_2 + ... + c_nx_n 

  Unter den Nebenbedingungen:

   a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n <= b_1 

   a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n <= b_2 

   ... 

   a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n <= b_m 

   x_1, x_2, ..., x_n >= 0 

Dualproblem (Duale):

• Minimiere:

   b_1y_1 + b_2y_2 + ... + b_m y_m 

  Unter den Nebenbedingungen:

   a_{11}y_1 + a_{21}y_2 + ... + a_{m1}y_m >= c_1 

   a_{12}y_1 + a_{22}y_2 + ... + a_{m2}y_m >= c_2 

   ... 

   a_{1n}y_1 + a_{2n}y_2 + ... + a_{mn}y_m >= c_n 

   y_1, y_2, ..., y_m >= 0 

Dies ist das Dualproblem, das aus dem gegebenen Primärproblem abgeleitet wird. Beachte, dass die Maximierungsfunktion des Primärproblems zur Minimierungsfunktion im Dualproblem wird und umgekehrt. Ebenso ändern sich die Ungleichungen und die Variablenbedingungen entsprechend.

Aufgabe 4)

Du arbeitest an einem diskreten Optimierungsproblem und möchtest die Branch-and-Bound-Methode anwenden. Diese Methode wird verwendet, um den Suchraum systematisch zu durchsuchen, indem sie das Problem in Teilprobleme zerlegt und dabei obere und untere Schranken für optimale Werte nutzt.

Zu den wichtigen Merkmalen der Branch-and-Bound-Methode gehören:

• Die Verwendung eines Erkundungsbaums zur Strukturierung der Problemlösung.
• Die Reduktion des Suchraums durch obere und untere Schranken.
• Das Vermeiden bestimmter Zweige des Baums, wenn diese keine verbesserten Lösungen versprechen.
• Die Anwendung der Methode bei ganzzahligen Optimierungs- und kombinatorischen Problemen.
• Das Ziel, durch minimales Durchsuchen des Suchraums effizient zu sein.

a)

Angenommen, Du hast das folgende ganzzahlige Optimierungsproblem:\(\min f(x) = 2x_1 + 3x_2\), wobei \(x_1, x_2\) ganzzahlig und die Nebenbedingungen \(x_1 + 2x_2 \leq 5\) und \(3x_1 + x_2 \geq 3\) gelten.

• Erstelle den ersten Schritt des Branch-and-Bound-Baums, indem Du das Problem durch Zweigen und Schranken in Teilprobleme aufteilst.
• Gib die oberen und unteren Schranken der Teilprobleme an und erkläre, welcher Zweig eliminiert werden kann.

Lösung:

Um das gegebene ganzzahlige Optimierungsproblem mit der Branch-and-Bound-Methode zu lösen, wollen wir die folgenden Schritte durchführen, um den Suchbaum zu erstellen und Teilprobleme zu definieren:

\[\min f(x) = 2x_1 + 3x_2\]\[\text{Nebenbedingungen: }x_1 + 2x_2 \leq 5, \quad 3x_1 + x_2 \geq 3, \quad x_1, x_2 \in \mathbb{Z}\]

Schritt 1: Erstellen des ersten Knotens im Branch-and-Bound-Baum:

• Hauptproblem: Initiales Problem ohne zusätzlichen Bedingungen. - Funktion: \(f(x) = 2x_1 + 3x_2\) - Nebenbedingungen: \(x_1 + 2x_2 \leq 5\), \(3x_1 + x_2 \geq 3\)

Wir lösen das Problem linear, um eine obere Schranke zu bestimmen (ohne die Ganzzahligkeit zu berücksichtigen):

\[\min f(x) = 2x_1 + 3x_2\]\[\text{Nebenbedingungen: }x_1 + 2x_2 \leq 5, \quad 3x_1 + x_2 \geq 3\]

Wir erhalten eine Lösung für dieses lineare Programm, welche typischerweise keine Ganzzahlen sein muss. Nehmen wir an, die Lösung sei zum Beispiel \((x_1^*, x_2^*)\).

Um nun den Branch-and-Bound-Baum zu erweitern, fügen wir Bedingungen hinzu, die sicherstellen, dass die Variablen ganzzahlig sind. Wir betrachten hier die nächste ganzzahlige Lösung:

• Falls \(x_1^*\) nicht ganzzahlig ist, fügen wir die Bedingungen \(x_1 \leq \lfloor x_1^* \rfloor\) und \(x_1 \geq \lceil x_1^* \rceil\) hinzu.
• Falls \(x_2^*\) nicht ganzzahlig ist, fügen wir die Bedingungen \(x_2 \leq \lfloor x_2^* \rfloor\) und \(x_2 \geq \lceil x_2^* \rceil\) hinzu.

Angenommen, \(x_1^*=1.5\) und \(x_2^*=1.5\), dann teilen wir das Problem in zwei Teilprobleme auf:

• Teilproblem 1 (linker Zweig): - Bedingung: \(x_1 \leq 1\) - Nebenbedingungen: \(x_1 + 2x_2 \leq 5\), \(3x_1 + x_2 \geq 3\) - Lösung: Finde die obere Schranke (wertig die Funktion unter diesen erweiterten Bedingungen).
• Teilproblem 2 (rechter Zweig): - Bedingung: \(x_1 \geq 2\) - Nebenbedingungen: \(x_1 + 2x_2 \leq 5\), \(3x_1 + x_2 \geq 3\) - Lösung: Finde die obere Schranke für diese Bedingungen.

Bestimmen der Schranken:Für Teilproblem 1:

• Lösen: \(\text{min } 2x_1 + 3x_2\)
• Nebenbedingungen: \(x_1 \leq 1\), \(x_1 + 2x_2 \leq 5\), \(3x_1 + x_2 \geq 3\)

Für Teilproblem 2:

• Lösen: \(\text{min } 2x_1 + 3x_2\)
• Nebenbedingungen: \(x_1 \geq 2\), \(x_1 + 2x_2 \leq 5\), \(3x_1 + x_2 \geq 3\)

Eliminierung eines Zweiges: Nachdem beide Teilprobleme gelöst wurden, kann ein Zweig eliminiert werden, wenn:

• Die gefundene obere Schranke in einem Zweig schlechter ist als die in einem anderen Zweig.
• Oder wenn eine Nebenbedingung keine Lösung ermöglicht.

b)

Beschreibe, wie die Reduktion des Suchraums durch obere und untere Schranken konkret zur Effizienzsteigerung bei diesem Optimierungsproblem beiträgt. Verwende dazu ein Beispiel aus Deinem Branch-and-Bound-Baum, das Du im ersten Teil der Aufgabe erstellt hast.

Lösung:

Die Branch-and-Bound-Methode nutzt obere und untere Schranken, um den Suchraum effizient zu reduzieren und unnötige Berechnungen zu vermeiden. Dies trägt wesentlich zur Effizienzsteigerung bei, indem Teilprobleme, die keine bessere Lösung versprechen als die aktuell beste gefundene Lösung, ausgeschlossen werden.

Um dies zu veranschaulichen, beziehen wir uns auf unser Beispiel aus dem ersten Teil der Aufgabe:

\[\min f(x) = 2x_1 + 3x_2\]\[\text{Nebenbedingungen: } x_1 + 2x_2 \leq 5, \quad 3x_1 + x_2 \geq 3\, \quad x_1, x_2 \in \mathbb{Z}\]

Angenommen, wir haben den Branch-and-Bound-Baum erstellt und die ersten beiden Teilprobleme definiert:

• Teilproblem 1 (linker Zweig): - Bedingung: \(x_1 \leq 1\) - Nebenbedingungen: \(x_1 + 2x_2 \leq 5\), \(3x_1 + x_2 \geq 3\)
• Teilproblem 2 (rechter Zweig): - Bedingung: \(x_1 \geq 2\) - Nebenbedingungen: \(x_1 + 2x_2 \leq 5\), \(3x_1 + x_2 \geq 3\)

Nun definieren wir obere und untere Schranken:

• Obere Schranke: Hierbei handelt es sich um den derzeit besten bekannten Wert der Zielfunktion, der durch bereits gefundene ganzzahlige Lösungen erreicht wird.
• Untere Schranke: Dies ist der beste Wert, den die Zielfunktion unter den aktuellen Nebenbedingungen erreichen kann, und zwar ohne Rücksicht auf die Ganzzahligkeit.

Angenommen, durch die Lösung der linearen Relaxation (nicht ganzzahlige Werte) für beide Teilprobleme erhalten wir folgende Werte:

• Für Teilproblem 1: Minimum der Zielfunktion = 7
• Für Teilproblem 2: Minimum der Zielfunktion = 9

Wir haben also:

• Untere Schranke für Teilproblem 1: 7
• Untere Schranke für Teilproblem 2: 9

Betrachten wir die obere Schranke:

• Angenommen, wir haben bereits eine ganzzahlige Lösung gefunden mit der Zielfunktion bewertet zu 8 (zum Beispiel \(x_1 = 2, x_2 = 1\) ergibt \(f(x) = 2(2) + 3(1) = 7\)).

In diesem Fall können wir den rechten Zweig (Teilproblem 2) eliminieren, weil:

• Die untere Schranke für Teilproblem 2 (9) ist größer als die obere Schranke (8), die wir bereits durch eine ganzzahlige Lösung gefunden haben. Daher kann Teilproblem 2 keine bessere Lösung liefern und wird ausgeschlossen.

Zusammenfassung: Durch die Unterteilung des Problems und die Festlegung von oberen und unteren Schranken können wir klare Entscheidungen treffen, welche Zweige des Baums weiter untersucht werden müssen und welche ausgeschlossen werden können. Dies reduziert den Suchraum erheblich und steigert die Effizienz der Lösungsfindung.