|
|
ganzzahliges Optimierungsproblem
ganzzahliges Programmierungsproblem.
I. Charakterisierung: Mathematisches Optimierungsproblem, bei dem mindestens eine der Strukturvariablen nur ganzzahlige Werte annehmen darf. - Arten: a) Vollständig-g. O.: Sämtliche Strukturvariablen müssen ganzzahlige Werte annehmen; gemischt-g. O.: Nur einige Strukturvariablen müssen ganzzahlige Werte annehmen. - b) Ganzzahlig-lineares Optimierungsproblem: ganzzahliges Optimierungsproblem O., in dem ausschließlich lineare Restriktionen (mit Ausnahme der Ganzzahligkeitsrestriktionen) und eine lineare Zielfunktion vorkommen; ganzzahlig-nichtlineares Optimierungsproblem: mindestens eine nichtlineare Restriktion und/oder eine nichtlineare Zielfunktion tritt auf. - c) Binäres Optimierungsproblem: Variablen dürfen nur den Wert 0 oder 1 annehmen.
II. Lösung: 1. Vorgehensweise: Es kann zunächst ein entsprechendes kontinuierliches Optimierungsproblem gelöst werden, um dann (sofern erforderlich) durch nachträgliches Runden eine Lösung des ursprünglichen Problems zu ermitteln. Der so gefundene Vektor der Variablenwerte kann aber von der gesuchten optimalen Lösung verschieden oder sogar überhaupt keine zulässige Lösung des betreffenden Restriktionssystems sein. - 2. Methoden: a) Für ganzzahlige klassische Transportprobleme mit ganzzahligen Vorrats- und Bedarfsmengen, lineare Zuordnungsprobleme und gewisse Flußprobleme in Netzwerken läßt sich zeigen, daß die Basislösungen der jeweiligen Optimierungssysteme stets ganzzahlig sind und sie deshalb (zumindest theoretisch) mit den Methoden der (kontinuierlichen) linearen Optimierung angegangen werden können. - b) Sofern keine dieser speziellen Problemstrukturen vorliegt, werden in der Literatur Schnittebenenverfahren zur Bestimmung optimaler, die Ganzzahligkeitsrestriktionen erfüllenden Lösungen vorgestellt. Numerische Stabilität und Rechenzeitverhalten dieser Verfahren befriedigen aber häufig selbst bei kleineren ganzzahlig-linearen Problemen nicht. - c) Tendenziell günstiger sind Branch-and-Bound-Verfahren, die aber nicht in jedem Fall in akzeptabler Rechenzeit die gesuchte Lösung liefern. - d) Bei größeren Problemen ist man deshalb auf den Einsatz von Heuristiken angewiesen (z. B. quadratisches Zuordnungsproblem). - 3. Einsatz kommerzieller Software: Branch-and-Bound-Verfahren bilden die Grundlage zur Lösung ganzzahlig-linearer Optimierungsprobleme. Mit derartiger Software läßt sich eine Vielzahl von Problemen realer Größenordnungen innerhalb eines akzeptablen Zeitrahmens optimal lösen. Bei sehr großen Problemen ohne eine besonders ausgeprägte spezielle Struktur muß man sich auch hier häufig mit der besten ganzzahligen Lösung zufrieden geben, die bis zum Erreichen einer Zeitschranke gefunden wurde.
III. Ökonomische Bedeutung: Streng genommen ist eine Vielzahl ökonomischer Probleme ganzzahlig, v. a. läßt sich der Einsatz von Arbeitskräften und Maschinen nicht immer sinnvoll in reellwertigen Variablen ausdrücken. Ähnliches gilt häufig für den Einsatz von Vorprodukten bzw. den Ausstoß von Zwischen- und Endproduktion, v. a. wenn die betreffende Bezugsgröße ein Fertigungslos ist. Entsprechend entstehen g. O. schwerpunktmäßig bei der Investitionsprogrammplanung, der Personaleinsatzplanung, der Produktprogrammplanung sowie der Ablaufplanung. Außerdem können "Ja-Nein"-Entscheidungsprobleme als binäre Optimierungsprobleme modelliert werden.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
