Kurs:Algorithmen und Datenstrukturen/Vorlesung/Lineare Optimierung

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Lineare Optimierung

Auf dieser Seite wird die lineare Optimierung behandelt. Eine lineare Optimierungsaufgabe ist: Maximiere eine lineare Funktion in mehreren Variablen

$max~c_{1}x_{1}+...+c_{n}x_{n}\ c_{i},x_{i}\in \mathbb {R} \Leftrightarrow maxc^{T}x$.

Die lineare Nebenbedingung sind gegeben als lineare Gleichungen:

$a_{11}x_{1}+...a_{1n}x_{n}=b_{1}$

...

$a_{m1}x_{1}+...a_{mn}x_{n}=b_{m}$

$\forall i=1,...,n:x_{i}\geq 0$

Dies entspricht dem Gleichungssystem:

$Ax=b,x\geq 0,a\in \mathbb {R} ^{mxn},b\in \mathbb {R} ^{m},x\in \mathbb {R} ^{n}$

Doch ist das ausdrucksstark genug für unsere Probleme?

Umformung von Gleichungssystemen

Beliebige Systeme lassen sich in die Standardform übertragen.

• Minimieren ist wie maximieren: $min~c^{T}x=max-c^{T}x$
• $\geq$ Bedingungen statt $\leq$ Bedingungen: $a_{i}^{T}x\leq b_{i}\Leftrightarrow -a_{i}^{T}x\geq -b$
• Gleichung zu Ungleichung: $a_{i}^{T}x=b_{i}\Leftrightarrow a_{i}^{T}x\geq b\land a_{i}^{T}x\leq b_{i}$
• Ungleichung zu Gleichung (Schlupfvariablen einführen): $a_{i}^{T}x\leq b_{i}\Leftrightarrow a_{i}^{T}x+s=b,s\geq 0$
• $x_{i}$ kann negativ sein: $x_{i}=s-t,s\geq 0,t\geq 0$

Beispiel Gewinnmaximierung

Eine Firma produziert zwei verschiedene Waren. Ware $x_{1}$ erbringt einen Gewinn von einem Euro. Ware $x_{2}$ erbringt einen Gewinn von 6 Euro. Die Frage hierzu lautet, welches Verhältnis von $x_{1}$ und $x_{2}$ führt zum größten Gewinn? Dazu gibt es zwei Nebenbedingungen:

• Die Firma kann täglich maximal 200 Einheiten der Ware $x_{1}$ produzieren und maximal 300 Einheiten der Ware $x_{2}$
• Insgesamt kann die Firma maximal 400 Einheiten pro Tag produzieren

Die Firma beschließt eine weitere Ware zu produzieren.

• Die Ware $x_{3}$ bringt einen Gewinn von 13 Euro.
• Die maximale Tagesproduktion liegt weiterhin bei 400 Einheiten.
• Für die Produktion von Ware $x_{2}$ und Ware $x_{3}$ wird dieselbe Maschine verwendet, allerdings ist der Produktionsaufwand für $x_{3}$ dreimal höher. Insgesamt kann die Maschine 600 Arbeitsschritte leisten.

Formuliere, die Zielfunktion: $max~x_{1}+6\cdot x_{2}+13\cdot x_{3}$.

Anschließend formuliere die Nebenbedingungen:

$x_{1}\leq 200$

$x_{2}\leq 300$

$x_{1}+x_{2}+x_{3}\leq 400$

$x_{2}+3\cdot x_{3}\leq 600$

$x_{1},x_{2},x_{3}\geq 0$

Polyeder

Die Nebenbedingungen definieren ein drei-dimensionales Polyeder, in dem die optimale Lösung liegt.

Nun formen wir in die Normalform um:

$max~x_{1}+6\cdot x_{2}+13\cdot x_{3}\to max~x_{1}+6\cdot x_{2}+13\cdot x_{3}$

$x_{1}\leq 200\to x_{1}+s_{1}=200$

$x_{2}\leq 300\to x_{2}+s_{2}=300$

$x_{1}+x_{2}+x_{3}\leq 400\to x_{1}+x_{2}+x_{3}+s_{3}=400$

$x_{2}+3\cdot x_{3}\leq 600\to x_{2}+3\cdot x_{3}+s_{4}=600$

$x_{1},x_{2},x_{3}\geq 0\to x_{1},x_{2},x_{3},s_{1}.s_{2}.s_{3},s_{4}\geq 0$

Polyeder

Die Nebenbedingungen definieren nun ein Polyeder, in dem die optimale Lösung liegt.

Polyeder

Die Zielfunktion $c=x_{1}+6\cdot x_{2}$ ist eine Gerade. Nun wird die Gerade verschoben, bis das Maximum erreicht ist.

Die Linearen Optimierungsprobleme der Form

$max~c^{T}x$

$(1)Ax=b;\ x\geq 0~$

$(2)Ax\leq b;\ x\geq 0$

besitzen genau dann eine endliche Optimallösung, wenn sie eine optimale Ecklösung (= „Ecke“ des zugehörigen Polyeders) besitzen. D.h. man muss zur Lösungsfindung nur die Ecken des Polyeders betrachten.