[BWL] Quantitative Methoden - Überblick SS08

Alle Anwendungsfächer des Bachelorstudiengangs (Abkürzungen)

Quantitative Methoden - Überblick SS08

Beitragvon Coolcat » 01.08.08 13:07

Code: Alles auswählen
=========================================================================================
Quantitative Methoden - Überblick, SS 08
Priv.-Doz. Dr. Stefan Irnich
(für Mathe, Info, ETechnik, ...)
=========================================================================================

Dies soll keine Zusammenfassung sein, sondern nur ein kleiner Überblick über den Stoff. Als Quelle dienen die Folien der Vorlesung.

=========================================================================================
Kap.1 - Einleitung
=========================================================================================
      Operations Research
         Quantitative Methoden
            Mathematische Methoden: Modell, Algorithmen
         Was ist "optimieren" und was ist "optimal"?
            explizit, implizit, zulässig, unzulässig, optimal
      Optimierung
         Zulässigkeit: Nebenbedingungen = Restriktionen = Constraints (hard constraints)
         "bestmöglich": Zielfunktion(en) (soft constraints)
      Merke: Optimierung
         Modellierung mit Entscheidungsvariablen, Modell
         Optimierungsproblem, optimale Entscheidung/Lösung
      MCDA (Multi Criteria Decision Analysis)
         Beispiel
      Optimierungsbegriff der "Praxis"
         verbessernde Lösung
      Optimierung - State of the Art
         "Optimierung" in der Praxis
         Barrieren und Probleme in der Praxis
      Historie des OR - OR an der RWTH Aachen
      Quantitative Methoden
      OR am Deutsche Post Lehrstuhl
      Gliederung der Vorlesung
      Literatur
=========================================================================================
Kap.2 - Modellierung
=========================================================================================
   -------------------------------------------------------------------------------------
   2.1 Einführendes Beispiel
   -------------------------------------------------------------------------------------
      Produktionsplanung
         optimaler Produktionsplan
         Entscheidungsvariablen, Restriktionen
         => Optimierungsproblem
         Beispiel
         Modell (Lineares Programm)
         Graphische Lösung
         Erkenntnisse aus dem Beispiel in Dimension 2
            benachbarte Ecken
   -------------------------------------------------------------------------------------
   2.2 Grundmodelle der linearen Programmierung
   -------------------------------------------------------------------------------------
      Übersicht
      Produktionsplanung
         Beschreibung
         Modell
         Modell in Matrixschreibweise
         Mögliche Erweiterungen
      Mischungsprobleme
         Beschreibung
         Modell
         Beispiel
         Mögliche Erweiterungen
      Zuschnittprobleme
         Beschreibung
         Beispiel
         Modell
      Das Umladeproblem
         Beschreibung
         Beispiel
         Modell
         Merke: Voraussetzung für Zulässigkeit des Umladeproblems
         Modell in Matrixschreibweise
         Das Umladeproblem - Eigenschaften von (Basis-)Lösungen
         Merke: Ganzzahligkeit beim Umladeproblem
         Umladeproblem ist Verallgemeinerung:
            Transportproblem
            Zuordnungsproblem
            Kürzeste-Wege-Problem
            Problem des maximalen Flusses
      Das Transportproblem
         Beschreibung
         Beispiel
         Modell
      Das Zuordnungsproblem
         Beschreibung
         Modell
      Das Kürzeste-Wege-Problem
         Beschreibung
         Voraussetzung
         Idee
         Modell
         Beispiel
         Modell in Matrixschreibweise
      Das Problem des maximalen Flusses
         Beschreibung
         Modell
   -------------------------------------------------------------------------------------
   2.3 Grundmodelle der kombinatorischen Optimierung
   -------------------------------------------------------------------------------------
      Lineare gemischt-ganzzahlige Programmierungsprobleme (mixed integer programming problems, MIP)
         Ganzzahlige und binäre Entscheidungsvariablen
         Bemerkungen
         Zulässigkeitsbereich
         ganzzahliges Programmierungsproblem (integer program, IP)
          binärens Programmierungsproblem (binary program, BP)
      Übersicht
      Das Rucksackproblem
         Beschreibung, Modell
         Anwendung
      Das Bin-Packing-Problem
         Beschreibung, Modell
         Beispiel
      Das Travelling-Salesman-Problem (TSP)
         Beschreibung
            symmetrisches TSP (STSP)
            asymmetrisches TSP (ATSP)
         Beispiel
         Modell
      Set-Covering-, Set-Partitioning- und Set-Packing-Probleme
         Beschreibung
         Beispiel
         Modelle
=========================================================================================
Kap.3 - Lineare Programmierung
=========================================================================================
   -------------------------------------------------------------------------------------
   3.1 Mathematische Grundlagen
   -------------------------------------------------------------------------------------
         Erkenntnisse aus dem Beispiel in Dimension 2
      Der Zulässigkeitsbereich ein LP
         Definition
            Konvexkombination
            konvexe Menge
         Bemerkung
         Definition
            konvexe Hülle
            Ecke
            Menge der Ecken
            (konvexes) Polytop
            Strahl
            Kegel
            Extremalstrahl
            (konvexes) Polyeder
         Bemerkung
         Merke: Der zulässige Bereich eines linearen Programms ist entweder leer oder ein konvexes Polyeder.
         Rang der Matrix
         Merke: ...
         Merke: (zentrale Aussage)
         Schlupfvariablen
         Beispiel
         Was ist bis hierher erreicht? Wo wollen wir hin?
      Basis und Basislösung
         Definition
            Basis
            Basisvariablen und Nicht-Basisvariablen
            Basislösung
            zulässige Basislösung
         Merke: ...
         Beispiel
      Standardproblem der linearen Programmierung
         Definition
            Standardproblem der lin. Progr. in kanonischer Form
         Merke: Jedes beliebige LP lässt sich in ein Standardproblem in kanonischer Form transformieren!
         Beispiel (Transformation)
   -------------------------------------------------------------------------------------
   3.2 Simplexalgorithmus
   -------------------------------------------------------------------------------------
      Basiswechsel und Optimalitätsbedingungen
         ...
         Definition
            benachbarte Basislösung
            Basiswechsel
         Interpretation
         Bemerkung
         Optimalitätsbedingungen
         Beispiel
      Simplexalgorithmus
         Annahme für den Simplexalgorithmus
         Grundidee
         Vier Komponenten
            Ausgangsbasislösung
            Aufnahmeregel
            Eliminationsregel
            Simplexkriterium
         Simplexalgorithmus
         Bemerkung
         Der Algorithmus unter Verwendung von Simplextableaus
            Tableau
            Vereinbarungen (Pivotspalte, Pivotzeile)
            Regeln
         Kreis-Regel
         Beispiel
         Bemerkung
         Verfahren wenn keine Einheitsmatrix als Teilmatrix in A vorhanden
            Anforderungen an den Algorithmus
         Erweiterung des einführenden Beispiels
   -------------------------------------------------------------------------------------
   3.3 Dualität
   -------------------------------------------------------------------------------------
      Duale Modelle und ihre Eigenschaften
         Paar von Modellen
         Dualtät
         Zuordnungen
         Primales Modell (PM)
         Satz: Das duale Modell des dualen Modells (DM) ist das primale Modell (PM).
         Merke: Die Bezeichnung primales Problem und duales Problem ist (...) nur eine Frage des
                (eigenen) Standpunkts (...)
         Satz von der schwachen Dualität
         Satz von der starken Dualität
         Merke: Interpretation der dualen Lösung
         Satz vom komplementären Schlupf
         Merke: Im Optimum ist das Produkt aus Schattenpreis und zugehörigem Schlupf immer null.
         Weitere Eigenschaften:
            Satz: Hat das (PM) [bzw. (DM)] keine zulässige Lösung, so hat das (DM) [bzw. (PM)]
                  keine optimale Lösung.
            Satz
         Beispiel
         Definition (primale und duale Zulässigkeit)
         Merke: Eine Basislösung ist genau dann optimal, wenn sie gleichzeitig primal und dual zulässig ist.
      Dualer Simplexalgorithmus
         Ausgangsbasislösung
         Eliminationsregel
         Aufnahmeregel
         Begründung
         Abbruchregel (Optimalitätskriterium)
         Beispiel
      Degeneration (= Entartung)
         Degeneration
         Definition (primal degenerierte Basislösung)
            primal degeneriert (= primal entartet)
         Beispiel
         Definition (dual degenerierte Basislösung)
            dual degeneriert (= dual entartet)
         Beispiel
         Merke: Degeneration ist keine rein geometrische Eigenschaft, sondern hängt (auch) von der Darstellung
                eines Polyeders durch Ungleichungen und Gleichungen ab.
         Bedeutet der primale Entartung für den Simplexalgorithmus
   -------------------------------------------------------------------------------------
   3.4 Postoptimale Analyse und Modifikation
   -------------------------------------------------------------------------------------
      Übersicht
         parametrischere Programmierung
      Sensitivitätsanalyse
         Veränderung der rechten Seite
         Einführendes Beispiel: optimales Endtableau
         Veränderung der Zielfunktionskoeffizienten
         Beispiel
          Parametrisches Programmieren
         Bisher
         Jetzt
         Vorgehen
         Reoptimieren
         Einführendes Beispiel
=========================================================================================
Kap.4 - Ganzzahlige Lineare Programmierung
=========================================================================================
   -------------------------------------------------------------------------------------
   4.1 Lösung allgemeiner ganzzahliger LP
   -------------------------------------------------------------------------------------
      Übersicht
      Schnittebenenverfahren und gültige Ungleichungen
         LP-Relaxation
         Beispiel
         Beobachtungen
         Definition (gültige Ungleichung)
         Schnittebenenverfahren
         Generelle Schnittebenen
         speziellen Schnittebenen
         Schnittebenen
            Grundmodell für IP (rein ganzzahliges Modell)
            Herleitung
            Chvàtal-Gomory-Ungleichungen
         Beispiele
         Offene Fragen
         Separation von C-G-Ungleichungen
         Reoptimierung des LP
         Beispiel
         Das Rucksackproblem
            Modell
            Definition Überdeckung
            Überdeckungsungleichung
         Das Rucksackproblem - Lösung der LP-Relaxation
         Das Rucksackproblem - Überdeckungsungleichungen
            Beispiel
   -------------------------------------------------------------------------------------
   4.2 Branch-and-Bound-Verfahren
   -------------------------------------------------------------------------------------
      Übersicht
      Generische Beschreibung von B&B
         hierarchischen Zerlegung
         Branch-and-Bound-Baum
         Branching / Bounding
         Erzeugung von Teilproblemen
         Übersicht zu Verzweigungsregeln
            Binäre Verzweigung
            Relaxationsbasierte Verzweigung
            Ganzzahlige Verzweigung
         Einige allgemeine Auswahlstrategien
            Kosten
            Gebrochene Variablen
            A priori Regeln
            Dynamische Bewertungskriterien
         Abarbeitung von Teilproblemen
            Möglichkeit einer Verbesserung des Verfahrens
               Variablenfixierung (-> siehe Bounding)
               heuristische Bestimmung einer zulässigen Lösung
         Auswahl von Teilproblemen
            Tiefensuche
            Breitensuche
            Bestensuche
            Beam-Search
         Bounding
            Variablen fixieren
         Generisches Branch-and-Bound-Verfahren
      Dakin-Algorithmus
         Komponenten
            Abarbeitung
            Erzeugung
            Variablenauswahl
            Auswahl
            Initialisierung
         Beispiel
         Set-Covering-Problem
            Beispiel: Lösung mit Dakin-Algorithmus
      B&B für das Bin-Packing-Problem
         Das Bin-Packing-Problem
         B&B-Algorithmus für das Bin-Packing-Problem
         Beispiel
      B&B für das Rucksack-Problem
         Das Rucksackproblem
         Komponenten des B&B-Algorithmus für das binäre Rucksackproblem
         Greedy-Algorithmus
         Beispiel (Tafel)
   -------------------------------------------------------------------------------------
   4.3/4.4 Lösung spezieller Probleme der kombinatorischen Optimierung
   -------------------------------------------------------------------------------------
      Ungarische Methode für das Zuordnungsproblem
           Das Zuordnungsproblem
         Satz (Invarianz optimaler Lösungen bzgl. Zeilen-/Spaltenaddtion)
         Satz (Zeilen-/Spaltenreduktion)
         Beispiel
         Definition (Auszeichnung von Nullen)
         Beispiel
         Definition (ausgezeichnete und freie Nullen)
         Anschauliche Beschreibung
            Sackgassenweg
         Prozedur "Alternierende Wege"
         Satz
         Satz (Überdeckungssatz)
         Beispiel
         Prozedur "Überdeckung"
         Algorithmus "Ungarische Methode"
      Lösung des STSP und ATSP
         Das Travelling-Salesman-Problem (TSP)
         Definition (Heuristik)
         Nearest-Neighbor-Heuristik
         Beispiel
         Nachteile der NN-Heuristik
            "Greedy-Heuristiken"
         k -Opt-Verfahren (Verbesserungsverfahren) für das TSP
         Erweitertes Zuordnungsmodell für das ATSP
         Branch-and-Bound-Verfahren für das ATSP
         Beispiel
      Kürzeste-Wege-Probleme und Labeling Algorithmen
         Das Kürzeste-Wege-Problem
         Modell zu simultanen Bestimmung aller kürzesten Wege
         Merke
         Merke
         Labeling Algorithmen
         Optimalitätsbedingungen und Dualität
         Generischer Kürzeste-Wege-Algorithmus
         Dijkstra-Algorithmus
         FIFO-Algorithmus
        Max-Flow/Min-Cut und der Ford-Fulkerson-Algorithmus
         Das Problem des maximalen Flusses
            Hilfsnetzwerk
         Definition (vergrößernder Weg)
         Ford-Fulkerson-Algorithmus
            Satz (Satz vom maximalen Fluss)
         Maximaler Fluss und minimaler Schnitt
      Branch-and-Cut für das STSP
         Übersicht
         Branch-and-Cut-Algorithmen
            Schnittebenenverfahren
         Branch-and-Cut
         Das Travelling-Salesman-Problem (TSP)
            2-Matching-Modell für das STSP
         Separation verletzter SEB
            Lösung des Separationsproblems für SEB
            Reduktionsverfahren von Padberg und Crowder
         Gültige Ungleichungen
         2-Matching-Ungleichungen
            2-Matching-Restriktion
         Separation von 2-Matching-Ungleichungen
         Branch-and-Cut für das STSP
         Leistungsfähigkeit von B&C-Algorithmen

Ende
My software never has bugs. It just develops random features.
Benutzeravatar
Coolcat
Promoter
 
Beiträge: 2574
Registriert: 28.11.05 21:26
Wohnort: Kohlscheid / Düsseldorf
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: BWL

Zurück zu Anwendungsfächer