WIXLIB

Runzheimer· Operations Research

Modeme WirtschaftsbücherHerausgegeben von Prof. Dr. Eduard Mändle

BODO RUNZHEIMEROperationsResearchLineare Planungsrechnung,Netzplantechnik, Simulationund Warteschlangentheorie7., aktualisierte underweiterte AuflageLEHRBUCH

Die Deutsche Bibliothek - CIP-EinheitsaufnahmeRunzheimer, Bodo:Operations Research: lineare Planungsrechnung, Netzplantechnik,Simulation und Warteschlangentheorie / Bodo Runzheimer. - 7. Aufl.- Wiesbaden: Gabler, 1999ISBN 978-3-409-30717-8ISBN 978-3-322-94495-5 (eBook)DOI 10.1007/978-3-322-94495-51. Auflage eAuflage198319861987199019951999Alle Rechte vorbehalten Betriebswirtschaftlicher Verlag Dr. Th. Gabler GmbH, Wiesbaden, 1999Der Gabler Verlag ist ein Unternehmen der Bertelsmann Fachinformation GmbH.Lektorat: lutta-Hauser-Fahr, Ulrike LörcherDas Werk einschließlich aller seiner Teile ist urheberrechtlieh geschützt. JedeVerwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohneZustimmung des Verlages unzulässig und strafbar. Das gilt insbesondere fürVervielfaltigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen.http://www.gabler-online.deHöchste inhaltliche und technische Qualität unserer Werke ist unser Ziel. Bei der Produktion undVerbreitung unserer Bücher wollen wir die Umwelt schonen: Dieses Buch ist auf säurefreiem undchlorfrei gebleichtem Papier gedruckt. Die Einschweißfolie besteht aus Polyäthylen und damit ausorganischen Grundstoffen, die weder bei der Herstellung noch bei der Verbrennung Schadstoffefreisetzen.Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werkberechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen imSinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und dahervon jedermann benutzt werden dürften.ISBN 978-3-409-30717-8

5Vorwort zur 1. AuflageDie zweibändige Darstellung des "Operations Research" - Band 1: "Lineare Planungsrechnung und Netzplantechnik", Band 2: "Methoden der Entscheidungsvorbereitung bei Risiko" - ist aus Vorlesungen, die ich an der Fachhochschule f"ür Wirtschaft in Pforzheim, der Württembergischen Verwaltungs- und WirtschaftsAkademie und der Verwaltungs- und Wirtschafts-Akademie Baden gehalten habesowie aus einer Reihe von Kompaktseminaren mit Wirtschaftspraktikern hervorgegangen. Sie wendet sich vornehmlich an Studierende der Betriebswirtschaft sowie anPraktiker in den Unternehmen, die sich mit dem Einsatz von Methoden zur Vorbereitung optimaler Entscheidungen auf quantitativer Basis beschäftigen oder ein Bedürfnis zur Weiterbildung haben.Dargestellt sind die Grundlagen, Techniken und betriebswirtschaftlichen Anwendungsmöglichkeiten des Operations Research. Die beiden Bände haben einführenden Charakter. Insbesondere habe ich mich bemüht, der Mathematik - als Hilfsmittel des Operations Research - die ihr zukommende begrenzte Rolle einzuräumen und sie so darzustellen, dass die Bände auch von solchen Lesern leicht gelesen werden können, für diedie Mathematik in der Schule nicht gerade Lieblingsfach war oder für die die Schulzeitschon lange zurückliegt. Aus diesem Grunde wurde auch auf die Verwendung der Symbolik der Mengenlehre verzichtet. Das Schwergewicht wurde auf eine Demonstrationder Lösungsmethoden an betriebswirtschaftlichen Problemstellungen sowie auf derenökonomische Interpretation gelegt. Dazu wird eine Reihe von didaktisch sinnvollenBeispielen aus der Planungspraxis verschiedener betriebswirtschaftlicher Funktionsbereiche behandelt. Ein Selbststudium sollte mit den beiden Bänden möglich sein, zumal die notwendigen Grundlagen - die mehr den Charakter von Hilfsmitteln haben - inForm von Exkursen relativ ausfiihrlich erörtert werden (z.B. "Begriffe und Regeln derMatrizenrechnung" bzw. der "Wahrscheinlichkeitsrechnung", ,,Einfiihrung in Stichprobentheorie", "Grundbegriffe der mehrperiodischen Investitionsrechnung").Der hier vorliegende erste Band enthält neben einer Einführung die bekanntesten und wohlauch arn meisten in der betriebswirtschaftlichen Praxis angewendeten Gebiete des Operations Research, nämlich die lineare Planungsrechnung und die Netzplantechnik.Im zweiten Band "Methoden der Entscheidungsvorbereitung bei Risiko" wird ganzgezielt nicht von der Prämisse vollständiger Information ausgegangen, sondern versucht, der Tatsache Rechnung zu tragen, dass sich der Entscheidungsträger bei der Suche nach optimalen Lösungen in einer Risikosituation befindet, d.h., dass er nur mangelhafte Kenntnisse über die künftige Entwicklung hat. Dabei kann es nicht darum gehen, das Risiko durch raffinierte Methoden aus dem Wege zu räumen. Das Ziel bestehtvielmehr darin, das Risiko sichtbar zu machen und es nach Möglichkeit zu quantif"lZie-

6ren. Im Einzelnen umfasst der zweite Band Kapitel über die Simulation, Warteschlangentheorie, Entscheidungsbaumverfahren und die Behandlung stochastischer Abläufe als Markov-Prozesse. Mancher Leser wird das eine oder andere Thema, wie z.B. dieSpieltheorie, vermissen. Bei der Auswahl habe ich mich aber nicht zuletzt von demfortgeschrittenen Entwicklungsstand der Methoden und ihren praktischen Anwendungsmöglichkeiten leiten lassen.Bei meinem Freund und Kollegen Professor Dr. Fritz Wegner möchte ich mich sehrherzlich ftlr wertvolle Anregungen und Diskussionen bedanken.Bodo RunzheimerVorwort zur 7. AuflageDie siebte Auflage des Bandes "Operations Research I" wurde verbessert und aktualisiert. Neben der Einleitung (I. Kapitel), der Linearen Planungsrechnung (2. Kapitel)und der Netzplantechnik (3. Kapitel) wurde zusätzlich die Simulation (4. Kapitel) unddie Warteschlangentheorie (5. Kapitel) in den Band aufgenommen. Wegen der zunehmenden Bedeutung der Simulation und der Warteschlangentheorie in Theorie undPraxis habe ich mich zu dieser Erweiterung des 1. Bandes entschlossen; dabei handelt essich größtenteils um eine Übernahme des 1. und 2. Kapitels aus dem Band OperationsResearch 11.Für die Anregungen zur Verbesserung darf ich mich bei Lesern, Studenten und Kollegen sehr herzlich bedanken. Auch in Zukunft bin ich fiir eine solche Unterstützung sehrdankbar.Bodo Runzheimer

7InhaltErstes Kapitel: Einleitung . 131Einige Bemerkungen zur Entwicklung des Operations Research . 1311Begriff Operations Research . 14IIITypische Vorgehensweise des Operations Research . 15IV.Modelle als Hilfsmittel des Operations Research . 16Übungsfragen zum 1. Kapitel. . 18Literatur zum 1. Kapitel . 19Zweites Kapitel: Lineare Planungsrechnung . 201EinfUhrung . 20IlFormulierung der Grundaufgabe der linearen Planungsrechnung . 20A.C.Maximierungsaufgabe: Optimierung eines Produktionsprogramms . 211. Beispiel mit linearem Programmansatz . 222. Grafische Lösung . 23Minimierungsaufgabe: Optimierung eines Werbeprogramms . 251. Beispiel mit linearem Programmansatz . 252. Grafische Lösung . 27Standardansatz der linearen Planungsrechnung . 29111Simplexmethode . 31A.Simplex-Algorithmus . 321. Überführung des Ungleichungssystems in ein Gleichungssystem. 322. "Nullprogramm" als erste zulässige Basislösung . 343. Simplexkriterium . 354. Sirnplextableau . 365. Iterationen . 386. Zusammenfassung der Vorgehensweise nach der Simplexmethode. .42Wirtschaftlicher Inhalt der Optimierungsmethode . 431. Ökonomische Interpretation der Inhalte von Simplextableaus . 432. Bewertung von Engpässen . 44Sonderfalle . 451. Mehrfachlösungen . 452. Degeneration . 463. Unbegrenzte Zielvariable . 46Probleme mit unzulässiger Ausgangslösung . .471. Zwei-Phasen-Verfahren zur Bestimmung einerzulässigen Ausgangslösung. 49B.B.C.D.

8E.2. Übungsbeispiel zur Ermittlung des optimalen ProduktionsprogrammsfUr einen Großbetrieb - Maximierungsproblem mit unzulässiger Ausgangslösung erörtert unter Verwendung des Zwei-Phasen-Verfahrens . 553. M-Methode zur Bestimmung einer zulässigen Ausgangslösungbei Gleichungen als Restriktionen . 644. M-Methode zur Bestimmung zulässiger Lösungen von linearen Planungsrechnungs-Problemen mit Ober- und Untergrenzen einzelner Variablen . 695. Freie Variablen und ihre Behandlung . 746. Beispiel zur Lösung eines linearen Gleichungssystemsmit Hilfe der Simplexmethode . 75Minimierung mit der Simplexmethode . 761. Beispiel: Kostenminimale Mischung . 762. Minimierung mit Hilfe der M-Methode . 773. Minimierung mit Hilfe des Zwei-Phasen-Verfahrens . 80Übungsfragen zu den Abschnitten I bis m . 82IV.Dualität in der linearen Planungsrechnung . 83A.B.Verknüpfung dualer Probleme . 831. Standardproblem . 842. Kanonisches Problem . 85Duale Simplexmethode . 871. Beispiel: Mischungsproblem. 882. Ökonomische Beziehungen zwischen Primal- und Dualproblem- dargestellt an einem Primal-Dual-Problem. 90V.Revidierte Simplexmethode . 94A.B.Rechenschritte der revidierten Simplexmethode . 95Zahlenbeispiel zur revidierten Simplexmethode . 101VIPostoptimale Rechnungen . 107A.B.Grundlegung . 107Parametrische Planungsrechnung und Sensitivitätsanalyse . l081. Variation der Zielfunktion . 1082. Variation der Nebenbedingungen . 115VIIWeiterführende Probleme der linearen Planungsrechnung . 121A.B.Ganzzahlige Planungsrechnung . 121Stochastische lineare Planungsrechnung . 122Übungsfragen zu den Abschnitten IV bis VII . 123VIII Transportmethode . 123A.B.Fonnulierung und Darstellung des Transportproblems . 123Rechenprozess (Lösungsverfahren) . 1271. Bestimmung einer zulässigen Ausgangslösung . 1292. Problem der Degeneration . 134

9E.F.3. Iterationsprozess der Transportmethode .Mehrdeutige Lösungen .Offene Transportprobleme (fiktive Anbieter und Nachfrager) .1. Fall 1: Angebotsmenge größer als Bedarfsmenge .2. Fall 2: Bedarfsmenge größer als Angebotsmenge .Transportprobleme mit zusätzlichen Kapazitätsbeschränkungen .Mehrstufige Transportprobleme - Umladeprobleme .IX.Zuordnungsproblem . 159A.B.Grundlegung .Ungarische Methode .1. Beispiel: Schaufensterzuteilung .2. Rechentechnik .XBeurteilung und Anwendungsmöglichkeitender linearen Planungsrechnung . gen zu den Abschnitten VIII bis IX . 172Literatur zum 2. Kapitel . 173Drittes Kapitel: Netzplantechnik (NPT) . 180IGraphen als Hilfsmittel anschaulicher Darstellungen undGrundbegriffe der Graphentheorie . 180ILGrundlagen der Netzplantechnik . 182IIIStrukturplanung . 184A.B.Srukturanalyse .Darstellung der Ablaufstruktur .1. Formen der Netzplandarstellung .2. Critical Path Method - CPM .3. Program Evaluation and Review Technique (PERT) .4. Metra - Potenzial - Methode (MPM) .5. Gegenüberstellung der Netzplantypen Vorgangspfeilnetz (CPM)und Vorgangsknotennetz (MPM) .Nummerierung der Knoten .1. Willkürliche Nummerierung .2. Aufsteigende (systematische) Nummerierung .3. Lückenlos aufsteigende Nummerierung .C.184188188188191192192195195195195IV.Zeitplanung . 196A.B.Zeitanalyse . 197Zeitplanung mit CPM . 1991. Ermittlung des kritischen Weges . 1992. Ermittlung und Interpretation der Pufferzeiten. 205