LPP

Linear Programming for Feasibility Analysis

Sangamesh K S

January 3, 2018

In this article I will be explaining a old school MBA technique to find feasible solution using Linear Programming popularly known as LPP.

LPP is widely used in the SCM domain(Optimal Pricing), Investment, product pricing, how much to produce and how much to store etc..

In industrial practice LPP is normally solved using Opensolver which is open source of Microsoft, SAS and MS-Excel.

What is Linear Programming?

In general, LPP is a approach to come up with the best possible outcome using mathematical model to identify extreme min or max approach to find the linear relationship with the dataset. Which help us optimizing and help finding a feasible point or region for the problem.

How Linear programming works?

Before explain how it work. let me introduce you to few terminology

Optimization: it is a objective function explaining what you want min or max? Linear Objective Function: It is normally quantitative variables or features like revenue, Profit, distance etc. from which we are going to optimize generally represented by

Optimization(Min or Max) Z= C1X1+C2x2…CnXn

Where Z is the measure of performance , which is a function of x1,x2,…xn.. Quantities C1,c2…cn(Parameters)

Linear Constraint: they are the limitation for the model. They are normally resourse like machine, raw materials, space, money etc..

Let me explain this very simple. My old school way: just plot the linear equation on a graph and draw lines and find the feasible region it is the most simple approach for a LPP. Which is a graphical approach/method for LPP; another approach is the simplex method.

Please Note: Linear Programming is a approach which is applied on optimization of linearly construct able data not on nonlinear data.

We will now use R; which has a better interface and computational capability. It is nothing different.

In my past articles I have showed how to use Linear Regression which is a minimization approach i.e R^2 and finding an optimum line which is an optimization approach.

In R we will use a package called lpSolve which is a package to solve LPP. If I go ahead and look into what is in the package then we can find lp,lp.assign, lp.transport and make.q8.

library(lpSolve)
ls("package:lpSolve")

## [1] "lp"           "lp.assign"    "lp.transport" "make.q8"

Wherein lp help us to solve using Linear Programming Model and lp.assign for Assignment problems, lp.transport for transportation problems.

We will now take an example and optimize a production.

Example:

A car company produces 2 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?

Solution:

Let’s start by defining the variables.

X= number of model A car Y=number of model B car

As we are going for the maximization the equation will be

-2000x+5000y=Z

And the constraints are

x>=100 {Demand of Model A}

y>=80 {Demand of Model B}

x<=200 {Model A’s Production Limit}

y<=170 {Model B’s Production Limit}

x+y>=200 {Transportation Contract}

Now Let’s solve this on R.

f.con<-matrix(c(1,0,0,1,1,0,0,1,1,1),nrow = 5,byrow = TRUE) #Matrix of Constraints i.e x>=100 is convered as (1,0) where in 100 is used in f.rhs
f.obj<-c(-2000,5000) #Objective function
f.dir <- c(">=",">=","<=", "<=",">=") #Direction
f.rhs <- c(100,80,200,170,200) #RHS of the matrix
lps1<-lp ("max", f.obj, f.con, f.dir, f.rhs,compute.sens = TRUE) #LPP Function
lps1$solution #Solution

## [1] 100 170

Conclusion

We have found x and y wherein we have to produce 100 units of Model A and 170 of Model B on daily basis for a optimum production planning