#4 Lineare Optimierung

Question 1

Lineare Gleichungen

Answer 1

• enthalten auf beiden Seiten nur variablen als lineare Ausdrücke
• also nur die Summe aus Variablen evtl. mit Konstanten als Vorfaktoren

Question 2

(Un)Gleichungs-Normalform

Answer 2

Alle Variablen und alle Konstanten auf eine Seite

1000x + 300 = 1200 => 1000x = 900

Question 3

Zeichnerische Lösung

2 Variablen

Answer 3

(1) Beide Gleichungen nach y auflösen
Bsp.: y = 2/3 x + 4

(2) Ergebnis = zwei Geradengleichungen (g)

(3) Geradengleichung in Koordinatensystem Einzeichen und Lösung ablesen
- Koeffizient vor dem x-gibt die Steigung an
- Koeffizient ohne Variable den Schnittpunkt mit der y-Achse
Bsp.: 2/3 x + 4 (Schnittpunkt mit y-Achse bei 4, dann drei nach recht und zwei nach oben)

(4) Abgelesene Lösung zur Probe in Gleichung(en) einsetzen

Suchbereich: erfüllt Nebenbedingungen
Optimalitätsbereich: Punkte, bei denen die Zielfunktion optimal ist

Question 4

Bestimmen ob Vektor eine Lösung ist

Definition Basislösungen

Answer 4

(1) sind genügend “0” vorhanden (p=n-r)

(2) Handelt es sich um eine Lösung des GLS
- einsetzen des Lösungsvektors für x

(3) Sind die dazugehörigen Spalten linear Abhängig?
Linear abhängig = Lösung
Linear unabhängig = Basis-Lösung
Linear unabhängig + positiv = zul. Basis-Lösung

Question 5

Vorgehensweise beim lösen von Optimierungsproblemen
(Matrix-Schreibweise)

Bestimmen aller Basislösungen

Answer 5

(1) Wenn Ungleichungen bestehen, Schrumpfvariablen addieren

(2) Rang der Matrix bestimmen
(Anzahl der Treppenform / NB)

(3) Anzahl der NBVs errechnen (p=n-r)
(4) Anzahl der Lösungen = I n über p I
(5) Einzelne Lösungen bestimmen, indem immer andere Variablen Null gesetzt werden
(6) Basislösungen entsprechen den Eckpunkten (Lösung in Tabellenform)

Eckpunkt / BV / NBV / BL
x und y Wert / ausgerechnet / null gesetzt / zul. Basislösung

Question 6

Primales Simplex Verfahren

vorgegebene zul. Lösung

Answer 6

NBV      BV        F      bi
                                   0
BV                              0
                                   0
F                                 1

(1) Pivospalte auswählen = Minimaler Zielfunktionskoeffizient
(2) Basislösung bi durch dazugehörigen Wert aus der Pivotspalte teilen => Zeile mit dem niedrigsten nichtnegativen Wert = Pivotzeile
(3) Kreuzung aus Pivotspalte und Pivotzeile = Pivotelement => muss auf den Wert 1 gebrach t werden
(4) Durch versch. Verfahren alle Werte in der Pivotspalte auf “0” bringen
(5) Variablentausch sodass die BV wieder 010 ergeben
(5) Wiederholen bis alle Zielfunktionskoeffizienten positiv sind

Question 7

Duales Simplex Verfahren

zur Bestimmung einer zul. Lösung

Answer 7

(1) Pivotzeile auswählen = kleinster Wert (größter negativste Wert)
(2) Pivotspalte ermitteln = f durch Pivotzeile, größten Wert aussuchen