Schöner absteigen mit ganzzahliger Optimierung
Axel Werner 

Zu Beginn einer neuen Bundesliga-Saison stellt sich für die eine oder
andere Mannschaft die Frage, wieviele Punkte mindestens eingefahren werden
müssen, um den Abstieg zu vermeiden. Es gibt die 40-Punkte-Regel, die
besagt, dass man mit 40 Punkten auf der sicheren Seite ist. Aber stimmt
das tatsächlich...?

Wenn man Pech hat bekommen vielleicht die letzten 4 Mannschaften alle
relativ viele Punkte, und dann ist man plötzlich mit mehr als 40 Punkten
doch noch abgestiegen. Ist das möglich, und wenn ja, wieviele Punkte
braucht man tatsächlich, um dem Abstieg mit Sicherheit zu entgehen? Bei 18
Mannschaften kann das leicht unübersichtlich werden, gibt es doch fast
$10^{146}$ Möglichkeiten dafür, wie so eine Saison ausgehen kann.

Um solche und ähnliche Fragen zu beantworten stellen wir ein ganzzahliges
lineares Programm, ein sogenanntes IP auf und lassen es vom Computer
lösen. Wenn man nicht allzu viele Details berücksichtigen will, gibt es
auch nur relativ wenige, unkomplizierte Nebenbedingungen. Will man zum
Beispiel Torverhältnisse mit in die Rechnung einbeziehen, werden die
Nebenbedingungen schon verzwickter. Wenn wir geeignete Zielfunktionen
wählen, lassen sich die unterschiedlichsten extremen Konstellationen
betrachten.

Die Frage allerdings, ob es noch Hoffnung für Hertha gibt, wird unser IP
auch nicht beantworten können; spätestens wenige Stunden nach dem Vortrag
werden wir aber auch hier Bescheid wissen...