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.


[Examples] [Links]

  automatically generated 1/26/2017