❌ Falsch.
💡 Begründung:Die Aussage ist falsch, da eine Funktion nicht schon dann als stetig gilt, wenn sie nur in einem Punkt stetig ist. Stattdessen muss sie in jedem Punkt ihres Definitionsbereichs stetig sein, um als stetige Funktion zu gelten.
b) Wird in einem Verfahren zur Nullstellensuche (Intervallhalbierungsverfahren, Newtonverfahren, Halleyverfahren, Gradientenverfahren) ε=0 gesetzt und liegt eine ganzzahlige Nullstelle vor, so wird diese nach endlich vielen Schritten ermittelt.
📖 Zitat aus dem Skript (Seite 27): "Das Intervallhalbierungsverfahren ist ein exaktes Verfahren mit einer Laufzeit von O(log(∣b−a∣/ε)).
Eine Nullstelle genau zu bestimmen, nehmen wir uns auf Grund einer womöglich unendlichen Zahl an Nachkommastellen nicht vor. Daher beschränken wir uns darauf, dass wir eine Rundungstoleranz von maximal ε>0 vorgeben."
Weiter heißt es beim Newtonverfahren (Seite 30): "Das Newtonverfahren garantiert zwar nicht, dass wirklich eine Nullstelle gefunden wird (auch wenn diese existiert), aber in den vielen Fällen, wo sie eine Nullstelle findet, geschieht dies sehr schnell. Es kann jedoch passieren, dass sich das Verfahren immer weiter von einer Nullstelle entfernt oder oszilliert."
💡 Begründung: Wenn ε=0 gesetzt wird, könnte das Verfahren unendlich viele Iterationen benötigen, insbesondere wenn die Nullstelle eine irrationale Zahl ist oder das Verfahren divergiert. Auch das Newton- und Halleyverfahren können bei schlechter Wahl des Startwertes oszillieren oder divergieren. Daher ist die Aussage falsch.
c) Ein stationärer Punkt einer stetig differenzierbaren und konvexen Funktion f ist ein globales Minimum.
✅ Richtig.
📖 Zitat aus dem Skript (Seite 36): "Eine Funktion ist genau dann konvex, wenn die Verbindungsstrecke zweier Funktionswerte oberhalb des Graphen von f liegt. Der Vorteil konvexer Funktionen ist insbesondere, dass sie nur ein lokales Minimum besitzen und bei Ihnen somit leicht ein globales Minimum gefunden werden kann."
Weiter heißt es im Satz 2.19 (Seite 36): "Sei *∗ ein stationärer Punkt einer stetig differenzierbaren und konvexen Funktion f:D→R: D wobei D ebenfalls konvex ist. Dann ist x*∗ ein globales Minimum von f."
💡 Erklärung: Bei einer konvexen Funktion gibt es höchstens ein lokales Minimum. Wenn ein stationärer Punkt existiert, dann ist er automatisch auch das globale Minimum.
📖 Zitat aus dem Skript (Seite 53): "Die Funktion h(x)=max{x+2,2x−4} lässt sich durch eine Einführung zusätzlicher Variablen linear darstellen."
Weiter heißt es: "Die Betragsfunktion kann durch eine Nebenbedingung mit einer Hilfsvariablen ersetzt werden, um die Linearisierung zu ermöglichen."
💡 Erklärung: Die gegebene Funktion besteht aus einer quadratischen und einer Betrag-Funktion, die durch Linearisierungstechniken umgeformt werden können.
Der Betrag ∣2x−4∣ kann durch eine Hilfsvariable und Nebenbedingungen ersetzt werden.
Der quadratische Term x^2 kann durch Stückweise-Linearität (Abschnittsweise Linearisierung) approximiert werden. Daher ist eine lineare Darstellung möglich.
e) Der Satz von Hoffmann und Kruskal sagt aus, dass bei einem LP, dessen Matrix A total unimodular ist, jede zulässige Lösung ganzzahlig ist.
📖 Zitat aus dem Skript (Seite 66-67)
💡 Erklärung:Eine total unimodulare Matrix hat die Eigenschaft, dass jede zulässige Lösung eines linearen Programms mit ganzzahligen Parametern automatisch ganzzahlig ist. Das bedeutet, dass man in einem solchen Fall auf die explizite Ganzzahligkeitsbedingung verzichten kann.
f) Jedes LP hat mindestens eine zulässige Lösung und mindestens eine Basislösung, die optimal ist.
📖 Zitat aus dem Skript (Seite 75): "Wenn ein LP eine optimale Lösung besitzt, dann gibt es mindestens eine Basislösung, die optimal ist."
Weiter heißt es auf Seite 87: "Ist (D) unbeschränkt, so hat (P) keine zulässige Lösung."
💡 Begründung:
Die Aussage wäre nur dann richtig, wenn jedes LP eine zulässige Lösung hätte, was nicht der Fall ist. Ein LP kann unzulässig oder unbeschränkt sein, sodass keine Lösung existiert.
Falls eine optimale Lösung existiert, dann gibt es auch eine Basislösung, die optimal ist. Allerdings garantiert das nicht, dass jedes LP immer eine zulässige Lösung hat.
g) Das Lemma von Farkas sagt aus, dass von zwei (in dem Lemma genauer spezifizierten) Gleichungssystemen stets nur eines lösbar ist.
💡 Erklärung:Das Lemma von Farkas ist eine fundamentale Aussage in der linearen Optimierung. Es besagt, dass genau eine der beiden genannten Bedingungen (F1 oder F2) erfüllt sein kann – aber niemals beide gleichzeitig. Das bedeutet, dass zwei bestimmte Gleichungssysteme sich gegenseitig ausschließen und nur eines lösbar ist.
h) Hat ein lineares Optimierungsproblem (mit endlicher Anzahl an Variablen und Nebenbedingungen) mindestens eine optimale Lösung und unendlich viele zulässige Lösungen, so braucht das Simplexverfahren unendlich viele Schritte, um die optimale Lösung zu bestimmen.
📖 Zitat aus dem Skript (Seite 76-77): "Das Simplexverfahren nutzt elementare Zeilenoperationen, um die Eingabe umzuformen. Dabei lässt sich in jeder Iteration aus den umgeformten Werten eine Basislösung ablesen, deren Zielfunktionswert sich stetig verbessert (oder zumindest nicht verschlechtert), bis sich (nach endlich vielen Iterationen) eine optimale Lösung einstellt."
💡 Begründung: Das Simplexverfahren kann zwar zyklisch werden (z. B. in Klee-Minty-Worst-Case-Beispielen), aber mit geeigneten Pivotregeln (z. B. Bland's Rule) wird sichergestellt, dass es immer nach endlich vielen Schritten terminiert. Unendlich viele zulässige Lösungen führen nicht automatisch zu unendlich vielen Iterationen.
i) Ist nach Abschluss des (primalen) Simplexverfahrens in der Zeile der Zielfunktionskoeffizienten der Wert einer Nicht-Basisvariablen gleich 0, so liegt duale Degeneration vor.
💡 Erklärung:Duale Degeneration tritt auf, wenn eine Nichtbasisvariable in der Zielfunktionszeile den Wert Null hat. Dies bedeutet, dass sich die Zielfunktion durch Aufnahme dieser Variablen in die Basis weder verbessert noch verschlechtert, was ein typisches Zeichen für eine alternative optimale Lösung oder Redundanzen im Modell ist.
Definition primale und duale Degeneration:
primale Degeneration = eine oder mehrere Basisvariablen haben den Wert null
(Zusatz: es gibt somit redundante Nebenbedingungen)
duale Degeneration = wenn in der Zielfunktionszeile die Werte der Nichtbasisvariablen 0 sind (unten ganze Zeile null)
j) Die Verknüpfungen Addition, Subtraktion, Multiplikation und Division sind auf allen Definitionsbereichen monoton steigend.
📖 Zitat aus dem Skript (Seite 136): "Die Monotonie einer Funktion bedeutet, dass sie entweder immer steigt oder immer fällt. Eine Funktion ist monoton steigend, wenn für x1<x2 stets f(x1)≤f(x2) gilt. Diese Eigenschaft trifft nicht auf alle Verknüpfungen zu."
Addition und Subtraktion sind nicht immer monoton steigend, wenn negative Zahlen im Spiel sind. Beispiel: x−y ist nicht immer steigend, da y negativ sein kann und die Richtung umkehrt.
Multiplikation ist nur dann monoton steigend, wenn beide Faktoren positiv sind. Bei negativen Zahlen ist sie monoton fallend (z. B. f(x)=−2x fällt für steigendes x).
Division ist nicht monoton steigend, wenn der Nenner negativ ist, da eine Umkehrung der Ordnung erfolgt (z. B. 1/x1 ist für x>0 fallend, aber für x<0steigend).
k) Bei Anwendung der Strahlsuche wird zwar nie eine optimale Lösung des dynamischen Programms gefunden, aber zumindest eine zulässige.
❌ Falsch
💡 Begründung: Die Aussage ist falsch, zwar garantiert die Strahlsuche nicht dass eine optimale Lösung ausgegeben wird, es ist aber möglich.
l) Bei Branch and Bound wird zu Beginn eine zulässige Lösung bestimmt. Wenn diese Lösung optimal sein sollte, bricht das Verfahren unabhängig von der anderen Schranke sofort ab.
📖 Zitat aus dem Skript (Seite 144): "Falls die Berechnung der unteren Schranke bereits eine optimale Lösung geliefert hat, wird diese direkt übernommen, und das Verfahren kann abbrechen."
💡 Erklärung:
Das Branch-and-Bound-Verfahren startet mit einer zulässigen Lösung, die als obere Schranke dient.
Falls diese Lösung bereits optimal ist, also keine bessere Lösung mehr möglich ist, wird das Verfahren sofort beendet.
Dies ist ein zentraler Vorteil von Branch-and-Bound, da es so frühzeitig abbrechen kann, wenn die optimale Lösung bereits bekannt ist.
Zuletzt geändertvor einem Monat
