1

Find the maximum solution to

$Z=4x+3y$

Suppose that the objective function is to the following constaraints:

$x≥0$ $y≥2$ $2y≤25−x$ $4y≤2x−8$ $y≤2x−5$

Solve this problems using mathematical model and R packages (please explain it step-by-step).

library(lpSolve)

# Set the coefficients of the objective function
obj.func <- c(4, 3)

# Create constraint matrix
constr <- matrix(c(1,0,
                   0,1,
                   1,2,
                   -2,4,
                   -2,1),
                 nrow = 5,
                 byrow = TRUE)

# Create right hand side or the result for the constraints
rhs <- c(0, 2, 25, -8, -5)

# Create the direction of the constraints
direc <- c(">=",">=","<=","<=","<=")

# Find the optimum solution
optimum <- lp(direction="max",
              objective.in = obj.func,
              const.mat = constr,
              const.dir = direc,
              const.rhs = rhs,
              all.int = T)
str(optimum)

## List of 28
##  $ direction       : int 1
##  $ x.count         : int 2
##  $ objective       : num [1:2] 4 3
##  $ const.count     : int 5
##  $ constraints     : num [1:4, 1:5] 1 0 2 0 0 1 2 2 1 2 ...
##   ..- attr(*, "dimnames")=List of 2
##   .. ..$ : chr [1:4] "" "" "const.dir.num" "const.rhs"
##   .. ..$ : NULL
##  $ int.count       : int 2
##  $ int.vec         : int [1:2] 1 2
##  $ bin.count       : int 0
##  $ binary.vec      : int 0
##  $ num.bin.solns   : int 1
##  $ objval          : num 90
##  $ solution        : num [1:2] 21 2
##  $ presolve        : int 0
##  $ compute.sens    : int 0
##  $ sens.coef.from  : num 0
##  $ sens.coef.to    : num 0
##  $ duals           : num 0
##  $ duals.from      : num 0
##  $ duals.to        : num 0
##  $ scale           : int 196
##  $ use.dense       : int 0
##  $ dense.col       : int 0
##  $ dense.val       : num 0
##  $ dense.const.nrow: int 0
##  $ dense.ctr       : num 0
##  $ use.rw          : int 0
##  $ tmp             : chr "Nobody will ever look at this"
##  $ status          : int 0
##  - attr(*, "class")= chr "lp"

# Print status: 0 = success, 2 = no feasible solution
print(optimum$status)

## [1] 0

# Display the optimum values for W and B
solution <- optimum$solution
names(solution) <- c("x","y")
print(solution)

##  x  y 
## 21  2

# Check the value of objective function at optimum point
print(paste("Maximum: ",
            optimum$objval,
            sep = ""))

## [1] "Maximum: 90"

So the maximum value for x is 21 and 2 for y with a maximum of 90.

2

Let say you are working as consultant for a boutique car manufacturer, producing luxury cars. They run on one-month (30 days) cycles, we have one cycle to show we can provide value. There is one robot, 2 engineers and one detailer in the factory. The detailer has some holiday off, so only has 21 days available.

The cars need different time with each resource:

resource  <- c("Robot","Engineer","Detailer")
car_A     <- c(3,5,1.5)
car_B     <- c(4,6,3)
car       <- data.frame(resource,car_A,car_B)
knitr::kable(car, caption = "Work count in days")

Work count in days
resource	car_A	car_B
Robot	3.0	4
Engineer	5.0	6
Detailer	1.5	3

Work count in days

Car A provides $30,000 profit, while Car B offers $45,000 profit. At the moment, they produce 4 of each car per month, for $300,000 profit. Not bad at all, but we think we can do better for them.

# Set the coefficients of the objective function
obj.func <- c(30000, 45000)

# Create constraint matrix
constr <- matrix(c(3,4,
                   5,6,
                   1.5,3),
                 nrow = 3,
                 byrow = TRUE)

# Create right hand side or the result for the constraints
rhs <- c(30, 60, 21)

# Create the direction of the constraints
direc <- c("<=","<=","<=")

# Find the optimum solution
optimum <- lp(direction="max",
              objective.in = obj.func,
              const.mat = constr,
              const.dir = direc,
              const.rhs = rhs,
              all.int = T)
str(optimum)

## List of 28
##  $ direction       : int 1
##  $ x.count         : int 2
##  $ objective       : num [1:2] 30000 45000
##  $ const.count     : int 3
##  $ constraints     : num [1:4, 1:3] 3 4 1 30 5 6 1 60 1.5 3 ...
##   ..- attr(*, "dimnames")=List of 2
##   .. ..$ : chr [1:4] "" "" "const.dir.num" "const.rhs"
##   .. ..$ : NULL
##  $ int.count       : int 2
##  $ int.vec         : int [1:2] 1 2
##  $ bin.count       : int 0
##  $ binary.vec      : int 0
##  $ num.bin.solns   : int 1
##  $ objval          : num 330000
##  $ solution        : num [1:2] 2 6
##  $ presolve        : int 0
##  $ compute.sens    : int 0
##  $ sens.coef.from  : num 0
##  $ sens.coef.to    : num 0
##  $ duals           : num 0
##  $ duals.from      : num 0
##  $ duals.to        : num 0
##  $ scale           : int 196
##  $ use.dense       : int 0
##  $ dense.col       : int 0
##  $ dense.val       : num 0
##  $ dense.const.nrow: int 0
##  $ dense.ctr       : num 0
##  $ use.rw          : int 0
##  $ tmp             : chr "Nobody will ever look at this"
##  $ status          : int 0
##  - attr(*, "class")= chr "lp"

# Print status: 0 = success, 2 = no feasible solution
print(optimum$status)

## [1] 0

# Display the optimum values for W and B
solution <- optimum$solution
names(solution) <- c("x","y")
print(solution)

## x y 
## 2 6

# Check the value of objective function at optimum point
print(paste("Total Profit: ",
            optimum$objval,
            sep = ""))

## [1] "Total Profit: 330000"

So, with a profit of 30,000 for car A and 45,000 for car B gets a maximum of 330,000 per month, where Car A and Car B make 2 and 6. respectively.

3

Let say you would like to make some sausages and you have the following ingredients available:

Assume that you will make 2 types of sausage:

Economy (>40% Chicken)
Premium (>60% Chicken)
One sausage is 50 grams (0.05 kg)

According to government regulations of Indonesia:

The most starch you can use in your sausages is 25%.
You have a contract with a butcher, and have already purchased 23 kg Chicken, that must go in your sausages.
You have a demand for 350 economy sausages and 500 premium sausages.

So, please figure out how to optimize the cost effectively to blend your sausages.

Obj. function

$Cost=4.32(c_e+c_p)+2.46(w_e+w_p)+1.86(s_e+s_p)$

Constraints

$c_e+w_e+s_e=350 × 0.05$ $c_p+w_p+s_p=500 × 0.05$ $c_e≥0.4(c_e+w_e+s_e)$ $c_p≥0.6(c_p+w_p+s_p)$ $s_e≥0.25(c_e+w_e+s_e)$ $s_p≥0.25(c_p+w_p+s_p)$ $c_e+c_p≤30$ $w_e+w_p≤20$ $s_e+s+p≤17$ $c_e+c_p≤23$

4

Please visualize a contour plot of the following function:

$f(x,y)=x^2+y^2+3xy$

f <- function(x, y) {x^2 + y^2 + 3*x*y}
n <- 30
xpts <- seq(-1.5, 1.5, len = n)
ypts <- seq(-1.5, 1.5, len = n)
gr <- expand.grid(x = xpts, y = ypts)
feval <- with(gr, matrix(f(x, y), nrow = n, ncol = n))
par(mar = c(5, 4, 1, 1))
contour(xpts, ypts, feval, nlevels = 20, xlab = "x", ylab = "y")
points(-1, -1, pch = 19, cex = 2)
abline(h = -1)

How coordinate descent works Coordinate descent successively minimizes along coordinate directions to find the minimum of a function. At each iteration, the algorithm determines a coordinate, then minimizes over the corresponding hyperplane while fixing all other coordinates.

How Steepest descent works The method of steepest descent or stationary-phase method or saddle-point method is an extension of Laplace’s method for approximating an integral, where one deforms a contour integral in the complex plane to pass near a stationary point (saddle point), in roughly the direction of steepest descent or stationary phase.Depending on the starting value, the steepest descent algorithm could take many steps to wind its way towards the minimum.
How Newton Method works The Newton-Raphson method (also known as Newton’s method) is a way to quickly find a good approximation for the root of a real-valued function f(x)=0. It uses the idea that a continuous and differentiable function can be approximated by a straight line tangent to it.
How Conjugate Gradient works Conjugate gradient methods represent a kind of steepest descent approach “with a twist”. With steepest descent, we begin our minimization of a function f starting at x0 by traveling in the direction of the negative gradient −f′(x0). In subsequent steps, we continue to travel in the direction of the negative gradient evaluated at each successive point until convergence.

Optimization

Theodora Putrina Gea

10/29/2020

1

2

3

4