kombinatorische Optimierung

Viele betriebswirtschaftliche Entscheidungsprobleme sind kombinatorischer Natur, d.h., Lösungen entstehen durch Kombinieren und Reihen von Lösungselementen. Die Anzahl der zu überprüfenden Lösungen steigt mit der Problemgröße exponentiell. So ergeben sich z.B. bei der Bildung von Reihenfolgen für n Elemente n! verschiedene Möglichkeiten. Kombinatorische Optimierungsprobleme kann man grob unterteilen in:
• Reihenfolgeprobleme: Festlegen der Besuchs- oder Bearbeitungsreihenfolge, z.B. Maschinenbelegung, Traveling Salesman-Problem
• Gruppierungsprobleme: Bilden von Gruppen von Objekten, z.B. Bin Packing- und Losgrößenprobleme, Tourenplanung
• Zuordnungsprobleme: Festlegen von Zuordnungen zwischen Objekten, z.B. lineares Zuordnungsproblem, Personaleinsatzplanung Maximiere (1)
• Auswahlprobleme: Ermittlung einer oder mehrerer Teilmengen auszuwählender Objekte, z.B. Knapsack- Problem, Investitionsplanung

Viele kombinatorische Probleme sind als lineare (gemischt-) ganzzahlige bzw. (gemischt-) binäre Optimierungsmodelle formulier- und lösbar.

wichtiges Teilgebiet der mathematischen Optimierung und der Planungsmathematik des 0perations Research. Es geht dabei im wesentlichen um die Zuordnung, Gruppierung, Reihung und/oder Auswahl von Elementen aus einer Menge gemäss folgenden vier Grundtypen: (1) Zuordnungsprobleme: Die Elemente einer bestimmten Elementemenge sollen einzelnen Plätzen zugeordnet werden, z. B. verschiedene Maschinen verschiedenen Standorten ( Raumzuordnungsproblem). (2) Gruppierungsprobleme: Zerlegung einer Elementemenge in Untermengen, z. B. Bildung von Wahlkreisen oder von Kundengruppen ( Absatzplanungsmodelle, Clusteranalyse). (3) Reihungsprobleme: Anordnung von Elementen einer Elementemenge in einer Reihenfolge ( Traveling-Salesman-Problem). (4) Auswahlprobleme: Selektion einer Menge von Elementen aus einer umfassenden Elementemenge (Knapsack-Problem, Set- Covering-Problem, Set-Partitioning-Pro- blem, Set-Packing-Problem). Die meisten in der realen Welt auftretenden kombinatorischen Probleme enthalten gleichzeitig Komponenten von verschiedenen dieser Grundtypen. Beispiele für kombinatorische Probleme sind: • "Schulstundenproblem": Welcher Lehrer soll wann welche Klasse in welchem Fach unterrichten (Zuordnung, Gruppierung, Reihung) ? • Maschinenbeieguiigsplan ung: Wann soll welcher Auftrag auf welcher Maschine bearbeitet werden (Zuordnung, Gruppierung, Reihung) ? • Fliessbandabgleich: Welche Elementararbeiten sollen welchen Arbeitsplätzen zugeteilt werden (Zuordnung und Gruppierung)? • Personaleinsatzplanung, z. B. für eine Flug- verkehrsunternehmung: An welchem Kalendertag soll welcher Flugkapitän welchen Flug (von wo nach wo) auf welcher Maschine durchführen (Mehrfachzuordnung, Reihung, Auswahl)? • Chip-Bestückung: Welche Bauelemente sollen an welcher x-Position und an welcher y-Position eines Chips untergebracht werden (mehrfache Zuordnung und Reihung) ? Die meisten Probleme der kombinatorischen Optimierung umfassen eine Zielsetzung ( Zielfunktion) und ein Bündel an Bedingungen ( Restriktionen). Fast alle diese Probleme lassen sich in Modellen der ganzzahligen Optimierung formulieren. Nur für wenige Problemtypen der kombinatorischen Optimierung sind effiziente Rechenverfahren verfügbar. Effizient nennt man solche Verfahren, deren Rechenaufwand po- lynomial mit der Problemgrösse ansteigt. Diese Probleme werden als solche der "Klasse P" bezeichnet. Für die Mehrzahl der Probleme der kombinatorischen Optimierung gibt es bisher nur solche Entscheidungsbaumverfahren, bei denen der Rechenaufwand (mit Ausnahme der heuristischen Verfahren) gewöhnlich exponentiell - also wesentlich steiler als poly- nomial - mit der Problemgrösse ansteigt. Für die Entscheidungsbaumverfahren liegen nur allgemeine Arbeitsprinzipien vor. Für jeden unterschiedlichen Problemtyp sind auf der Basis dieser Prinzipien spezifische Algorithmen zu entwickeln. Insofern besteht ein grundsätzlicher Unterschied zu anderen Teilbereichen der mathematischen Optimierung, insb. zur linearen Optimierung, wo generell anwendbare Rechenverfahren zur Verfügung stehen. Literatur: Müller-Merbach, H., Operations Research, 3. Aufl., München 1973. Lawler, E. L., Combinatorial Optimization: Networks and Ma- troids, New York 1976. Hu, T. C., Combinatorial Algorithms, Reading, Mass. 1982.

Vorhergehender Fachbegriff: Kombinative Variation | Nächster Fachbegriff: kombinierte Anpassung

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Disclosure | Reihenfolgeprobleme | Protective Put

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