 [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] 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 subject to the constraints with an -matrix is called a linear program. A solution satisfies the Kuhn-Tucker conditions, with (for a maximum, ).

For the concrete example min we have and the Kuhn-Tucker conditions are  with , , ,  . Obviously, exactly one of the Lagrange multipliers must be zero. For each of the three cases, two constraints are active and determine and uniquely: A comparison of the values of the target function shows that the minimum is attained at . The corresponding Lagrange multipliers are , . The figure illustrates a geometric construction of the solution. The solution 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.

Annotation: