Programs

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

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

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

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

 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

 480

> resource_constraints

 1800

Let’s now create the already-defined equations:

> rhs <- c(resource_constraints, time_constraints)

> rhs

 1800  480

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

> direction

 “<=” “<=”

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

 45 75

The optimum sales figure:

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

> optimum\$objval

 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.

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

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

## 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. ## Prepare for a Career of the Future

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