Operations Research

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

determin. : Folgezustand steht fest 

stochastisch: Folgezustand ist zufallsabhängig 

Ein Graph wird bipartiter genannt, wenn seine Knotenmengen in zwei disjunkte Teilmengen zerlegbar sind 

Der Ort, an dem Auslieferungsfahrten, Sammelfahrten etc. beginnen 

Die Menge aller Kunden , die auf einer und derselben, in einem Depot beginnenden und in einem Depot endenden, Fahrt bedient werden 

Die Reihenfolge, in der die Kunden einer Tour zu bedienen sind 

eine Menge von Touren und dazugehörige Routen, die alle Bedingungen des betrachteten Problems erfüllen 

- alle Längen der Kanten sind nichtnegativ 

- Zyklen sind zulässig, aber Zyklen negativer Länge dürfen nicht auftreten, da keine negativ bewerten Kanten im Graphen vorkommen dürfen 

• Menge A der Knoten, zu denen bereits kürzester Weg von der Quelle s aus bekannt ist 
• Menge B der Knoten, zu ddenen Wege von s aus bekannt sind, jedoch nicht sicher ist, ob diese minimal sind 
• Menge C der Knoten, zu denen noch keine Wege von s aus bekannt sind 

• Kanten werden  in der Reihenfolge nichtfallender Gewichte gefärbt 
• Rot: eine Kante, deren beiden Endknoten im gleichen Baum liegen, wird rot gefärbt 
• Blau: alle anderen 

• ausgehend von einem festen Knoten s wird ein einziger blaugefärbter Baum T schrittweise aufgebaut 
• ist T dieser blaugefärbte Baum, so färbt der nächste Schritt eine Kante mit minimalen Gewicht blau, die T mit einem Knoten außerhalb von T verbindet 
• bei jedem Schritt wird einer der Knoten der Grenze zu den T Knoten hinzugefügt, der von T aus mit einer Knate minimalen Gewichtes erreichbar ist 
• das Verfahren endet, wenn alle Knoten in T sind 

• ich suche mir die Kanten mit dem mininalen Gesichten : 1,2,3, 
• diese markiere ich rot , damit sind sie besucht 
• es darf kein Zyklus entstehen 
• es müssen alle Orte besucht werden und es muss eine Verbindung zwischen den Punkten bestehen 

• Unterschied Kruskal: wir haben einen festen Startpunkt 
• von diesem Startpunkt aus, suchen wir die mininalen Kanten 
• immer die minimal gewichteten Kanten von einem der besuchten Orte suchen und markieren 

• Fixkosten sind Kosten, die in konstanter Höhe anfallen, unabhängig davon, welche Menge von einem Produkt verbraucht wird 
• Kosten können auch andere Formen annehmen z,B. Tage, Stunden, Material 

• um Würstchen zu grillen, muss einmalig in einen Grill investiert werden 
• um eine Wand zu streichen, braucht man Pinsel &  Farbe 

• Einführen einer logischen 0/1 Variable , die genau dann 1 wird wenn Fixkosten anfallen 

Simulation ist

• der Prozess der Erstellung eines Modells eines realen Systems 
• und das Experimentieren mit diesem Modell 

mit der Absicht 

• entweder das Systemverhalten zu verstehen 
• oder verschiedenen Strategien für die Systemoperation zu entwickeln 

• permanent : bleibt im System zB Kasse 
• Temporär : bewegt sich durch das System : zB Kunde 

Eigenschaften eines Entity zB Anzahl der gekauften Artikel

Globale Eigenschaften des Systems zB Anzahl der verfügbaren Kassierer 

Einzelne Zustandsänderung  zB Beginn der Bearbeitung 

Perioden, in denen ein bestimmter Vorgang zu einer konstanten Ausprägung des Attributs führen 

• Schwachstellen im Betrieb identifizieren 
• Kennzahlen zum Bewerten des Systems 
• Lösungsszenarien entwickeln, die Kennzahlen verbessern 

Properties: statische Eigenschaften eines Objektes 

States: dynamische Eigenschaften eines Objektes 

• wenn ein hoch komplexes System untersucht werden soll, für das eine analytische Beschreibung nicht möglich ist 
• Experimente am Realsystem zu teuer/zu gefährlich/unmöglich sind 
• das Realsystem nicht direkt beobachtbar ist 
• Alternativen eines Systems, das noch nicht existiert untersucht werden sollen 

VWL: Konjunkturzyklen, Entwicklung des Rentenniveaus

Medizin: Blutkreislauf der Menschen, Bewegungsabläufe 

Informatik: Simulation von neuronalen Netzen 

Verkehr: Kreisverkehr oder Ampel 

Simulation von Naturkastastrophen