Applying Linear Programming to Solve Real-Life Problems in R Language

Linear programming (or LP for short) in one of the fundamental mathematical concepts with a wide variety of applications.

Wikipedia would define LP as

"Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming"

So basically it's a method to help us solve something in the best way according to what we want when there are several constraints involved. It is important to note that this can be used only when the parameter of our concern follows a linear relationship with the other parameters that determine it's value. 

Every linear programming problem consists of three elements:

1. Decision variables: The ones that describe our choices that are under our control.
2. Objective function: The one that describes a criterion that we wish to minimize (e.g., cost) or maximize (e.g., profit)
3. Constraints: The ones that describe the limitations that restrict our choices for decision variables.

While approaching any LP problem, the very first step is to identify the decision variables. The next is to define the objective function after which you should look for all the constraints in the given situation. Once this is done, solving it is just as simple as writing a line of code in R. We will be using R programming to solve here. While it can be done simply using pen and paper or by any other language, R can be used to do it more quickly and efficiently. Solving an LP can often be a part of solving a major problem statement and R is one widely used software for programming solutions in business analytics.

Traditionally, any LP problem can be solved graphically by plotting the constraint equations and narrowing down the feasible region to find the optimum values of the decision variables as shown in the diagram below.

(Image Source: Wikipedia)

Solving an LP problem in R using lpsolve

lpsolve is an R package, as the name suggests will help us solve any kind of LP problem with ease. Let's understand how to use it with the following standard example problem.

Given Sample Question:

A car company produces two models, model A and model B. Long-term projections indicate an expected demand of at least 100 model A cars and 80 model B cars each day. Because of limitations on production capacity, no more than 200 model A cars and 170 model B cars can be made daily. To satisfy a shipping contract, a total of at least 200 cars much be shipped each day. If each model A car sold results in a $2000 loss, but each model B car produces a $5000 profit, how many of each type should be made daily to maximize net profits?

Take a moment to grasp the question.

From the given question, we have:

1. Let a = number of Model A cars per day
2. Let b = number of Model B cars per day

We have the constraints as follows:

a >= 100

b >= 80 

a <= 200

b <= 170

a + b >= 200


Net profit, P = (Profit in selling model B)*b - (loss in selling model A)*a

P = -2000a + 5000b

We want the profit, P to be maximized.

Basically to solve this using lpsolve, we need the following:

#Constraint Matrix (Coefficents)
1 0 100
0 1 80
1 0 200
0 1 170
1 1 200

1. Coefficient matrix of the constraints (We have 5 constraints in this case. In case the variable a or b is not present in any constraint, it's coefficient is taken as 0)
2. RHS side of the matrix (Here it would be {100, 80, 200, 170, 200})
3. The order of Inequalities
4. The coefficients of the cost function

Finally putting them all together, we can solve the problem as given below using the standard syntax:

#R code snippet

library(lpSolve)

#coefficencts of objective function
f.obj <- c(-2000, 5000) #Note that <- is assignment operator in R

#constraint matrix
f.con <- matrix(c(1,0,0,1,1,0,0,1,1,1), nrow=5, byrow=TRUE)  

#constraint inequalities in order
f.dir <-c(">=", ">=", "<=", "<=", ">=") 

#RHS side of constraint inequalities
f.rhs <- c(100,80,200,170,200)

#solving the problem using lp function
lp("max", f.obj, f.con, f.dir, f.rhs)$solution

#Output upon executing the above code
[1] 100 170

# This implies that for obtaining maximum profit, 
# we must produce 100 model A cars 
# and 170 model B cars in the given scenario.

Max_profit <- 100*(-2000) + 5000*170
print(Max_profit)

# Output upon execution
[1] 650000

# Hence the maximum profit is 650000.

Applications of Linear Programming

A lot of situations we come across in everyday life have processes that follow linear relationships with several day to day factors. As such, linear programming finds in application in many unique ways and in different domains of science and technology as follows:

1. Optimization in Scheduling: Classic example is scheduling of an airline crew.
2. Manufacturing and Transportation: In situations involving manufacturing and transportation of goods, productivity can be optimized using this approach as seen in the discussed example.
3. VLSI Chip Production: Another interesting application in the field of electronics, LP programming can actually help us in fabricating shortest possible routes in the chip. 
4. Diet Optimization: Another classic example where we can determine the cheapest combination of foods that will satisfy all your nutritional requirements.

All of these versatile real life problem statements can be solved in R in a similar fashion as demonstrated. R Studio is available for free to download, which is an ideal IDE to use. lpsolve package can be directly installed by going to 'Tools -> Install Packages' option.

What's most important in linear programming is identifying the problem statement. What can be optimized in your firm using this approach? Are there any linear dependent variables in your system and subsystems? What are the constraints? Pondering over such questions is important.

Stay tuned for more utility based and interesting content!

#IndiaStudents #StudentVoices #LinearProgramming #R