ZU DEN KURSEN!

Operations Research 2 - Definition: Lineares Programm

Kursangebot | Operations Research 2 | Definition: Lineares Programm

Operations Research 2

Definition: Lineares Programm

Ein lineares Programm besteht zunächst einmal aus einer zu maximierenden bzw. zu minimierenden linearen Zielfunktion:

$f(x_1, x_2, ... , x_n) = c_1 x_1 + c_2 x_2 + ... c_3 x_n = \sum_{j = 1}^n c_j x_j$    $\rightarrow $   max / min

Merke

Die in der Zielfunktion auftretenden Variablen $(x_1, x_2, ..., x_n)$ nennt man Entscheidungsvariablen.

Es müssen zusätzlich die linearen Nebenbedingungen (=Restriktionen) berücksichtigt werden:

$a_{ij} x_j + ... + a_{in} x_n = b_i$

$a_{ij} x_j + ... + a_{in} x_n \le b_i$

$a_{ij} x_j + ... + a_{in} x_n \ge b_i$

mit

$i = 1, ..., m$  und   $j = 1, ..., n$.

Häufig muss auch die Nichtnegativitätsbedingung erfüllt sein:

$x_1, x_2, ..., x_n \ge 0$

Merke

Bei den meisten Aufgaben aus der Praxis gibt es eine Beschränkung der Entscheidungsvariablen auf Werte größer/gleich Null (Nichtnegativitätsbedingung). Grund dafür ist, dass diese in der Regel keine negativen Werte annehmen können. So kann zum Beispiel ein Unternehmen keine "negative Anzahl" an Produkten produzieren.

Definition der Lösungen

  • Jede Lösung $\vec{x} = (x_1, x_2, ..., x_n)$ , die alle obigen Nebenbedingungen erfüllt, heißt Lösung des LP.

  • Erfüllt $\vec{x}$ zusätzlich die Nichtnegativitätsbedingungen, so heißt $\vec{x}$ zulässige Lösung des LP.

  • Es handelt sich um eine optimale Lösung $\vec{x}^* = (x_1^*, x_2^*, ..., x_n^*)$ des LP, wenn kein $\vec{x}$ mit kleinerem (bei einem Minimierungsproblem) bzw. größerem (bei einem Maximierungsproblem) Zielfunktionswert $f(x_1^*, x_2^*, ..., x_n^*)$ existiert.

  • Mit $X$ wird die Menge aller zulässiger Lösungen eines LP bezeichnet, mit $X^*$ die Menge aller optimalen Lösungen eines LP.