|
|
binäres Optimierungsproblem
binäres Programmierungsproblem, Boolesches Optimierungs- bzw. Programmierungsproblem, 0-1-Optimierungsproblem. 1. Begriff: Mathematisches Optimierungsproblem (genauer ganzzahliges Optimierungsproblem), bei dem mindestens eine der Variablen nur die (ganzzahligen) Werte 0 oder 1 annehmen darf, d. h. die betreffende Variable ist eine Binärvariable. - 2. Arten: a) Vollständiges b. O.: Sämtliche Strukturvariablen sind Binärvariablen; gemischt-b. O.: Nur einige, aber nicht alle Strukturvariablen sind Binärvariablen. - b) Linear-b. O.: Optimierungsproblem, in dem - mit Ausnahme der 0-1-Restriktionen - nur lineare Restriktionen und eine lineare Zielfunktion vorkommen; nichtlinear-b. O.: Mindestens eine nichtlineare Restriktion und/oder eine nichtlineare Zielfunktion treten auf. - c) binäres Optimierungsproblem O. mit spezieller Struktur: Rucksackproblem, Fixkostenproblem, lineares Zuordnungsproblem und quadratisches Zuordnungsproblem. - 3. Lösungsmethoden: a) Schnittebenenverfahren führen bei Praxisproblemen nur selten zu einem befriedigenden Rechenzeitverhalten. - b) Bei den in kommerziellen Softwarepaketen implementierten Algorithmen handelt es sich meist um Branch-and-Bound-Verfahren, kombiniert mit einer Reihe weiterer Techniken, die vor der eigentlichen Optimierungsphase eingesetzt werden, um die Konsistenz des Problems zu prüfen und um es ggf. zu vereinfachen. Jüngere Entwicklungen zeigen, daß v. a. vollständig b. O. realer Größenordnungen in angemessener Rechenzeit bewältigt werden können. - 4. Ökonomische Anwendungen: Die mathematische Formulierung einer ganzen Reihe ökonomischer Entscheidungsprobleme führt auf b. O., v. a. wenn "Ja-Nein"- bzw. "Entweder-Oder"-Entscheidungen zu modelliern sind, z. binäres Optimierungsproblem bei Problemen der betrieblichen und innerbetrieblichen Standortplanung, der Auftrags- bzw. Maschinenreihenfolgeplanung und der Personaleinsatzplanung. Darüber hinaus lassen sich Situationen, bei denen entscheidungsrelevante Fixkosten zu berücksichtigen sind, mit Hilfe von Binärvariablen erfassen. Ferner dienen Binärvariablen der Linearisierung ursprünglich nichtlinearer Zielfunktionen.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
