Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon:

Lineares Programm

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Die Minimierung einer linearen Funktion

$\displaystyle (c_1, \dots, c_n)x \mapsto \textrm{min} $

unter linearen Nebenbedingungen

$\displaystyle Ax \ge b $

mit einer $ m\times n$-Matrix $ A$ bezeichnet man als lineares Programm. Eine Lösung $ x_\star \in \mathbb{R}^n$ erfüllt die Kuhn-Tucker-Bedingung, falls

$\displaystyle c^{\text{t}}=\lambda^{\text{t}}A, \quad \lambda^{\text{t}}(Ax_\star-b)=0 $

mit $ \lambda_i \ge 0$. Für ein Maximun gilt entsprechend $ \lambda_i \le 0$.

Für das konkrete Beispiel

$\displaystyle x+y \mapsto$   min$\displaystyle , \quad x+2y \ge 8, x\ge4, y\ge 3 $

ist

$\displaystyle c= \left( \begin{array}{c} 1 \\ 1 \\ \end{array} \right),... ...uad b= \left( \begin{array}{c} 8 \\ 4 \\ 3 \\ \end{array} \right) $

und man erhält die Kuhn-Tucker-Bedingung

$\displaystyle 1=\lambda+\varsigma, 1=2\varsigma+\delta $

$\displaystyle \lambda[x+2y-8] \mp \varsigma[x-4]=\delta[y-3]=0 $

mit $ \lambda$, $ \varsigma$, $ \delta$, $ [\dots]$ $ \geq 0$. Man erkennt schnell, dass genau einer der Lagrange-Multiplikator gleich Null sein muss. Für die drei Fälle sind dann jeweils zwei Nebenbedingungen aktiv. Diese legen $ x$ und $ y$ eindeutig fest:

\begin{displaymath} \begin{array}{c} \lambda = 0 \mapsto (4,3) \\ \varsigm... ...\mapsto (2,3) \\ \delta = 0 \mapsto (4,2) \\ \end{array} \end{displaymath}

Vergleich der Zielfunktionswerte $ x+y$ zeigt, dass das Minimum bei $ (2,3)$ angenommen wird. Die zugehörigen Lagrange-Multiplikatoren sind $ \lambda=1$, $ \delta=1$.

\includegraphics[width=0.4\linewidth]{Bild_Lineares_Programm}

Eine geometrische Konstruktion der Lösung ist in der Abbildung illustriert. Die Lösung $ (2,3)$ ist der Punkt in dem eine Niveaugerade der Zielfunktion den schraffierten zulässigen Bereich berührt. Es ist offensichtlich, dass die Zielfunktion ansteigt (fällt), wenn die Niveaugeraden den zulässigen Bereich schneiden (nicht schneiden).

Beispiele:

[Erläuterungen] [Verweise]
  automatisch erstellt am 26.  1. 2017