Midterm-Exam
Nicholas Andrian
October 29, 2020
1 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\\\]
answer
## Warning: package 'lpSolve' was built under R version 3.6.2# this is the code for setting the coefficients of the objective function
obj.func <- c(4, 3)
# and the code for create constraint matrix
constr <- matrix(c(1,0,
0,1,
1,2,
-2,4,
-2,1),
nrow = 5,
byrow = TRUE)
# for the right hand side or the result for the constraints we use this code
rh <- c(0, 2, 25, -8, -5)
# for the direction of the constraints we use this code
direc <- c(">=",">=","<=","<=","<=")
# and finally for Finding the optimum solution use this code
optimum <- lp(direction="max",
objective.in = obj.func,
const.mat = constr,
const.dir = direc,
const.rh = rh,
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"## [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"#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 2 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)| resource | car_A | car_B |
|---|---|---|
| Robot | 3.0 | 4 |
| Engineer | 5.0 | 6 |
| Detailer | 1.5 | 3 |
Car A provides \(30,000\) profit, whilst 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. #Problem Definition
\[30000A+45000B\le300000\]
The constraints can be set in the following ways:
$$
3A+4B30 \ 5A+6B60 \ 1.5A+3B21 \
$$
# code for Creating constraint matrix
constraint <- matrix(c(3,4,
5,6,
1.5,3),
nrow = 3,
byrow = TRUE)
# for Creating right hand side or the result for the constraints use this code
rh_s <- c(30, 60, 21)
# and for the direction of the constraints use this code
direction <- c("<=","<=","<=")# after that we Finding the optimum solution
opti <- lp(direction="max",
objective.in = obj,
const.mat = constraint,
const.dir = direction,
const.rhs = rh_s,
all.int = T)
str(opti)## 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"## [1] 0## A B
## 2 6# Check the value of objective function at optimum point
print(paste("Maximum Profit: ",
opti$objval,
sep = ""))## [1] "Maximum Profit: 330000"So, we get the results \(A=2\) and \(B=6\). The maximum profit is \(330000\).
2 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.
3 4. Please visualize a contour plot of the following function:
\(f(x,y) = x^2+y^2+3xy\) • How coordinate descent works • How Steepest descent works • How Newton Method works • How Conjugate Gradient works
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 works is simple. This method can minimize function by successively minimizing each of the individual dimension of the function in a cyclic fashion, while holding the values of the function in the other dimension fixed.
How Steepest descent works The steepest descent is a simple gradient method for optimization. This method works with a deep slow convergence towards the optimum solution, this happens because of the steps zigzagged. When certain parameters are highly correlated with each other, the steepest descent algorithm can require many steps to reach the minimum. Depending on the starting value, the steepest descent algorithm could take many steps to wind its way towards the minimum.
How Newton Method works Newton Method works as a technique for approximating the zero generator of a function \(F(x) = 0\). This method uses tangents to approximate the intersection of a function graph with the x-axis.
How Conjugate Gradient works Conjugate gradient 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. The conjugate gradient approach begins in the same manner, but diverges from steepest descent after the first step. In subsequent steps, the direction of travel must be conjugate to the direction most recently traveled.