Linear Optimization-Solved Examples
Parag Verma
14th July, 2022
Introduction
In this blog we will look at a linear optimization problem and how we can leverage lpsolve library to solve it.
package.name<-c("dplyr","lpSolve")
for(i in package.name){
if(!require(i,character.only = T)){
install.packages(i)
}
library(i,character.only = T)
}Step 1: The Problem
Lets say there is a furniture company which manufactures 3 products.
- Tables: Each table makes a profit of 500 Dollars, costs 8.4 production hours to make and 3\(m3\) of storage to store
- Sofas: Each sofa makes a profit of 450 Dollarsc, costs 6 production hours to make, and 6\(m3\) of storage to store
- Beds: Each bed makes a profit of 580 Dollars, costs 9.6 production hours to make, and 8\(m3\) of storage to store
Each week you have a budget of only 72 production hours at your factory. Additionally, you have enough warehouse storage to store only 40\(m3\) (cubic-meters). Furthermore, from past trends, you can only sell a maximum of 8 tables a week.
How many of each type of furniture should you make for next week to maximise profit?
Step 2: Defining the Objective Function
Let X1 be the unit of Tables sold in the market
Let X2 be the unit of Sofas sold in the market.
Let X3 be the unit of Beds sold in the market.
Hence the objective function will become:
Max(Profit) = 500X1 + 450X2 + 580X3
X1,X2 and X3 are the decision variables
Step 3: Defining the Constraints
Lets define the constraints around:
- Production Hours
- Storage Space
- Upper cap on table production
Defining the Production Hours constraint
There are only 72 production hours available each week:
8.4X1 + 6X2 + 9.6X3 <= 72
Defining the Storage Space constraint
Maximum space available is 40\(m3\):
3X1 + 6X2 + 8X3 <= 40
Defining the constraint around table production
you can only sell a maximum of 8 tables a week
X1 + 0X2 + 0X3 <= 8
And obviously we have the non negativity constraint
X1>=0 X2>=0 X3>=0
Step 4: Defining the objective function in R
objective.in<-c(500,450,580)
objective.in[1] 500 450 580Step 5: Creating the Constraint Matrices
Const.mat<-matrix(c(8.4, 6 , 9.6,
3, 6 , 8,
1, 0, 0
),byrow = T,nrow = 3)
colnames(Const.mat)<-c("X1","X2","X3")
Const.mat X1 X2 X3
[1,] 8.4 6 9.6
[2,] 3.0 6 8.0
[3,] 1.0 0 0.0Time,space and table constraints
time_constraint<-72
space_constraint<-40
table_constrint<-8
Const.rhs<-c(time_constraint,space_constraint,table_constrint)
Const.rhs[1] 72 40 8Equality/Inequality constraints
Const.dir<-c("<=","<=","<=")
Const.dir[1] "<=" "<=" "<="Step 6: Identifying the Optimal Solution
Optimal_solution<-lp(direction="max",objective.in,Const.mat,Const.dir,Const.rhs)
Optimal_solutionSuccess: the objective function is 4629.63 Max Sales
Optimal_solution$solution[1] 5.925926 3.703704 0.000000The total maximum sales is 4629.63
To achieve the above, we need to sell
X1 = 5.9 X2 = 3.7 X3 = 0
The optimal solution is to not produce any beds at all!
