Linear Programming Problem (LPP)

Linear Programming Problem (LPP)

5 mins read32.9K Views Comment
clickHere
Vikram
Vikram Singh
Assistant Manager - Content
Updated on Jan 29, 2024 14:18 IST

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.

Linear Programming Problem - LPP

 

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 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 

  • aij and bj’s are constants, 
  • xi’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 (xn+1) in the above equation, i.e.,

and if we have,

Then, subtract a surplus variable ( xn+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
Transportation Problem: Definition, Formulation, and Types
Transportation Problem: Definition, Formulation, and Types
Transportation problems are used to find the minimum cost of transportation of goods from m source to n destination. In this article we will learn transportation problem, formulation, types and...read more
Difference Between Transportation Problem and Assignment Problem
Difference Between Transportation Problem and Assignment Problem
The transportation problem in operational research aims to find the most economical way of transporting goods from multiple sources to multiple destinations. On the other hand, the assignment problem focuses...read more

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.

Corner Point f(x,y) = 3x+2y
(0, 0) 0
(8, 0) 24
(6, 6) 30
(3, 12) 33
(0, 14) 28

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!!

FAQs

What is LPP?

Linear Programming problem (LPP) 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.

What are the different applications of LPP?

Applications of LPP: 1. Resource Allocation 2. Production Planning 3. Transportation and Logistics 4. Financial Planning 5. Energy Management 6. Marketing and Advertising

What are the basic terminologies used in Linear Programming Problem?

Some of the basic terminologies used in Linear Programming Problems are:

Decision Variable, Objective Function, Constraints, Feasible Solution, Optimal Solution.

What are the characteristics of Linear Programming Problem (LPP)?

Characteristics of Linear Programming Problems:

  • 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.

How to Formulate a Linear Programming Problem?

To Formulate a LPP you can follow, the given below steps:

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

What are the different 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
About the Author
author-image
Vikram Singh
Assistant Manager - Content

Vikram has a Postgraduate degree in Applied Mathematics, with a keen interest in Data Science and Machine Learning. He has experience of 2+ years in content creation in Mathematics, Statistics, Data Science, and Mac... Read Full Bio

Comments