1.1 Case study

M&D Chemicals produces two products that are sold as raw materials to companies manufacturing bath soaps and laundry detergents. Based on an analysis of current inventory levels and potential demand for the coming month, M&D’s management specified that the combined production for products A and B must total at least 350 gallons.

Separately, a major customer’s order for 125 gallons of product A must also be satisfied.

Product A requires 2 hours of processing time per gallon and product B requires 1 hour of processing time per gallon.

For the coming month, 600 hours of processing time are available.

M&D’s objective is to satisfy these requirements at a minimum total production cost.

Production costs are $2 per gallon for product A and $3 per gallon for product B.

Problem: the company should produce how many products of A and B to meet the above requests and constraints with a minimum cost.

1.2 Problem formulation

1.What are decision variables need to be solved?

Denote that: x_A and x_B is the optimal gallons of product A and product B, respectively.

2.What is the objective function to optimize?

The production costs are defined: \[ 2x_A + 3X_B \]

Because the problem need to solve is optimization the number of products A and B with a minimum cost. Then, the object function is:

\[ Minimize \ 2x_A + 3x_B \]

3.What are constraints?

For the first constraint, the total products A and products B is at least 350 gallons, which is specified by managers.

\[ x_A + x_B \geq 350 \]

Then for the second constraint, major customer’s demand is satisfied that 150 gallons of Product A. \[ x_A \geq 350 \]

In addition, the process time per gallon are required 2 hours and 3 hours for Product A and Product B, respectively. The available processing time must not exceed 600 hours. The third constraint is determined: \[ 2x_A +3x_B \leq 600 \]

Of course that both of product A and B are also non-negative. \[x_A \geq 0, x_B \geq 0\]

4.How do we find the solution analytically?

First of all, we obtain all the constraints, the linear programing can be written as:

\[ Minimize \ 2x_A + 3x_B \]

\[ s.t \ x_A \geq 350 \] \[ x_A + x_B \geq 350 \] \[ 2x_A +3x_B \leq 600 \] \[ x_A \geq 0, x_B \geq 0 \]

5. Write a R code to find the solution.

library('lpSolveAPI')
# Set a linear programming with 2 decision variables, no constraints
my.lp <- make.lp(0,2) 
# set a minimize problem
lp.control(my.lp,sense='min') 

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] -1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "minimize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

set.objfn(my.lp,c(2,3))
# set the objective function
add.constraint(my.lp,c(1,0),'>=',125)
add.constraint(my.lp,c(1,1),'>=',350)
add.constraint(my.lp,c(2,1),'<=',600)
set.bounds(my.lp,lower=rep(0,2),columns=c(1:2))
solve(my.lp)

## [1] 0

# Get the optimization result:
get.objective(my.lp)

## [1] 800

# Get the result of optimization point: 
get.variables(my.lp)

## [1] 250 100

The optimal cost is 800 and with (250, 100).

2.1 Example:

Par, Inc., is a small manufacturer of golf equipment and supplies whose management has decided to move into the market for medium- and high-priced golf bags.

Par, Inc.’s distributor has agreed to buy all the golf bags Par, Inc., produces over the next three months.

The number of hours for producing each type of bag is summarized in the below table:

Available working hours for next 3 months:

• 630 hours for cutting and dyeing,
  
• 708 hours for finishing,
  
• and 135 hours for inspection and packaging will
  Profit contribution of $10 for every standard bag and $9 for every deluxe bag produced.

How to determine the number of standard bags and deluxe bags to produce in order to maximize total profit contribution.

2.1.1 Problem formulation

1. What are decision variables need to be solved?

Denote that S and D are the number of standard bags and deluxe bag, respectively.

2. What is the objective function to optimize?

The total profit contribution is: \[10S + 9D\]

The object is to maximize the total profit contribution.

\[ Maximize \ 10S + 9D \]

3. What are constraints?

Four production time limits limit the quantity of ordinary and deluxe bags that may be manufactured.

Constraint 1 : Number of hours of cutting and dyeing time used must be less than or equal to 630 hours.
\[ \frac{7}{10}S + 1D \leq 630\]

Constraint 2 : Number of hours of sewing used must be less than or equal to 600 hours.
\[ \frac{1}{2}S + \frac{5}{6}D \leq 600 \]

Constraint 3 : Number of hours of finishing used must be less than or equal to 708 hours. \[ 1S + \frac{2}{3}D \leq 708 \] Constraint 4 : Number of hours of inspection and packaging used must be less than or equal to 135 hours. \[ \frac{1}{10}S + \frac{1}{4}D \leq 135 \]

4. Write a R code to find the solution.

First of all, we obtain all the constraints, the linear programing can be written as: \[ Maximize \ 10S + 9D \] \[ s.t \ \frac{7}{10}S + 1D \leq 630\] \[ \frac{1}{2}S + \frac{5}{6}D \leq 600 \] \[ 1S + \frac{2}{3}D \leq 708 \] \[ \frac{1}{10}S + \frac{1}{4}D \leq 135 \] \[ S \geq 0, D \geq 0 \]

my.lp <- make.lp(0,2) ### Set a linear programming with 2 decision variables, no constraints
lp.control(my.lp,sense='max') ### set a maximize problem

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] 1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "maximize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

set.objfn(my.lp,c(10,9))
### set the objective function
add.constraint(my.lp,c(7/10,1),'<=',630)
add.constraint(my.lp,c(1/2,5/6),'<=',600)
add.constraint(my.lp,c(1,2/3),'<=',708)
add.constraint(my.lp,c(1/10,1/4),'<=',135)
set.type(my.lp,1:2,'integer')
set.bounds(my.lp,lower=rep(0,2),columns=c(1:2))
solve(my.lp)

## [1] 0

# Get the optimization result:
get.objective(my.lp)

## [1] 7668

# Get the result of optimization point: 
get.variables(my.lp)

## [1] 540 252

The optimal cost is 7668 and with (540, 252).

3.1 Case study

• Hewlitt Corporation established an early retirement program as part of its corporate restructuring.

• At the close of the voluntary sign-up period, 68 employees had elected early retirement.

• As a result of these early retirements, the company incurs the following obligations over the next eight years:

The cash requirements (in thousands of dollars) are due at the beginning of each year.

The corporate treasurer must determine how much money F must be set at the beginning of year 1 to meet the eight yearly financial obligations as they come due.

The financing plan for the retirement program includes investments in annually coupon bonds as well as savings.

The investments in coupon bonds with faced value $1000 are limited to three choices:

Investments in bonds can take place only in this first year, and the bonds will be held until maturity.

Any funds not invested in bonds will be placed in savings and earn interest at an annual rate of 4%.

The objective function is to minimize the total dollars F needed to meet the retirement plan’s eight-year obligation.

Problem formulation

1.What are decision variables? Let:

\(F\) = total dollars required to meet the retirement plan’s eight-year obligation

\(x_1\) = units of bond 1 purchased at the beginning of year 1

\(x_2\) = units of bond 2 purchased at the beginning of year 1

\(x_3\) = units of bond 3 purchased at the beginning of year 1

\(S_i\) = amount placed in savings at the beginning of year \(i\) for i=1,2,…,8

2.What is the objective fuction?

The objective function is to minimize the total amount needed to meet the retirement plan’s eight-year obligation.\((F)\)

\[Minimize \ F\] 3. What are constraints?

\[objective \ fuction: minimize \ F\] \[ s.t \ Year \ 1: F - 1.15x_1 - x_2 - 1.35x_3 - s_1 = 430\] \[ Year \ 2: 0.08875x_1 + 0.055x_2 + 0.1175x_3 + (1+0.04)s_1 - s_2 = 210\] \[ Year \ 3: 0.08875x_1 + 0.055x_2 + 0.1175x_3 + (1+0.04)s_2 - s_3 = 222\] \[ Year \ 4: 0.08875x_1 + 0.055x_2 + 0.1175x_3 + (1+0.04)s_3 - s_4 = 231\] \[ Year \ 5: 0.08875x_1 + 0.055x_2 + 0.1175x_3 + (1+0.04)s_4 - s_5 = 240\] \[ Year \ 6: 1.08875x_1 + 0.055x_2 + 0.1175x_3 + (1+0.04)s_5 - s_6 = 195\] \[ Year \ 7: 1.055x_2 + 0.1175x_3 + (1+0.04)s_6 - s_7 = 225\] \[ Year \ 8: 1.1175x_3 + (1+0.04)s_7 - s_8 = 255\]

4. Write a R code to find the solution.

my.lp <- make.lp(0,12) ### Set a linear programming with 12 decision variables, no constraints
# Objective function
lp.control(my.lp,sense='min') ### set a maximize problem

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] -1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "minimize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

set.objfn(my.lp,c(1, rep(0, 11)))
# Constraints
# Year 1: 
add.constraint(my.lp,c(1,-1.15,-1,- 1.35,-1, rep(0, 7)),'=',430)
# Year 2:
add.constraint(my.lp,c(0,0.08875,0.055,0.1175,1.04,-1, rep(0, 6)),'=',210)
# Year 3: $$0.08875B1 + 0.055B2 + 0.1175B3 + 1.04S2 - S3 = 222 $$
add.constraint(my.lp,c(0,0.08875,0.055,0.1175,0,1.04,-1, rep(0, 5)),'=',222)
# Year 4: $$0.08875B1 + 0.055B2 + 0.1175B3 +1.04S3 - S4 = 231 $$
add.constraint(my.lp,c(0,0.08875,0.055,0.1175,0,0,1.04,-1, rep(0, 4)),'=',231)
# Year 5: $$0.08875B1 + 0.055B2 + 0.1175B3 + 1.04S4 - S5 = 240$$ 
add.constraint(my.lp,c(0,0.08875,0.055,0.1175,0,0,0,1.04,-1, rep(0, 3)),'=',240)
# Year 6: $$1.08875B1 + 0.055B2 + 0.1175B3 + 1.04S5 - S6 = 195 $$
add.constraint(my.lp,c(0,1.08875,0.055,0.1175,0,0,0,0,1.04,-1, rep(0, 2)),'=',195)
# Year 7: $$1.055B2 + 0.1175B3 + 1.04S6 - S7 = 225 $$
add.constraint(my.lp,c(0,0,1.055,0.1175,0,0,0,0,0,1.04,-1, 0),'=',225)
# Year 8: $$1.1175B3+  1.04S7 - S8 = 255 $$
add.constraint(my.lp,c(0,0,0,1.1175,0,0,0,0,0,0,1.04,-1),'=',255)

## positive variables
set.bounds(my.lp,lower=rep(0,12),columns=c(1:12))
## natural numbers
set.type(my.lp,2:4,'integer')

solve(my.lp)

## [1] 0

get.objective(my.lp)

## [1] 1728.803

round(get.variables(my.lp),3)

##  [1] 1728.803  145.000  188.000  228.000  636.253  501.702  349.769  182.759
##  [9]    0.068    0.069    0.202    0.000

Practice

• Acompany incurs the following obligations over the next 7 years

• The cash requirements (in thousands of dollars) are due at the beginning of each year.

• The company treasurer must determine how much money F must be set at the beginning of year 1 to meet the 7-yearly financial obligations as they come due.

• The financing plan for the retirement program includes investments in annually coupon bonds as well as savings.

• The investments in coupon bonds with faced value $100 are limited to 10 choices

• Investments in bonds can take place only in this first year, and the bonds will be held until maturity.

• Any funds not invested in bonds will be placed in savings and earn interest at an annual rate of 5%.

• The objective function is to minimize the total dollars \(F\) needed to meet the retirement plan’s eight-year obligation.

Problem formulation

1. What are decision variables?

Let:

\(F\) = total dollars required to meet the retirement plan’s eight-year obligation

\(x_1\) = units of bond 1 purchased at the beginning of year 1

\(x_2\) = units of bond 2 purchased at the beginning of year 1

\(x_3\) = units of bond 3 purchased at the beginning of year 1

\(S_i\) = amount placed in savings at the beginning of year \(i\) for i=1,2,…,8

2. What is the objective function?

The objective function is to minimize the total amount needed to meet the retirement plan’s eight-year obligation.\((F)\)

3. What are constraints?

\[objective \ fuction: minimize \ F\] \[ s.t \ Year \ 1: F - 95.2x_1 - 102x_2 - 104x_3 - 110x_4 - 92.9x_5 - 97.2x_6 - 93.1x_7 - 99.5x_8 - 94.8x_9 - 109x_10 - s_1 = 150000\] \[ Year \ 2: 1000x_1 + 9x_2 + 8x_3 + 10x_4 + 5x_5 + 7x_6 + 6x_7 + (1+0.05)s_1 - s_2 = 1000000\] \[ Year \ 3: 1009x_2 + 8x_3 + 10x_4 + 5x_5 + 7x_6 + 6x_7 + (1+0.05)s_2 - s_3 = 1200000\] \[ Year \ 4: 1008x_3 + 1010x_4 + 5x_5 + 7x_6 + 6x_7 + (1+0.05)s_3 - s_4 = 1800000\] \[ Year \ 5: 1005x_5 + 1007x_6 + 1006x_7 + (1+0.05)s_4 - s_5 = 110000\]

4. Write a R code to find the solution.

library(lpSolveAPI)

my.lp <- make.lp(0,13) ### Set a linear programming with 18 decision variables, no constraints
#F,B1,B2,B3,B4,B5,B6,B7,S1,S2,S3,S4,S5

# Objective function
lp.control(my.lp,sense='min') ### set a minimize problem

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] -1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "minimize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

set.objfn(my.lp,c(1, rep(0, 12)))
# Constraints
# Year 1: F-95.2B1-102B2-104B3-110B4-92.9B5-97.2B6-93.1B7-99.5B8-94.8B9-109B10-S1=150000
add.constraint(my.lp,c(1,-952,-1020,-1040,-1100,-929,-972,-931, -1, rep(0, 4)),'=',150000)
# Year 2:
add.constraint(my.lp,c(0,1000,9,8,10,5,7,6,1.05,-1, rep(0, 3)),'=',1000000)
# Year 3: 
add.constraint(my.lp,c(rep(0,2),1009,8,10,5,7,6,0,1.05,-1, rep(0, 2)),'=',1200000)
# Year 4: 
add.constraint(my.lp,c(rep(0,3),1008,1010,5,7,6,rep(0,2),1.05,-1, rep(0, 1)),'=',1800000)
# Year 5: 
add.constraint(my.lp,c(rep(0,5),1005,1007,1006,rep(0,3),1.05,-1),'=',1100000)

## positive variables
lp.control(my.lp, 'positive', 1:12)

## $anti.degen
## [1] "none"
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] -1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "minimize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

## natural numbers
set.type(my.lp,2:11,'integer')

solve(my.lp)

## [1] 0

get.objective(my.lp)

## [1] 4648898

round(get.variables(my.lp),3)

##  [1] 4648898.000    4724.000       0.000       0.000       0.000       0.000
##  [7]       0.000       0.000    1650.000 3725733.000 2712019.000 1047620.081
## [13]       1.085

Intro

• Capital budgeting is the process of identifying and selecting investment projects that bring the most benefit (net present value) under a budget constraint.

Case study

• The Ice-Cold Refrigerator Company is considering investing in several projects that have varying capital requirements over the next four years.

• The estimated net present value for each project, the capital requirements, and the available capital over the four-year period are shown in below table.

- Four projects are independent to each other.

• Faced with limited capital each year, management would like to select the most profitable projects.

Problem formulation

1. What are decision variables?

\(x_i\) = 1, if project i accepted \(x_i\) = 0, otherwise

2. What is the objective function

\[Maximize \ 90x_1 + 40x_2 + 10x_3 + 37x_4 \]

3. What are constraints? \[Maximize \ 90x_1 + 40x_2 + 10x_3 + 37x_4 \] \[ s.t \ 15x_1 + 10x_2 + 10x_3 + 15x_4 \leq 40\] \[ 20x_1 + 15x_2 + 10x_4 \leq 50\] \[ 20x_1 + 20x_2 + 10x_4 \leq 40\] \[ 15x_1 + 5x_2 + 4x_3 + 10x_4 \leq 35\]

4. Write a R code to find the solution

library(lpSolveAPI)

my.lp <- make.lp(0,4) ### Set a linear programming with 4 decision variables, no constraints
lp.control(my.lp,sense='max') ### set a maximize problem

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] 1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "maximize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

set.objfn(my.lp,c(90,40,10,37))
add.constraint(my.lp,c(15,10,10,15),'<=',40)
add.constraint(my.lp,c(20,15,0,10),'<=',50)
add.constraint(my.lp,c(20,20,0,10),'<=',40)
add.constraint(my.lp,c(15,5,4,10),'<=',35)
set.type(my.lp,1:4,'binary')
solve(my.lp)

## [1] 0

get.objective(my.lp)

## [1] 140

round(get.variables(my.lp),3)

## [1] 1 1 1 0

Exercise

A company has identified a number of promising projects. The cash flows (with unit $1000) for the first two years are shown in the following table.

The company managers have decided that they can allocate up to $250,000 in each of the first 2 years to fund these projects. If the money spent for each year is less than the budget allowance, the remaining money can be invested at rate 5% per year and then added to the next year’s budget. The problem is to choose an optimal set of investment projects to maximize the obtained profit (net present value).

1. What are decision variables?

\(x_i\) = 1, if project i accepted \(x_i\) = 0, otherwise

2. What is the objective function?

\[Maximize \ 150x_1 + 200x_2 + 100x_3 + 100x_4 + 120x_5 + 150x_6 + 240x_7 \]

3. What are constraints? \[Maximize \ 150x_1 + 200x_2 + 100x_3 + 100x_4 + 120x_5 + 150x_6 + 240x_7 \] \[s.t \ 90x_1 + 80x_2 + 50x_3 + 20x_4 + 40x_5 + 80x_6 + 80x_7 + s_1 = 250 \] \[ 50x_1 + 80x_2 + 100x_3 + 64x_4 + 50x_5 + 20x_6 + 100x_7 - s_1 \leq 250 \]

4. Write a R code to find the solution

library(lpSolveAPI)
my.lp <- make.lp(0,8) ### Set a linear programming with 4 decision variables, no constraints
lp.control(my.lp,sense='max') ### set a maximize problem

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] 1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "maximize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

set.objfn(my.lp,c(150,200,100,100,120,150,240,0))
add.constraint(my.lp,c(90,80,50,20,40,80,80,1),'=',250)
add.constraint(my.lp,c(58,80,100,64,50,20,100,-1.05),'<=',250)
set.type(my.lp,1:7,'binary')
solve(my.lp)

## [1] 0

get.objective(my.lp)

## [1] 610

Intro

• Sometimes various projects are interdependent, i.e., the feasibility of one being dependent on whether others are undertaken.

• There are several independent goals, but each goal has more than possible method of implementation (sub-projects).

Case study: County transportation choices

A transportation authority, with the total budget 5 million dollars, wishes

• to construct a road between Augen and Burger cities: choose 1 of 4 below sub projects A1: Concrete 2 lanes A2: Concrete 4 lanes A3: Asphalt2 lanes A4: Asphalt 4 lanes

• to improve Cay Road bridge: choose 1 of 3 below sub projects

• to build more traffic control in Downsberg: choose 1 of 3 below sub projects

Problem formulation

1. What are decision variables?

\(x_i\) = 1, if project i accepted

\(x_i\) = 0, otherwise

2. What is the objective function? \[Maximize \ 4000x_1 + 5000x_2 + 3000x_3 + 4300x_4 + 1000x_5 + 1500x_6 + 2500x_7 + 300x_8 + 1000x_9 + 2000x_{10}\]

3. What are constraints?

\[Maximize \ 4000x_1 + 5000x_2 + 3000x_3 + 4300x_4 + 1000x_5 + 1500x_6 + 2500x_7 + 300x_8 + 1000x_9 + 2000x_{10}\]

\[s.t \ 2000x_1 + 3000x_2 + 1500x_3 + 2200x_4 + 500x_5 + 1500x_6 + 2500x_7 + 100x_8 + 600x_9 + 1000x_{10}\]

\[ x_1 + x_2 + x_3 + x_4 = 1\]

\[ x_5 + x_6 + x_7 = 1\]

\[ x_8 + x_9 + x_{10} = 1\] 4. Write a R code to find the solution.

library(lpSolveAPI)

my.lp <- make.lp(0,10) ### Set a linear programming with 9 decision
lp.control(my.lp,sense='max') ### set a maximize problem

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] 1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "maximize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

set.objfn(my.lp,c(4000,5000,3000,4300,1000,1500,2500,300,1000,2000)) 
add.constraint(my.lp,c(rep(1,4),rep(0,6)),'=',1)
add.constraint(my.lp,c(rep(0,4),rep(1,3),rep(0,3)),'=',1)
add.constraint(my.lp,c(rep(0,4),rep(0,3),rep(1,3)),'=',1)
add.constraint(my.lp,c(2000,3000,1500,2200,500,1500,2500,100,600,1000),'<=',5000)
set.type(my.lp,1:10,'binary')
solve(my.lp)

## [1] 0

get.objective(my.lp)

## [1] 8000

round(get.variables(my.lp),3)

##  [1] 0 1 0 0 1 0 0 0 0 1