Grundlagen des Projektmanagements und der Optimierung

Projektmanagement und der kritische Pfad

106: Pufferzeit (Slack): Wenn die Pufferzeit (Mlikh) gleich 0 ist, führt jede Verzögerung zu einer Verspätung der nachfolgenden Aktivitäten. Wenn die Pufferzeit jedoch größer als Null ist, verzögert eine Verzögerung das Gesamtprojekt nicht (MTIJ > 0).

107: Kritischer Pfad: Dies ist der längste Weg durch das Projektnetzwerk und bestimmt die unbedingt notwendige Mindestdauer des Projekts. Die Aktivitäten auf diesem Pfad werden als kritisch bezeichnet.

PERT-Methode und Zeitschätzungen

109: PERT-Verfahren: Dieses tritt auf, wenn die Dauer der Aktivitäten nicht mit Sicherheit bekannt ist. Es werden drei Schätzungen verwendet:

• Optimistisch (aij)
• Realistisch (mij)
• Pessimistisch (bij)

Es wird davon ausgegangen, dass die Dauer der Aktivitäten einer Beta-Verteilung folgt. Unter der Annahme, dass die Dauern (tij) unabhängige Zufallsvariablen sind, folgt die Gesamtdauer des Projekts (T) laut dem zentralen Grenzwertsatz einer Normalverteilung. Die Formulierung einer PERT-Optimierung lautet: min z = Summe von i=1 bis n Ti, wobei die Nebenbedingungen die Zeitabstände zwischen den Knoten berücksichtigen.

Grundlagen der Graphentheorie

• 110: Knoten: Ein Knoten ist ein Schnittpunkt im Graphen, der mit einer Nummer identifiziert wird.
• 111: Bogen (Arco): Die Verbindung zwischen zwei Knoten. Ein Netzwerk heißt orientiert, wenn alle Bögen eine bestimmte Richtung haben.
• 112: Kapazität: Die maximale Durchflussmenge, die durch einen orientierten Bogen fließen kann.
• 113: Verbindung: Zwei Knoten gelten als verbunden, wenn sie durch einen Bogen verknüpft sind.
• 114: Kette, Pfad und Zyklus: Eine Gruppe aufeinanderfolgender Bögen. Eine Route, die am selben Knoten beginnt und endet, wird als Zyklus bezeichnet.

Optimierungsprobleme in Netzwerken

115: Kürzester-Weg-Problem

Suche nach der kürzesten Strecke zwischen Start und Ziel in einem Netz mit zugeordneten Entfernungen für jeden Bogen. Dieses Problem wird häufig mit dem Dijkstra-Algorithmus gelöst.

116: Maximaler Spannbaum (Spanning Tree)

Ziel ist es, alle Knoten in einem Netzwerk so zu verbinden, dass die Gesamtstrecke minimal ist. Ein Spannbaum für ein Netzwerk mit n Knoten besteht aus genau n-1 Bögen.

117: Maximaler Durchfluss

Bestimmung der maximal möglichen Strömungsmenge von einer Quelle zu einem Ziel unter Berücksichtigung begrenzter Kapazitäten der Bögen.

118: Bedingungen für den Fluss

Der Fluss in einem Bogen darf nicht negativ sein und die Kapazität nicht überschreiten. Zudem muss die Menge des einfließenden Stroms dem ausfließenden Strom entsprechen.

Logistik und das Traveling Salesman Problem

119: Logistische Funktion: Ziel ist die Bereitstellung von Waren und Dienstleistungen zu angemessenen Bedingungen. Wichtig sind hierbei die Routenplanung und die Dimensionierung von Flotten.

120: Traveling Salesman Problem (TSP): Entwurf einer Route, die alle erforderlichen Punkte genau einmal durchläuft und zum Ausgangspunkt zurückkehrt, sodass die Gesamtdistanz minimal ist.

Ganzzahlige Programmierung (PE)

122: Eigenschaften: Lineare Zielfunktion, lineare Nebenbedingungen und die Bedingung, dass einige Variablen ganzzahlig sein müssen.

123: Simplex-Verfahren: Der Simplex-Algorithmus kann nicht direkt auf die ganzzahlige Programmierung angewendet werden, da der zulässige Bereich eine Menge isolierter Punkte und keine konvexe Menge mehr ist.

124: Typen der ganzzahligen Programmierung

• Rein: Alle Variablen müssen ganzzahlig sein.
• Gemischt: Nur einige Variablen müssen ganzzahlig sein.
• Binär: Variablen können nur die Werte 0 oder 1 annehmen.

125: Rucksack-Problem (Knapsack Problem)

Maximierung des Nutzwerts einer Auswahl von Objekten innerhalb einer begrenzten Kapazität unter Verwendung binärer Variablen.

126: Fixkosten-Problem

Entscheidungsproblem, bei dem Aktivitäten sowohl feste als auch variable Kosten verursachen, sobald ein Bogen genutzt wird.

130: Lösungsmethoden

Zur Lösung von Problemen der ganzzahligen Programmierung wird üblicherweise das Branch-and-Bound-Verfahren (Zweig- und Schrankenverfahren) verwendet.

131: Relaxiertes Problem

Ein lineares Programm, bei dem die Ganzzahligkeitsbedingung vernachlässigt wird. Die Lösung der Relaxierung ist stets optimistisch und liefert ein besseres Ergebnis als das ursprüngliche, restriktivere Problem.