Welches Buch darf in die Klausur mitgenommen werden, das orangene "Einführung in die Optimierung"?
View 8 more comments
Ka. Bin auch in deinem Semester
Ich habe die Klausur mit dem Buch geschrieben, es allerdings danach wieder retourniert. Die meisten Aufgabentypen solltet ihr können, indem ihr das Schema dahinter versteht. Ich habe das Buch innerhalb der Klausur nur für die Wissensfragen gebraucht. In dem Buch gibt es allerdings auch noch einige weitere Übungsaufgaben, was beim Verständnis mancher Algorithmen helfen kann. Allgemein: Die Klausur ist super dankbar, wenn ihr die ganzen Algorithmen könnt. Ballert Altklausuren durch, dann ist eine super Note easy drin. Das Lernen der ganzen Wissensfragen für Multiple Choice habe ich als nicht sinnvoll erachtet, und dann eben in der Klausur drin rumgeblättert weil ich noch Zeit hatte.
Was sind eurer Meinung nach Grundlagen aus Mathe für WiWis 1 die ich in Operations Research auf jeden Fall brauchen werden? Wäre dankbar für eure Auskunft, weil ich dann weiß was ich am besten wiederhole &/ nachhole :).
View 7 more comments
ah okay, andere Sprachen wie SQL?
das macht ihr in Datenmanagement
Kann mir jemand sagen, wie ich bei der Altklausur bei Aufgabe 2 (Simplex) auf die Zielfunktion komme?
Ergebnisse sind da
Ganz ok insgesamt, oder? Auf jeden Fall besser als die letzte. Habt ihr auch einen Zielwert von -25 beim Simplex?
View 7 more comments
hab auch -65 aber eine Schlupfvariable noch in der Basis gehabt.
hab auch -65
Viel Erfolg euch morgen. Wenn ihr jemanden wild im Buch blättern hört versuche ich die MC Fragen zu beantworten - sorry dafür :D
Hat jemand die Aufgabe 2c vom Sonderübungsblatt 1 mit dem Branch and Bound beim Scheduling?
Wäre eine Lösung eigentlich zulässig, wenn eine Schlupfvariable nicht die Basis verlassen hat, aber sonst alle Kriterien für eine optimale Lösung erfüllt sind? Oder weiß jemand wie man solche eine Lösung interpretieren würde?
Was meint ihr kommen für Fragen bzgl Scheduling dran? Meint ihr das Skript durchgelesen zu haben reicht aus?
Ich glaube nicht, dass es reicht... WIe bei den Aufgaben in den Sonderübungszetteln können Aufgaben gestellt sein.. und da wir kein Skript in die Klausur nehmen dürfen..
nur einmal durchlesen reicht wahrscheinlich nicht, aber wenn du grob die Zielfunktionen und was diese aussagen, sowie die optimalen Vorgehensweisen für verschiedenen Zielmethoden halbwegs auf dem Schirm hast, ist das denke ich ausreichend, wenn man jetzt nicht gerade die 1,... anvisiert
Warum multipliziert man hier bspw. die NB nicht einfach mit -1 und führt dannn den dualen Simplex aus?
View 1 more comment
Jo stimmt. Beides möglich.
@Regenschirm danke für deine Antwort! Ich dachte auch erst, dass es egal ist, man kommt aber mit dem dualen Simplex leider auf eine komplett andere Optimallösung
Kannst du das bitte ein bisschen genauer erklären? Habs noch nicht ganz verstanen :/ Brauch ich da schon Pivotspalten?
View 7 more comments
Ok. Passt mein Vorgehen bei dem dualen Simplex denn?
ja, passt alle Fragen dazu werden in Skript 4 ausführlich mit Beispielen beantwortet
Hat einer einen Tipp oder eine Idee, was man sich am besten fur Turing Maschine zurechtlegen kann? Danke und viel Erfolg für morgen!
das müsste doch {V3, V8} sein
Ja, hast recht. Ich habe da auch V3, V8
Hat jemand Aufgabe 5c in WS08 gelöst bzw weiß wie man Ganzzahligkeit bei Simplex-Tableaus herstellt?
Wie ermittelt ihr die Startlösung beim Transportproblem der WS 08/09- Klausur beispielsweise? Klar, ich muss einen zusätzlichen Lieferanten hinzufügen, aber egal nach welcher Methode (MMM, NWE, NOE etc.) ich es bisher probiert habe, es kam jedes Mal eine Startlösung, bei welcher ich nicht die Stepping-Stone-Methode durchführen konnte, weil die Punkte so ungünstig verteilt waren. Das Problem ist mir schon 1,2 Mal aufgefallen. Habt ihr einen Ansatz?
Sehr gute Frage, habe mir das auf deine Frage hin auch angeguckt - keine Ahnung. Vielleicht hatten die früheren Jahrgänge noch eine weitere Methode die über die Jahre rausgenommen wurde. Ich denke nicht, dass die Klausur MMM bzw NWE übersteigen wird.
Das ist ein degeneriertes Transportproblem wie es auf S131 im Buch beschrieben wird. Man muss da wo man Stepping Stones braucht einfach eine 0 einsetzen dann kommt man auf eine Startlösung. Edit: So löst man das, glaub aber nicht dass es klausurelevant ist, da zu komplex und nur kurz erwähnt https://cbom.atozmath.com/CBOM/Transportation.aspx?q=ss&q1=3%2c4%2c1%3b5%2c3%2c4%3b7%2c6%2c7%6050%2c70%2c40%6060%2c60%2c60%60S1%2cS2%2cS3%60D1%2cD2%2cD3%60nwcm%60false%60true%60MIN&do=1#PrevPart
Hi, ist dieses DTM und NDTM wohl wichtig?
was ist das? Also eher nicht :D
In der letzten Klausur kam ja scheinbar auch Ford-Fulkerson dran, gab es für die (Residual-)Graphen Schablonen oder musste man die alle per Hand zeichnen?
View 5 more comments
@Anonymer MOnd: Ich kann mich wirklich kaum erinnern... die Klausur war in meinen Augen ganz anderes gestellt, als die Aufgaben davor in den Klausuren. Es gab immer mehrere Aufgabenteile zu einer Aufgabe, wir mussten irgedwas zeichnen... Transportproblem war ein Sonderfall.. an mehr kann ich mich nicht erinnern... Ich hatte aber das Gefühlt, dass mehr Transferleistung abgefragt wurde, als in den Altklausuren. Also würde ich es nicht ausschließen.. aber auch keinen großen Fokus drauf
Es kam Süd-West-Eckenregel, Dijkstra, Ford & Fulkerson, Huruwitz und noch irgendein Kack (Entscheidungsfindung), PMX, Simplex, Single-Choice (true or false) über verschiedene Themen und im Scheduling Skript etwas zu S. 13 Beispiel 1.7 Reduktion der Zielfunktionen. Sonst kann ich mich nicht mehr an andere Sachen erinnern
Habt ihr eine Laufzeit für DFS?
genau wie die von BFS
BFS & DFS: O(|V|+|E|)
Worauf legt ihr den Fokus? Simplex, Transport (MMM, NWE), B&B (TSP, Rucksack), Dijkstra? Finde es schwer für Scheduling zu lernen, weil wir keine Altklausuren dafür haben. Bei NichtLOP und Spieltheorie kann alles dran kommen, da muss man ja mehr oder weniger Glück haben.
View 2 more comments
Werde bei Nicht-Lineare Opt nicht die ganzen Verfahren auswendig lernen (Fibonacci & Boxing In hab ich mir näher angeschaut), da ich auch glaube, dass Hooke & Jeeves, steilster Abstieg & Co zu aufwendig zum Herunterschreiben ist. Ansonsten hab ich mir Graphen und die dazugehörigen Algorithmen genauer angeschaut, Spieltheorie, Branch & Bound, Turingmaschine, Simplex, evol. Algorithmen (Nur Crossover & Co) und Transportprobleme. Bei Scheduling hab ich mir die Beweise angeschaut, aber ich wüsste nicht, ob ich das so in der Klausur könnte, da ich finde, dass mit dem Scheduling-Thema nochmal ein echt großes Fass aufgemacht wurde.. Generell finde ich, dass man sau viel können muss. Ich bin mal gespannt, ob Grimme uns alle/ den Großteil in die Pfanne hauen oder ob es machbar sein wird, da sich nichts abschätzen lässt, da nur einfachere Klausuren von 2014/15 online sind, wo man nicht das Buch mitnehmen durfte. Wie denkt denn der Rest darüber? Wünsche euch allen viel Erfolg nächste Woche!
Glaube nicht dass die nochmal so schwer wird, letzte mal sind ja auch viele durchgefallen. Bei NLO wäre crossover natürlich super, hoffe ich auch drauf. Was glaubt Ihr könnten im Scheduling für Aufgaben drankommen außer Verständnisfragen?
weiß jemand, ob wir beim Simplex-Algo auch immer die Variablenbezeichnungen (also x1, x1, ...) als Extrazeile bzw. -spalte an den Rand schreiben müssen wie in den Musterlösungen?
Nein, nicht unbedingt. Habs nur beim ersten Tableau gemacht. Ich kann nur empfehlen es zumindest im ersten Tableau zu machen, weils einfach anfällig für Flüchtigkeitsfehler ist.
Wie funktioniert die Matrix-Minimum-Methode? Ich suche die günstigsten Kosten in der Matrix, schöpfe damit dann entweder einen S oder einen Z-Punkt aus, streiche ihn also. Danach suche ich wieder den nächstgünstigsten, und wiederhole das bis alles ausgefüllt ist. In der Präsentation (Folie 4-92) hat man direkt am Anfang zwei "kleinste" Werte, sodass das Ergebnis auch anders ist je nachdem wo ich anfange. Folgen wir da einer Metrik oder soll das zufällig passieren?
Du kommst damit ja nur an eine geeignete Startlösung. Selbst wenn du eine Startlösung mit NWR und MMM suchst, kann die sich noch unterscheiden. In deinem Fall würde ich sagen, dass Du einfach einen auswählst, den zu erst füllst. Die Startlösung daraus wird genauso geeignet sein, wie eine, in der Du zuerst den anderen Knoten mit gleichen Kosten füllst.
Kann jemand eventuell nochmal kurz erklären wie bei einem degenerierten Transportproblem vorzugehen ist bzw. was man beachten muss? :)
Wann müssen wir den einfachen, dualen, primalen Simplex verwenden? Ich steige da nicht hinter
das hängt alles von der Startlösung ab, welches Verfahren man verwendet
Das duale Verfahren ist wie der primale Simplex, den nimmst du nur wenn es in der Aufgabe gefordert wird und der 2-Phasen-Simplex wird benötigt wenn in der Standardform nicht genug Pivotspalten vorhanden sind
Kann mir jemand 4.2 vom Übungsblatt 4 erklären? Ich checks nicht, wie wir auf die Lauftzeit von O(|V|^3) kommen
Dijkstra findet von einem Knoten aus alle kürzesten Wege von diesem Knoten zu allen anderen Knoten im Graphen wenn wir den kürzesten Weg von S zu D finden wollen, würden wir also Dijkstra für jeden Knoten in S einmal ausführen und hätten so für jeden Knoten in S die kürzesten Wege zu allen anderen Knoten im Graphen (somit auch zu allen Knoten in D) und wählen davon den kleinsten aus die naive Laufzeit von Dijkstra ist O(V²), wir führen Dijkstra für jeden Knoten in S einmal aus, also insgesamt S-mal, der Aufwand wäre somit etwas genauer ausgedrückt O(S * V²), was aber in der Größenordnung von O(V³) ist, da S ja eine Teilmenge von V ist, deren Größe vorher unbekannt, aber maximal V ist
Moin! Eine Frage... Auf dem OR Übungsblatt ist die aufgabe 2.3 mit dem absorbierenden Knoten. Aufgrund der Bezeichnung weiß man ja schon, dass also alle Kanten in den Konten eingehen und keine aus. Auf dem Blatt steht aber, das der delta- = (0) und delta+ = (|V|-1. Im Buch steht aber bei Knotengrad, dass der Ausgrad delta+ ist und der Eingrad delta - beim dem gerichteten Graphen (mit Beispiel sogar). Hatte mich beim Lernen schon gewundert, aber es so aus dem Buch hingenommen. (S. 31 2.8) Was ist jetzt richtig?? Danke
Bei Wiki steht das auch so wie im Buch... delta- ist Eingrad und delta+ ist Ausgrad. Damit bezeichnet man einen Konten, der einen Eingrad d-=0 hat als Quelle und einen Knoten, der einen Ausgrad d+=0, als Senke.... ist das dann auf dem OR Blatt ein Fehler?
würde es definitiv so wie auf dem Blatt und im Foliensatz lernen (Folie 3-9), weil das die einheitliche Methode ist, mit der wir letztes Semester gearbeitet haben, also: delta+ = Eingrad und delata- = Ausgrad insgesamt aber für die Klausur kaum relevant, da derartige Fragen zum Thema Graphen mit hoher Sicherheit kein Bestandteil der Klausur sein werden
Ich habe eine andere Reihenfolge, also erst x1+x2+x3=4 x1-x4 = 1 x2-x5=1 wenn man dann die ersten 3 pivotisiert, dann hat man halb eine andere Lösung, als du jetzt.. Wieos gehen wir hier so vor, dass zuerst die NB in die koeffizienzenmatrix geschrieben werden?
View 2 more comments
Beide Lösungen sind zulässig, also keine Heransgehensweise ist falsch. Bei der Lösung von Said kommt der Zielfunktionswert -2,5 für x1=3, x2=1 (und x3=2) raus (wie ihr ja im Dokument seht), was die rechte Ecke des Dreiecks/ Polyeder darstellt. Eure Lösung mit x1 & x2 = 1 (und x3=2) ergibt den Zielfunktionswert von -1,5, also noch schlechter, und ist die linke untere Ecke des Dreiecks/ Polyeders. Da in -0,5x1-x2 -> min immer x2 sich stärker vergrößert (weil es nicht mit 0,5 multipliziert wird), muss für eine bessere oder optimale Lösung gelten x2>x1. Folglich kann man beide o.g. Lösungen ausschließen, da in Saids Lösung x1>x2 und in eurer Lösung x1=x2 ist. Die optimale Lösung lautet übrigens x1=1 und x2=3. Dies lässt sich sehr leicht aus der Nebenbedingung x1+x2<=4 erkennen. Die optimale Lösung ist die linke obere Ecke des Dreiecks
Wenn ihr noch e) und f) weiterrechnet, werdet ihr auf den gleichen Engpass (x5<=2) und Basiswechsel (also die neuen Basisspalten sind dann x1, x2 und x5; x3=x4) kommen. Das Ergebnis ist dann optimal. Es ist also wirklich egal, welche Reihenfolge man wählt, da man in beiden Fällen auf das optimale Ergebnis kommt.
Hallo, kann sich jemand noch erinnern was in der letzten Klausur zu Scheduling für Fragen dran kamen? :) Reicht es das Skript dazu einmal zu überfliegen oder sollte man sich das genauer angucken?
Verkaufe das Buch "Einführung in die Optimierung", welches man auch in die Klausur mitnehmen darf. Bei Interesse einfach melden :)
hey Johannes, ich besitze leider schon ein Exemplar von dem Buch, aber da ich mal stark davon ausgehe, dass du die Klausur letztes Semester geschrieben hast: Könntest du eventuell ganz kurz was zur letzten Klausur und den Anforderungen im Vergleich zu den Altklausuren sagen? 😅 habe da unterschiedliche Dinge von sehr viel schwerer als sonst bis ziemlich vergleichbar gehört 😕
Kann sich jemand noch daran erinnern, wie die Klausur im vergangenen Wintersemester aufgebaut war? War diese vergleichbar mit den bereitgestellten Musterklausuren aus den Jahren 14 und 15 oder inhaltlich anders bzw. schwerer?
View 1 more comment
@Brief: vielen Dank für deine Antwort! inwiefern schwerer? also nicht nur stumpfes Anwenden der Algorithmen, sondern auch Transfer / Verständnisfragen?
dadurch das wir das Buch mitnehmen dürfen, musste die schwerer gemacht werden - so hab ichs zumindest gehört. die einfachen Sachen wurden einfach weggelassen wie z.B. Branch & Bound was in Altklausuren gerne mal 15 Punkte gab - Transportprobleme war ein Sonderfall zu behandeln und den Rest weiß ich leider auch nicht mehr so genau
Kann mir jemand aus dem Gedächtnisprotokoll wiedergeben, was in der Klausur dran kam? Schreibe im Winter und eine grobe Orientierung wäre hilfreich, da ja bspw. das Thema Scheduling neu eingebaut wurde! Danke im Voraus:)
View 1 more comment
Beim scheduling sind die beweise wichtig zu lernen
@Nicki blöde Frage, aber ist das ein Witz gewesen oder kamen wirklich Fragen zu diesen Beweisen dran?
OR im Wintersemester nachschreiben oder lieber im Sommersemester? Soll die Nachschreibeklausur schwerer sein?
Weiß jemand zufällig was zur Klausur?
View 5 more comments
4.0
vielleicht an die höheren Semester: OR lieber regulär schreiben oder kann man das ohne Bedenken vorgezogen schreiben?
Wie fandet ihr die Klausur?
View 1 more comment
Viel zu wenig Zeit
Wie inkompetent muss man eigentlichen sein, um beim Transportproblem in der Aufgabenstellung die Hälfte der Werte zu vergessen.
Woher weiß ich, ob ich eine künstliche Variable einfügen muss oder nicht?
wenn keine gültige Basislösung vorliegt
Denkt ihr es wird wieder Multiple Choice Fragen geben? Macht wenig Sinn wenn wir das Buch mit in die Prüfung nehmen dürfen, oder?
Jo das ist recht dick und Grimme hat uns gesagt, dass man das eigentlich nicht braucht. Also ich bezweifel, dass du da was findest, was dir weiter hilft
Und ja es wird sehr wahrscheinlich wieder mc geben
Was war nochmal ein kritischer Pfad?
Wenn frühster Zeitpunkt = spätester Zeitpunkt, man sich also bis dahin nicht verspäten darf.
WS 2014/2015 Klausur Warum wird in der zweiten Iteration der Wert vom Knoten R schon auf 2 aktualisiert? Normalerweise wird das doch nicht gemacht und der Weg dann einfach vom Schlusstableau abgelesen
View 2 more comments
!!! Hier WS 14/15 wird es NICHT so gemacht. Der "eingeloggte" wird nicht berücksichtigt. f wäre über h (eingeloggt) mit Kosten 6 erreichbar. ABER in der Lösung steht, dass über g mit Kosten 7 gegangen wird. Immer unterschiedlich ? Was ist dennn jetzt richtig ?
Es ist natürlich beides richtig. Oben ist der Knoten eingeloggt, dessen x umkreist ist. Bei Deinem Beispiel markiert man mit dem Kreis den Knoten für den darauffolgenden Schritt. Ist Geschmackssache, wie man das lieber macht. In der ersten Iteration erkennt man auch, welche Vorgehensweise gewählt wurde.
Kann mir jemand sagen, warum ich bei Aufg. 3 bei der Klausur SS 14 bei A,E,C... mit U=11 schon aufhören kann? Danke!
Weil es nach A,E,C nur einen möglichen weg gibt der wieder zurück zu A führt :)
Danke :)
Welche Blätter müssen bei B&B weggestrichen werden? Meines Verständnisses nach die, deren obere Schranke von der unteren Schranke eines anderen Pfads dominiert werden, sofern sie auf der gleichen bzw tieferen Ebene sind. Wie gehe ich denn vor bei dem Aufstellen? Gehe ich erst jeden Zweig komplett durch bis auf die unterste Ebene oder baue ich die parallel auf? In den Klausuren ist mir eine Aufgabe incl Lösung aufgefallen, bei der ich die Reihenfolge der Traversierung nicht erkennen konnte. Danke!
Richtig! Du baust immer alle Zweige einer Ebene komplett auf, sofern ein Pfad nicht gestrichen werden konnte. Bei der Auswahl welchen Zweig/Pfad einer Ebene du zuerst oder als nächstes aufbauen sollst gehst du gierig vor und wählst zuerst den mit der größten unteren Schranke
Das kommt drauf an ob du den das B&B auf das TSP anwendest oder auf das Rucksackproblem. Ich meine beim Rucksackproblem nimmt man die Obere Schranke um gierig vorzugehen und beim TSP gibt es ja nur die untere
Ich verstehe das vorgehen noch nicht genau. Wieso läuft man jetzt nach Rechts? Muss man nicht Boxing in in alle Richtungen machen und die beste Lösung wählen?
nein du nimmst die erste bessere lösung
Die Werte links sind vertauscht, es müsste zuerst 1 und darunter 2 sein. Demzufolge müssten die Delta-Werte 0, 0, 1/3, 0, -0.5, 0.5 lauten.
Ich habe 0, 0, -0.5, 0, 0, -0.5. jemand auch?
ich habe 0, 0, -0,5, 0, -0,5, -0,5 raus
-0.18 ist doch bereits besser als -0.02, warum geht man also nicht mit schritt 2.2 in x-richtung??
Man vergleicht die -0,18 mit dem Ausgangswert der Extrapolation also der -0,78. Die -0,02 würde erst ausgewertet werden, wenn die Exploration scheitern würde.
Warum ist das falsch?
weil xk+1 = xk + zk ist
wann muss man den dualen und wann den primalen simplex anwenden? Steht das immer in der Aufgabenstellungen oder gibt es dafür Kriterien? Und brauchen wir die Umwandlung von einem primalen in ein duales Problem? steht ja auf den vorlesungsslides drauf aber das kam ja so nie in den tutorien dran
primal: wenn primal zulässig: b-Werte >0 dual: wenn dual zulässig: Delta-Werte <0 (b-Werte können daher <0 sein) Dualisierung brauchen wir wahrscheinlich eher nicht, ist ja unabhängig vom dualen Simplex und meist nur dazu gedacht, ein Problem zu vereinfachen. Mit der Zweiphasenmethode und dem primalen sowie dualen Simplex lässt sich ja alles lösen!
ich meine auch das gesagt wurde, dass das in der Klausur dran stehen würde
Durch [], -> geht der doch viel mehr zum ersten Element / Anfang der 2. Zahl, oder?
Hier wäre ich nach unten auf -0,79 gegangen, da wir immer erst in Positive Richtung gehen und direkt bei Verbesserung die Teillösung übernehmen. (Auch wenn es eine schlechtere Wahl ist). Nach der Extrapolation und weiterer Exploration finde ich keine Verbesserung und terminiere ich. Habe ich das so richtig verstanden oder wieso gehst du nach oben ?
Ja aber da du mit einer Schrittweite von 0,2 gehst würdest du zur -0,56 gelangen und nicht zur -0,79
Guter Einwand 🙈
Müsste man an dieser Stelle nicht, wie in der Aufgabe beschrieben zuerst in die pos. Koordinatenrichtung schauen und dort dann die Verbesserung -0,58 nehmen?
View 1 more comment
Ja man würde hier natürlich auch erst in die pos. horizontale Richtung schauen, aber feststellen, dass der Wert nicht besser ist und somit in die negative Richtung schauen
Muss man in der Klausur auch die nichterfolgreichen Explorationsschritte aufzeigen? Z.B. Vergleich f(0,4; -1,6)= -0,47 mit f(0,4; -1,4)= -0,39
Was lernt ihr jetzt alles für Scheduling? Habt ihr noch gute Übungsaufgaben ausm Internet oder ähnliches? Oder reichen die Aufgaben aus den Sonderübungszetteln?
Ich würde mir das Scheduling Skript nochmal ein wenig anschauen, vor allem Kapitel 2: einfache Schedulingprobleme. Was auch dran kommen kann ist wie du schon gesagt hast so etwas wie auf dem Sonderübungsblatt, also Branch & Bound mit einem Scheduling Problem
In den Altklausuren gibt es kein Scheduling @Mr.Anonym479
Weiss jemand, ob wenn man das buch ausdruckt/kopiert ob man es dann mit in die klausur nehmen kann?
nein
Load more