Explore Courses

# Linear Programming Problems, Solutions & Applications [With Example]

Updated on 06 September, 2024

12.88K+ views

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.

upGrad’s Exclusive Data Science Webinar for you –

## Explore our Popular Data Science Online Certificat

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)

> 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

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

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.

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.

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

### 2. How 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.

### 3. Where 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.

Rohit Sharma

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

See More

## SUGGESTED BLOGS

5.64K+

Announcing PG Diploma in Data Analytics with IIIT Bangalore

08 Feb'16

5.09K+

How Organisations can Benefit from Bridging the Data Scientist Gap

03 May'16

5.13K+

Computer Center turns Data Center; Computer Science turns Data Science

11 May'16

5.19K+

Enlarge the analytics &amp; data science talent pool

14 May'16

5.69K+

We are happy to announce our partnership with Analytics Vidhya, a pioneer in the Data Science community. Analytics Vidhya is well known for its impressive knowledge base, be it the hackathons they organize or tools and frameworks that they help demystify. In their own words, “Analytics Vidhya is a passionate community for Analytics/Data Science professionals, and aims at bringing together influencers and learners to augment knowledge”. Explore our Popular Data Science Degrees Executive Post Graduate Programme in Data Science from IIITB Professional Certificate Program in Data Science for Business Decision Making Master of Science in Data Science from University of Arizona Advanced Certificate Programme in Data Science from IIITB Professional Certificate Program in Data Science and Business Analytics from University of Maryland Data Science Degrees We are joining hands to provide candidates of our PG Diploma in Data Analytics, an added exposure to UpGrad Industry Projects. While the program already covers multiple case studies and projects in the core curriculum, these projects with Analytics Vidhya will be optional for students to help them further hone their skills on data-driven problem-solving techniques. To further facilitate the learning, Analytics Vidhya will also be providing mentoring sessions to help our students with the approach to these projects. Our learners also read: Free Online Python Course for Beginners Top Essential Data Science Skills to Learn SL. No Top Data Science Skills to Learn 1 Data Analysis Certifications Inferential Statistics Certifications 2 Hypothesis Testing Certifications Logistic Regression Certifications 3 Linear Regression Certifications Linear Algebra for Analysis Certifications This collaboration brings great value to the program by allowing our students to add another dimension to their resume which goes beyond the capstone projects and case studies that are already a part of the program. Read our popular Data Science Articles Data Science Career Path: A Comprehensive Career Guide Data Science Career Growth: The Future of Work is here Why is Data Science Important? 8 Ways Data Science Brings Value to the Business Relevance of Data Science for Managers The Ultimate Data Science Cheat Sheet Every Data Scientists Should Have Top 6 Reasons Why You Should Become a Data Scientist A Day in the Life of Data Scientist: What do they do? Myth Busted: Data Science doesn’t need Coding Business Intelligence vs Data Science: What are the differences? Through this, we hope our students would be equipped to showcase their ability to dissect any problem statement and interpret what the model results mean for business decision making. This also helps us to differentiate UpGrad-IIITB students in the eyes of the recruiters. upGrad’s Exclusive Data Science Webinar for you – Transformation & Opportunities in Analytics & Insights document.createElement('video'); https://cdn.upgrad.com/blog/jai-kapoor.mp4 Check out our data science training to upskill yourself
09 Oct'16

5.69K+

Data Analytics Student Speak: Story of Thulasiram

07 Dec'16

5.12K+

Decoding Easy vs. Not-So-Easy Data Analytics

14 Dec'16

5.14K+

15 Dec'16

5.22K+

What&#8217;s Cooking in Data Analytics? Team Data at UpGrad Speaks Up!

23 Dec'16

SUPPORT

MBA

DATA SCIENCE & ANALYTICS

DOCTORATE

SOFTWARE & TECH

AI & ML

MARKETING

MANAGEMENT

LAW