Edit This Site

Linear Programming

By: Andreas Bigger
Posted: May 23, 2020
––– views
An introduction into the mathematical optimization method linear programming.


Most things in life, and life itself, is finite. Optimization even at the smallest margins can make all the difference between companies and in any improvement.
For a subset of problems, linear programming (LP) can be applied to obtain an optimal solution. The fundamentals and applications are what we will look at in this brief introduction.


Linear programming is a method of mathematical optimization that takes a linear objective function to optimize given a set of linear inequalities or equality constraints. To break this down, there are combinations of values for the problem's variables that provide feasible solutions in a region known as the convex region. Linear programming algorithms then attempt to optimize where a function may intersect such a region, if it does, in order to find an optimal solution answering business questions such as maximum profit, minimum cost, or both. Importantly, these algorithms become computationally valuable as multiple values of variables can be parallelized when computed by using vectors allowing the linear algorithms to determine optimal solutions quickly as computations are performed simultaneously.

A Brief History

During the period of 1946-1947, George B. Dantzig invented the simplex algorithm for linear programming. This algorithm runs polynomial time in most cases, the key being it dramatically reduces the number of incorrect solutions rapidly, in a process of elimination form.


Linear programming is commonly used for a number of specific problems such as network flow and multi-commodity flow. Its use for these flow problems merely suggests the wider use for logistical planning and operations as optimality is crucial in the movement of physical goods.
For example, consider the limitations of material and labor and their profit as a function of their costs. This creates an optimization problem intrinsic to businesses in their quest to turn a profit. While this example only takes into consideration the two generalized limitations of material and labor, "real life" contains a skew of variables that we cannot visualize in the second, and even third dimensions.
While the simplex method, and a variety of others, can be abstractly used to solve optimization problems we cannot visualize, determining the constraint functions and the variables is not trivial.


A quick google search for linear programming tools will bring you to the website https://online-optimizer.appspot.com/
This online solver can quickly solve optimization problems using augmented matrices, parallelizing computations for efficiency, and breaks the solution down in a tabular and graphical form.
An interesting experiment you can perform on the tool is what happens when the number of variables increase from 2 to 3. Try it out.
Spoiler Alert - the graphical representation of the model is not shown.


Linear Programming: Wikipedia - https://en.wikipedia.org/wiki/Linear_programming