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 580

Step 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.0

Time,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  8

Equality/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_solution

Success: the objective function is 4629.63 

Max Sales

Optimal_solution$solution

[1] 5.925926 3.703704 0.000000

The 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!

Link to Previous Blogs

https://www.aimlmadeeasy.com

My Channel

• Link