Linear programming is very useful to model and solve production and network flow problems, and many other types of problems. An LP problem is a problem with a linear objective function and constraints which are either linear equations or linear inequalities. Here is an example for a LP problem:
The first ideas of how to solve LP problems date back to 200 years ago. This is not so surprising since LP problems are strongly linked to linear algebra which is an old subject. However, these early ideas were more of a theoretical nature and they were not used to solve any real world problems. George Dantzig developed the simplex algorithm and applied LP solution techniques to planning problems in the american military during the second world war. After the second world war until now there have been advances and continuous research in this area. Also the increase of power of computers has made it possible to apply LP codes to more and larger problems in industry and commerce.
Consider the following small example: A company produces fertilizers of type A and B. One tonne of type A fertilizer consists of 30% nitrogen and requires 3 tonnes of water in the production process. One tonne of type B fertilizer consists of 50% nitrogen and requires 4 tonnes of water in the production process. One tonne of type A fertilizer can be sold for 1000 Euro and one tonne of type B for 1300 Euro. The company can use at most 100 tonnes of water and 11 tonnes of nitrogen per day. How many tonnes of fertilizer of each type should the company produce to maximise its revenue? If and are the daily produced amounts in tonnes of fertilizers A and B respectively then this problem can be formulated in the linear programming form which was given above as an LP example.
If a LP problem has the additional constraint that some (or all)
variables must be integer then this is called a mixed integer programming
problem (or integer programming problem).
Mixed integer programming, abbreviated MIP, problems are much harder
to solve than LPs. LPs with 1000 variables and constraints are considered
small today, whereas MIP problems of that size generally can not be
solved to global optimality.
MIP problems are so important because it is possible to model
yes-no type decisions with 0-1 variables and also because for a lot
of problems certain objects must be integer.
For example, when modelling the number of planes an airline should order,
the number of planes should of course be an integer. To order
2.6 planes does not make much sense.
For further information about LP and MIP look up their frequently asked
questions web page.