Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconData Sciencebreadcumb forward arrow iconLinear Programming Problems, Solutions & Applications [With Example]

Linear Programming Problems, Solutions & Applications [With Example]

Last updated:
10th Dec, 2020
Views
Read Time
12 Mins
share image icon
In this article
Chevron in toc
View All
Linear Programming Problems, Solutions & Applications [With Example]

 Data science encompasses numerous applications, with optimization being one of the most prominent. We’re always striving to optimize various aspects to achieve the best possible outcomes with the resources at our disposal. There are diverse problems within optimization, ranging from simple to highly complex.   

 Despite these, linear programming problems have a distinct place. In this article, I have delved into these issues and how professionals can tackle them effectively. Aspiring data scientists should familiarize themselves with linear programming problems they commonly encounter in real-world scenarios and mastering them can significantly enhance one’s analytical capabilities in data science.  

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

Types of Linear Programming Problems     

  1. Maximization Problems: These involve maximizing an objective function subject to linear constraints. The goal is to find the optimal values of decision variables that maximize the objective function.  
  2. Minimization Problems: Unlike maximization problems, minimization problems seek to minimize an objective function while satisfying linear constraints. The objective is to identify the optimal values of decision variables that minimize the objective function.  
  3. Feasibility Problems: Feasibility problems focus on determining whether a feasible solution exists within the given constraints. The aim is to ascertain if any possible solutions satisfy all constraints without optimizing an objective function.  
  4. Unboundedness Problems: Arise when the feasible region is unbounded, leading to infinitely many solutions. The objective function can either be maximized or minimized without reaching an optimal solution due to the unbounded nature of the feasible region.    

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:

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.

Conclusion:  

In summary, linear programming problems systematically optimize resources and achieve desired outcomes across various industries. Understanding the basics and steps in formulating these problems is crucial for mid-career professionals seeking to enhance their analytical skills and decision-making abilities. Through real-world examples and applications, we’ve explored the versatility and effectiveness of linear programming in solving complex optimization challenges.  

 Aspiring data scientists and professionals can benefit from delving deeper into linear programming problems, leveraging tools like R to implement solutions and drive impactful results in their respective fields. Continuously expanding our knowledge in linear programming and data science opens doors to new opportunities and advancements in our careers. 

Profile

Rohit Sharma

Blog Author
Rohit Sharma is the Program Director for the UpGrad-IIIT Bangalore, PG Diploma Data Analytics Program.

Frequently Asked Questions (FAQs)

1 How does linear programming help in optimization?

Optimization is a way of life for many people. Everything utilizes optimization, from how you spend your time to how you solve supply chain issues for your organization. It's a very fascinating and relevant issue in data science. Linear Programming is one of the most effective methods for doing optimization. It aids in the solution of specific extremely complicated optimization problems by making more easy assumptions. As an analyst, you will undoubtedly come across applications and situations that need Linear Programming. Machine Learning takes advantage of optimizations as well. Supervised learning builds on the foundations of Linear Programming. A system is trained to fit a mathematical model of a function using labeled input data to predict values from unknown test data.

2How is linear programming useful in data science and machine learning?

Linear programming is a necessary skill for anyone interested in machine learning/data science. Everything in machine learning and deep learning is about optimization. Convex or nonconvex optimization is used in ML algorithms. The key difference between the two categories is that there can only be one optimal solution in convex optimization, which is globally optimal, or you can prove that there is no feasible solution to the problem. In contrast, in nonconvex optimization, there can be multiple locally optimal points. It can take a long time to determine whether the problem has no solution or if the answer is global.

3Where is linear programming used?

Professionals can use linear programming in a wide range of disciplines of study. It is often used in mathematics and to a lesser extent in business, economics, and some engineering difficulties. Transportation, energy, telecommunications, and manufacturing are among the industries that employ linear programming methods. It is beneficial in simulating a wide range of problems in planning, routing, scheduling, assignment, and design. Certain specific instances of linear programming, such as network flow issues and multicommodity flow problems, are deemed significant enough to warrant extensive study on specialized methods to solve them. To stabilize YouTube videos, Google employs linear programming.

Explore Free Courses

Suggested Blogs

Top 13 Highest Paying Data Science Jobs in India [A Complete Report]
905120
In this article, you will learn about Top 13 Highest Paying Data Science Jobs in India. Take a glimpse below. Data Analyst Data Scientist Machine
Read More

by Rohit Sharma

12 Apr 2024

Most Common PySpark Interview Questions &#038; Answers [For Freshers &#038; Experienced]
20868
Attending a PySpark interview and wondering what are all the questions and discussions you will go through? Before attending a PySpark interview, it’s
Read More

by Rohit Sharma

05 Mar 2024

Data Science for Beginners: A Comprehensive Guide
5064
Data science is an important part of many industries today. Having worked as a data scientist for several years, I have witnessed the massive amounts
Read More

by Harish K

28 Feb 2024

6 Best Data Science Institutes in 2024 (Detailed Guide)
5153
Data science training is one of the most hyped skills in today’s world. Based on my experience as a data scientist, it’s evident that we are in
Read More

by Harish K

28 Feb 2024

Data Science Course Fees: The Roadmap to Your Analytics Career
5075
A data science course syllabus covers several basic and advanced concepts of statistics, data analytics, machine learning, and programming languages.
Read More

by Harish K

28 Feb 2024

Inheritance in Python | Python Inheritance [With Example]
17605
Python is one of the most popular programming languages. Despite a transition full of ups and downs from the Python 2 version to Python 3, the Object-
Read More

by Rohan Vats

27 Feb 2024

Data Mining Architecture: Components, Types &#038; Techniques
10778
Introduction Data mining is the process in which information that was previously unknown, which could be potentially very useful, is extracted from a
Read More

by Rohit Sharma

27 Feb 2024

6 Phases of Data Analytics Lifecycle Every Data Analyst Should Know About
80620
What is a Data Analytics Lifecycle? Data is crucial in today’s digital world. As it gets created, consumed, tested, processed, and reused, data goes
Read More

by Rohit Sharma

19 Feb 2024

Sorting in Data Structure: Categories &#038; Types [With Examples]
139010
The arrangement of data in a preferred order is called sorting in the data structure. By sorting data, it is easier to search through it quickly and e
Read More

by Rohit Sharma

19 Feb 2024

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon