Was ist mathematische Optimierung und Programmierung?

Die mathematische Optimierung bzw. Programmierung beschäftigt sich mit der Bestimmung einer optimalen Lösung aus einer Menge von zulässigen Lösungen. Die Menge der zulässigen Lösungen wird im Allgemeinen durch sog. Restriktionen (engl.: constraints) über den Entscheidungsvariablen definiert. Die "Optimalität" wird durch Angabe einer sog. "Zielfunktion" über den Entscheidungsvariablen definiert, die es zu maximieren oder minimieren gilt. Typische Beispiele sind die Kostenminimierung oder die Deckungsbeitragsmaximierung.

Je nach Struktur der Entscheidungsvariablen oder der Restriktionen erhält man spezielle mathematische Optimierungs- bzw. -Programmierungsprobleme. Bekannte Beispiele sind:

  • Lineare Programmierungsprobleme: Die Entscheidungsvariablen sind nicht-negative reelle Variablen und die Zielfunktion und alle Restriktionen sind lineare Funktionen.
  • Ganzzahlige (lineare) Programmierungsprobleme: Die Entscheidungsvariablen sind nicht-negative ganzzahlige Variablen und die Zielfunktion und alle Restriktionen sind lineare Funktionen.
  • Gemischt-ganzzahlige (lineare) Programmierungsprobleme: Die Entscheidungsvariablen sind nicht-negative ganzzahlige oder reelle Variablen und die Zielfunktion und alle Restriktionen sind lineare Funktionen.
  • Quadratische Programmierungsprobleme: Die Entscheidungsvariablen sind nicht-negative reelle Variablen,  die Zielfunktion ist eine quadratische Funktion und alle Restriktionen sind lineare Funktionen.
  • Nichtlineaere Programmierungsprobleme: Die Entscheidungsvariablen sind nicht-negative reelle Variablen,  die Zielfunktion und alle Restriktionen sind lineare oder nichtlineare Funktionen.

Während die Lösung von linearen und quadratischen Programmierungsproblemen mit dem Simplex-Algorithmus oder anderen Algorithmen sowohl theoretisch betrachtet als auch in der Praxis relativ einfach ist, ist das Lösen von Problemen aus den anderen Klassen auch heute noch schwierig. Allerdings hat der Fortschritt bei der Entwicklung von Algorithmen und den darauf aufbauenden Programmern (den sog. Solvern) in den letzten 20 Jahren dazu geführt, dass man heute auch schwierige gemischt-ganzzahlige oder nichtlineare Programmierungsprobleme lösen kann.