Ganzzahlige Optimierung

Die bereits im Online-Kurs Operations Research 1 angewandten Methoden der linearen Optimierung dienen zum Großteil zur Bestimmung des optimalen Produktions- oder Investitionsprogramms. Die dort ermittelten Lösungen waren sowohl ganzzahlig als auch nicht ganzzahlig.

Häufig ist es erforderlich, dass bei der Lösung solcher Probleme ganzzahlige Lösungen resultieren. Hierzu wird die ganzzahlige Optimierung herangezogen. Diese schließt nicht-ganzzahlige Lösungen aus und lässt demnach nur ganzzahlige Lösungen zu. Der Unterscheid zur linearen Optimierung besteht darin, dass innerhalb der Nebenbedingungen die Zusatzbedingungen der Ganzzahligkeit für alle oder einige Variablen eingeführt wird. Es ist auch möglich, dass die Variablen nur die Werte 0 und 1 annehmen dürfen. Will ein Unternehmen beispielsweise eine Investitionsplanung durchführen, dann möchte das Unternehmen wissen, ob eine Investition durchgeführt werden soll ($x = 1$) oder nicht durchgeführt werden soll ($x = 0$). Das Ergebnis sind also Binärzahlen.

In den folgenden Abschnitten werden einige Verfahren zur Lösung von ganzzahligen Optimierungsproblemen aufgezeigt und ausführlich erläutert. Hierzu zählen:

• Das grafische Verfahren,
  
  
• das Verfahren von Gomory,
  
  
• das Branch-and-Bound-Verfahren sowie
  
  
• das Verfahren der vorsichtigen Annäherung.