ZU DEN KURSEN!

Operations Research 1 - Definition: Lineares Programm

Kursangebot | Operations Research 1 | Definition: Lineares Programm

Operations Research 1

Definition: Lineares Programm

Inhaltsverzeichnis

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

$f(x_1, x_2, ... , x_n) = c x_1 + c x_2 + ... c 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.