Mathematik | Operations Research

Question 1

Dualität

Answer 1

1. Primales Problem: maximieren einer Zielfunktion unter einer Nebenbedingung
2. Duales Problem: minimieren einer Zielfunktion unter einer Nebenbedingung
   ⇒ Umwandlung durch transponieren der Tableaus möglich

Question 2

Duale- & Simplexmethode & Duale Simplexmethode

Answer 2

Optimierungsverfahren des Types Pivotverfahren für lineare Optimierungsprobleme.
Duale Probleme sind transponierte primale Probleme
Laufzeit: 2^n

Question 3

Problemformen

Answer 3

• Normalform
• Kanonische Form
• Standardform

Question 4

Normalform

Answer 4

1. Maximierungsproblem
2. Für alle Nebenbedingungen gilt die ≤-Bedingung
3. Für alle Variablen gilt die Nichtnegativitätsbedingung

Question 5

Kanonische Form

Answer 5

⇒ Normalform

4. Werte der rechten Seite müssen alle Positiv sein

Question 6

Standardform

Answer 6

5. Einfügen der Schlupfvariablen

⇒ Standardform

Question 7

Parametrische Optimierung

Answer 7

Die Parametrische Optimierung befasst sich mit dem Einfluss veränderlicher Parameter auf die Lösung
von Optimierungsproblemen. Hilft bei der Beurteilung numerisch gewonnener Lösungen

Question 8

Nordwest-Ecken-Regel

Answer 8

Erstellt nur eine Ausgangslösung durch Belegung der nordwestlichsten Ecke eines Transportplans mit der maximalen Menge und der anschließenden sukzessiven Belegung
Lösung mit Simplexmethode möglich

Question 9

Stepping-Stone-Methode

Answer 9

Z.b. aus der NWE-Regel ergibt sich eine Anfangslösung, die durch die Stepping Stone Methode iterativ optimiert werden kann, bis keine Optimierungsmöglichkeit mehr besteht.

Question 10

Lineares Zuordnungsproblem

Answer 10

Klassisches Transportproblem der Operations Research. Lösbar durch lineare Programmierung zb.

Question 11

Graphentheorie

Answer 11

Untersucht die Eigenschaften von Graphen und ihre Beziehungen zueinander. Graph ist eine Menge von Objekten die in einer Beziehung zueinander stehen.

Question 12

Graphenarten der Graphentheorie

Answer 12

1. Digraph –> Knoten werden durch gerichtete Kanten (Pfeile) verbunden
2. Multigraph –> Knoten können durch mehrfache Kanten verbunden sein
3. Hypergraph –> Eine Kante kann mehr als 2 Knoten miteinander verbinden

Question 13

Kürzester Pfand

Answer 13

Der Pfad zwischen 2 Knoten mit der minimalsten Länge nach Kantengewichtsfunktionen

Question 14

Minimal spannende Bäume

Answer 14

Frage, welche Weg muss man in gewichteten Graphen nehmen, um die best mögliche Strecke zwischen allen im Graphen vorhandene Knoten abzuschreiten.

Question 15

Netzplantechnik

Answer 15

Die Netzplantechnik verwendet Netzpläne, die eine temporale und finale Verkettung von Aktionen beschreiben. Sie findet ihre Anwendung insbesondere in der Terminplanung von Projekten.

Question 16

Branch-and-Bound-Verfahren

Answer 16

Das Verfahren hat das Ziel darin, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch-and-Bound führt zu einem Entscheidungsbaum.

Question 17

Knapsackproblem (Rucksackproblem)

Answer 17

Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden.

Question 18

Monte-Carlo-Methode

Answer 18

Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern dürfen. Dafür sind sie im Vergleich zu deterministischen Algorithmen häufig effizienter