Operations Research & Optimierung: Methoden, Modelle & Algorithmen

Operations Research: Grundlagen und Methoden

Operations Research (OR) ist ein System, das exakte Methoden, Heuristiken, deterministische Methoden und probabilistische Modelle nutzt, um komplexe Entscheidungsprobleme zu lösen.

Einführung in die Lineare Programmierung

Modellierung und Annahmen

Die Lineare Programmierung (LP) befasst sich mit der Optimierung einer linearen Zielfunktion unter linearen Nebenbedingungen. Wichtige Elemente sind:

• Das lineare Programmierungsmodell
• Der zulässige Bereich (Lösungsraum)
• Machbare Lösungen und grundlegende Annahmen

Lösungsraum und Optimalität

Die Analyse des Lösungsraums umfasst:

• Konvexe Mengen und Stützpunkte
• Grundlegende und nicht-basische Lösungen
• Extrempunkte und Stützpunkte
• Fälle ohne optimale Lösung oder mit multiplen optimalen Lösungen
• Erkennung von Entartung

Simplex-Algorithmus

Der Simplex-Algorithmus ist eine zentrale Methode zur Lösung linearer Programme:

• Grundform und kanonische Form
• Simplex-Phasen (erste und zweite Phase)
• Die Zwei-Phasen-Simplex-Methode

Dualität und Sensitivitätsanalyse

Die Dualitätstheorie und Sensitivitätsanalyse sind entscheidend für das Verständnis von LP-Modellen:

• Beziehungen zwischen primalen und dualen Problemen
• Komplementäre Schlupfvariablen
• Interpretation der Schattenpreise (Dolmetschkosten)
• Auswirkungen von Koeffizientenänderungen auf Basisvariablen und Zielfunktionskoeffizienten
• Konsequenzen technologischer Veränderungen
• Hinzufügen neuer Variablen und Restriktionen
• Erkennung unbegrenzter und unzulässiger Probleme

Spezielle Optimierungsprobleme

Transport- und Zuordnungsprobleme

Das Transportproblem ist ein klassisches LP-Problem:

• Transporttabelle und geschlossener Kreis
• Methoden zur Berechnung optimaler Lösungen
• Degenerationsgrad
• Maximale Flusslösung
• Der Ungarische Algorithmus für Zuordnungsprobleme

Netzwerkanalyse und Flussprobleme

Die Netzwerkanalyse befasst sich mit:

• Verbundene Knoten, Bögen und Bogenkapazitäten
• Flussprobleme (z.B. maximaler Fluss)
• Das Kürzester-Weg-Problem
• Netzwerkkosten, Kapazitätsengpässe und Ausfallkosten

Projektmanagement (PERT/CPM)

Methoden des Projektmanagements wie PERT (Program Evaluation and Review Technique) und CPM (Critical Path Method) sind essenziell für die Planung und Steuerung von Projekten:

• Analyse von Prioritäten
• Früheste und späteste Startzeiten
• Der Kritische Pfad
• Pufferzeiten (Gesamt- und freier Puffer) von Aktivitäten
• Aktivitätsdauer unter Unsicherheit
• PERT-Formulierung: Knoten, Bögen, Bogenkapazitäten

Ganzzahlige Programmierung

Modelltypen und Anwendungen

Die Ganzzahlige Programmierung (GP) erweitert die LP, indem sie ganzzahlige Variablen zulässt:

• Merkmale und Grundannahmen
• Typen der ganzzahligen Programmierung (reine und gemischte)
• Relaxierte Probleme

Spezifische Probleme und Algorithmen

Wichtige Probleme der ganzzahligen Programmierung sind:

• Das Knapsack-Problem (Rucksack-Problem)
• Das Traveling Salesperson Problem (TSP)
• Probleme mit festen Kosten
• Methoden zur Lösung ganzzahliger Programmierprobleme

Erweiterte Konzepte

Heuristische und exakte Algorithmen

Ein Vergleich von heuristischen und exakten Algorithmen ist wichtig für die Wahl der richtigen Lösungsmethode.

Unsicherheit und Stabilität

Die Berücksichtigung von Unsicherheit und die Analyse der Stabilität von Lösungen sind fortgeschrittene Themen:

• Aktivitäten mit spezifischen Parametern (z.B. mij=0)
• Kritischer Pfad bei unbekannter Dauer
• Logistikfunktionen