OR Kapitel #4-6 Flashcards
Normalform
Ungleichungs-Normalform = Maximierungsproblem mit Ungleichungen, bei dem alle Variablen Vorzeichenbeschränkt sind
Gleichung-Normalform=
Maximierungsproblem mit Gleichungen, bei dem alle Variablen Vorzeichenbeschränkt sind und ggf. Schlupfvariablen addiert werden
Zeichnerische Lösung
2 Variablen
(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
Lineares Optimierungsproblem
Lösungsarten
Lösung: erfüllt alle Nebenbedingungen
zulässige Lösung: erfüllt alle Nebenbedingungen und alle Punkte sind nicht negativ
Optimale Lösung: jede zulässige Lösung bei der der Zielfunktionswert optimal ist
unbeschränktes Optimierungsproblem: keine optimale Lösung
Schlupfvariablen
Schlupfvariablen machen aus Ungleichungen => Gleichungen
<= Addieren einer Schlupfvariablen (s) >= Subtraktion einer positiven Schlupfvariablen (s)
Konvexität
Lineare Optimierungsprobleme
- der Suchbereich S und der Optimalbereich S* sind immer konvex
- der Suchbereich eines linearen Optimierungsproblems ist immer ein konvexes Polyeder
- die Optimale Lösung befindet sich immer am Rand des Polyeders
Rang einer Matrix
p = n-r
n = Anzahl der Variablen r = Anzahl der Zeilen (Nebenbedingungen)
wenn p ungleich “0” ist, handelt es sich um ein unterbestimmtes Gleichungssystem
p-Variable können “0” gesetzt werden
Bestimmen ob Vektor (Lösung) eine Basislösung ist
Vorgehensweise
(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
Vorgehensweise beim lösen von Optimierungsproblemen
Matrix-Schreibweise
(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
Simplex-Tableau Vorgehensweise
bekannte zur. Lösung
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 Werte = 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) Wiederholen bis alle Zielfunktionskoeffizienten positiv sind
(6) Variablen aus Pivotspalte und Pivotzeile müssen getauscht werden (Neue BVs und NBVs)
Simplex-Tableau Vorgehensweise
unzulässige Lösung
Dualer Simplex-Algorithmus
(Voraussetzung: rechte Seite des Tableaus bi ist negativ)
(1) Zeile mit dem kleinsten bi Wert wählen
(2) Spalte mit dem größten Zielfunktionskoeffizienten auswählen
(3) Kreuzung aus Pivotzeile und Pivotspalte ist Pivotlement
(4) Pivotverfahren anwenden bis bi positiv ist
(5) Sollten zu diesem Zeitpunkt bereits alle Zielfunktionskoeffizienten positiv sein, ist die optimale Lösung bereits gefunden.
(6) Wenn nicht, dann herkömmliches Pivotverfahren durchführen
Simplex-Verfahren
rechnerische Vorgehensweise
(1) Basislösung anhand der Nebenbedingungen aufstellen. NBVs sind dabei die Variablen aus der Zielfunktion
(2) Variable mit dem größten Einfluss auf die Zielfunktion auswählen
(3) Eine Gleichung der Nebenbedingungen nach dieser Variablen umstellen
(4) Lösung aus 3 in Zielfunktion einsetzen
(5) Schritt 2 - 4 solange durchführen, bis Variablen in Zielfunktion negativ sind => keine Maximierung mehr möglich, Zielfunktionswert ablesen
Duale lineare Optimierungsprobleme
Einschließungssatz: F(x) ≤ F(x) = FD(w) ≤ FD(w)
Beispiel:
Maximiere F(x) = 10x + 20y unter x + y ≤ 100 6x + 9y ≤ 720 y ≤ 60
wird zu
Minimiere F(w) = 100w1 + 720 w2 + 60w3
unter
w1 + 6w2 ≥ 10
w1 + 9w2 + w3 ≥ 20
Sonderfälle beim Simplexverfahren
(1) Primale Unzulässigkeit: es gibt keine zul. Lösung, da die Nebenbedingungen im Widerspruch stehen
Beim dualen Simplex-Verfahren gibt es in der Pivotzeile nur Werte größer oder gleich null
(2) Duale Unzulässigkeit: Ausgangsproblem enthält Lösungen, aber keine Optimale = Zielfunktion kann unbeschränkt wachsen
Beim primalen Simplex-Verfahren gibt es in der Pivotspalte nur Werte kleiner oder gleich null
(3) Primale Degeneration
Mehr als zwei Geraden schneiden sich in einem Eckpunkt.
Vermeidung durch Blandsche Pivot-Regel: Immer erste Zeile oder Spalte auswählen, wenn Werte zur Auswahl gleichwertig
(4) Duale Degeneration
mehrere optimale Lösung.
Unter einer NBV befindet sich bereits eine Null.
(5) Redundante Nebenbedingungen
Mind. eine Nebenbedingung ist überflüssig
Rechnerische Lösung
Additionsverfahren:
Gleichungen des LGS miteinander multiplizieren
eine Variable muss identisch sein und umgekehrte Vorzeichen haben
Bsp: (1) 2x + 3y = 5 (2) -2x + 7y = 10
Einsetzverfahren:
Eine Gleichung so umstellen, dass eine Variable durch die andere ersetzt wird.
Bsp: (1) 6x =18 -6y I :6 => x = 3 -y
Wichtig: Wenn die erste Gleichung umgeformt wird, muss die Lösung in die zweite Gleichung eingesetzt werden
Gleichsetzungsverfahren:
(1) Beide Gleichung nach einer variablen auflösen (z.B. x= 7y + 1)
(2) Beide Lösungen Gleichsetzen => y-Wert ist ermittelt.
(3) ermittelten Wert in einer der beiden Gleichungen aus Schritt (1) einsetzen
Gauß-Verfahren:
Tabellenform mit Stufernform 0
