Please enable JavaScript.
Coggle requires JavaScript to display documents.
Operations Research (Lineare Optimierung (Zielfunktion (f(x) = c1x1 + c2x2…
Operations Research
Lineare Optimierung
Zielfunktion
f(x) = c1x1 + c2x2 + ... + cnxn =c^T x (= ❬c, x❭
Die Menge M der zulässigen Punkte (kurz: zulässige Menge) besteht aus den x ∈ |R^n, die sämtliche Restriktionen erfüllen
Ein zulässiger Punkt x' heißt optimaler Punkt, wenn es keine zulässigen Punkte mit besserem Zielfunktionswert gibt. Für ein Maximierungsproblem ist es also optimal, falls f(x) <= f(x') für alle x ∈ M gilt. z' = f(x') heißt dann optimaler Wert. mit ' = *
um zu berücksichtigen, dass optimale Punkte nicht notwendigerweise eindeutig sind, definierre die Menge der optimalen Punkte M' = {x ∈ M | f(x) = z'} mit ' = *
Standardform
max c^T x s.t. Ax <= b, x >= 0
Lösbarkeit
Eine reellwertige stetige Funktion f besitzt auf einer nichtleeren, beschränkten und abgeschlossenen Menge M stets einen Minimal- und einen Maximalpunkt. Ein lineares Optimierungsproblem in Standardform besitzt einen optimalen Punkt, falls M nichtleer und beschränkt ist
Konvexität
K teilmenge von R^n heißt konvex, falls für alle x,y aus der Menge K gilt, dass alle Punkte auf der Geraden zwischen den Punkten x und y auch Element der Menge K sind
Extrempunkte
Ein Element e einer konvexen Menge K heißt Extrempunkt von K, falls er an einer Ecke der Menge liegt, bzw. e = (1 - λ)x + λy nicht lösbar
-
Berechnung von Ecken
Problem: es gibt n + m über n Möglichkeiten, Gleichungssysteme zu bilden. für große M und n dauert das zu lange
Simplex-Verfahren
Grundidee
bestimme Kanten von M, entlang denen f(x) wächst
-
-
wiederhole, bis keine Anstiefskanten mehr zu finden sind, oder bis entlang einer Anstiegskante keine weitere Ecke existiert
Schlupfvariablen
-
-
Die Handhabung von Ecken vereinfacht sich durch Einführung von Schlupfvariablen: Aufteilung in Strukturvariablen und Schlupfvariablen
aus n + m Gleichungen alle Systeme mit n Gleichungen bilden, Systeme auf Lösbarkeit prüfen, Lösung auf Zulässigeit prüfen, verbleibende Kandidaten auf höchsten Zielfunktionswert untersuchen
Operations Research ist die Anwendung mathematischer Methoden zur Vorbereitung optimaler Entscheidungen