3.8 Lineare Optimierung

Die lineare Optimierung beschäftigt sich damit, eine Zielfunktion (lineare Funktion) unter bestimmten linearen Nebenbedingungen zu maximieren oder minimieren. Typische Beispiele sind Ressourcenplanungen oder Transportprobleme, bei denen man Kosten (Zielfunktion) unter begrenzten Kapazitäten (Nebenbedingungen) optimieren möchte.

1. Grundidee

• Zielfunktion: Eine lineare Funktion $z(x)=c_1{x}_1+c_2{x}_2+\dots +c_n{x}_n,$ wobei $x=(x_1,\dots ,x_n)$ die Variablen und $c_1,\dots ,c_n$ gegebene Koeffizienten sind.

• Ziel: Maximiere (oder minimiere) $z(x)$ unter Einhaltung bestimmter Nebenbedingungen wie

  $$\begin{array}{rl}& a_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n\le b_1,\\ & a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n\le b_2,\\ & ⋮\\ & a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n\le b_m,\\ & x_j\ge 0(j=1,\dots ,n).\end{array}$$

  Diese linearen Nebenbedingungen beschreiben den Lösungsraum.

2. Formale Definition: Lineare Programme

Ein lineares Programm (LP) hat die Form

$\text{Maximiere }z(x)=c^{\mathsf{T}}x\text{unter}Ax\le b,x\ge 0.$

• $x\in {\mathbb{R}}^n$ sind die Variablen.
• $c\in {\mathbb{R}}^n$ sind die Zielfunktions-Koeffizienten.
• $A$ ist eine $(m\times n)$-Matrix, $b\in {\mathbb{R}}^m$ geben die Nebenbedingungen an.

3. Lösungsraum und Nebenbedingungen

• Der Lösungsraum (feasible region) ist die Menge aller $x$, die alle Nebenbedingungen erfüllen:$$\{x\in {\mathbb{R}}^n\mid Ax\le b,x\ge 0\}.$$
• Geometrisch gesehen ist dieser Lösungsraum ein Polyeder (Schnitt endlich vieler Halbräume).

4. Beispiel für ein lineares Programm

Betrachte ein kleines Transportproblem:

$$\begin{array}{rl}\text{Maximiere }& z(x_1,x_2)=3x_1+2x_2\\ \text{unter }& x_1+x_2\le 10,\\ & 2x_1+x_2\le 16,\\ & x_1,x_2\ge 0.\end{array}$$

• Zielfunktion: $3x_1+2x_2$
• Nebenbedingungen: Zwei lineare Ungleichungen und Nichtnegativität.
• Visualisiert man die Ungleichungen in der $(x_1,x_2)$-Ebene, erhält man eine polygonale Lösungsmenge.
• Bei linearen Programmen liegt mindestens eine optimale Lösung in Eckpunkten (Extrempunkten) dieses Polygons.

5. Simplex-Verfahren

Das Simplex-Verfahren ist ein algorithmisches Verfahren, um lineare Programme zu lösen:

1. Startlösung: Wähle eine Basislösung (etwa Eckpunkt) als Start.
2. Pivot-Schritt: Überprüfe, ob man durch Verschieben zu einem benachbarten Eckpunkt den Zielfunktionswert verbessern kann.
3. Abbruch: Das Verfahren terminiert, wenn keine Verbesserung mehr möglich ist (optimum gefunden) oder das Problem unbeschränkt ist (Zielfunktion kann ins Unendliche gesteigert werden).

5.1 Ablauf des Simplex

• Man konstruiert eine Tableau-Darstellung, analog zu einer erweiterten Matrix.
• In Pivot-Schritten (ähnlich dem Gauß-Algorithmus) verbessert man iterativ die Lösung.
• Falls das LP eine endliche optimale Lösung besitzt, findet Simplex diese in endlich vielen Schritten.

Hinweis: Es gibt weitere Verfahren (z. B. Innere-Punkte-Verfahren), doch Simplex ist eines der klassischen und praktisch sehr wichtigen Algorithmen.