a) Hat der Wertebereich einer Zielfunktion eines Optimierungsproblems nur zwei Elemente, so bezeichnen wir das Problem auch als Entscheidungsproblem.
✅ Richtig.
📖 Zitat aus dem Skript (Seite 16): "Ein Entscheidungsproblem ist ein Optimierungsproblem, bei dem die Zielfunktion den Handlungsoptionen nur einen von zwei möglichen Werten zuordnet."
Das bedeutet, dass ein Optimierungsproblem mit genau zwei möglichen Zielfunktionswerten (z. B. 0 oder 1) als Entscheidungsproblem bezeichnet wird.
b) Das Intervallhalbierungsverfahren findet sehr schnell eine Nullstelle, hat aber den Nachteil, dass es sich in manchen Fällen immer weiter von der Nullstelle entfernt (Divergenz) oder immer abwechselnd zwei Lösungen betrachtet (Oszillation).
❌ Falsch.
📖 Zitat aus dem Skript (Seite 27): "Das Intervallhalbierungsverfahren ist ein exaktes Verfahren und garantiert Konvergenz zur Nullstelle, solange die Bedingungen erfüllt sind."
Weiter heißt es: "Das Verfahren hat den Vorteil, dass die zu untersuchende Funktion nicht differenzierbar sein muss."
Das bedeutet, dass das Intervallhalbierungsverfahren nicht divergiert oder oszilliert. Es konvergiert immer zur Nullstelle, solange die Eingangsbedingungen korrekt gewählt wurden.
c) Soll in einem Optimierungsproblem eine Nebenbedingung ein „ungleich“ darstellen (also eine Gleichung soll nicht erfüllt sein), so lässt sich dies mittels einer großen Zahl M linear modellieren.
Richtig
Ja, ich kann ein ungleich auch als ein kleiner und größer Modellieren.
z.B. x ungleich 5
wird zu ->
x -My1< 5
und
x + My2 > 5
d) Bei der Modellierung von Optimierungsproblemen ist es besonders hilfreich, wenn möglichst wenig Entscheidungsvariablen und möglichst wenig Nebenbedingungen verwendet werden.
📖 Zitat aus dem Skript (Seite 61): "Es ist unbedingt festzuhalten, dass es zwar viele sinnvolle Modellierungseigenschaften für gemischt ganzzahlige Optimierungsprobleme gibt, es aber im Allgemeinen dennoch schwer ist abzuschätzen, wie leicht oder schwer sich ein Modell lösen lässt. Außer in Extremfällen ist weder die Größe der Menge der zulässigen Lösungen, die Anzahl an Entscheidungsvariablen, noch die Anzahl an Nebenbedingungen ein sicheres Kriterium für die Lösbarkeit eines Modells und somit auch nicht für die Güte der Modellierung."
Das bedeutet, dass zwar eine geringe Anzahl an Entscheidungsvariablen und Nebenbedingungen die Berechnung vereinfachen kann, jedoch nicht immer die beste Modellierung gewährleistet. In manchen Fällen können zusätzliche Nebenbedingungen hilfreich sein, um z. B. Symmetrien zu vermeiden und die Lösbarkeit zu verbessern.
e) Der Satz vom komplementären Schlupf sagt (unter anderem) aus, dass in JEDER Lösung und für JEDE Nebenbedingung gilt, dass die Schlupfvariable dieser Nebenbedingung multipliziert mit der zugehörigen Dualvariablen gleich 0 ist.
f) Im Simplextableau der optimalen Lösung stellen die Zahlen in der ganz rechten Spalte die Opportunitätskosten der jeweiligen Basisvariablen dar.
📖 Zitat aus dem Skript (Seite 96): "Die Werte in der Zielfunktionszeile der Nichtbasisvariablen (eingekreist) stellen Opportunitätskosten dar."
Das bedeutet, dass die Opportunitätskosten nicht in der rechten Spalte des Simplextableaus stehen, sondern in der Zielfunktionszeile der Nichtbasisvariablen. Die rechte Spalte enthält hingegen die Werte der Basisvariablen.
g) Das duale Simplexverfahren wird immer dann angewendet, wenn der Nullvektor keine zulässige Lösung für das zu lösende lineare Optimierungsproblem darstellt.
📖 Zitat aus dem Skript (Seite 99): "Das duale Simplexverfahren unterscheidet sich beim Übergang von einer Basislösung zur nächsten nur in der Bestimmung des Pivotelements von dem primalen Simplexverfahren. Der zweite und letzte Unterschied ist, dass nachdem die rechte Spalte des Tableaus keine negativen Werte mehr hat, wir womöglich noch nicht fertig sind, da die Basislösung dann zwar (primal) zulässig ist, unter Umständen aber noch nicht optimal ist."
Weiter heißt es: "Wir nutzen das duale Simplexverfahren, um lineare Optimierungsmodelle zu lösen, bei denen die Bedingung b≥0b \geq 0b≥0 nicht erfüllt ist."
Das bedeutet, dass das duale Simplexverfahren nicht nur dann angewendet wird, wenn der Nullvektor keine zulässige Lösung ist, sondern allgemein dann, wenn das Optimierungsproblem in einer Form vorliegt, bei der das primale Simplexverfahren nicht direkt anwendbar ist (z. B. wenn die rechte Seite des Tableaus negative Werte enthält).
h) Das quadratische Zuordnungsproblem lässt sich als gemischt ganzzahliges lineares Optimierungsproblem modellieren.
❌ Falsch.
💡 Begründung: Das quadratische Zuordnungsproblem ist ursprünglich nicht linear, sondern quadratisch, da die Zielfunktion Produkte von Entscheidungsvariablen enthält.
i) Metaheuristiken haben den Vorteil, dass sie sich mit geringer Rechenzeit auf viele Optimierungsprobleme anwenden lassen, und den Nachteil, dass sie keine optimalen Lösungen liefern.
💡 Begründung: Die Aussage ist falsch, weil Metaheuristiken nicht grundsätzlich ausschließen, dass eine optimale Lösung gefunden wird. Sie garantieren keine optimale Lösung, aber es ist möglich, dass sie eine liefern.
j) Die dynamische Programmierung und Branch-and-Bound sind exakte Verfahren, die die optimale Lösung ermitteln, indem sie sämtliche Lösungen eines Optimierungsproblems explizit betrachten.
📖 Zitat aus dem Skript (Seite 139, 142): "Branch-and-Bound ist ein sehr allgemeines Lösungprinzip, das sich auf nahezu alle Optimierungsprobleme anwenden lässt, um diese exakt zu lösen. Die Grundidee ist dabei, dass die Lösungsmenge des zu untersuchenden Problems in kleinere Mengen aufgeteilt wird (branch) und mittels logischer Schlussfolgerungen einzelne Teilmengen von der weiteren Betrachtung ausgeschlossen werden, da diese keine optimale Lösung enthalten können (bounding). Die Teilmengen, die nicht ausgeschlossen werden können, werden weiter unterteilt, unter Umständen so lange, bis jede Teilmenge nur noch eine einzelne Lösung enthält. Branch-and-Bound betrachtet somit implizit sämtliche Lösungen, aber die zulässigen Lösungen werden nur in Ausnahmefällen explizit betrachtet."
💡 Begründung: Branch-and-Bound betrachtet nicht alle Lösungen explizit, sondern schließt große Teile des Lösungsraums durch Schranken aus, bevor sie überhaupt betrachtet werden müssen. Dadurch wird die Anzahl der tatsächlich überprüften Lösungen stark reduziert.
Auch die dynamische Programmierung nutzt eine rekursive Struktur, um das Problem in Teilprobleme zu zerlegen und nicht alle möglichen Lösungen direkt zu betrachten, sondern durch geschickte Zerlegung nur relevante Lösungen zu ermitteln.
k) Die Laufzeit der (diskreten) dynamischen Programmierung hängt maßgeblich davon ab, wie viele Elemente die Mengen erlaubter Zustände in den einzelnen Perioden haben
📖 Zitat aus dem Skript (Seite 134): "Da die Laufzeit des Algorithmus von der Anzahl an Zuständen abhängt, sollte bereits bei der Modellierung auf Sparsamkeit hinsichtlich der Zustände geachtet werden."
Weiter heißt es: "Die Laufzeit der dynamischen Programmierung wurde in Abhängigkeit der Anzahl der Zustände angegeben, was bei kontinuierlichen Zustandsmengen natürlich wenig aussagekräftig ist."
💡 Erklärung: Die Anzahl der erlaubten Zustände in den einzelnen Perioden beeinflusst direkt die Komplexität der dynamischen Programmierung. Je mehr Zustände eine Periode erlaubt, desto größer wird der Lösungsraum und desto länger dauert die Berechnung. Dies gilt besonders für diskrete Zustandsmengen, während kontinuierliche Zustandsräume oft mit Näherungsverfahren behandelt werden.
l) Wird bei Branch-and-Bound stets das Teilproblem als nächstes untersucht, dessen lokale obere Schranke am größten ist (Best-Bound-Search bzw. Breitensuche), so werden stets nur Teilprobleme ausgewählt, die auch bei jeder anderen Auswahlstrategie noch hätten untersucht werden müssen. Wegen dieses Vorteils wird in Theorie und Praxis ausschließlich diese Strategie angewendet.
📖 Zitat aus dem Skript (Seite 143): "Branch-and-Bound ist ein sehr allgemeines Lösungprinzip, das sich auf nahezu alle Optimierungsprobleme anwenden lässt, um diese exakt zu lösen. [...] Wichtig ist nur, dass alle zulässigen Lösungen in mindestens einem Teilproblem auftauchen."
💡 Begründung: Die Best-Bound-Strategie (auch Breitensuche genannt) ist eine mögliche Auswahlstrategie für Branch-and-Bound, aber nicht die einzige, die in Theorie und Praxis genutzt wird. Es gibt auch andere Methoden wie Tiefensuche oder hybride Strategien, die je nach Problemstellung effizienter sein können.
Daher ist die Aussage falsch, weil sie suggeriert, dass ausschließlich die Best-Bound-Strategie verwendet wird, was nicht zutrifft.
Zuletzt geändertvor einem Monat
