Mathematische Optimierungsmodelle

1. Charakterisierung Ein Optimierungsmodell enthält vier Hauptkomponenten: · Entscheidungsvariablen, die unter der Kontrolle der Planer sind, z.B. „Wann und wie viele Teile sollen von welchem Lieferanten bestellt werden?” · Restriktionen für die Entscheidungsvariablen, z.B. die begrenzte Produktionskapazität eines Fertigungssystems; · eine Zielfunktion dient zur Bewertung der Entscheidungen, wobei Freiheitsgrade der Restriktionen ausgenutzt werden, z.B. die Kostenminimierung der Entscheidungsvariablen; · Parameter und Daten (Konstanten), die zwar konstant sind, jedoch von der Zeitperiode und dem betrachteten Objekt abhängen können, z.B. die Einkaufspreise für Rohmaterialien (E/ME) oder die Fertigungszeit eines Produktes auf einer Maschine (ZE/ME). Die allgemeine Form eines deterministischen Optimierungsproblems mit einer Zielfunktion lautet: mi nimiere oder maximiere f(x) unter den Nebenbedingungen gi(x) {5., =, > } 1:oje 91, i=1,..,m, x=(xl,..,x.), xe X, Xce, wobei 91 die Menge der reellen Zahl ist. Je nach Art der Variablen, Restrikti onen und der Zielfunktion unterscheidet man lineare, nichtlineare und Modelle mit diskreten Variablen. Im Folgenden werden lineare Modelle (LP) bzw. gemischt-ganzzahlige Optimierungsmodelle (IP) betrachtet. Formal wird die zu betrachtende Modellklasse folgendermassen definiert: min/max cTx, Ax 5_ b, 311, Xj ganzzahlig für jE J1 c {1,..,n}, wobei x, c, 1, u E91”, be 91m und A eine reelle (m,n)-Matrix ist. Ein Optimierungsmodell muss im Rahmen eines Anwendersystems implementiert und mit Optimierungssoftware gelöst werden. Eine Lösung eines Optimierungsmodells (Optimierungsmodelle, Lösungen) besteht aus einer Wertzuweisung an die Variablen des Modells, d.h. ein n-Vektor x E 9i”. f(x) wird als der Zielfunktionswert einer Lösung bezeichnet.
2. . Lineare Optimierungsmodelle Bei linearen Optimierungsmodellen (LP) sind Zielfunktion und Restriktionen lineare Funktionen der Entscheidungsvariablen. Jede Variable darf nur Werte in einem reellen Intervall [1,u] annehmen. Im Normalfall ist I = 0; einzelne 1 und u können auch —00 oder + 00 sein.
3. Lösung linearer Optimierungsmodelle Die Lösungsverfahren basieren entweder auf der Simplexmethode oder Innere-Punkte-Verfahren, die ursprünglich auf die Arbeiten von G.B. Dantzig bzw. N. Karmarkar zurückgehen. Beide Verfahren weisen unterschiedliche Vor- und Nachteile auf und ergänzen sich. Die Simplexmethode unterteilt sich in primale und duale Simplex-Algorithmen. Es gibt Modellklassen, bei denen jeder der drei Algorithmen die schnellste Laufzeit aufweist. Die folgende Tabelle zeigt die Laufzeiten dieser Algorithmen bei zwei LP-Modellen mit MOPS.
Mathematische Optimierungsmodelle

In diesem Beispiel ist für das Modell PTV der duale Simplex am schnellstens, während für das Modell Ken-18 das Innere-Punkte-Verfahren schneller ist. Einen wesentlichen Einfluss auf die Lösungszeit von LP- und IP-Modellen haben auch Techniken des   LP-Preprocessing.
4. Gemischt-ganzzahlige Optimierungsmodelle (IP-Modelle) Dies sind LP-Modelle, bei denen einige oder alle Variablen ganzzahlige Werte annehmen müssen. Im Unterschied zu LP-Modellen gehören IP-Modelle (bis auf spezielle Ausnahmen) mathematisch zur Klasse der NP-harten Probleme, für die keine effizienten Algorithmen bekannt sind. Es gibt relativ kleine Modelle, die bereits sehr schwierig zu lösen sind. Weiterhin kann die Art der Modellierung bei IP-Modellen über deren Lösbarkeit entscheiden. Die wichtigste Modellklasse sind gemischte 0-1- Modelle. Eine Vielzahl von Modellierungstechniken, unter anderem auch für Nichtlinearitäten und lo-gische Verknüpfungen von Entscheidungen über 0-1-Variablen, erlauben es, fast jedes deterministische Entscheidungsproblem in einem IP-Modell abzubilden.
5. Lösung gemischt-ganzzahliger Optimierungsmodelle Alle Softwaresysteme zur Lösung von IP-Modellen basieren auf Branch-and-Bound/Cut-Algorithmen. Nach dem LP-Preprocessing des IP-Modells wird das zugehörige Anfangs-LP gelöst. Danach erfolgt ein erstes   IP-Preprocessing (Supernode Processing), um eine möglichst strenge LP-Relaxation des IP-Modells zu erreichen. Optional kann dann eine Heuristik zur Bestimmung ei-ner ganzzahligen Anfangslösung ausgeführt werden. Danach wird das IP-Modell mit einem Branch and Bound/Cut-Algorithmus optimiert. Hinweis Zu den angrenzenden Wissensgebieten bzw. zu Anwendungsbereichen siehe u.a. Analysemethoden, betriebswirtschaftliche, Beschaffungslogistik,   Beschaffungsmanagement, Distributionslogis-tik, Entscheidung, betriebswirtschaftliche, Industriemanagement, Logistik,   Nutzwertanaly-se,   Ökonometrie,   Operations Research, Optimierung, Grundlagen, Portfoliomanagement, Produktionsmanagement,   Prozessmanagement,   Statistik,   Supply Chain Management,   Wirtschaftsmathematik.

Literatur: Bixby R.E., Solving real-world linear programs: a decade and more of progress, Operations Research 50
(1), 3-15, 2002; Maros, I., Computational Techniques of the Simplex Method, Kluwer\'s International Series, 2003; Padberg, M.W., Linear optimization and extensions, Springer, 1995; Vander-bei, Robert J., Linear Programming: Foundations and Extensions, Kluwer Academic Publishers, 1997; Wright, S.J., Primal Dual Interior Points Methods, Society for Industrial & Applied Mathematics, 1997; Meszaros, C. and U.H. Suhl, Advanced preprocessing techniques for linear and quadratic program-ming, OR Spectrum, 25
(4), 575-595, 2003; Kallrath, J., Gemischt-ganzzahlige Optimierung: Model-lierung in der Praxis, vieweg, 2002; Johnson, E.L., Nemhauser, G.L. and Savelsbergh, M.W.P., Pro-gress in Linear Programming-Based Algorithms for Integer Programming: An Exposition, INFORMS Journal on Computing, 12
(1), 2-23, 2000; Suhl, U.H. and Szymanski, R., Supernode Processing of Mixed-Integer Models, Computational Optimization and Applications 3, 317-331, 1994; Suhl, U.H. und. Waue, V, Fortschritte bei der Lösung gemischt-ganzzahliger Optimierungsmodelle, in „Quantita-tive Methoden in ERP und SCM” (Eds. L. Suhl und S. Voss), DSOR Beiträge zur Wirtschaftsinfor-matik, 35-53, 2004; Wolsey, L.A., Integer Programming, John Wiley, 1998; Kallrath, J. (Hrsg.), Mod-eling Languages in Mathematical Optimization, Springer, 2004; Fourer, R., Gay, D., Kernighan, B., AMPL - A Modeling Language for Mathematical Programming, The Scientific Press, 1993; Williams, H. P., Model Building in Mathematical Programming, John Wiley & Sons, Inc., 1991. Internetadressen:                             http://www.wiwiss.fu-berlin.de/suhl/;      http://www-fp.mcs.anl.gov/otc/Guide/; http://www.ilog.com/products/cplex/; http://www.dashoptimization.comi;                                                    http://www.mops‑optimizer.com/

Vorhergehender Fachbegriff: mathematische Optimierung | Nächster Fachbegriff: mathematische Planungsrechnung

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Tarif, proportionaler | Euro-EUR-Markt | Schlechtwettergeld

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer