Definition:Linear Programming

From ProofWiki
Jump to navigation Jump to search


Linear programming is the branch of mathematical programming which studies optimization of mathematical models whose requirements are represented by linear relationships.

Such optimizations may be maximizations or minimizations.

The sort of functions which are being maximized often represent:

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.


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

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