Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Nebenfächer » mathematik » nalip-2021-08-26   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:nebenfach:mathematik:nalip-2021-08-26 [26.08.2021 12:37] – angelegt gabriel2029pruefungen:nebenfach:mathematik:nalip-2021-08-26 [26.08.2021 15:59] (aktuell) – TMT
Zeile 11: Zeile 11:
 __Phase 1 des Simplex-Algorithmus__ __Phase 1 des Simplex-Algorithmus__
   * F: Problem in Standardform aufstellen\\ A: min c^Tx, s.t. Ax = b, x >= 0   * F: Problem in Standardform aufstellen\\ A: min c^Tx, s.t. Ax = b, x >= 0
-  * F: Das = in Ax = b wird durch ein <= ersetzt. Zudem sei b >= 0. Wie findet man eine gültige Basis?\\ A: Für Simplex muss man sowieso Schlupfvariablen einführen, diese kann man dann direkt als Basis verwenden.+  * F: Das = in Ax = b wird durch ein ≤ ersetzt. Zudem sei b >= 0. Wie findet man eine gültige Basis?\\ A: Für Simplex muss man sowieso Schlupfvariablen einführen, diese kann man dann direkt als Basis verwenden.
   * F: Was passiert nun, wenn man die Bedingung b >= 0 streicht? Wie löst man das Problem?\\ A: Die Schlupfvariablen bilden nicht mehr unbedingt eine Basis, da die Bedingung x >= 0 eventuell verletzt ist. Einführen von künstlichen Variablen mit negativen Koeffizienten und Starten der Phase 1.   * F: Was passiert nun, wenn man die Bedingung b >= 0 streicht? Wie löst man das Problem?\\ A: Die Schlupfvariablen bilden nicht mehr unbedingt eine Basis, da die Bedingung x >= 0 eventuell verletzt ist. Einführen von künstlichen Variablen mit negativen Koeffizienten und Starten der Phase 1.
   * F: Wie ist die Zielfunktion für das Phase 1-Problem zu wählen?\\ A: Für künstliche Variablen y entsprechend 1^Ty. Wenn die Optimallösung des Problems 0 ist, dann existiert eine Basis für das ursprüngliche Problem.   * F: Wie ist die Zielfunktion für das Phase 1-Problem zu wählen?\\ A: Für künstliche Variablen y entsprechend 1^Ty. Wenn die Optimallösung des Problems 0 ist, dann existiert eine Basis für das ursprüngliche Problem.
Zeile 19: Zeile 19:
 __Pricing-Verfahren__ __Pricing-Verfahren__
   * F: Erläutere kurz das partielle Pricing. Warum ist das besser als Dantzig und weshalb eignet sich das vor allem am Beginn des Simplex?\\ A: Aufteilen der Menge der Nichtbasisvariablen in Abschnitte. Betrachten der Abschnitte separat und Minimumsbildung pro Abschnitt. Man muss dabei im Regelfall nicht alle Nichtbasisvariablen betrachten (im Gegensatz zu Dantzig); vor allem zu Beginn des Simplex gibt es viele Nichtbasisvariablen, die potenziell die Zielfunktion verbessern.   * F: Erläutere kurz das partielle Pricing. Warum ist das besser als Dantzig und weshalb eignet sich das vor allem am Beginn des Simplex?\\ A: Aufteilen der Menge der Nichtbasisvariablen in Abschnitte. Betrachten der Abschnitte separat und Minimumsbildung pro Abschnitt. Man muss dabei im Regelfall nicht alle Nichtbasisvariablen betrachten (im Gegensatz zu Dantzig); vor allem zu Beginn des Simplex gibt es viele Nichtbasisvariablen, die potenziell die Zielfunktion verbessern.
-  * F: Was ist die Grundidee hinter dem Verfahren des steilsten Abstiegs?\\ A: Ausführliche Erklärung, was der Vektor der reduzierenden Kosten bedeutet, warum der misleading sein kann (-> Auswirkung auf andere Basisvariablen nicht berücksichtigt), wie man den Richtungsvektor u berechnet, und ein paar Rückschlüsse auf die Länge des Vektors u.+  * F: Was ist die Grundidee hinter dem Verfahren des steilsten Abstiegs?\\ A: Ausführliche Erklärung, was der Vektor der reduzierenden Kosten bedeutet, warum der misleading sein kann (-> Auswirkung auf andere Basisvariablen nicht berücksichtigt), wie man den Richtungsvektor u berechnet, und ein paar Rückschlüsse auf die Länge des Vektors u.\\ -> Man wählt diejenige Variable mit negativen reduzierenden Kosten, welche in der Zielfunktion den steilsten Ansteig in Bezug auf das entsprechende u verursacht.
   * F: Warum ist das ineffizient? Wie kann man das besser machen?\\ A: Man muss für jede mögliche eintretende Variable k ein FTRAN durchführen (d. h. ein ganzes Gleichungssystem lösen). Stattdessen Update-Regeln von Goldfarb verwenden.   * F: Warum ist das ineffizient? Wie kann man das besser machen?\\ A: Man muss für jede mögliche eintretende Variable k ein FTRAN durchführen (d. h. ein ganzes Gleichungssystem lösen). Stattdessen Update-Regeln von Goldfarb verwenden.
   * F: Auf der Tafel stehen ein paar Gleichungen aus der Vorlesung zum Goldfarb. Erläutere diese mal und erkläre, was wie aufwendig zu berechnen ist.\\ A: Im Wesentlichen wurden hier die Update-Regeln aus der Vorlesung zitiert. Man durfte jeweils den Berechnungsaufwand der drei Summanden in der Formel beschreiben.   * F: Auf der Tafel stehen ein paar Gleichungen aus der Vorlesung zum Goldfarb. Erläutere diese mal und erkläre, was wie aufwendig zu berechnen ist.\\ A: Im Wesentlichen wurden hier die Update-Regeln aus der Vorlesung zitiert. Man durfte jeweils den Berechnungsaufwand der drei Summanden in der Formel beschreiben.