Anhang A
Ganzzahlige Lineare Programmierung
In diesem Buch wird der Anhang benutzt, um grundlegende Kenntnisse zu vermitteln, die für das Verständnis der vorangegangenen Kapitel erforderlich sind, die
man aber nicht unbedingt voraussetzen kann. Dabei werden drei Themenkreise
behandelt. Im aktuellen Anhang wird die Ganzzahlige Lineare Programmierung
vorgestellt. Die Ganzzahlige Lineare Programmierung (engl. Integer Linear Programming (ILP)) ist eine mathematische Optimierungstechnik, die auf eine große
Zahl von Optimierungsproblemen anwendbar ist. ILP-Modelle sind ein allgemeiner
Ansatz, um Optimierungsprobleme zu lösen.
ILP-Modelle bestehen aus zwei Teilen: einer Kostenfunktion und einer Menge an
Nebenbedingungen. Beide Teile referenzieren eine Menge X = {x i } ganzzahliger
Variablen. Die Kostenfunktionen müssen lineare Funktionen dieser Variablen sein.
Damit haben sie die allgemeine Form
C =
i
a i x i , with a i ∈ R, x i ∈ N 0
(A.1)
Die Menge der Nebenbedingungen J muss ebenfalls aus linearen Funktionen über
ganzzahligen Variablen bestehen. Diese müssen folgende Form haben:
∀j ∈ J :
i
b i, j x i ≥ c j with b i, j , c j ∈ R
(A.2)
Definition A.1: Die Ganzzahlige Lineare Programmierung (ILP) beschreibt die
Aufgabe, die Kostenfunktion von Gleichung (A.1) unter den gegebenen Nebenbedingungen von Gleichung (A.2) zu minimieren. Wenn alle Variablen entweder
den Wert 0 oder 1 annehmen müssen, dann wird das entsprechende Modell ein
0/1-ILP-Modell genannt. In diesem Fall werden die Variablen auch als (binäre)
Entscheidungsvariablen bezeichnet.
Hierbei kann in Gleichung (A.2) ≥ durch ≤ ersetzt werden, wenn die Konstanten
b i, j entsprechend angepasst werden. Der Fall von negativen Variablen x i entsteht,
wenn man zulässt, dass x i einen beliebigen ganzzahligen Wert annehmen kann.
Er kann in den Fall nicht-negativer Variablen gewandelt werden, indem man die
425
P. Marwedel, Eingebettete Systeme, https://doi.org/10.1007/978-3-658-33437-6
© Der/die Autor(en) 2021
Ganzzahlige Lineare Programmierung
In diesem Buch wird der Anhang benutzt, um grundlegende Kenntnisse zu vermitteln, die für das Verständnis der vorangegangenen Kapitel erforderlich sind, die
man aber nicht unbedingt voraussetzen kann. Dabei werden drei Themenkreise
behandelt. Im aktuellen Anhang wird die Ganzzahlige Lineare Programmierung
vorgestellt. Die Ganzzahlige Lineare Programmierung (engl. Integer Linear Programming (ILP)) ist eine mathematische Optimierungstechnik, die auf eine große
Zahl von Optimierungsproblemen anwendbar ist. ILP-Modelle sind ein allgemeiner
Ansatz, um Optimierungsprobleme zu lösen.
ILP-Modelle bestehen aus zwei Teilen: einer Kostenfunktion und einer Menge an
Nebenbedingungen. Beide Teile referenzieren eine Menge X = {x i } ganzzahliger
Variablen. Die Kostenfunktionen müssen lineare Funktionen dieser Variablen sein.
Damit haben sie die allgemeine Form
C =
i
a i x i , with a i ∈ R, x i ∈ N 0
(A.1)
Die Menge der Nebenbedingungen J muss ebenfalls aus linearen Funktionen über
ganzzahligen Variablen bestehen. Diese müssen folgende Form haben:
∀j ∈ J :
i
b i, j x i ≥ c j with b i, j , c j ∈ R
(A.2)
Definition A.1: Die Ganzzahlige Lineare Programmierung (ILP) beschreibt die
Aufgabe, die Kostenfunktion von Gleichung (A.1) unter den gegebenen Nebenbedingungen von Gleichung (A.2) zu minimieren. Wenn alle Variablen entweder
den Wert 0 oder 1 annehmen müssen, dann wird das entsprechende Modell ein
0/1-ILP-Modell genannt. In diesem Fall werden die Variablen auch als (binäre)
Entscheidungsvariablen bezeichnet.
Hierbei kann in Gleichung (A.2) ≥ durch ≤ ersetzt werden, wenn die Konstanten
b i, j entsprechend angepasst werden. Der Fall von negativen Variablen x i entsteht,
wenn man zulässt, dass x i einen beliebigen ganzzahligen Wert annehmen kann.
Er kann in den Fall nicht-negativer Variablen gewandelt werden, indem man die
425
P. Marwedel, Eingebettete Systeme, https://doi.org/10.1007/978-3-658-33437-6
© Der/die Autor(en) 2021