Definition:Linear Programming

Definition

Linear programming is the branch of mathematical programming which finds optimal solutions of mathematical models whose requirements are represented by linear relationships.

Such optimal solutions may be maximizations or minimizations.

The sort of functions which are being maximized often represent:

profits

volumes of goods to be produced

and so on.

The sort of functions which are being minimized often represent:

production costs

production times

and so on.

Examples

Arbitrary Example

Let it be required to find the minimum of the function:

$\map U {x, y} = 4 x + 3 y$

subject to the conditions:

\(\ds x + y\)

\(\le\)

\(\ds 20\)

\(\ds 3 x + y\)

\(\le\)

\(\ds 30\)

\(\ds x\)

\(\ge\)

\(\ds 0\)

\(\ds y\)

\(\ge\)

\(\ds 0\)

The maximum feasible value of $U$ is given by:

$U = 65$

Also see

• Definition:Karmarkar's Algorithm

• Results about linear programming can be found here.

Historical Note

The mathematical discipline of linear programming arose from problems in economics of maximization and minimization that could not be solved using the methods of calculus.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): linear programming
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): linear programming
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): linear programming