Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online lexicon:

Linear Program

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 overview
The minimization of a linear function

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

subject to the constraints

$\displaystyle Ax \ge b $

with an $ m\times n$-matrix $ A$ is called a linear program. A solution $ x_\star \in \mathbb{R}^n$ satisfies the Kuhn-Tucker conditions,

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

with $ \lambda_i \ge 0$ (for a maximum, $ \lambda_i \le 0$).

For the concrete example

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

we have

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

and the Kuhn-Tucker conditions are

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

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

with $ \lambda$, $ \varsigma$, $ \delta$, $ [\dots]$ $ \geq 0$. Obviously, exactly one of the Lagrange multipliers must be zero. For each of the three cases, two constraints are active and determine $ x$ and $ y$ uniquely:

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

A comparison of the values of the target function $ f$ shows that the minimum is attained at $ (2,3)$. The corresponding Lagrange multipliers are $ \lambda=1$, $ \delta=1$.

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

The figure illustrates a geometric construction of the solution. The solution $ (2,3)$ is the point where a level line of the target function touches the shaded admissible region. Clearly, the target function increases (decreases) if the level lines begin to intersect (not intersect) the admissible region.

Examples:

[Annotations] [Links]
  automatically generated 1/26/2017