Definition:
Entscheidungsproblem
Optimierungssproblem
Optimierungsproblem:
Ein Optimierungsproblem besteht aus einer Zielfunktion, die minimiert oder maximiert werden soll, sowie Nebenbedingungen, die eingehalten werden müssen.
Ein Entscheidungsproblem ist ein Optimierungsproblem, bei dem die Zielfunktion den Handlungsoptionen nur einen von zwei möglichen Werten zuordnet.
restringiertes Optimierungsproblem
=> hat ein Lösungsbereich der eingeschränkt wird
Schlechter Startwert für das Halleyverfahren
Ein Hochpunkt oder ein Tiefpunkt ist schlecht.
+ wenn 2f’(x)^2 *f’’(x) = 0
Wie genau muss e gewählt werden, für das Newton und Halleyverfahren damit f(x)=0 auf 2 Nachkommastellen genau bestimmt wird.
e kleiner gleich 0,005
Jede nichlineare Funktion lässt sich stückweise als lineare Funktion approximieren.
Wahr!
Lassen sich Nebenbedingungen der Form g(x) <= min h(x) in einem LP linear darstellen?
Ja:
g(x) = 2x1 + x2
f(x) = 3
z.B. aus 2x1+x2 <= 3
=> als Nebenbedingungen aufschreiben
2 x1 + x2 <= 3
Die Lösung eines LP ist ganzzahlig, wenn A total unimodular ist, sowie der Parametervektoren c und b ganzzahlig sind?
wahr
Wiesokann es sich lohnen ein MILP auf totale Unimodularität zu prüfen?
Vernachlässigt man die Ganzzahligkeitsbedingungen des MILP erhält man ein verwandeltes LP. Wenn die Matrix total unimodular ist und alle Parametder des umgewandelten LP ganzzahlig sind, so ist auch die Lösung des LP ganzzahlig.
Dann nur LP lösen. Lösung LP ist Lösung MILP.
Bei vielen Nebenbedingungen findet die M-Methode i.d.R: schneller eine Lösung
Der ZFW der optimalen Lösung des primalen Problems entspricht dem ZFW der optimalen Lösung des dualen Problems?
Nur, wenn starke Dualität gilt!
Satz des komplementären Schlupfs
primale Degeneration
eine Basisvariable hat den Wert 0 (eine redundante Nebenbedingung)
Bellmansches Optimalitätsprinzip
Last changeda month ago
