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

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),...
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:

\lambda = 0 \mapsto (4,3) \\
...\mapsto (2,3) \\
\delta = 0 \mapsto (4,2) \\

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$.


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