• Home
  • Operations Research – Die Unternehmensforschung

Operations Research – Die Unternehmensforschung

Operations Research

Operations Research – Die Unternehmensforschung

Operations Research oder deutsch Operationsforschung, Unternehmensforschung, beschäftigt sich als Teilgebiet der Mathematik mit der mathematischen Optimierung ganzer Unternehmens- oder Produktionsprozesse.

Einleitung in die Unternehmensforschung (Operations Research)

Ausgehend vom mathematischen Gedankengut werden die Unternehmensprozesse analysiert und in einem mathematischen Modell bestehend aus einem System von Nebenbedingungen und einer entsprechenden Zielfunktion erfasst. Die Variablengrößen, deren Verbesserung oder Optimierung angestrebt werden sollen, werden mittels geeigneter mathematischer Verfahren bis zu den optimalsten Werten als Maximal- oder Minimalwert variiert. Die Operationsforschung dient mit ihren Modellen und Methoden der Entscheidungsfindung innerhalb der Unternehmen. Operations Research als Ablauf- oder Planungsforschung findet heute Anwendung in vielen Teilen der Ingenieur- und Wirtschaftswissenschaften.

Welche Teilgebiete des Operations Research gibt es?

Die mathematische Optimierung ist das wichtigste Teilgebiet der Operationsforschung. Eingeschlossen werden hierbei Kenntnisse und Erfahrungen aus der Matrizenrechnung, Stochastik, Vektoranalysis und Grafentheorie. Die Modellbildung des unternehmerischen Fallbeispiels eines Betriebes setzt das reale ökonomisch spezielle Problem in ein mathematisches Modell um, dass häufig aus einem System der Restriktionen und der zu optimierenden Zielfunktion besteht. Operations Research wird je nach Aufgabenstellung und Betrachtungsweise in vielen anderen Teilgebieten analysiert. Dazu gehören:

• Lineare Optimierung
• Ganzzahlige Optimierung (diskrete Mathematik)
• Ganzzahlige lineare Optimierung und Kombinatorische Optimierung
• Parametrische Optimierung
• Dynamische Optimierung
• Nichtlineare Optimierung
• Kontrolltheorie
• Heuristische Verfahren
• Entscheidungstheorie
• Spieltheorie
• Grafentheorie
• Netzplantechnik
• Simulation
• Warteschlangentheorie
• Transportoptimierung
• etc.

Die Lineare Optimierung als das Hauptverfahren optimiert wie bereits erwähnt die Zielfunktion und sucht entsprechend der Vorgaben der Nebenbedingungen als Gleichungs- oder Ungleichungssystem eine zulässige Basis- und Optimallösung in der Menge der zulässigen Lösungen. Das mathematische Modell liegt oft in folgender Standardform vor:

Max { c^T x | Ax <= b, x >= 0}

Die geometrische Interpretation zeigt sich für jede Restriktion als Teilung deren Hyperebene im n-dimensionalen Raum in jeweilige Halbräume. Der Durchschnitt dieser Halbräume aller Restriktionen bildet die zulässige Lösungsmenge, die im trivialsten Fall konvex sein sollte, das heißt bildlich, der Lösungsraum wird von den Restriktionen vollständig umschlossen. Die Optimallösung wird durch Verschiebung der Zielfunktion in Richtung des Vektors c mittels mathematischer Verfahren wie die der Simplexmethode solange verbessert, bis die Zielfunktion in einem Punkt die Lösungsmenge berührt. Dann existiert eine einzige Optimallösung. Liegt die Zielfunktion auf einer Restriktionsungleichung, dann existieren viele Lösungen entlang der Berührungspunkte.

Äquivalente Umformungen können Operationen in diese Standardform bringen, falls diese nicht in der Standardform bereits vorliegen z. B. bei:

• Minimierungsproblemen, wobei der Zielfunktionsvektor c mit (-1) multipliziert wird
• >= statt <= Bedingungen: Multiplikation der Ungleichungen mit (-1) • = Bedingungen statt <= Bedingungen: a[i]x = b[i] wird durch a[i]x <= b[i] und –a[i]x <= -b[i] ersetzt • Variablen ohne Nichtnegativitätsbedingung: statt x wird x` - x`` mit x`, x`` >= 0 verwendet

Lineare Modelle, die nicht in Standardform vorliegen, können durch folgende Umformungsvorschriften für eine Dualisierung das Problem dennoch mittels geeigneter mathematischer Verfahren lösen. Zunächst sind die Problematiken in die geeignete Ausgangsform zu bringen, um Lösungsalgorithmen anzuwenden.

Primales LP
Duales LP

Max {c^T x : Ax <= b, x >= 0}
Min {y^T b : y^T A >= c^T, y >= 0}

Max {c^T x : Ax = b, x >= 0}
Min {y^T b : y^T A >= c^T}

Max {c^T x : Ax <= b} Min {y^T b : y^T A = c^T, y >= 0}

Liegt das primale Problem als Minimierungsproblem vor, gilt folgendes:

Primales LP
Duales LP

Min {c^T x : Ax >= b, x >= 0}
Max {y^T b : y^T A <= c^T, y >= 0}

Min {c^T x : Ax = b, x >= 0}
Max {y^T b : y^T A <= c^T} Min {c^T x : Ax >= b}
Max {y^T b : y^T A = c^T, y >= 0}

Im Allgemeinen kann man für die Umformung des primalen in das duale Problem folgendes festhalten:

Primales LP
Duales LP

nicht negative Variable
Ungleichung

nicht Vorzeichen beschränkte Variable
Gleichung

Ungleichung
nicht negative Variable

Gleichung
nicht Vorzeichen beschränkte Variable

Die kombinatorische Optimierung als Zweig der diskreten Mathematik soll aus einer großen Menge diskreter Elemente eine Teilmenge konstruieren, die vorgegebenen Nebenbedingungen genügt und deren Kostenfunktion optimal sein soll. Bekannte Problematiken wie das Problem des Handlungsreisenden, des Spannbaums, das Rucksackproblem, das Egalisieren verschieden gewichtiger Produkte bei Sortierung oder Verpackung im Bereich der Betriebswirtschaft oder das Behälterproblem sind mit der kombinatorischen Optimierung behandelbar.

Der Unterschied der ganzzahligen linearen Optimierung zur linearen Optimierung zeigt sich in der Voraussetzung, dass einige oder alle Variablen nur ganzzahlige Werte annehmen dürfen. Besonders in den letzten Jahren des vergangenen Jahrhunderts wurden Fortschritte in der Entwicklung von Lösungsalgorithmen in der Produktion, Planung von Telekommunikations- und Nahverkehrsnetzen oder in der Tourenplanung erzielt.

In der dynamischen Optimierung besteht das Optimierungsproblem zunächst aus vielen kleineren gleichartigen Teilproblemen, deren direkte Lösungen direkt berechnet werden. Diese werden zur Lösung des nächst größeren Problems zusammengesetzt. Dieses Verfahren wird solange wiederholt, bis die Endlösung des Gesamtproblems gefunden wurde. Die dynamische Optimierung findet besonders in der Regelungstheorie Anwendung.

Bei der nichtlinearen Optimierung sind die Zielfunktion oder die Restriktionsfunktionen nicht affin. Das kann für die Zielfunktion oder Restriktionen bzw. für beide zutreffen. Zielfunktion, Restriktionen oder beide seien dabei wenigstens einmal stetig differenzierbar. Das mathematische Problem formuliert sich dann wie folgt:

P : f(x) soll extremiert werden, wobei x Element aus dem n-dim. reellen Raum R ist und somit von n Einflussfaktoren abhängt

f : x ist Element aus S, wobei S Teilmenge von D Teilmenge, die gleich dem n-dim R sein kann -> werden auf den eindimensionalen reellen Raum R abgebildet. Nachfolgend gilt für S

S : wenn der Vektor x Element aus D ist:: so folgen

die geltenden Restriktionen g[i](x) <= 0, für alle 1 <= i <= m, g[k](x) = 0 , für alle 1 <= k <= l Es kann also sein, dass die Zielfunktion nicht eine Gerade oder Ebene ist, sondern zum Beispiel eine Parabel oder ein Paraboloid. Dann wäre das nichtlineare Optimierungsproblem z. B. ein Problem der quadratischen Optimierung Bei den Teilgebieten Kontrolltheorie, Heuristische Verfahren, Entscheidungstheorie, Spieltheorie, Grafentheorie, Netzplantechnik, Simulation und Warteschlangentheorie verweise ich bei speziellem oder intensiverem Interesse wie auch bei allen anderen Teilgebieten auf einschlägige Literatur aus dem Internet. Ein besonders hervorzuhebendes Teilgebiet ist die Transportoptimierung, die sehr oft in Wirtschaft und Industrie anzutreffen ist. Dieses Problem aus dem Operations Research beschäftigt sich mit dem optimalen Transport von Objekten von mehreren Angebotsorten zu verschiedenen Nachfrageorten. Die Transporte sollen kostenoptimal, zeitoptimal oder streckenoptimal durchgeführt werden. Beim Standardfall einer linearen Kostenfunktion kann mittels der Linearen Optimierung und dem Simplexverfahren eine Optimallösung gefunden werden. Das klassische Transportproblem, das keine Kapazitätsbeschränkungen auf den Transportwegen besitzt, gilt als Spezialfall. Das kapazitierte Transportproblem legt für Wege Mindest- oder Höchsttransportmengen fest. Beim Umladeproblem gibt es zusätzlich neben den Angebots- und Nachfrageorten noch Umladeorte. Als Sonderfall sei noch das Zuordnungsproblem erwähnt, bei dem nur eine Einheit je Ort angeboten oder nachgefragt wird. Die mathematische Formulierung wird linear wie folgt vorgenommen: Minimiere Zielfunktion z = Summe(i=1,…,m)Summe(j=1….n)c[i,j]x[i,j] unter den Nebenbedingungen 1. für die Angebotsorte: Summe(j=1,..,m)x[i,j] = a[i] für alle i, 2. für die Nachfrageorte: Summe(i=1,…,m)x[i,j] = b[j] für alle j, 3. die Nichtnegativitätsbedingung: x[i,j] >= 0 für alle i, für alle j,
3. Anwendungsgebiete

Für die lineare Optimierung können viele Praxisbeispiele aufgezählt werden.

* Beispiel Produktionsplanung:

Ein Unternehmen stellt mit bekannten Kosten eine Anzahl von Produkten her, wofür es beschränkte Ressourcen wie Produktionskapazität, Rohmaterial oder Arbeitszeit benötigt. Ziel ist nun, das Modell des Produktionsprogramms so aufzustellen, dass bei einem gewissen Produktionsziel der Gewinn des Unternehmens maximiert werden kann. Auch in der Produktionsplanung ist es mitunter erforderlich, die Variablen ganzzahlig vorauszusetzen, zum Beispiel bei Stückzahlen. 20 Flugzeuge, 100 Stühle, es machen Werte wie der Bau von 0,5 Flugzeugen keinen Sinn.

* Beispiel Mischungsprobleme:

Ein besonderes Beispiel ist das Diätproblem. Die Ressourcen untergliedern sich in Rohmaterialien wie Hafer, Schweinefleisch, Sonnenblumenöl etc. aufgeführt nach ihrem Gehalt an Nährstoffen wie Eiweiß, Fett oder Vitamine entsprechend einer Gewichtseinheit. Ziel ist nun, unter Vorgabe von Mindest- und Höchstgrenzen einzelner Nährwerte ein oder mehrere Endprodukte mit minimalen Kosten zu mischen.

* Beispiel Routing in Telekommunikationsnetzen:

Als klassisches Gebiet gilt in Verbindung mit Kapazitätsplanung die Bestimmung eines Routings für Anforderungen in Telekommunikations- oder Verkehrsnetzen. Verkehrsflüsse sollen durch ein Netz unter Beachtung aller Forderungen und ohne Verletzung der Kapazitätsbedingungen geroutet werden.

* Beispiel Spieltheorie:

Ziel ist hierbei mithilfe von Wahrscheinlichkeitsverteilungen, optimal gemischte Strategien zu ermitteln und Entscheidungssituationen zu simulieren. Es dient vor allem dazu, rationales Entscheidungsverhalten in sozialen Konfliktsituationen abzuleiten. Es ist zwischen nicht-kooperativer und kooperativer Spieltheorie zu unterscheiden. Bekannte Probleme dieser Art sind das Gefangenendilemma, Spiel mit dem Untergang, Hirschjagd oder Kampf der Geschlechter.

* Beispiel Auktionsmodell:

Eine Anzahl von Kunstgegenständen oder Waren ist auf die gleiche Anzahl von Käufern zu verteilen. Jeder Käufer hat als Bedingung seine eigenen Preisvorstellungen. Das Ziel der Auktion beläuft sich darauf, einen maximalen Auktionsgewinn zu erreichen. Zur Lösung dieses Problems bietet sich die Ungarische Methode an.

* Beispiel Jobproblem:

Eine Anzahl von Arbeitsaufträgen ist auf die gleiche Anzahl Maschinen oder Arbeitern aufzuteilen. Eine Bewertung der Aufträge erfolgt nach Kosten oder nach Eignung eines Arbeiters für den jeweiligen Auftrag. Auch hier ist die Ungarische Methode anzuwenden.

* Beispiele der optimalen Wegeplanung eines Bohrers auf einer Leiterplatte, eine möglichst günstige Routenplanung oder eine kostenoptimale Belegung von Maschinen sind Anwendungsgebiete der Kombinatorischen Optimierung.

* Beispiel aus dem Öffentlichen Nahverkehr:

Die Dienst- und Umlaufplanung verteilt Busse und Bahnen entsprechend der Fahrpläne bestückt mit dem jeweiligen Fahrer auf die einzelnen Linien. In diesem Beispiel der ganzzahligen linearen Optimierung kommen binäre Entscheidungsvariablen zum Einsatz. Fährt ein Zug oder nicht, also entweder 1 oder 0.

* Beispiel Rucksackproblem:

Beim Rucksackproblem handelt es sich um ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten mit jeweiligen Gewichten und Nutzwerten soll eine Teilmenge gewählt werden. Bedingung ist, dass das Gesamtgewicht eine vorgegebene obere Schranke einhält. Unter diesen Voraussetzungen soll der Nutzwert der gewählten Objekte zum Maximum werden. Sind die Gewichte ganzzahlig, kann das Problem mittel dynamischer Programmierung / Optimierung gelöst werden.

* Beispiel: Die Reduzierung des Gewichts eines Bauteils unter den Bedingungen der Einschränkung des Bauraums oder bestehender Obergrenzen für Verformungen bei bekannten Lasten ist ein Problem aus der nichtlinearen Optimierung.

* Beispiel: Nichtlineare Einflüsse und Einschränkungen von Parametern, z. B. die Unzulässigkeit von negativen Werten, führen zu nichtlinearen Problemstellungen.

* Viele Transportprobleme existieren aus der Industrie und Wirtschaft.

Welche Lösungsverfahren werden verwendet?

Für die Lineare Optimierung finden vorwiegend folgende Verfahren Verwendung:

* Das Simplex-Verfahren:

Durch die Schnittmenge der Hyperebenen entsteht ein so genanntes konvexes Polyeder, das durch das Simplexverfahren von einer ersten Basislösung zur Optimallösung in endlich vielen Schritten durchlaufen wird. Unter der Voraussetzung, dass die Restriktionsmatrix wenige Koeffizienten verschieden von Null besitzt, erlangt das Verfahren in angemessener Zeit seinen Optimalwert.

* Das Innere-Punkte-Verfahren:

Dieses Verfahren nähert sich einer optimalen Ecke durch das Innere des konvexen Lösungspolyeders. Sie sind gekennzeichnet von polynomialer Komplexität und schnellerer Konvergenz. Das Innere-Punkte-Verfahren wird besonders für die Lösung linearer Probleme Min {c^T x : Ax = b, x >= 0} verwendet. Dazu dienen Logarithmische Barrieren. Das Barriereproblem kann dann mittels Lagrangschen Multiplikatorensatz für Lösung nichtlinearer Gleichungssystem gelöst werden. Das Gleichungssystem, bestehend aus dem primären, dem dualen Problem mit geeigneten Schlupfvariablen und dem komplementären Schlupf wird mit dem Newton-Verfahren gelöst. Nach jeder Iteration wird der Parameter ” griechisch mü” reduziert mit dem Ziel, dass das Barriereproblem zum Ursprungsproblem konvergiert.

* Die Ellipsoidmethode:

Bei diesem Verfahren wird ein Ellipsoid definiert, der alle Ecken des Polyeders (konvexen Lösungsraums) enthält. Liegt der Mittelpunkt des Ellipsoids im Polyeder, ist eine Lösung gefunden worden. Andernfalls bestimmt man im Halbellipsoid, der das Polyeder enthält, ein kleineres Ellipsoid um den Polyeder. Nach einer Anzahl derartiger Verfahrensschritte wurde entweder ein Punkt gefunden oder der Polyeder ist leer.

* Die Ungarische Methode:

Die Ungarische Methode ist eine angepasste primal-dual Lösungsform. Zwischen zwei Gruppen von Objekten, Quellen und Zielen, sind eineindeutige Zuordnungen herzustellen. Also jeder Quelle wird höchstens genau ein Ziel und umgekehrt zugeordnet. Das Ziel ist es, die Summe der Zuordnungen zu minimieren oder zu maximieren je nach Problemstellung.

Bei der linearen ganzzahligen Optimierung finden das Schnittebenenverfahren, Branch-and-Bound oder Branch-and-Cut die entsprechenden Optimallösungen, wobei zunächst mit dem Simplexalgorithmus unter Nichtbeachtung der Ganzzahligkeit eine optimale Lösung gesucht wird. Beim Schnittebenenverfahren werden danach unter Hinzufügung weiterer Restriktionen die im ersten Verfahren gefundenen Schranken verschärft und der Simplexalgorithmus bis zur ganzzahligen Optimallösung wiederholt.

Die dynamische Programmierung wird als Methode zum Lösen dynamischer Optimierungsprobleme eingesetzt. Beispiele für die Anwendung dieses Prinzips sind der CYK-Algorithmus, der Earley-Algorithmus, der Needleman-Wunsch-Algorithmus, der Smith-Waterman-Algorithmus, der Viterbi-Algorithmus, der Algorithmus von Floyd und Warshall oder der Pseudopolynomielle Algorithmus z. B. für die Lösung des Rucksackproblems.

Bei der nichtlinearen Optimierung sind Verfahren bekannt, die hier kurz informativ etwas näher erläutert werden, damit die Anwendung im mathematischen Programm, das am Ende des Artikels vorgestellt wird, nachvollziehbar ist. Das nichtlineare Problem wird mithilfe der nachfolgenden Verfahren auf die Optimierung von Hilfsfunktionen ohne eine Nebenbedingung zurückgeführt.

* Lagrange-Multiplikatoren:

Die Nebenbedingungen werden mit reellen Faktoren, den Lagrange-Multiplikatoren, multipliziert. Diese werden dann in die Zielfunktion eingebaut. Bei positiven Faktoren wird die Verletzung der Nebenbedingungen bestraft. Man nennt diese Hilfsfunktion Lagrange-Funktion.

* Barrierefunktion:

Die Nebenbdingungen werden mit Barrierefunktionen dargestellt. Bei Annäherung an die Definitionsbereichsgrenze werden diese positiv oder wachsen auf der Grenze ins Unendliche. Die Barrierefunktionen, multipliziert mit einem Parameter und eingebaut in die Zielfunktion, werden bei Annäherung an die Nebenbedingungen bestraft.

* Straffunktion:

Die Straffunktionen werden wie die Barrierefunktionen eingesetzt. Diese Straffunktionen verschwinden im Definitionsbereich, sind aber bei Verletzung der Nebenbedingungen positiv. In diesem Fall muss die Zulässigkeit der Lösung überprüft werden.

* Erweiterte Lagrange Methode:

Diese Methode stellt eine Kombination der Lagrange-Multiplikatoren und der Strafmethode dar. Anhand der Verletzung der Nebenbedingung wird der Lagrange-Multiplikator iterativ bestimmt.

* Trivial:

Aktive Nebenbedingungen werden zur Eliminierung von Variablen eingesetzt, das heißt, sie erhalten Werte zugeordnet, wo die Verletzung der Nebenbedingungen nicht mehr möglich ist.

Für die Transportoptimierung seien folgende Verfahren hier kurz genannt:

* Exakte Verfahren: Simplex, Netzwerk-Simplex

* Eröffnungsheuristiken:

Dazu gehören die Verfahren der Nord-West-Ecken-Regel, das Matrixminimumverfahren sowie die Vogelsche Approximationsmethode.

* Verbesserungsverfahren:

Stepping-Stone-Methode (Sprungbrettmethode), Modi-Methode (Potenzialverfahren)

Diese Verfahren sollen zu einer Verbesserung der Kostenfunktion beitragen.

Fazit

In den Anwendungsgebieten wurden viele Beispiele aufgeführt, wo ein Unternehmen sich einordnen kann. Jeder Mathematiker könnte ein Unternehmen auf mögliche Optimierungen von Prozessen, Kosten, Ressourcen o. a. Problematiken durchforsten, die es zu verbessern gilt. Die Vorteile eines Unternehmens, das kostengünstig und wirtschaftlich arbeitet, liegen auf der Hand. Die sachkundige Modellierung des Problems wäre die Voraussetzung für eine ebenfalls kostengünstige oder sogar kostenfreie Anwendung bereits bestehender Open Source Tools wie die frei verfügbare OR Software COIN-OR, GNU Linear Programming Kit oder MatCont. Mathematischen Optimierung mit MATLAB, Mathworks oder der Solver von Excel seien an dieser Stelle zu nennen. Beim Transportproblem kann zunächst auf die Potenzialmethode verwiesen werden. Aber auch mathematische oder wirtschaftswissenschaftliche Fakultäten der Universitäten wie die der Fernuni Hagen beschäftigen sich mit Operationsforschung speziell dem Rundreiseproblem, Färbungsproblem, Transportproblem, Warteschlangenproblem oder Grafenalgorithmen.

Ein Unternehmen, das seine Betriebsabläufe optimieren, Kosten sparen, Produktionskosten senken, Lieferzeiten optimieren und somit optimal wirtschaftlich arbeiten will, wird die durch Optimierung freigewordenen Ressourcen für Forschung und Entwicklung, Expansion seines Unternehmens oder Qualifizierung der Mitarbeiter einsetzen, damit den Gewinn steigern und den Bestand seines Unternehmens in einer globalen Welt festigen können.