Lineare Optimierung: Modell, Lösung, Anwendung

3835101390......Page 1
Lineare Optimierung......Page 3
Vorwort......Page 5
Inhalt......Page 8
1 Modellierung linearer Optimierungsaufgaben......Page 10
2.1 Zwei Entscheidungsvariablen......Page 18
2.2 Zwei Restriktionen......Page 23
3 Fourier-Motzkin-Elimination......Page 27
4.1 Normalform......Page 32
4.2 Primale Simplexmethode in vektorieller Form......Page 34
4.3 Primale Simplexmethode in Tableauform......Page 39
4.4 Zwei-Phasen-Methode......Page 43
4.5 Entartung......Page 50
5.1 Duale Aufgabe......Page 52
5.2 Starke Dualität......Page 55
5.3 Duale Simplexmethode......Page 56
5.4 Sensitivität und Postoptimalität......Page 58
5.4.1 Probleme mit parameterabhängiger Zielfunktion......Page 59
5.4.2 Probleme mit parameterabhängiger rechter Seite......Page 61
5.4.3 Aufnahme einer neuen Variablen......Page 63
5.4.4 Auftreten einer neuen Nebenbedingung......Page 64
6.1 Komplexität linearer Optimierungsaufgaben......Page 66
6.2.1 Lösung nichtlinearer Gleichungen......Page 70
6.2.2 Lösung nichtlinearer Gleichungssysteme......Page 72
6.3.1 Das ungestörte Gleichungssystem......Page 74
6.3.2 Der zentrale Pfad......Page 76
6.3.3 Anwendung des Newton-Verfahrens......Page 78
6.3.4 Zur Berechnung einer Startlösung für den Kurz-Schritt-Algorithmus......Page 79
7.1 Lösbarkeit von Matrixspielen in gemischten Strategien......Page 83
7.2.1 Das Modell und seine Eigenschaften......Page 89
7.2.2 Ein Lösungsalgorithmus......Page 94
7.3.1 Pareto-optimale Lösungen......Page 99
7.3.2 Berechnung aller Pareto-optimaler Lösungen bei Aufgaben mit zwei Zielfunktionen......Page 103
7.3.3 Der Fall von mehr als zwei Zielfunktionen......Page 104
7.4.1 Gerichtete Graphen......Page 106
7.4.2 Kürzeste Wege......Page 107
7.4.3 Flüsse maximaler Stärke......Page 109
7.4.4 (q-s)-Flüsse mit minimalen Kosten......Page 112
8.1 Begründung des Simplexalgorithmus......Page 113
8.2 Begründung des Newton-Verfahrens......Page 120
9 Hinweise und Lösungen......Page 124
10 Testklausur......Page 133
Literaturempfehlungen......Page 140
Literaturverzeichnis......Page 141
Sachverzeichnis......Page 143