Defining Linear Programming

Linear programming (LP) is a mathematical technique for solving real world problems. It will describe the situation, the requirements and constraints that define the problem, in mathematical terms using variables and state the relationship of these variables in linear equations. The equations are solved through the application of algorithms which are a set of instructions defining a process of calculations. The objective is to figure out the best possible outcome which means that the solution would show either the maximum or minimum values for the variables. The process of solving a problem expressed in linear programming fashion is called optimization.

Today linear programming problems are more efficiently computed through the use of computers and software. But the similarity of the name with the modern term 'programming' that refers to the creation of computer programs is only accidental. Linear programming was developed during the Second World War when the military requested mathematicians to help plan their operations in such a way that the greatest possible loss to the enemy is achieved with smallest amount of cost. The common military term for operational plans was 'programs' and this is where the name was derived. The name first arose in the 1940's when George B. Dantzig, one of the main developers of LP wrote a paper entitled Programming in a Linear Structure. This paper was an analysis of the Unites States Air Force's planning problems at that time of war and it showed how the said problems could be formulated in a system of linear inequalities. Later on the title was shortened to linear programming. It was Dantzig who contributed the simplex method or simplex algorithm. This is a numerical solution to LP problems that involved repeated computations after which the optimal solution is extracted from the set of values generated.

Other methods and techniques for modeling and solving evolved as the field was developed further by other mathematicians. Integer programming for example is a type of linear programming where the variables are limited to take on only integer values. Then there is quadratic programming where the objective function which is the mathematical statement of the problem is a quadratic function - the variable or variables are squared, but the constraints are still expressed in linear equalities or inequalities. Standard linear programming problems are deterministic in nature which means that the variables can be known. But of course real-world problems are hardly ever certain. To compensate for uncertainty, Stochastic programming was developed and it takes a further step by considering random variables and using probability distributions. As the field grew, and new methods for optimization were discovered, the term mathematical programming was eventually used and this included all mathematical techniques that systematically solved for optimal solutions on problems whether they were expressed as linear functions or otherwise.


Share this article!

Follow us!

Find more helpful articles: