2
Inhalt§ 8.1 Motivation
§ 8.2 Optimierung ohne Nebenbedingungen
§ 8.3 Optimierung unter Nebenbedingungen
§ 8.4 Lineare Programmierung
§ 8.5 Kombinatorische Optimierung
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
3
8.1 Motivation§ Viele Anwendungen erfordern das Minimieren oder
Maximieren einer Zielfunktion unter Berücksichtigungeiner oder mehrerer Nebenbedingungen
§ Beispiele:
§ Bestimmen der optimalen Alternative (vgl. Kapitel 2)
§ Bestimmen der optimalen Regressionsgerade (vgl. Kapitel 3)
§ Bestimmen einer optimalen Abdeckung (SET COVER)
§ Bestimmen eines optimalen Produktionsplans
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
4
Motivation§ Das Gebiet der mathematischen Optimierung beschäftigt
sich allgemein mit solchen Optimierungsproblemen
§ In der Betriebswirtschaftslehre kümmert sich das GebietOperations Research darum, Entscheidungen herbeizuführen, indem betriebswirtschaftlicheFragestellungen mit Methoden der Optimierungmodelliert und gelöst werden
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
5
8.2 Optimierung ohne Nebenbedingungen§ Aus den Mathematikvorlesungen ist bekannt, wie man
die Extremstellen einer reellen Funktion
bestimmen kann
§ Vorgehensweise:
§ bestimme Nullstellen der ersten Ableitung
§ überprüfe zweite Ableitung an den ermittelten Nullstellen x*§ (lokales) Minimum, falls
§ (lokales) Maximum, falls
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
f : R æ R
f
Õ(x) = 0
f
ÕÕ(xú) > 0f
ÕÕ(xú) < 0
6
Beispiel: Optimierung ohne Nebenbedingungen§ Beispiel: Betrachte die Funktion
damit -1 und +1 als Nullstellen
damit ist -1 ein Maximum und +1 ein Minimum
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
-4 -2 0 2 4
-0.6
-0.4
-0.2
0.0
0.2
0.4
0.6
x
f(x)
f(x) = ≠x e
≠0.5 x
2
f
Õ(x) = ≠(1 ≠ x
2) e
≠0.5 x
2
f
ÕÕ(x) = x (3 ≠ x
2) e
≠0.5 x
2
7
Lokale und globale Minima und Maxima§ Wir finden so alle lokale und globale Minima (Maxima)
§ lokal, d.h. die Funktion nimm in der Nachbarschaftkeinen kleineren (größeren) Wert an
§ global, d.h. die Funktion nimmt nirgendwoeinen kleineren (größeren) Wert an
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
-40 -20 0 20 40
-1000
-500
0
x
f(x)
f(x) = ≠x
2 + e
0.15 x + e
≠0.19x
8
Funktionen mehrerer Variablen§ Vorgehensweise verallgemeinerbar für Funktionen
mehrerer Variablen (hier: x und y)
§ Vorgehensweise:
§ bestimme gemeinsame Nullstellen der partiellen Ableitungen
§ überprüfe zweite partielle Ableitungen an den Nullstellen x*
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
f : R ◊ R æ R
ˆf
ˆx
= 0 ˆf
ˆy= 0
9
8.3 Optimierung unter Nebenbedingungen§ Häufig gilt es, ein Minimum (Maximum) unter Einhaltung
einer oder mehrerer Nebenbedingungen zu finden
§ Beispiel: Produktionsplanung in einem Unternehmen
§ Produkt x erzielt Erlös von 10 € pro verkaufter Einheit
§ Produkt y erzielt Erlös von 25 € pro verkaufter Einheit
§ Beide Produkte benötigten ein gemeinsames Bauteil§ hiervon sind 50 Einheiten verfügbar
§ Produkt x benötigt eine Einheit; Produkt y benötigt drei Einheiten
§ Es kann eine beliebige (reelle) Anzahl der Produkte x und yproduziert werden; Ziel ist die Maximierung des Erlös
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
10
Beispiel: Optimierung unter Nebenbedingungen§ Produktionsplanung formuliert als Optimierungsproblem
§ Welche Mengen von x und y sollen produziert werden?
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
arg max
x,y
f(x, y) = 10 x + 25 y
s.t. 1 x + 3 y = 50
11
Reduktionsmethode§ Lässt sich die Nebenbedingung eindeutig nach einer der
beiden Variablen x und y auflösen, so können wir die Lösung in die Zielfunktion einsetzen
§ Beispiel: Auflösen der Nebenbedingung nach x
und Einsetzen in die Zielfunktion ergibt
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
1 x + 3 y = 50 … x = 50 ≠ 3 y
F (x, y) = 10 (50 ≠ 3y) + 25 y = 500 ≠ 5y
12
Reduktionsmethode§ Die Extremwerte der neuen Zielfunktion F(x,y) lassen sich
nun mit der bekannten Vorgehensweise bestimmen
§ Beispiel:
§ Wir stellen fest, dass y* = 0 ein Extremwert ist, d.h.das Unternehmen soll folgende Mengen produzieren:§ 0 Einheiten des Produkts y
§ 50 Einheiten des Produkts x
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
13
8.4 Lineare Programmierung§ Lineare Programmierung betrachtet den wichtigen
Spezialfall einer linearen Zielfunktion, die unterBerücksichtigung einer Menge linearerNebenbedingungen optimiertwerden soll
§ Beispiel: Produktionsplanung im Unternehmen
§ Produkt x erzielt Erlös von 1 €, Produkt y einen Erlös von 2 €
§ 150 Einheiten von Material a stehen zur Verfügung;jede Einheit von x benötigt 10, jede Einheit von y benötigt 10
§ 80 Einheiten von Material b stehen zur Verfügung;jede Einheit von x benötigt 4, jede Einheit von y benötigt 8
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
14
Ganzzahlige lineare Programmierung§ Allgemeine Form eines linearen Programms
§ Beispiel:
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
arg max
x1,...,xn
F (x1, . . . , x
n
) = c1 x1 + . . . + c
n
x
n
s.t. a
i1 x1 + . . . + a
in
x1 Æ b1
.
.
.
a
m1 x1 + . . . + a
mn
x1 Æ b
m
arg max
x1,...,xn
F (x, y) = 1 x + 2 y
s.t. 10 x + 10 y Æ 150
4 x + 8 y Æ 80
m Nebenbedingungen}
15
Graphische Lösung eines linearen Programms§ Im Fall zweier Variablen lässt sich graphisch eine Lösung
bestimmen (ähnlich zu graphischen Modellen in Kapitel 2)
§ Vorgehensweise:
§ jede Nebenbedingung beschreibt eine Gerade (Halbraum)
§ Schnitt dieser Halbräume ist Menge zulässiger Lösungen§ Zielfunktion beschreibt Menge von Geraden
§ weiter vom Ursprung entfernte Geraden entsprechen einemhöheren Wert der Zielfunktion
§ bestimme optimale Lösung durch Geradenverschiebung
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
16
Graphische Lösung eines linearen Programms§ Beispiel:
Bestimmen der Geraden zu den Nebenbedingungen
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
arg max
x1,...,xn
F (x, y) = 1 x + 2 y
s.t. 10 x + 10 y Æ 150
4 x + 8 y Æ 80
10 x + 10 y Æ 150 ∆ y = 15 ≠ x
4 x + 8 y Æ 80 ∆ y = 10 ≠ 0.5 x
17
Graphische Lösung eines linearen Programms
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
0 5 10 15
05
1015
x
y
10 x + 10 y Æ 150 ∆ y = 15 ≠ x
4 x + 8 y Æ 80 ∆ y = 10 ≠ 0.5 x
Menge zulässigerLösungen
18
Graphische Lösung eines linearen Programms§ Werte der Zielfunktion entsprechen Geraden der Form
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
0 5 10 15
05
1015
x
y
y = ≠0.5 x + c
19
Graphische Lösung eines linearen Programms§ Durch Verschiebung der Geraden finden wir die Menge
der optimalen Lösungen: der maximale Erlös von 20wird z.B. mit folgenden Produktionsmengen erzielt
§ x = 0 und y = 10
§ x = 10 und y = 5
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
0 5 10 15
05
1015
x
y
Menge optimalerLösungen
20
Ganzzahlige lineare Programmierung§ Zwei wichtige Spezialfälle der linearen Programmierung:
§ ganzzahlige lineare Programmierung (integer linear programming), wobei Variablen nur ganzzahligeWerte annehmen dürfen
§ 0/1 lineare Programmierung (0/1 linear programming), wobei Variablen nur die Werte 0 und 1annehmen dürfen
§ Diese Einschränkungen der Variablen machen das Finden einer optimalen Lösung deutlich schwerer
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
21
Solver§ Bekanntester Algorithmus zum Lösen linearer Programme
ist der sogenannte Simplex-Algorithmus
§ Zahlreiche Softwarepakete zum Lösen linearer Programme
§ IBM CPLEX
§ Gurobi
§ LINGO
§ Microsoft Excel (Solver Add-In)
diese sogenannten Solver können in der Regel auch ganzzahlige LPs und 0/1-LPs lösen
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
22
8.5 Kombinatorische Optimierung§ In der Informatik beschäftigen wir uns sehr häufig mit
kombinatorischer (d.h. mengenwertiger) Optimierung
§ Beispiel: SET COVER als bekanntes Optimierungsproblem
§ betrachte ein Universum U von Elementen
§ gegeben ist eine Menge S von Teilmengen Si⊆ U
§ finde eine möglichst kleine Teilmenge von S, so dass alle Elemente des Universumsdarin enthalten sind
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
arg minC™S
|C| s.t.€
SiœC
Si = U
23
Beispiel SET COVER
§ Beispiel: Universum seien die Zahlen 1, 2, …, 5
§ Eine optimale Lösung ist C = {S4, S6}
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
S1 = {1, 3, 5}S2 = {4}S3 = {5}S4 = {1, 2, 5}S5 = {1, 5}S6 = {3, 4}
24
SET COVER
§ Wie können wir allgemein eine optimale Lösung finden?
§ SET COVER ist als NP-schweres Problem bekannt
§ Idee 1: Zähle Teilmengen von S in aufsteigender Größeauf und überprüfe, ob sie alle Elemente aus U enthalten
§ Idee 2: Verwende einen gierigen (greedy) Algorithmus,der mit leerer Menge C beginnt und immer die Menge Si
hinzufügt, welche die meisten zusätzlichen Elementeaus U beinhaltet
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
25
Approximationsalgorithmus für SET COVER
§ Man kann zeigen, dass dieser gierige Algorithmuseine O(log n) Approximation liefert, d.h. die ermittelte Lösung C ist höchstens um einen Faktor O(log n)schlechter als eine optimale Lösung
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
1 greedySC (U ,S,C) {2 // Initial ist C leer3 C = ÿ;4
5 while (fiSjœC Sj ”= U ) {6 // Bestimme Teilmenge Sú mit meisten zus a tzlichen Elementen7 Sú
= arg max
SjœS|Sj fl (U \ fiSiœC Si)| ;
8
9 // Fuge Sú zu C hinzu10 C = C fi {Sú};11 }12 }
26
SET COVER mittels Simulated Annealing§ Simulated Annealing ist ein randomisiertes
Suchverfahren, welches häufig zur Lösung kombinatorischer Optimierungsproblemeneingesetzt werden kann
§ Idee:
§ beginne mit einer Lösung
§ wiederhole für eine Gesamtzahl von R Runden§ verändere die aktuelle Lösung zufällig
§ es sei d die erreichte Veränderung der Zielfunktion§ ist d ≤ 0, so übernehme veränderte Lösung
§ ist d > 0, so übernehme veränderte Lösung mit Wahrscheinlichkeitexp(-d/r) mit r als Zahl verbleibender Runden
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
27
SET COVER mittels Simulated Annealing§ Um Simulated Annealing auf SET COVER anwenden zu
können, benötigen wir eine initiale Lösung sowie ein Möglichkeit Lösungen zufällig ändern
§ als initiale Lösung verwenden wir C = S
§ um eine Lösung zu ändern, wählen wir zufällig§ eine enthaltene Teilmenge, entfernen sie und überprüfen,
ob dies noch eine gültige Lösung ist oder
§ eine nicht enthaltene Teilmenge aus und fügen sie hinzu
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
28
SET COVER als ganzzahliges lineares Programm§ Kombinatorische Optimierungsprobleme lassen sich oft
als ganzzahlige lineare Programme formulieren
§ Man kann dann einen verfügbaren Solver (z.B. Gurobi)verwenden, um eine (nahezu) optimale Lösung zu findenund muss sich selbst keine Gedanken über einengeeigneten Algorithmus machen
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
29
SET COVER als ganzzahliges lineares Programm§ SET COVER als ganzzahliges lineares Programm formuliert
§ eine Variable xi je Teilmenge Si
§ eine Nebenbedingung je Element uj aus U, die sicherstelltdass das Element uj abgedeckt wird; hierzu seien Gewichtecij definiert als
§ eine Nebenbedingung je Variable xi, die sicherstelltdass deren Wert in {0,1} liegt
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
cij = 1(uj œ Si)
30
SET COVER als ganzzahliges lineares Programm§ Damit ergibt sich folgendes ganzzahliges
lineares Programm
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung
arg minx1,...,xn
ÿ
i
x
i
s.t. ’j :ÿ
i
c
ij
x
i
Ø 0
’i : x
i
Æ 1
31
Zusammenfassung§ Reduktionsmethode zur Optimierung einer Funktion
mehrerer Variablen unter einer Nebenbedingung
§ Lineare Programmierung als wichtiger Spezialfall einer linearen Zielfunktion und einer Menge von linearenNebenbedingungen
§ SET COVER als Beispiel eines kombinatorischen Optimierungsproblems, welches sich aufunterschiedliche Arten lösen lässt
Entscheidungsunterstützende Systeme / Kapitel 8: Optimierung