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

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.

If the rows of $ A$, which are multiplied with positive $ \lambda_i$, are linearly independent, the characterization is an immediate consequence of the Kuhn-Tucker conditions for the general nonlinear case. For linear problems, redundant constraints, which cause linear dependence, can be omitted, and we can restrict ourselves to the nondegenerate case.

[Back]
  automatisch erstellt am 26.  1. 2017