Gemischt-ganzzahlige Optimierung

In vielen Anwendungsproblemen dürfen die Variablen nur ganzzahlige (oft sogar nur binäre) Wert annehmen. In diesem Fall muß man ein lineares Programm um spezielle Nebenbedingungen erweitern, die die Ganzzahligkeit (aller oder) einiger Entscheidungsvariablen sichern. Das sieht dann so aus:

1

Hier sind einige Beispiele:

Knapsack-Problem (Rucksack-Problem):

Ein Bauer will seine Produkte auf dem Markt verkaufen. Das Produkt j bringt ihm einen Stückgewinn von cj GE und wiegt aj Kilogramm. Der Bauer kann maximal b Kilogramm in seinem Rucksack tragen. Das Problem lautet damit: Welche Produkte soll der Bauer zum Markt tragen, wenn er seinen Gewinn maximieren will?

2

Läßt man für die Variablen $x_j$ kontinuierliche Wert zu, dann entsteht das kontinuierliche Knapsack-Problem.

Standort-Problem (Simple Plant Location Problem):

3

Verallgemeinertes Zuordnungsproblem:

Erweitert man das klassische Zuordnungsproblem um die Option, daß jedem Agenten aus der ersten Gruppe mehrere Agenten aus der zweiten Gruppe zugeordnet werden können, dann erhält man das verallgemeinerte Zuordnungsproblem:

3