Operations Research: Eine Einführung

1.1 Entwicklung und Begriff des Operations Research Die rasche technische und wirtschaftliche Entwicklung im Laufe dieses Jahrhun­ derts brachte in allen Unternehmensbereichen komplexe Probleme mit sich, die al­ lein mit den traditionellen Verfahren zur Entscheidungsfindung nicht mehr zu lösen sind. Es fehlte eine Methode, um die verschiedenartigen Probleme und Problemver­ knüpfungen - wie z. B. die Verknüpfung des Losgrößenproblems der Lagerhaltung mit den Fragen der Produktions- und Absatzgeschwindigkeit - mit quantitativen, mathematischen Methoden zu behandeln. Aus den Versuchen, diese Probleme systematisch zu lösen, hat sich seit dem 2. Weltkrieg Operations Research als Anwendung mathematischer Methoden in der Planung entwickelt. Vor dem 2. Weltkrieg gab es nur vereinzelt Arbeiten, die man heute dem Operations Research zuordnen würde, wie z. B. das Warteschlangenmo­ dell für das Kopenhagener Telefonnetz von Erlang [1909], die Losgrößenformeln von Andler [1929] u. a. und Untersuchungen von Levinson in den 20er Jahren (s. Le­ vinson [1953]). Levinson arbeitete in einem Versandhaus. Er bemerkte bei seiner Arbeit dort, daß eine große Anzahl von Nachnahmesendungen zurückkam, da die Empfänger die Annahme verweigert hatten (Problemerkennung). Die Aufdeckung der Abhän­ gigkeit dieser Annahmeverweigerungen von der Zeitverzögerung zwischen Bestell­ zeitpunkt und Versandzeitpunkt (Problemstrukturierung) ließ ihn nach einem opti­ malen zeitlichen Abstand zwischen Bestellungseingang und Warenversand suchen (Problem/äsung).

Table of Contents:
1 Einführung.- 1.1 Entwicklung und Begriff des Operations Research.- 1.1.1 Entscheidungsvorbereitung.- 1.1.2 Optimierung der angestrebten Lösung.- 1.1.3 Verwendung mathematischer Methoden.- 1.1.4 Die Bedeutung der EDV bei der Anwendung von OR.- 1.2 Einsatzbereiche des Operations Research.- 1.3 Problemtypen des Operations Research.- 1.3.1 Kombinatorische Probleme.- 1.3.2 Lagerhaltungsprobleme.- 1.3.3 Ersatzprobleme.- 1.3.4 Wartezeitprobleme.- 1.3.5 Konkurrenzprobleme.- 1.4 Verfahren des Operations Research.- 1.4.1 Statische Programmierung.- 1.4.1.1 Lineare Programmierung.- 1.4.1.2 Nichtlineare Programmierung.- 1.4.1.3 Ganzzahlige und Gemischt-ganzzahlige Programmierung.- 1.4.2 Dynamische Programmierung.- 1.4.3 Entscheidungsbaumverfahren.- 1.4.4 Netzplantechnik.- 1.4.5 Warteschlangentheorie.- 1.4.6 Spieltheorie.- 1.4.7 Simulation.- 1.4.8 Heuristische Verfahren.- 2 Grundlagen der Linearen Programmierung.- 2.1 Optimales Produktionsprogramm.- 2.1.1 Graphische Lösung.- 2.1.2 Simplexmethode.- 2.2 Mischungsproblem (zulässige Ausgangslösung).- 2.3 Das allgemein lineare Programm und Sonderfälle.- 2.3.1 Das allgemeine lineare Programm.- 2.3.2 Nichtexistenz einer zulässigen (Basis-)Lösung.- 2.3.3 Nichtexistenz einer endlichen Optimallösung.- 2.4 Zusammenfassende Darstellung der Simplexmethode anhand eines Beispiels.- 2.5 Dualität.- 2.6 Die Lösung eines Problems der Linearen Planungsrechnung mit Hilfe eines Standardprogrammpaketes.- 2.6.1 Die Eingabe.- 2.6.2 Die Ausgabe.- 3 Verfahren zur Lösung des Transportproblems.- 3.1 Beispiel zum klassischen Transportproblem.- 3.2 Allgemeine Darstellung des klassischen Transportproblems.- 3.3 Lösung nach der Stepping-Stone-Methode.- 3.4 Modi-Methode.- 3.5 Entartung.- 3.6 Vergleich von Stepping-Stone-Methode und Simplexmethode.- 3.7 Erweiterungen des Transportmodells.- 3.7.1 Angebot größer als Nachfrage.- 3.7.2 Nachfrage größer als Angebot,.- 3.7.3 Unterschiedliche Produktionskosten.- 4 Sensitivitätsanalyse in der Linearen Programmierung.- 4.1 Aufgaben der Sensitivitätsanalyse.- 4.2 Graphische Betrachtungen zur Sensitivitätsanalyse.- 4.2.1 Änderung des Deckungsbeitrags eines Produktes (eines Zielfunktionskoeffizienten).- 4.2.2 Gradientenbetrachtung bei Deckungsbeitragsänderungen.- 4.2.3 Änderung einer Faktormenge (eines Wertes auf der rechten Seite).- 4.3 Beziehungen zwischen Anfangs-und Endtableau.- 4.3.1 Beziehungen für die Zielfunktionszeile.- 4.3.2 Beziehungen für die Zeilen der Nebenbedingungen.- 4.3.3 Formale Darstellung der Beziehungen zwischen Anfangs- und Endtableau.- 4.4 Analytische Sensitivitätsanalyse.- 4.4.1 Änderung von Kapazitäten (von Werten auf der rechten Seite).- 4.4.2 Änderungen der Deckungsbeiträge einzelner Produkte (der Zielfunktionskoeffizienten).- 4.4.2.1 Deckungsbeitragsänderungen bei einem der im optimalen Produktionsprogramm nicht enthaltenen Produkte.- 4.4.2.2 Deckungsbeitragsänderungen bei einem der im optimalen Produktionsprogramm enthaltenen Produkte.- 4.4.3 Änderung einzelner Produktionskoeffizienten (von Koeffizienten auf der linken Seite der Restriktionen).- 4.4.4 Einführung eines neuen Produktes (einer neuen Strukturvariablen).- 4.4.5 Auftreten zusätzlicher Beschränkungen.- 4.5 Zusammenfassende ökonomische Interpretation der Größen eines Simplextableaus für ein Programmplanungsproblem.- 4.6 Sensitivitätsanalyse im Rahmen eines Standardprogrammpaketes.- 5 Einführung in die Parametrische Programmierung.- 6 Ganzzahlige Lineare Programmierung.- 6.1 Einführung.- 6.2 Lösungsverfahren.- 6.2.1 Das Cutting Plane-Verfahren von Gomory.- 6.2.1.1 Beschreibung des Verfahrens.- 6.2.1.2 Ableitung der Schnittrestriktionen.- 6.2.1.3 Auswahl einer optimalen Schnittbedingung.- 6.2.1.4 Anwendung des Verfahrens.- 6.2.2 Das Branch and Bound-Verfahren von Dakin.- 6.2.2.1 Das Branch and Bound-Prinzip.- 6.2.2.2 Der Ablauf des Verfahrens von Dakin.- 6.2.2.3 Rechenschritte zum Algorithmus von Dakin.- 7 Nichtlineare Programmierung.- 7.1 Einführung.- 7.1.1 Allgemeine Formulierung eines nichtlinearen Programmierungsmodells.- 7.1.2 Das Problem der Programmplanung als Anwendungsbeispiel zur Nichtlinearen Programmierung.- 7.1.3 Graphische Darstellung eines konkreten quadratischen Programmplanungsproblems.- 7.2 Grundlagen der Nichtlinearen Programmierung.- 7.2.1 Klassifikation nichthnearer Programmierungsmodelle.- 7.2.1.1 Konvexität von Mengen und Funktionen.- 7.2.1.2 Konvexe Optimierungsmodelle und ihre Eigenschaften.- 7.2.1.3 Quadratische Optimierungsmodelle.- 7.2.1.4 Zusammenfassende Klassifikation von NLP-Modellen.- 7.2.2 Optimalitätsbedingungen: Das Kuhn-Tucker-Theorem.- 7.2.2.1 Darstellung und Bedeutung der Kuhn-Tucker-Bedingungen.- 7.2.2.2 Darstellung der Kuhn-Tucker-Bedingungen am Zahlenbeispiel.- 7.3 Verfahren der Nichtlinearen Programmierung.- 7.3.1 Überblick.- 7.3.2 Das Verfahren von Wolfe.- 7.3.3 Gradientenverfahren.- 7.3.3.1 Einführung.- 7.3.3.2 Das Grundkonzept der Gradientenverfahren.- 7.3.3.3 Das Verfahren der projizierten Gradienten von Rosen.- 7.3.4 Das Verfahren SUMT.- 8 Dynamische Programmierung.- 8.1 Grundbegriffe der Dynamischen Programmierung.- 8.2 Das Produktionsglättungsproblem als Anwendungsbeispiel zur Dynamischen Programmierung.- 8.3 Erweiterungen.- 9 Literaturverzeichnis.- 10 Sachverzeichnis.