Operations Research

gerichteter Graph G, wobei N die Menge der Knoten und A die Menge der Kanten darstellt 

Voraussetzungen: Netzwerk ohne untere Schranken und alle Kosten auf den Kanten nichtnegativ --> der Nullfluss ist ein kostenminimaler Fluss auf dem Netzwerk der Größe 0

Idee : Ausgehend vom Nullfluss --> versuche den Fluss sukzessive über kürzeste Wege von s nach t des Restflussnetzwerkes zu vergrößern bis ein kostenminimaler Fluss der gewünschten Größte entsteht 

• Spezialfall des Transshipment Modells 
• eine Quelle 
• eine Senke 
• alle anderen Knoten sind Umladeknoten 

Bsp: Verkehrsfluss im Stadtnetzwerk, Datenpakete im Telekommunikationsnetzwerk

1. Route- First Cluster second: geeignet  für kantenorientierte Tourenplanungsprobleme 

2. Cluster-first route second: geeignet für knotenorientierte Tourenplanungsprobleme (Sweep verfahren) 

- geeginet für knotenorientierte Probleme 

1. Konsutrktionsverfahren : Savings Verfahren 

2- 2 -opt und 3-opt Verfahren sowie Verallgemeinerungen 

1. Eröffnungsverfahren: Bilde eine gute zulässige Lösung (Sweep oder Savings) 

2. Verbesserungsverfahren : Verbessere diese Tour iterativ (2-opt) 

• gegeben : symmetrische Entfernungsmatrix 
• Anfangslösung : Pendeltour zu jedem Kunden und zurück, Anfangslösung wird schrittweise verbessert 
• jeweils zwei Touren werden zusammengelegt, soweit Zeit-/Kapazitätsrestriktionen nicht verletzt werden 
• Endkunden sind die ersten und letzten Kunden 
• zwei Routen werden durch Übergang von einem Endkunden der ersten Tour zu einem Endkunden der zweiten Tour verknüpft 

• Graph oder Balkendiagramm mit einem Balken für jede Projektaktivität
• hierbei wird der Zeitverbrauch der einzelnen Aktivitäten dargestellt 

• es sind gegeben : Vorgänge und Ereignisse & Reihenfolgebeziehungen zwischen Vorgängen/Ereignissen 
• Vorgänge werden als Knoten dargestellt 
• Knoten werden durch Rechtecke symbolisiert und Reihenfolgebeziehungen durch Pfeile veranschaulicht 

• Vorgänge werden als Knoten dargestellt 
• Knoten werden durch Rechtecke symbolisiert und Reihenfolgebeziehungen durch Pfeile veranschaulicht 
•  

• Heuristisches Verbesserungsverfahren, das durch vertauschen von 2 Kanten gegen 2 andere Kanten in einer zuvor bestimmten Tour versucht diese zu verbessern 
• Voraussetzungen : Kostenmatrix eines ungerichteten, bewerteten Graphen mit n Knoten UND eine Tour mit Route 

• wähle 2 Knoten die nicht aufeinander folgen und weit vom Depot entfernt sind 
• Bestimmt die jeweiligen Nachfolger dieser Knotenpunkte 
• Verbinde die gefundenen Knotenpunkte 
• Löse die Beziehung von den Knotepunkten zu ihren Nachfolgern 
• verbinde beide Nachfolger miteinander ? 
• Ist gefundene Lösung besser ? 

• Savings = die Strecke, die gespart werden kann, wenn zwei Touren über die Enkunden i und j verbunden sind 
• sij = doi + doj - dij 
• sij ist umso größer, je näher i und j beinander liegen und je weiter sie vom Depot entfernt sind 
• verbinde Touren miteinander, da wo das Saving am größten ist 

• Forschung und Entwicklung 
• Bauprojekte (Schiffe, Kraftwerke, Fabriken) 
• Kampagnen (Werbekampagnen) 
• Planung von Großveranstaltungen 

• ein gewichteter Graph mit Kanten-und/oder Knotenbewertungen 
• enthält die vom Planer als wesentlich erachteten Elemente und deren Reihenfolgebeziehungen 
• er gibt die Struktur des Projektes wieder 
• Hat ein Startereignis (Projektanfang) und ein Endergebnis (Projektende) 

Koeffizient der Variable in der modifizierten Zielfunktion (Simplex) bei der optimalen Lösung

reduzierte Kosten der Schlupfvariable , die zur Restriktion gehört 

Der Grenzwert (reduzierte Kosten) einer strukturellen Nichtbasisvariable stellt die marginale Auswirkung im Zielfunktionswert dar, wenn der Wert der Variable um eine Einheit erhöht wird. Wenn der Grenzertrag für eine Variable negativ (bei einer Max-Zielfunktion) ist, verschlechtert sich der Zielfunktionswert bei erzwungener Erhöhung des Wertes dieser Variablen marginal 

Ein Schattenpreis einer Restriktion gibt an, wie viel sich der Zeilfunktionswert ändert, wenn die Kapazität der entsprechenden Ressource um eine Einheit erhöht wird. 

Kette ist eine Folge von Kanten aus E bzw. aus A eines Graphen G, die in der gegebenen Reihefolge durch Knoten verbunden sind 

Ein Weg ist in einem gerichteten Graph eine Kette, wobei die Pfeile nur in eine Richtung zeigen 

• in einem ungerichteten Graphen heißt eine Kette Kreis, wenn gilt io = it 
• in einem gerichteten Graphen heißt ein Weg mit io=it Zyklus 

• Baum: zusammenhängender, ungerichteter, kreisloser Graph 
• Wald: ungerichteter kreisloser Graph, seine Kompenenten sind Bäume 

Sei G ein zusammenhängender ungerichteter Graph, so nennt man einen kreisfreien Teilgraphen T von G einen spannenden Baum 

- der Prozess der Erstellung eines Modells eines realen Systems 

- und das Experimentieren mit diesem Modell 

• VWL: Konjunkturzyklen 
• Medizin: Blutkreislauf des Menschen 
• Informatik: Entwurf von Rechnernetzen 
• Verkehr : Planung von Verkehrsknotenpunkten (Kreuzung oder Ampel? ) 
• Simulation von Naturkatastrophen 

• Eingagswerte können beliebig geändert werden 
• es sind Tests über Systeme möglich, die noch nicht existieren 
• Zeitkompression 
• Sensitivitätsanalyse durch Manipulation der Eingangsgrößen 
• Grafische Darstellung und Animation möglich 

• hoher Zeitaufwand zur Modellentwicklung 
• Datensammlung schwierig und zeitaufwendig 
• Simulationsergebnisse schwer zu interpretieren 
• bei stochastischen Elementen nur repräsentativ wenn Stichprobe repräsentativ 

eine Gruppe oder Menge von Objekten, die in Form einer regelmäßigen Interaktion oder Abhängigkeit vereinigt sind, um eine

bestimmte Funktion durchzuführen