Stephan Dempe, Heiner Schreier Operations Research Deterministische Modelle und Methoden Prof. Dr. Stephan Dempe Geboren 1956 in Weimar. Von 1976 bis 1981 Studium der Mathematik an der TH Karl-Marx-Stadt, Promotion 1985 auf dem Gebiet der diskreten Optimierung, Habilitation 1991 auf dem Gebiet der nichtdifferenzierbaren Optimierung an der TU Karl-Marx-Stadt. Förderpreis der Deutschen Akademie der Naturforscher Leopoldina 1994. Studienaufenthalte 1982 an der Belorussischen Staatlichen Universität Minsk, 1988 an der Leningrader Staatlichen Universität. Seit 1997 Professor für Mathema- tische Optimierung an der TU Bergakademie Freiberg. Dr. Heiner Schreier Geboren 1952 in Chemnitz. Von 1973 bis 1978 Studium der Mathematik an der Bergakademie Frei- berg. Seit 1978 wissenschaftlicher Mitarbeiter an der Fakultät für Mathematik und Informatik der TU Bergakademie Freiberg. Promotion 1982 über ein Tourenproblem der Schüttgutoptimierung. Mitglied der Applikationsgruppe Mathematik im Bergbau von 1982 bis 1986. Seit 1986 eigenverantwortliche Lehrveranstaltungen zu Gebieten der Wirtschaftsmathematik, insbesondere diskrete und parametri- sche Optimierung, Transportoptimierung und Finanzmathematik. 1. Auflage September 2006 Alle Rechte vorbehalten © B.G.Teubner Verlag / GWV Fachverlage GmbH, Wiesbaden 2006 Lektorat: Ulrich Sandten / Kerstin Hoffmann Der B. G. Teubner Verlag ist ein Unternehmen von Springer Science+Business Media. www.teubner.de ISBN-10 3-519-00448-8 ISBN-13 978-3-3-519-00448-6 Vorwort Das vorliegende Buch ist aus Vorlesungen zu verschiedenen Gebieten des Operations Re- search entstanden, die die Autoren an der Technischen Universit¨at Bergakademie Freiberg gehaltenhaben.ZumVerst¨andnisseinesInhaltessindGrundkenntnissederlinearenAlgebra und der mehrdimensionalen Differentialrechnung erforderlich. Eine allgemeingu¨ltige Definition des Begriffes Operations Research“ gibt es nicht. Aner- ” kannt ist jedoch, dass das Herzstu¨ck des Operations Research in der Entwicklung (und Begru¨ndung) quantitativer Modelle und Methoden sowie deren Anwendung bei der Un- tersuchungpraktischerAufgabenstellungeninsbesondereim¨okonomischenUmfeldbesteht. Von Gal [Gal 92] wird es zwischen Mathematik, Systemtheorie, Informatik und Entschei- dungstheorie eingeordnet und betont, dass es ein interdisziplin¨arer Wissenschaftszweig ist. TheoretischeGrundlagensindnebenderEntscheidungstheoriediemathematischeOptimie- rung,dieStatistik/StochastikunddieGraphentheorie.DieAnwendungensindinpraktisch allen Disziplinen der Betriebs- und Volkswirtschaftslehre zu finden. Ohne Informatik geht in der heutigen Zeit bei der Bearbeitung realer Probleme nichts mehr. Wir haben uns bei der Konzipierung des Werkes deshalb einschr¨anken mu¨ssen einerseits auf deterministische Probleme und andererseits auf einige wenige anwendungsorientierte Gebiete. Weder stochastische Probleme und Modelle noch Aufgaben und Methoden der unscharfen Optimierung haben aus Platzgru¨nden Eingang in das Werk gefunden. Behan- delt werden lineare und nichtlineare Optimierungsaufgaben, Transportprobleme, diskrete Optimierung und die Graphentheorie als die mathematischen Grundlagen des Operations Research. Als Anwendungsbebiete haben wir die Logistik und die Spieltheorie ausgew¨ahlt. DieKomplexit¨atstheorie,dieeigentlichzwischenderMathematikunddertheoretischenIn- formatik angesiedelt ist, hat in der letzten Zeit immer mehr an Bedeutung gewonnen. Sie versucht,eineAntwortaufrechentechnischeProbleme,diedieAnwendungdergewonnenen theoretischenErkenntnissebeiderBearbeitungpraktischerAufgabenstellungenerschweren oder behindern, dadurch zu geben, dass sie die zu l¨osenden Probleme bezu¨glich der er- forderlichen Rechenzeiten auf dem Computer klassifiziert. Nicht aufgenommen haben wir ebenfallsausPlatzgru¨ndeneinerseitsdieBeweisederangefu¨hrtenAussagenundandererseits HinweisezurUmsetzungderbeschriebenenAlgorithmenmitHilfeeinesComputers.DieBe- weise findet der interessierte Leser in den angefu¨hrten Literaturstellen. Viele Algorithmen fu¨r Optimierungsaufgaben sind in den Programmpaketen AMPL [Fou 03], GAMS, LIN- GO/LINGO [Win 97] oder auch in der Optimization Toolbox fu¨r Mathematica(cid:1) [Bha 00] implementiert.StudentenversionenvonAMPL,GAMS,LINDO/LINGOk¨onnenimInternet herunter geladen werden. Jedes der einzelnen Kapitel enth¨alt die wesentlichen Aussagen mindestens zweistu¨ndiger Vorlesungen. Wesentlicher Bestandteil des Buches sind ausfu¨hrlich durchgerechnete Bei- spiele, die das Verst¨andnis der Ausfu¨hrungen unterstu¨tzen sollen. SchwerpunkteimKapitel1u¨berlineareOptimierungsaufgabensindnebendemModellder primalen und der dualen Aufgabe der Simplexalgorithmus, die Konstruktion einer Start- basisl¨osung und die Interpretation der dualen Aufgabe. Vorgestellt werden einparametri- sche Aufgaben ebenso wie die lineare Vektoroptimierungsaufgabe. Kapitel 2 befasst sich ausfu¨hrlicheralsinvergleichbarenWerkenmitTransportproblemen.Außerdemklassischen Problem und dem linearen Zuordnungsproblem werden verschiedene offene Transportpro- bleme vorgestellt. Fu¨r diese Probleme werden insbesondere L¨osbarkeitsbedingungen und HerangehensweisenzurTransformationineinklassischesTransportproblemformuliert.Ein erster Schwerpunkt im Kapitel 3 sind verschiedene Zug¨ange zur Modellierung diskreter Optimierungsaufgaben. Nach der Beschreibung (klassischer) exakter L¨osungsalgorithmen werden Grundlagen fu¨r die Konzeption und Bewertung von N¨aherungsalgorithmen gelegt und am Beispiel des Rucksackproblemes demonstriert. Probleme der Optimierung u¨ber Netzen(beziehungsweisederGraphentheorie)habenvielf¨altigeAnwendunginsbesonderein derO¨konomie.VorgestelltwerdenimKapitel4Problemedesku¨rzestenWeges,Flussproble- me, Matchingprobleme, Probleme Hamilton’scher und Euler’scher Kreise. Mit dem Rund- reiseproblem wird ein anwendungsorientiertes, schwierig zu l¨osendes Problem vorgestellt, fu¨r welches N¨aherungsalgorithmen beschrieben werden. Kapitel 5 ist der Anwendung der Graphentheorie in der O¨konomie, speziell den Modellen der Logistik, gewidmet. Behan- deltwerdenVerallgemeinerungendesRundreiseproblemsunddesProblemsderEuler’schen Graphen ebenso wie Standort- und Tourenprobleme. Diese Probleme sind zumeist schwie- rig l¨osbar und werden dann mit N¨aherungsalgorithmen bearbeitet. Vorgestellt werden au- ßerdem Modellierungszug¨ange mit Hilfe der diskreten Optimierung. Kapitel 6 untersucht Grundaussagen zu Problemen der nichtlinearen Optimierung, speziell Optimalit¨atsbedin- gungen und duale Optimierungsaufgaben. Die mathematische Spieltheorie im Kapitel 7 ist eine fu¨r betriebs- und volkswirtschaftliche Fragestellungen wichtige Anwendung der linea- ren und nichtlinearen Optimierung. Vorgestellt werden das Nash’sche Gleichgewicht fu¨r Spiele in strategischer Normalform, das Stackelberg-Gleichgewicht fu¨r Spiele in extensiver Normalform sowie die klassischen Zug¨ange fu¨r kooperative Spiele. L¨osungshinweise zu den U¨bungsaufgaben findet man auf den Internetseiten der Autoren an der TU Bergakademie Freiberg. Herzlichbedankenm¨ochtenwirunsbeiallen,diewesentlichzumEntstehendesBuchesbei- getragenhaben.SpeziellsinddiesHerrU.SandtenalsverantwortlicherLektordesVerlages und B. Luderer als Herausgeber der Reihe Teubner Studienbu¨cher Wirtschaftsmathema- ” tik“, unsere Studenten I. Graichen und F. Martin und unsere Kollegen D. Fangh¨anel und S. Lohse, die unsere Vorlagen sehr sorgf¨altig durchgesehen haben. Freiberg, Stephan Dempe August 2006 Heiner Schreier Inhalt 1 Lineare Optimierung 13 1.1 Das Modell der linearen Optimierung . . . . . . . . . . . . . . . . . . . . . 13 1.2 Graphische L¨osung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3 Der primale Simplexalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.2 Der Optimalit¨atstest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.3.3 Verbesserungsschritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.3.4 Der Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.3.5 Zyklenvermeidung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.3.6 Berechnung einer ersten zul¨assigen Basisl¨osung . . . . . . . . . . . . . . . . 35 1.4 Duale lineare Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.4.1 Konstruktionsprinzipien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.4.2 Dualit¨atss¨atze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 1.4.3 Interpretation der dualen Aufgabe . . . . . . . . . . . . . . . . . . . . . . . 45 1.4.4 Der duale Simplexalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 48 1.5 Einparametrische lineare Optimierungsaufgaben . . . . . . . . . . . . . . . 52 1.5.1 Aufgaben mit einem Parameter in der Zielfunktion . . . . . . . . . . . . . . 52 1.5.2 Aufgaben mit einem Parameter in der rechten Seite der Nebenbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 1.6 Vektoroptimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 1.6.1 Pareto-optimale Punkte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 1.6.2 Ersatzprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 1.6.3 Zweikriterielle Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 1.7 Ein polynomialer Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . 66 1.7.1 Komplexit¨at des Simplexalgorithmus . . . . . . . . . . . . . . . . . . . . . . 66 1.7.2 Der zentrale Pfad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 1.7.3 Innere-Punkt-Methode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 1.8 U¨bungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2 Transportoptimierung 72 2.1 Das klassische Transportproblem . . . . . . . . . . . . . . . . . . . . . . . . 73 2.1.1 Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 2.1.2 Qualitative Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2.1.3 Er¨offnungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.1.4 Optimierungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 2.1.5 Erg¨anzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 2.2 Das lineare Zuordnungsproblem . . . . . . . . . . . . . . . . . . . . . . . . 103 2.2.1 Modelle und Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 2.2.2 Ungarische Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 2.3 Offene Transportprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 2.3.1 Standardmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 2.3.2 Modell mit gemischten Restriktionen. . . . . . . . . . . . . . . . . . . . . . 132 2.4 Kapazitierte Transportprobleme . . . . . . . . . . . . . . . . . . . . . . . . 137 2.4.1 Das kapazitierte klassische Transportproblem . . . . . . . . . . . . . . . . . 137 2.4.2 Erweiterung des primalen L¨osungsverfahrens . . . . . . . . . . . . . . . . . 141 2.5 Umladeprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 2.6 Bottleneck Transportprobleme . . . . . . . . . . . . . . . . . . . . . . . . . 159 2.7 U¨bungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 3 Diskrete Optimierung 166 3.1 Begriffe zur diskreten Optimierung . . . . . . . . . . . . . . . . . . . . . . . 167 3.2 Modellierung von Diskretheitsbedingungen . . . . . . . . . . . . . . . . . . 170 3.2.1 Optimierungsprobleme mit Ganzzahligkeitsforderungen . . . . . . . . . . . 170 3.2.2 Modellierung mit Hilfe von 0-1-Variablen . . . . . . . . . . . . . . . . . . . 174 3.2.3 Permutationsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 3.3 Das Verzweigungsprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 3.3.1 Formulierung und Begru¨ndung des Verzweigungsprinzips . . . . . . . . . . 186 3.3.2 Anwendung des Verzweigungsprinzips . . . . . . . . . . . . . . . . . . . . . 192 3.4 Das Schnittprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 3.4.1 Formulierung und Begru¨ndung des Schnittprinzips . . . . . . . . . . . . . . 197 3.4.2 Anwendung des Schnittprinzips . . . . . . . . . . . . . . . . . . . . . . . . . 201 3.5 Dynamische Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 3.5.1 L¨osungsprinzip der dynamischen Optimierung . . . . . . . . . . . . . . . . 208 3.5.2 Anwendung der dynamischen Optimierung . . . . . . . . . . . . . . . . . . 211 3.6 N¨aherungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 3.6.1 Gu¨te von N¨aherungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . 215 3.6.2 Greedy-Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 3.6.3 N¨aherungsverfahren fu¨r das Rucksackproblem. . . . . . . . . . . . . . . . . 222 3.7 U¨bungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 4 Optimierung u¨ber Graphen 231 4.1 Definitionen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 Inhalt 9 4.2 Ku¨rzeste Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 4.3 Minimalgeru¨ste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 4.4 Flussprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 4.4.1 Flu¨sse maximaler St¨arke. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 4.4.2 (q−s)-Flu¨sse mit minimalen Kosten . . . . . . . . . . . . . . . . . . . . . 247 4.4.3 Das Minimalkosten-Flussproblem . . . . . . . . . . . . . . . . . . . . . . . . 249 4.5 Matchingprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 4.5.1 Matchings maximaler Kantenzahl . . . . . . . . . . . . . . . . . . . . . . . 251 4.5.2 Matchings minimalen Gewichtes . . . . . . . . . . . . . . . . . . . . . . . . 254 4.6 Euler’sche Kreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 4.7 Das Rundreiseproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 4.7.1 Hamiltonkreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 4.7.2 N¨aherungsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 4.7.3 Verbesserungsalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 4.8 U¨bungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 5 Modelle der Logistik 268 5.1 Verallgemeinerte Rundreiseprobleme . . . . . . . . . . . . . . . . . . . . . . 268 5.1.1 Besuch eines Teiles der Knoten . . . . . . . . . . . . . . . . . . . . . . . . . 269 5.1.2 Mehrere Reisende . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 5.2 Das Problem des Postboten . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 5.2.1 Das Problem im gerichteten Graphen . . . . . . . . . . . . . . . . . . . . . 271 5.2.2 Das Problem im ungerichteten Graphen . . . . . . . . . . . . . . . . . . . . 273 5.2.3 Das Problem des Postboten in gemischten Graphen . . . . . . . . . . . . . 275 5.2.4 Das Problem des Postboten auf dem Lande . . . . . . . . . . . . . . . . . . 276 5.2.5 Das Problem des Postboten mit richtungsabh¨angigen Kosten . . . . . . . . 278 5.3 Tourenprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 5.3.1 Modellierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 5.3.2 N¨aherungsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 5.4 Standortprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 5.4.1 Modellierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 5.4.2 Das unkapazitierte Standortproblem . . . . . . . . . . . . . . . . . . . . . . 288 5.4.3 L¨osungszug¨ange fu¨r das kapazitierte Standortproblem . . . . . . . . . . . . 290 5.5 Bestimmung optimaler Maschinenstandorte . . . . . . . . . . . . . . . . . . 292 5.6 U¨bungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 6 Nichtlineare Optimierung 299 6.1 Konvexe Mengen und konvexe Funktionen. . . . . . . . . . . . . . . . . . . 299 6.1.1 Mengen und Hu¨lloperationen . . . . . . . . . . . . . . . . . . . . . . . . . . 299 6.1.2 Konvexe Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 6.2 Konvexe Optimierungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . 303 6.3 Notwendige Optimalit¨atsbedingungen . . . . . . . . . . . . . . . . . . . . . 305 6.3.1 Allgemeine Nebenbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . 305 6.3.2 Explizite Nebenbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . 307 6.3.3 Regularit¨atsbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 6.4 Hinreichende Optimalit¨atsbedingungen zweiter Ordnung . . . . . . . . . . . 311 6.5 Duale Optimierungsaufgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 6.5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 6.5.2 Beziehungen zwischen primaler und dualer Aufgabe . . . . . . . . . . . . . 317 6.6 Sattelpunkte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 6.7 U¨bungsaufgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 7 Mathematische Spieltheorie 320 7.1 Spiele in strategischer Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 7.1.1 Definition und Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 7.1.2 Existenz und Berechnung Nash’scher Gleichgewichte . . . . . . . . . . . . . 323 7.1.3 Nullsummen- und Matrixspiele . . . . . . . . . . . . . . . . . . . . . . . . . 324 7.2 Spiele in extensiver Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 7.2.1 Definition und Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 7.2.2 Stackelberg-Gleichgewicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 7.3 Axiomatische Verhandlungsspiele . . . . . . . . . . . . . . . . . . . . . . . . 333 7.4 Kooperative Spiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 7.4.1 Charakteristische Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 7.4.2 Zuteilungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337 7.4.3 Strategische A¨quivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 7.4.4 Dominante Auszahlungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 7.4.5 Der Kern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 7.4.6 Die Neumann-Morgenstern-L¨osung . . . . . . . . . . . . . . . . . . . . . . . 341 7.4.7 Der Shapley-Vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 7.5 U¨bungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 8 Komplexit¨atstheorie 345 8.1 Notationen zum Wachstumsverhalten . . . . . . . . . . . . . . . . . . . . . 346 8.2 Probleme, Algorithmen, Kodierung. . . . . . . . . . . . . . . . . . . . . . . 348 8.3 Komplexit¨at und polynomiale Transformation . . . . . . . . . . . . . . . . 355 8.4 Klassifizierung von Entscheidungsproblemen . . . . . . . . . . . . . . . . . 360 8.5 Klassifizierung von Optimierungsproblemen . . . . . . . . . . . . . . . . . . 369 Inhalt 11 Literaturverzeichnis 373 Sachverzeichnis 378 1 Lineare Optimierung Im ersten Kapitel werden lineare Optimierungsaufgaben, die eine der wesentlichen Grund- lagen des Operations Research darstellen, betrachtet. Neben der primalen und der dualen linearen Optimierungsaufgabe mit dem entsprechenden primalen und dualen Simplexalgo- rithmus werden die Postoptimalit¨atsanalyse sowie die mehrkriteriellen linearen Optimie- rungsaufgaben im Mittelpunkt der Untersuchungen stehen. Das Kapitel wird mit einigen AussagenzualternativenL¨osungsalgorithmenfu¨rlineareOptimierungsaufgabenabgeschlos- sen werden. Lineare Optimierungsaufgaben standen am Beginn der Entwicklung der Optimierung zu einer eigenst¨andigen wissenschaftlichen Disziplin in der Mathematik. U¨ber ihre Anf¨ange in den 30er und 40er Jahren des 20ten Jahrhunderts, die eng mit den Namen von L. V. Kantorovich, W. Leontief und G. B. Dantzig verbunden sind, kann in der Monographie [Dan 97] nachgelesen werden. Lineare Optimierungsprobleme werden h¨aufig in der Praxis angewendet, die L¨osung auch sehr groß dimensionierter Aufgaben ist mit Hilfe ausgereifter Computerprogramme m¨oglich. Von großer Bedeutung sind lineare Optimierungsaufgaben auchfu¨rdieL¨osungdiskreterProbleme,seieszurBestimmungvonN¨aherungsl¨osungenoder als Teil von exakten L¨osungsverfahren, wie dem branch-and-bound Algorithmus (n¨aheres dazu in Kapitel 3). Aussagen zur L¨osung von linearen Optimierungsaufgaben sind in fast allen Bu¨chern u¨ber Operations Research enthalten, siehe zum Beispiel [Neu 93]. Umfangreiche Beschreibungen einschließlich der notwendigen Beweise lassen sich in [Gei 02], [Dan 97], [Dan 03], [Jar 04] finden. 1.1 Das Modell der linearen Optimierung Es sei M ⊆Rn eine gegebene Menge von Alternativen und f :M →R eine auf der Menge M gegebene Funktion, die die Qualit¨at der Elemente in M bewertet. Die mathematische Optimierung untersucht Aufgaben der Art min{f(x):x∈M} oder max{f(x):x∈M}, also Aufgaben der Suche nach solchen Alternativen in der Menge M, fu¨r die die Funktion f(x) einen minimalen beziehungsweise maximalen Wert annimmt. In der linearen Optimierung wird vorausgesetzt, dass die Menge der Alternativen durch lineare Ungleichungen und Gleichungen beschrieben werden kann und dass die Funktion