Linear Programming Problem (LPP)

Linear Programming problem or LPP is a method to find the optimum solution of a set of parameters represented in linear form. In this article, we will discuss all linear programming problems, such as types of apps, methods to solve them, and, finally, their application.

 

True optimization is the revolutionary contribution of modern research to decision processes. 

~George Dantzig

Linear Programming Problem, or LPP, is a mathematical method to determine the best possible outcome for a given set of parameters represented in linear relationships. This article will briefly discuss LPP, its definitions, basic terminologies, methods to solve the Linear Programming Problem and its applications.

Must Check: Top Math Courses for Data Science

Must Check: Top Data Science Online Courses and Certifications

Table of Content

• What is LPP?
• Formulation of LPP
• Types of LPP
• Application of LPP

What is a Linear Programming Problem or LPP?

Definition

Linear Programming problem is a technique that helps to find the optimal solution for a given problem modeled as a set of linear relationships. It is a type of optimization problem that determines the feasible region (a region that contains all the possible solutions of an LPP) and optimizes the solution to get the maximum or minimum function value.

In simple terms, a linear programming problem is a set of linear equations that are used to find the value of variables to optimize the objective functions.

Basic Terminologies

• Decision Variable: These are quantities to be determined.
• Objective Function: The function (value) that needs to be optimized.
• Constraints: Represents on decision variables how to use the available resource (amount of time, number of people, etc.)
• Feasible Solution: Set all the possible solutions that satisfy the given constants.
• Optimal Solution: It is the best possible solution among all the possible feasible solutions.

Characteristics of LPP

• Decision variables will decide the output.
• The objective function should be specified quantitatively.
• Constraints (limitations) should be expressed in mathematical form.
• Relationships between two or more variables should be linear.
• The values of the variables should always be non-negative or zero.
• There should always be finite and infinite inputs and output numbers.

For a Linear Programming problem, the the Decision Variable, Objective Function, and Constraint function should always be linear.

Formulation of LPP

• Identify the decision variable.
• Write the Objective Function
• Write the constraints
• State the non-negative restrictions

Standard Form of LPP

Any Linear Programming Problem can be written as:

where 

• a_ij and b_j’s are constants, 
• x_i’s are variables (decision variables).

Note: 

• All the constraints are written in equalities (rather than inequalities).
• If constraints are not in the standard form, they can be converted to the standard form by adding or subtracting the slack or surplus variable, respectively.

Then, add a slack variable (x_n+1) in the above equation, i.e.,

and if we have,

Then, subtract a surplus variable ( x_n+1 ) from the above equation, i.e.,

• All the decision variables are required to be positive.

Types of Linear Programming Problems

Following are the types of Linear Programming Problems:

• Manufacturing Problem

• Diet Problem

• Transportation Problem

• Optimal Assignment Problem

Methods to solve Linear Programming Problems

There are different methods to solve any Linear Programming Problem.

• Graphical Method
• Simplex Method
• North West Corner Method
• Least Square Methods

For now, we will discuss only the Graphical method to solve LPP

Graphical Method

Steps for Graphical Method:

• Formulate the LPP.
• Construct the graph and plot all the constraint lines.
• Determine the valid side of each constraint line.
• Identify the feasible solution region.
• Find the optimum points.
• Calculate the coordinates of optimum points.
• Evaluate the objective function at the optimum point.

Example: Solve the given linear programming problem by graphical method.

Max Z = f(x, y) = 3x + 2y

Constraints: 2x + y <= 18

2x + 3y <= 42

3x + y <= 24

x >= 0, y >= 0

Now, let’s plot the graph of the given constraints and find the feasible region.

The above-shaded region (blue colour) is the feasible region for the given app.
Now, we will find the value of the objective function at the corner points of the feasible region.

The above table shows that the objective function obtains its maximum value at (3, 12).

Hence, the maximum value of the objective function f(x,y) = 3x + 2y = 33.

Application of Linear Programming Problem

Linear Programming Problems have their application across different domains like manufacturing/ transportation/ sports/ share market/ engineering/ energy industry/ machine learning, etc. But here, we will discuss some of its real-life applications.

• Let ‘n’ number of tasks and ‘m’ number of people completing the task. Now, assign the task so that overall productivity is optimum. We will get the optimum solution by setting the minimum cost, time is taken by each person or maximum profit. This type of problem is a type of Optimal Assignment Problem.
• Manufacturing Industries: Industries use lpp models to maximize efficiency with minimum operational cost.
• Transport Company: Company like ola, uber, and Rapido uses LPP to optimize delivery routes. The objective of these companies is to reduce time and operational costs and increase revenue.
• Machine Learning: Supervised learning works on the fundamentals of linear programming.

Conclusion

This article has discussed all linear programming problems (app), methods to solve them, and their applications.

Hope you will like the article.

Keep Learning!!

Keep Sharing!!