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:
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?
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:
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: