Linear Programming Problem (LPP) in R

Python
Author

Tony Duan

Published

October 12, 2023

using two differnct package to solve Linear Programming Problem lpSolve and linprog

1 problem:

How many hectares of each habitat should be conserved? The decision is not so simple because you have a number of decision constraints to contend with. These constraints contain bits of information that need to be included in the decision problem (such as the cost per hectare or the total new plant species that are added with each new hectare conserved).

• Budget: The maximum budget is 24,000 pickles.

• Total unique plant species by habitat:

– valley = 350

– highland = 240

• Number of new species conserved for each additional hectare purchased:

– valley = 5

– highland = 3

• Edge effects

– valley = 15

– highland = 25

• Political Considerations

– valley = 2

– highland = 2

• Social upheaval per hectare

– valley = 5

– highland = 2

• Cost per hectare

– valley = 300

– highland = 200

2 putting to LP

2.1 direction and objective:

Max(5v + 3h)

  • variable valley highland

2.2 constraint:

1v + 0h >= 15 (edge effects for valley)

0v + 1h >= 25 (edge effects for highland)

1v - 2h <= 0 (politics constraining valley purchase)

-2v + 1h <= 0 (politics constraining highland purchase)

5v + 2h <= 400 (social upheaval constraint)

300v + 200h <= 24000 (budge constraint)

1v + 0h <= 70 (species richness valley constraint)

0v + 1h <= 60 (species richness highland constraint)

2.3 Question:

How many v and how many h ?

3 solve in lpSolve

3.1 package

Code 
#install.packages("lpSolve")
library(lpSolve)

3.2 define

Code 
# first, let's define the coefficients for the function to be optimized
f.obj <- c(5, 3)

# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(1, 0, 0, 1, 1, -2, -1, 1, 5, 2, 300, 200, 1, 0, 0, 1),
nrow = 8,
byrow = TRUE)

# Set unequality signs
f.dir <- c(">=", ">=", "<=", "<=", "<=", "<=", "<=", "<=")

# Set right hand side coefficients
f.rhs <- c(15, 25, 0, 0, 400, 24000, 70, 60)

3.3 formula

1v + 0h >= 15 (edge effects for valley)

0v + 1h >= 25 (edge effects for highland)

1v - 2h <= 0 (politics constraining valley purchase)

-2v + 1h <= 0 (politics constraining highland purchase)

5v + 2h <= 400 (social upheaval constraint)

300v + 200h <= 24000 (budge constraint)

1v + 0h <= 70 (species richness valley constraint)

0v + 1h <= 60 (species richness highland constraint)

3.4 left side of the constrain

Code 
f.con
     [,1] [,2]
[1,]    1    0
[2,]    0    1
[3,]    1   -2
[4,]   -1    1
[5,]    5    2
[6,]  300  200
[7,]    1    0
[8,]    0    1

3.5 sign of the constrain

Code 
f.dir
[1] ">=" ">=" "<=" "<=" "<=" "<=" "<=" "<="

3.6 right side of the constrain

Code 
f.rhs
[1]    15    25     0     0   400 24000    70    60

3.7 run LP

Code 
# Now run
results=lp(direction = "max",
objective.in = f.obj,
const.mat = f.con,
const.dir = f.dir,
const.rhs = f.rhs,
all.int = T
)

3.8 result

Code 
results
Success: the objective function is 390
Code 
# Variables final values
results$objval
[1] 390
Code 
# Variables final values
results$solution
[1] 60 30
Code 
60 *5+30*3
[1] 390

so buy 5 valley(60) and buy 3 highland(30)

4 solve in linprog

Code 
#install.packages("linprog")
library("linprog")

4.1 define

Code 
# first, let's define the coefficients for the function to be optimized
f.obj <- c(5, 3)

# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(1, 0, 0, 1, 1, -2, -1, 1, 5, 2, 300, 200, 1, 0, 0, 1),
nrow = 8,
byrow = TRUE)

# Set unequality signs
f.dir <- c(">=", ">=", "<=", "<=", "<=", "<=", "<=", "<=")

# Set right hand side coefficients
f.rhs <- c(15, 25, 0, 0, 400, 24000, 70, 60)

4.2 run LP

Code 
linprog_results=solveLP(cvec = f.obj,
bvec = f.rhs,
Amat = f.con,
maximum = TRUE,
const.dir = f.dir)

4.3 result

Code 
linprog_results


Results of Linear Programming / Linear Optimization

Objective function (Maximum): 390 

Iterations in phase 1: 3
Iterations in phase 2: 1
Solution
  opt
1  60
2  30

Basic Variables
    opt
1    60
2    30
S 1  45
S 2   5
S 4  30
S 5  40
S 7  10
S 8  30

Constraints
  actual dir  bvec free    dual dual.reg
1     60  >=    15   45 0.00000       45
2     30  >=    25    5 0.00000        5
3      0  <=     0    0 0.12500       48
4    -30  <=     0   30 0.00000       30
5    360  <=   400   40 0.00000       40
6  24000  <= 24000    0 0.01625     4000
7     60  <=    70   10 0.00000       10
8     30  <=    60   30 0.00000       30

All Variables (including slack variables)
    opt cvec      min.c     max.c     marg marg.reg
1    60    5   4.500000       Inf       NA       NA
2    30    3 -10.000000  3.333333       NA       NA
S 1  45    0  -0.500000       Inf  0.00000       NA
S 2   5    0 -13.000000  0.333333  0.00000       NA
S 3   0    0       -Inf  0.125000 -0.12500       48
S 4  30    0  -0.200000       Inf  0.00000       NA
S 5  40    0         NA  0.250000  0.00000       NA
S 6   0    0       -Inf  0.016250 -0.01625     4000
S 7  10    0         NA  0.500000  0.00000       NA
S 8  30    0  -0.333333 13.000000  0.00000       NA

Same result: buy 5 valley(60) and buy 3 highland(30)

5 Reference

https://blog.uvm.edu/tdonovan-vtcfwru/files/2020/08/LinearProgramming.pdf

https://github.com/gaborcsardi/lpSolve

https://www.youtube.com/watch?v=E72DWgKP_1Y