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.

see also:

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