Linear Programming Problems, Solutions & Applications [With Example]

Data science has many applications, one of the most prominent among them is optimization. We all tend to focus on optimizing stuff. Optimization focuses on getting the most desired results with the limited resources you have.

There are all sorts of optimization problems available, some are small, some are highly complicated. While going through them, you’ll find a specific category called linear programming problems. In this article, we’ve discussed what they are and how you can work on them. 

Suppose you’re a fruit seller who can either buy oranges or apples or a certain combination of them both. However you only have a budget of INR 5,000 and you can only store 30 bags of them. Now, you have to buy them in the way that yields you the highest profit.

Now one bag of oranges costs you INR 500 while a bag of apples costs you INR 750. You can make INR 100 from the sale of one bag of oranges and INR 200 from the sale of one bag of apples. 

This problem has various possibilities. You might choose to only buy oranges but then, you’d only have 10 bags in your storage and your profit would be INR 1000. Similarly, you might choose to only buy apples and make INR 1500 as profit. You can also buy a combination of the two. 

Such problems are called linear programming problems and we’ll discuss them in detail. Let’s get started:

What is Linear Programming?

Linear programming is a method of depicting complex relationships by using linear functions. Our aim with linear programming is to find the most suitable solutions for those functions. The real relationship between two points can be highly complex, but we can use linear programming to depict them with simplicity. Linear programming finds applications in many industries. 

Check out our data science online courses to upskill yourself

Basics of Linear Programming

Here are some fundamental terms of linear programming:

Constraint

The limitations (or restrictions) of your decision variables are called constraints. Most of the time constraints are the limitations you have on your resources for solving a problem. 

Decision Variable

These variables define your output. Your result depends on these variables, that’s why we call them ‘decision variables’. 

Non-negativity Restriction

The decision variables of a linear programming problem can only have non-negative value. It means the values for your decision variables can be equal to or greater than zero only. 

Objective Function

The objective function is the objective of making your decision. In simple terms it is the final result of your linear programming problem. For example, when you’re finding the maximum profit you can make with a given set of resources, the maximum profit is the objective function.

Formulating Linear Programming Problems

You should know how to formulate a linear programming to apply it in real-life. Suppose you are a manufacturer of toys and you only produce two toys: A and B. Roughly speaking, your toys require two resources X and Y to manufacture. Here are the requirements of your toys:

• One unit of toy A requires you one unit of resource X and three units of resource Y

• One unit of toy B requires one unit of resource X and two units of resource Y

You have five units of resource X and 12 units of resource Y. Your profit margins on the sale of these toys are:

• INR 6 on each sold unit of toy A
• INR 5 on each sold unit of toy B

How many units of each toy would you produce to get the maximum profit?

The Solution

Let’s represent our linear programming problem in an equation:

Z = 6a + 5b

Here, z stands for the total profit, a stands for the total number of toy A units and b stands for total number to B units. Our aim is to maximize the value of Z (the profit). 

Now, your company would want to produce as many units of these toys as possible, but you have limited resources. The limitations on our resources are the constraints of this problem. We only have a total of

a + b 5

Now every unit of toy A and B requires 3 and 2 units of resource Y respectively. And we only have a total of 12 units of resource Y so mathematically, it would look like this:

3a + 2b 12

Remember that the values for the units of toy A can be in integers only. This means we also have the constraints of a->0 and b<-0. 

So, now you have a proper linear programming problem. You can formulate other linear programming problems by following this example. While this example was quite simple, LP problems can become highly complicated. 

Read: Linear Programming Project Ideas & Topics

upGrad’s Exclusive Data Science Webinar for you –

ODE Thought Leadership Presentation

Explore our Popular Data Science Online Courses

Steps of Formulating Linear Programming Problems

To formulate a linear programming problem, follow these steps:

• Find the decision variables
• Find the objective function
• Identify the constraints
• Remember the non-negativity restriction

If a problem meets the above criteria, it is a linear programming problem. It’s best practice to keep this criterion in mind when you’re working on identifying the type of the problem. 

Solving Linear Programming Problems with R

If you’re using R, solving linear programming problems becomes much simpler. That’s because R has the lpsolve package which comes with various functions specifically designed for solving such problems. It’s highly probable that you’ll be using R very frequently to solve LP problems as a data scientist. That’s why we’ve shared two distinct examples to help you understand its implementation better:

Example

Let’s start with a basic problem. An organization has two products with selling prices of INR 25 and INR 20 and are called product A and B respectively. Every day, they have 1800 units of resources to produce these products. Product A requires 20 resources units and B requires 12 resources units. The production time for both of these products is four minutes and the organization gets a total of eight working hours every day. The problem is, what should be the production quantity for each of these products to maximize the company’s profits?

Solution:

We’ll start solving this problem by defining its objective function:

max(Sales) = max( 25y1 + 20y2)

Here, 25 and 20 are the prices of product A and B respectively, y1 is the total units of product A produced and y2 is the total units of product B produced. Our decision variables are y1 and y2. 

Top Data Science Skills to Learn to upskill

We’ll now set the constraints for our problem:

Resource constraint:

20y1 + 12y2 1800

Time constraint:

4y1 + 4y2 8*60

We aim to find the correct number of products we have to manufacture to get the maximum profit. 

Using R to Solve the Problem:

We’ll use lpsolve to solve this LP problem and start with setting the objective function:

> require(lpSolve)

Loading required package: lpSolve

> objective.in  <- c(25, 20)

> objective.in

[1] 25 20

Then we’ll build a matrix for the constraints:

> const <- matrix(c(20,  12, 4, 4), nrow=2, byrow=TRUE)

> const

     [,1] [,2]

[1,]   20 12

[2,]    4 4

> time_constraints <- (8*60)

> resource_constraints <- 1800

> time_constraints

[1] 480

> resource_constraints

[1] 1800

Let’s now create the already-defined equations:

> rhs <- c(resource_constraints, time_constraints)

> rhs

[1] 1800  480

> direction  <- c(“<=”, “<=”)

> direction

[1] “<=” “<=”

Once all the necessary information is added, we can start finding the optimal answer. The syntax for our package is:

lp( direction, objective, const.mat, const.dir, const.rhs )

> optimum <-  lp(direction=”max”,  objective.in, const, direction,  rhs)

> optimum

Success: the objective function is 2625

> summary(optimum)

                 Length Class Mode     

direction        1 -none- numeric  

x.count          1 -none- numeric  

objective        2 -none- numeric  

const.count      1 -none- numeric  

constraints      8 -none- numeric  

int.count        1 -none- numeric  

int.vec          1 -none- numeric  

bin.count        1 -none- numeric  

binary.vec       1 -none- numeric  

num.bin.solns    1 -none- numeric  

objval           1 -none- numeric  

solution         2 -none- numeric  

presolve         1 -none- numeric  

compute.sens     1 -none- numeric  

sens.coef.from   1 -none- numeric  

sens.coef.to     1 -none- numeric  

duals            1 -none- numeric  

duals.from       1 -none- numeric  

duals.to         1 -none- numeric  

scale            1 -none- numeric  

use.dense        1 -none- numeric  

dense.col        1 -none- numeric  

dense.val        1 -none- numeric  

dense.const.nrow 1      -none- numeric 

dense.ctr        1 -none- numeric  

use.rw           1 -none- numeric  

tmp              1 -none- character

status           1 -none- numeric

After running the code above, you can get the desired solutions for our problem.

The optimum values for y1 and y2:

Remember that y1 and y2 were the units of product A and product B we had to produce:

> optimum$solution

[1] 45 75

The optimum sales figure:

The maximum profit we can generate with the obtained values of y1 and y2 is:

> optimum$objval

[1] 2625

Also Read: Linear Algebra For Machine Learning

Read our popular Data Science Articles

Uses of Linear Programming

As we mentioned before, linear programming finds applications in many industries. Here are some areas where we use it:

• With the rising popularity of delivery services, linear programming has become one of the most favoured methods of finding the optimum routes. When you take an Ola or Uber, the software would use linear programming to find the best route. Delivery companies like Amazon and FedEx also use it to determine the best routes for their delivery men. They focus on reducing the delivery time and cost. 
• Machine learning’s supervised learning works on the fundamental concepts of linear programming. In supervised learning, you have to find the optimal mathematical model to predict the output according to the provided input data.
• The retail sector uses linear programming for optimizing shelf space. With so many brands and products available, determining where to place them in the store is a very rigorous task. The placement of a product in the store can affect its sales greatly. Major retail chains such as Big Bazaar, Reliance, Walmart, etc. use linear programming for determining product placement. They have to keep the consumers’ interest in mind while ensuring the best product placement to yield maximum profit. 
• Companies use linear programming to improve their supply chains. The efficiency of a supply chain depends on many factors such as the chosen routes, timings, etc. By using linear programming, they can find the best routes, timings, and other allocations of resources to optimize their efficiency. 

Learn More about Linear Programming and Data Science

Linear programming is one of the most vital concepts of data science. It is also a fundamental topic that you should know about to become a proficient data scientist. As we discussed, there are many applications for this concept and you can find its use cases in your daily life. 

You can learn more about data science and its related concepts, by going to our blog. We have many valuable resources to help you learn more. Here are some for your further reading:

• Top Reasons to become a Data Scientist
• The Algorithms Every Data Scientist Should Know
• How to Become a Data Scientist

On the other hand, you can get a data science course to learn from industry experts. You’ll get to learn interactively through videos, quizzes, and projects. Taking a course will help you learn the necessary skills to become a professional data scientist. Check out IIIT-B & upGrad’s PG Diploma in Data Science which is created for working professionals and offers 10+ case studies & projects, practical hands-on workshops, mentorship with industry experts, 1-on-1 with industry mentors, 400+ hours of learning and job assistance with top firms.

Prepare for a Career of the Future

UPGRAD AND IIIT-BANGALORE'S PG DIPLOMA IN DATA SCIENCE

Learn More