{"id":2600,"date":"2013-10-04T19:09:56","date_gmt":"2013-10-04T17:09:56","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=2600"},"modified":"2013-10-04T19:09:56","modified_gmt":"2013-10-04T17:09:56","slug":"01142-algorithmische-mathematik-simplex-cholesky","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=2600","title":{"rendered":"01142: Algorithmische Mathematik (SIMPLEX, Cholesky)"},"content":{"rendered":"

Da mich nun mittlerweile die gef\u00fchlte 100. Mail erreicht hat, die nach meinem Spickzettel f\u00fcr Algorithmische Mathematik (01142) fragt, habe ich beschlossen meinen Widerstand aufzugeben. Widerstand? Ja, Widerstand. Euch ist bewusst, warum Spickzettel sinnvoll sind? Durch die Anfertigung eines Spickzettels konzentriert man sich \u00fcber einen l\u00e4ngeren Zeitraum auf den Inhalt und seine Aufarbeitung und braucht – oh Wunder! – ihn in der Klausur dann nicht mehr. Das ist der Grund, warum im Wintersemester 09 dieser Spickzettel zu der 150% Klausur von Prof. Dr. Hochst\u00e4ttler zugelassen war (und es wohl noch ist, wie ich den Mails bzgl. meines Spickzettels implizit entnehmen kann).<\/p>\n

Durch diesen didaktischen Kniff (und das tolle Skript, Prof. Dr. Hochst\u00e4ttler ist sehr engagiert und nimmt seinen Lehrauftrag \u00e4u\u00dferst ernst) konnte ich die bisher beste Note in einem mathematischen Fach holen. Daher: Auch wenn Ihr euch meinen Spickzettel herunterl\u00e4dt, eine kleine Bitte: fertigt zun\u00e4chst euren eigenen an und schaut euch erst dann meinen an um evtl. fehlende Themen noch aufzunehmen.<\/p>\n

Lange Rede, kurzer Sinn: Das war damals meiner.<\/p>\n

\"spickzettel_png\"<\/a><\/p>\n

Und noch ein paar Tipps, die ich bereits an anderer Stelle<\/a> gegeben habe:<\/p>\n

Ihr habt 150% in der Klausur, die auf zwei Stunden ausgelegt ist. Der Schl\u00fcssel ist also auch hier: schnell sein. Es gibt sehr schreibintensive Themen, wo Fl\u00fcchtigkeitsfehler euch Punkte kosten k\u00f6nnen. Dazu geh\u00f6ren die LU Zerlegung, Chokesly, Dijsktra, Simplex und Optimierung. Hier hei\u00dft es: \u00dcben, \u00fcben, \u00fcben!<\/p>\n

Die folgenden Beschreibungen sind ohne Gew\u00e4hr. Sie sind aus dem WS09, d.h. es ist mittlerweile 3 Jahre her und ich habe mich mit dem Stoff nicht mehr besch\u00e4ftigt. Sollten sich also Fehler eingeschlichen haben, bitte sofort melden.<\/p>\n

SIMPLEX<\/h1>\n

Der absolute Punktebringer. Aber wehe man verrechnet sich. Daher habe ich mir irgendwann alles haarklein aufgedr\u00f6selt und ein kleines Howto geschrieben. Alle, die im Stoff bisschen drin sind, sollten das nachvollziehen k\u00f6nnen. Wie gesagt: ohne Gew\u00e4hr… ist alles lange her \ud83d\ude09<\/p>\n

– Das kleine HowTo zu SIMPLEX gibt es auch als PDF<\/a>.<\/p>\n

– Um nicht immer die Klammern usw. in den Rechnungen zu schreiben, habe ich mir auch eine Simplex Vorlage<\/a>\u00a0gebastelt.<\/p>\n

Beispiel\u00a0<\/strong><\/p>\n

1. Das Problem wird in Normalform gebracht<\/b><\/span><\/p>\n

A) Zielfunktion<\/span><\/span><\/p>\n

Das Problem wird immer in Maximierungsform dargestellt. Ein Problem in Minimierungsform wird einfach mit (-1) multipliziert.\u00a0<\/span><\/p>\n

\"s1\"<\/a><\/p>\n

B) Nebenbedingungen<\/span><\/span><\/p>\n

Die Nebenbedingungen werden in Gleichungsform \u00fcberf\u00fchrt. Generell ist die Vorgehensweise wie folgt:<\/span><\/p>\n

\"s2\"<\/a><\/p>\n

Dabei ist zu beachten, dass als Ergebnis keine negativen Zahlen stehen d\u00fcrfen. Ist hinter dem Gleichheitszeichen\/Ungleichheitszeichen ein negativer Wert, so wird die Un-\/Gleichung mit (-1) multipliziert. Dabei dreht sich das $$\\leq$$ oder $$\\geq$$ entsprechend, das $$=$$ bleibt<\/span>. Dann wird eine Schlupfvariable ($$yA$$) und eine Hilfsvariable ($$s1$$) eben addiert oder subtrahiert um aus der Ungleichung eine Gleichung zu machen.\u00a0<\/span><\/p>\n

Beispiel:<\/p>\n

\"s3\"<\/a><\/p>\n

C) Duales Problem (wenn n\u00f6tig).<\/span> Beispiel:<\/span><\/p>\n

\"s4\"<\/a><\/p>\n

2. SIMPLEX Starttableu aufstellen<\/b><\/span><\/p>\n

A) Anhand der Normalform wird das Starttableu aufgestellt.<\/span> Beispiel:\u00a0<\/span><\/p>\n

\"s5\"<\/a><\/p>\n

B) Die Auswahl der Pivotspalte<\/span> geschieht nach folgenden Regeln. Zun\u00e4chst die Spalte, wo bei einer Zelle in $$\\delta_2$$\u00a0<\/span>(Hilfsfunktion) der erste positive Wert steht ($$\\delta_2$$,\u00a0<\/span>Spalte 2 mit dem Wert „1“). Dann sucht man sich die Zeile mit einem positiven Wert und teilt den x-Wert in dieser Zeile durch den positiven Wert und tr\u00e4gt die Werte in Spalte x\/f ein. Die Zeile mit dem niedrigsten Wert beinhaltet den Pivotwert (1).\u00a0<\/span><\/p>\n

C) Nun wird das 2. Tableu aufgestellt <\/span>indem man zun\u00e4chst die Pivotzeile durch das Pivotelement (1)<\/b> dividiert. Diese bildet die neue Pivotzeile<\/b><\/span> im n\u00e4chsten Tableu.\u00a0<\/span>F\u00fcr die anderen Zeilen geht man wie folgt vor: man subtrahiert vom alten <\/span>Zeilenwert<\/b><\/span> (<\/span>altes Spaltenpivot<\/b><\/span>*<\/span>neues Zeilenpivot<\/b><\/span>). Ergebnis ist die gleiche Zeile in der neuen Tabelle. Rechnung:<\/span><\/p>\n

\"s7\"<\/a><\/p>\n

Die Ergebniswerte sind die neuen Zeilen im neuen Tableau. Dabei werden dann $$yB$$ und $$y$$ „im Kopf“ vertauscht.<\/span><\/p>\n

\"s8\"<\/a><\/p>\n

Das ganze geht so lange, bis in der Zeiler der Hilfsfunktion $$\\delta_2$$\u00a0<\/span><\/p>\n

keine positiven Werte mehr sind. In diesem Fall ist es bereits jetzt soweit. Somit ist es das Endtableau f\u00fcr Phase 1. Wir beginnen mit<\/span><\/p>\n

D) dem Aufstellen des Starttableaus f\u00fcr Phase 2<\/span><\/span><\/p>\n

Hier werden nun die Hilfsfunktions-Zeile $$\\delta_2$$\u00a0<\/span>und die Hilfsvariablenspalte (s1) gel\u00f6scht. Das bringt uns zu folgendem Starttableau f\u00fcr Phase 2.<\/span>\"s9\"<\/a><\/p>\n

Wir w\u00e4hlen die Pivotspalte und Zeile wieder wie gehabt und f\u00fchren wieder die \u00fcbliche Rechnung durch.\u00a0<\/span><\/p>\n

\"s10\"<\/a><\/p>\n

Die Rechnung f\u00fchrt uns zu folgender, 1. Tabelle von Phase 2:<\/span><\/p>\n

\"s11\"<\/a><\/p>\n

Nun stehen nur negative Werte in der Zielfunktionszeile $$\\delta_1$$.\u00a0<\/span><\/p>\n

Wir k\u00f6nnen also die L\u00f6sung<\/span><\/p>\n

\u00a0$$x=1$$<\/span><\/p>\n

$$y=15$$<\/span><\/p>\n

mit einem Funktionswert von<\/span><\/p>\n

$$f(x,y) = 17$$<\/p>\n

ablesen. W\u00e4re es eine <\/span>Minimierungsaufgabe<\/b>, so m\u00fcsste man den Funktionswert -17 nicht mit (-1) multiplizieren. Der Funktionswert w\u00e4re dann -17.\u00a0<\/span><\/p>\n

Hier findet Ihr noch ein kleines, handschriftliches Simplex Beispiel<\/a>\u00a0von mir.<\/p>\n

 <\/p>\n

CHOLESKY-Zerlegung<\/h1>\n

Auch hier gilt: je schneller, desto besser. In den \u00dcbungsaufgaben und in der Klausur kommen meist nur 2×2 oder 3×3 Matritzen vor. Daf\u00fcr habe ich mir damals ganz einfach f\u00fcr jedes Feld eine Formel gebastelt:<\/p>\n

3×3 Matrix<\/strong><\/p>\n

\"cholesky\"<\/a><\/p>\n

That’s it. Die 2×2 Matrix ist – das wollte ich schon immer mal sagen – doch trivial \ud83d\ude00<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Da mich nun mittlerweile die gef\u00fchlte 100. Mail erreicht hat, die nach meinem Spickzettel f\u00fcr Algorithmische Mathematik (01142) fragt, habe ich beschlossen meinen Widerstand aufzugeben. Widerstand? Ja, Widerstand. Euch ist bewusst, warum Spickzettel sinnvoll sind? Durch die Anfertigung eines Spickzettels konzentriert man sich \u00fcber einen l\u00e4ngeren Zeitraum auf den Inhalt und seine Aufarbeitung und braucht … <\/p>\n

\u201e01142: Algorithmische Mathematik (SIMPLEX, Cholesky)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-2600","post","type-post","status-publish","format-standard","hentry","category-fernuni"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2600","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2600"}],"version-history":[{"count":15,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2600\/revisions"}],"predecessor-version":[{"id":2632,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2600\/revisions\/2632"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2600"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2600"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2600"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}