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

Standort-Problem:
Erweitert man das klassische Transportproblem um die Option, bestimmte Angebotsorte zu nutzen oder nicht, dann erh lt man das einfache Standortproblem. In seiner einfachsten Form kann es wie folgt beschrieben werden:

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:

4