DeepAI AI Chat
Log In Sign Up

Linear Programming

What is Linear Programming?

Linear Programming is the technique of portraying complicated relationships between elements by using linear functions to find optimum points. The relationships may be more complicated than accounted for, however linear programming allows for a simplified understanding of their connections. Linear programming is often used when seeking the optimal solution to a problem, given a set of constraints. To find the optimum result, real-life problems are translated into mathematical models to better conceptualize linear inequalities and their constraints.

How does Linear Programming work?

Linear Programming begins by taking the real-world data and translating it into a series of mathematical formulas. For example, a toy manufacturer wants to maximize their profits selling toy cars and tractors. Both the cars and the tractors use the same type of wheels and draw from a limited supply (this is the first constraint). Additionally, the manufacturer makes more money selling toy tractors for 6 dollars than toy cars for 5 dollars (this is another constraint). One can represent the total number of tractors with variable X, and the total number of cars with variable Y. Accordingly, the total profit will be represented by Z. In short, the formula becomes Z = 6X + 5Y. In order for the manufacturer to maximize their profits, they will need to find maximum value for Z.

The process of translating real-world constraints like these to linear functions is called Operation Research, and is a crucial step in incorporating linear programming into problem solving. Furthermore, by translating the number of toy units to X and Y, we assigned decision variables which are incorporated into the objective functions used to make decisions and understand the data. As denoted above, the objective function for maximum profit is  Z = 6X + 5Y. For all linear programs, the decision variables must be defined with non-negative values.

Graphically, we can represent optimum values as the area under which our constraints lie. In the image below, note the blue area represents the feasible region that is bound by the constraint functions. 

Source

Applications of Linear Programming

As Linear Programming is a valuable way of displaying real-world data in a mathematical way, it is commonly used in manufacturing and the service industry. For example, many large distribution companies will use linear programming in the analysis of their supply chain operations, similar to the toy example above. Additionally, linear programming can be used outside the warehouse in the optimization of delivery routes. Companies like Amazon and FedEx use linear programming to find the shortest and most efficient delivery routes. Linear programming is also used in machine learning applications where a neural network is trained to fit model of a function in order to label input data and predict unknown future values.