Realität VS Modell
Die Realität beschreibt die Wirklichkeit (im Gegensatz zur Fiktion). Synonyme dafür sind auch Tatsachen (also keine Illusionen). Allerdings unklar ob in Wahrheit immer alles so ist, wie es scheint. Realität im Grunde nur messbar, da Menschen Dinge unterschiedlich wahrnehmen. Die Realität ist kurz gesagt die uns umgebende Wirklichkeit (das, was tatsächlich ist).
Das Modell hingegen ist etwas (meist verkleinert) vereinfacht nachzubilden. Meist dient es zur wissenschaftlichen Erklärung eines Objektes. Somit ist ein Modell ein vereinfachtes Abbild der Wirklichkeit, beispielsweise ein Modell vom den Planeten. Das Modell ist kurz gesagt ein vereinfachtes Abbild der Wirklichkeit.
Deskreptiver VS präskreptiver Lösungsansatz
Der deskriptive Lösungsansatz bezieht sich auf die Darstellung des Inhalts sowie der Struktur der Entscheidungen für oder gegen einen Wissenstransfer. Dieser Ansatz ist beschreibend und erläuternd ohne Bewertung oder Ableitung von Handlungsempfehlungen.
Der präskriptive Lösungsansatz versucht Strategien und Modelle herzuleiten, die Menschen helfen, bessere Entscheidungen zu treffen, indem sie normative (Realität gestalten anstelle sie zu beschreiben) Modelle verwenden. Dieser Lösungsansatz ist also vorschreibend statt bloß feststellend. Meist werden Strukturmerkmale festgelegt und eine These herausgebildet.
Kontinuierliche VS diskrete kombinatorische Optimierung
Kombinatorik handelt von den Möglichkeiten, endlich viele Objekte anzuordnen oder zusammenzustellen. Kombinatorische Optimierung beschäftigt sich mit Lösungsverfahren für Optimierungsprobleme der Form (OP) mit endlich vielen zulässigen Punkten, d. h. mit endlicher Menge M, untersucht x ∈ Z n (TSP). Die Teilmenge, welche durch die Kombinatorik konstruiert wurde, muss gewissen Nebenbedingungen entsprechen sowie bezüglich einer Zielfunktion optimal sein.
Zwischen kontinuierlichen Optimierungsaufgaben und den kombinatorischen Optimierungsaufgaben liegen die ganzzahligen Probleme, die über einen kontinuierlichen Konfigurationsraum definiert sind. Somit sind kombinatorische Optimierungen immer diskret.
Optimalverfahren und Heuristik
Ein Optimalverfahren hat eine eindeutige und bekannte Lösungsstrategie und der Aufwand (zum Beispiel die Rechenzeit) ist vertretbar. Es handelt sich um ein Verfahren (meist Algorithmus) der nach einer endlichen Anzahl an Iterationen oder einer gewissen Zeit eine zulässige sowie auch optimale Lösung hinsichtlich einer Zielfunktion liefert.
Eine Heuristik wird verwendet, wenn kein (effizientes) Optimalverfahren existiert. Heuristiken kommen für Probleme zum Einsatz und sie sind eine Vorgehensweise zur (schnellen) Lösung für allgemeine Probleme. Einfacher gesagt: Daumenregeln aufgrund von subjektiver Erfahrungen. Die Lösungen von Heuristiken sind hinreichend gut und zulässig, es besteht aber weder eine Optimalitäts- noch eine Gütegarantie.
Modell IO, Modellparameter, Entscheidungsvariablen und Konstanten
Die Input Parameter des Modells sind Eingangsgrößen, welche das Modell spezifizieren (zum Beispiel Modellparameter oder eine Startlösung).
Modell Output Parameter sind Informationen, welche sich durch das Lösungsverfahren oder den Algorithmus ergeben (Lösung, Laufzeit, etc.).
Modellparameter sind starre Grundwerte, welche das Modell spezifizieren. Sie sind für eine konkrete Instanz eines Modells fixiert (starr).
Die Entscheidungsvariablen sind durch den Entscheider beeinflussbare Größen, oftmals auch veränderliche Größen durch die Optimierung. Sie definieren somit Handlungsalternativen.
Konstanten sind gleichbleibende Größen, zum Beispiel die Lichtgeschwindigkeit. Für alle Instanzen eines Modells besitzen diese den gleichen Wert.
Unterschied Traveling Salesman Problem (TSP) VS Vehicle Routing Problem (VRP)
Beide Probleme sind NP hart, wobei beim Traveling Salesman Problem der Handlungsreisende zum Startpunkt zurückkehren muss. Es ist also eine (und nur eine) Route vorhanden.
Das Vehicle Routing Problem ist die Generalisierung vom TSP. Das VRP kann auch mehrere Routen (Subtouren) haben, welche alle einen gemeinsamen Knoten als Ausgangspunkt aufweisen müssen (Depot).
Transportproblem VS Zuordnungsproblem
Das Transportproblem ist die Generalisierung des Zuordnungsproblems (Spezialfall). Ein Zuordnungsproblem besitzt genau n Anbieter und n Nachfrager. Dies bedeutet, dass ein Nachfrager von einem Anbieter befriedigt wird (zugeordnet wird). Beim Transportproblem gibt es m Nachfrager und n potenzielle Anbieter. Zudem kann beim Transportproblem ein einzelner Anbieter auch mehrere Nachfrager beliefern.
Unkapazitiertes Warehouse Location Problem VS Transportproblem
Das unkapazitierte Warehouse Location Problem besitzt keine Kapazitätsrestriktionen hinsichtlich des Lagers. Aus mehren möglichen Standorten für ein Lager ist einer oder mehre auszuwählen, sodass die Summe aus Fixkosten (für das Lager) und der Transportkosten (variable Kosten) von den errichteten Lagern zu den Nachfragern minimiert werden.
Im Gegensatz zum Transportproblem stehen die Lagerpositionen bereits im Vorfeld fest und es unterliegt keiner Kapazitätsrestriktionen.
Set Covering VS Set Partitioning Problem
Bei beiden Problemen gibt es eine endliche Menge an Instanzen, sowie Teilmengen von den Instanzen. Das Partitioning Problem ist ein Spezialfall des Set Covering (Überdeckung) Problems. Deshalb ist der Zielfunktionswert des Partitioning Problems gleich oder schlechter als der Zielfunktionswert des Set Covering Problems.
Das Überdeckungsproblem wählt aus den vorhandenen Teilmengen jene Teilmengen aus, sodass jedes Element aus I zumindest in einer Teilmenge enthalten ist.
Beim Partitionierungs Problem werden die Teilmengen so ausgewählt, dass jedes Element aus I in genau einer Teilmenge enthalten ist und lediglich einmal vorkommt.
Beispiel eines Add Algorithmus
Zurodnungsproblem
Das Überdeckungs- bzw. Partitionsproblem kann mit LiPS folgendermaßen eingegeben werden.
Der dazugehörige Programmcode zum kopieren für die Überdeckung:
Min: 35*M1 + 30*M2 + 30*M3 + 40*M4 + 35*M5 + 50*M6 + 50*M7 + 40*M8 + 50*M9 + 35*M10; Job1: M3 + M4 + M6 + M7 + M8 >= 1; Job2: M1 + M2 + M4 + M5 + M7 + M10 >= 1; Job3: M2 + M4 + M5 + M6 + M9 >= 1; Job4: M1 + M2 + M8 + M10 >= 1; Job5: M4 + M7 + M9 >= 1; Job6: M1 + M2 + M5 + M6 + M7 + M8 + M10 >= 1; Job7: M1 + M3 + M8 + M9 >= 1; Job8: M2 + M5 + M7 + M9 >= 1; Job9: M1 + M3 + M7 >= 1; int M1, M2, M3, M4, M5, M6, M7, M8, M9, M10;
Der dazugehörige Programmcode zum kopieren für die Partition:
Min: 35*M1 + 30*M2 + 30*M3 + 40*M4 + 35*M5 + 50*M6 + 50*M7 + 40*M8 + 50*M9 + 35*M10; Job1: M3 + M4 + M6 + M7 + M8 = 1; Job2: M1 + M2 + M4 + M5 + M7 + M10 = 1; Job3: M2 + M4 + M5 + M6 + M9 = 1; Job4: M1 + M2 + M8 + M10 = 1; Job5: M4 + M7 + M9 = 1; Job6: M1 + M2 + M5 + M6 + M7 + M8 + M10 = 1; Job7: M1 + M3 + M8 + M9 = 1; Job8: M2 + M5 + M7 + M9 = 1; Job9: M1 + M3 + M7 = 1; int M1, M2, M3, M4, M5, M6, M7, M8, M9, M10;
Downloads
Die letzten beiden Beispiele sind auch als Excel Dokument für den Download verfügbar.
Zum letzen Beispiel gibt es auch LiPS Modelle.
Die Beispiele mit der kontinuierlichen und diskreten kombinatorischen Optimierung sind echt gut. Es zeigt, wie vielfältig Optimierungsprobleme sein können. Danke für die Infos!
Die Erklärungen zu den Modellparametern und Entscheidungsvariablen sind wirklich gut nachvollziehbar. Ich habe jetzt ein besseres Verständnis dafür, wie Modelle aufgebaut sind. Danke für den Beitrag!
Echt spannend! Ich habe noch nie über den deskriptiven und präskriptiven Lösungsansatz gehört. Das macht schon Sinn, dass man unterschiedliche Herangehensweisen hat. Weiter so mit den Erklärungen!
Toller Artikel! Sehr interessant zu lesen und gut erklärt. Ich wusste gar nicht, dass die Realität und Modelle so viele Unterschiede haben. Danke für die Information!
Die Unterschiede zwischen dem Traveling Salesman Problem und dem Vehicle Routing Problem sind sehr klar dargestellt. Ich habe jetzt einen besseren Überblick über diese Optimierungsprobleme. Vielen Dank!
Es ist beeindruckend, wie viele verschiedene Ansätze es gibt, um Probleme zu lösen. Ich kannte bisher nur Optimalverfahren, aber jetzt weiß ich auch mehr über Heuristik. Sehr lehrreich, danke!