426
A Ganzzahlige Lineare Programmierung
Konstanten mit -1 multipliziert. Anwendungen, welche die Maximierung einer
Gewinnfunktion C ′ erfordern, können in die obige Form gebracht werden, indem
C = −C ′ gesetzt wird.
Beispiel A.1: Unter der Annahme, dass x 1 , x 2 und x 3 ganzzahlig sein müssen, stellt
das folgende Gleichungssystem ein 0/1-ILP-Modell dar:
C = 5x 1 + 6x 2 + 4x 3
(A.3)
x 1 + x 2 + x 3 ≥ 2
(A.4)
x 1 ≤ 1
(A.5)
x 2 ≤ 1
(A.6)
x 3 ≤ 1
(A.7)
Durch die Nebenbedingungen nehmen alle Variablen entweder den Wert 0 oder 1 an.
Es gibt vier mögliche Lösungen, diese sind in Tabelle A.1 aufgeführt. Die Lösung
mit Kosten von 9 ist optimal.
Tabelle A.1 Mögliche Lösungen des vorgestellten ILP-Problems
x 1 x 2 x 3 C
0
1
1 10
1
0
1
9
1
1
0 11
1
1
1 15
∇
ILP ist eine besondere Variante der Linearen Programmierung (LP). Bei Linearer
Programmierung können Variablen beliebige reelle Werte annehmen. ILP- und LPModelle sind optimal durch Anwendung mathematischer Programmiertechniken
lösbar. Leider ist ILP NP-vollständig (LP hingegen nicht) und die Ausführung einer
ILP-Optimierung kann sehr viel Zeit erfordern.
Dennoch sind ILP-Modelle nützlich, um Optimierungsprobleme zu modellieren,
solange die Modelle nicht sehr groß werden. Die Modellierung von Optimierungsproblemen als ILP-Probleme ist trotz der Komplexität des Problems sinnvoll: viele
Probleme lassen sich in akzeptabler Zeit lösen. Wenn dies einmal nicht der Fall ist,
liefert das ILP-Modell einen guten Ausgangspunkt zur Entwicklung von Heuristiken. Die Ausführungszeit hängt von der Anzahl der Variablen und der Anzahl und
Beschaffenheit der Nebenbedingungen ab. Gute ILP-Löser (wie lp_solve [17] oder
CPLEX) können gut strukturierte Probleme mit einigen tausend Variablen in akzeptabler Zeit, meist im Bereich von Minuten, lösen. Mehr Informationen zum Thema
ILP und LP findet man in Fachliteratur zu diesen Themen, z.B. bei Wolsey [594].
A Ganzzahlige Lineare Programmierung
Konstanten mit -1 multipliziert. Anwendungen, welche die Maximierung einer
Gewinnfunktion C ′ erfordern, können in die obige Form gebracht werden, indem
C = −C ′ gesetzt wird.
Beispiel A.1: Unter der Annahme, dass x 1 , x 2 und x 3 ganzzahlig sein müssen, stellt
das folgende Gleichungssystem ein 0/1-ILP-Modell dar:
C = 5x 1 + 6x 2 + 4x 3
(A.3)
x 1 + x 2 + x 3 ≥ 2
(A.4)
x 1 ≤ 1
(A.5)
x 2 ≤ 1
(A.6)
x 3 ≤ 1
(A.7)
Durch die Nebenbedingungen nehmen alle Variablen entweder den Wert 0 oder 1 an.
Es gibt vier mögliche Lösungen, diese sind in Tabelle A.1 aufgeführt. Die Lösung
mit Kosten von 9 ist optimal.
Tabelle A.1 Mögliche Lösungen des vorgestellten ILP-Problems
x 1 x 2 x 3 C
0
1
1 10
1
0
1
9
1
1
0 11
1
1
1 15
∇
ILP ist eine besondere Variante der Linearen Programmierung (LP). Bei Linearer
Programmierung können Variablen beliebige reelle Werte annehmen. ILP- und LPModelle sind optimal durch Anwendung mathematischer Programmiertechniken
lösbar. Leider ist ILP NP-vollständig (LP hingegen nicht) und die Ausführung einer
ILP-Optimierung kann sehr viel Zeit erfordern.
Dennoch sind ILP-Modelle nützlich, um Optimierungsprobleme zu modellieren,
solange die Modelle nicht sehr groß werden. Die Modellierung von Optimierungsproblemen als ILP-Probleme ist trotz der Komplexität des Problems sinnvoll: viele
Probleme lassen sich in akzeptabler Zeit lösen. Wenn dies einmal nicht der Fall ist,
liefert das ILP-Modell einen guten Ausgangspunkt zur Entwicklung von Heuristiken. Die Ausführungszeit hängt von der Anzahl der Variablen und der Anzahl und
Beschaffenheit der Nebenbedingungen ab. Gute ILP-Löser (wie lp_solve [17] oder
CPLEX) können gut strukturierte Probleme mit einigen tausend Variablen in akzeptabler Zeit, meist im Bereich von Minuten, lösen. Mehr Informationen zum Thema
ILP und LP findet man in Fachliteratur zu diesen Themen, z.B. bei Wolsey [594].