1 Question 1

Find the maximum solution to \[Z=4x+3y\]

Suppose that the objective function is subject to the following constraints: \[\begin{eqnarray} x &\geq& {0}\\ y &\geq& {2}\\ 2y &\leq& {25-x}\\ 4y &\leq& {2x-8}\\ y &\leq& {2x-5} \end{eqnarray}\] Solve these problems using mathematical model and R packages (please explain it step-by-step).

1.1 Answer

1.1.1 Problem Definition

We would like to maximize the solution, so we must set our objective function as follows \[Z = 4x+y = MAX(solution)\] which means that \[\hat {Z} = \begin{pmatrix} 4 \\ 3 \end{pmatrix}\]

Now, We can define the coefficient matrix \[A=\begin{pmatrix} 0 & -1 \\ 1 & 2 \\ -2 & 4 \\ -2 & 1 \end{pmatrix}\] and, \[B=\begin{pmatrix} -2 \\ 25 \\ -8 \\ -5 \end{pmatrix}\] Now, we will solving the problem using lpSolve.

1.1.2 Solution with lpSolve

## List of 28
##  $ direction       : int 1
##  $ x.count         : int 2
##  $ objective       : num [1:2] 4 3
##  $ const.count     : int 4
##  $ constraints     : num [1:4, 1:4] 0 -1 2 -2 1 2 1 25 -2 4 ...
##   ..- 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 100
##  $ solution        : num [1:2] 25 0
##  $ 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
##  x  y 
## 25  0
## [1] "Maximum: 100"

So, the maximum solution is 100.

2 Question 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 Time Car A Car B
Robot 3 days 4 days
Engineer 5 days 6 days
Detailer 1.5 days 3 days

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.

2.1 Answer

2.1.1 Problem Definition

We would like to maximize the solution, so we must set our objective function as follows \[P = 30000x+45000y = MAX(profit)\] which means that \[\hat {P} = \begin{pmatrix} 30000 \\ 45000 \end{pmatrix}\]

The constraints can be set in the following ways:

  • Robot \[3x+4y \leq 30\]
  • Engineer \[5x+6y \leq 60\]
  • Detailer \[1.5x+3y \leq 21\]

Now, We can define the coefficient matrix \[A=\begin{pmatrix} 3 & 4 \\ 5 & 6 \\ 1.5& 3 \end{pmatrix}\] and, \[B=\begin{pmatrix} 30 \\ 60 \\ 21 \end{pmatrix}\] Now, we will solving the problem using lpSolve.

2.1.2 Solution with lpSolve

## 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
## x y 
## 2 6
## [1] "Maximum: 330000"

So, the maximum profit is $330000.

3 Question 3

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

Ingredient Cost($/kg) Availability(kg)
Chicken 4.32 30
Wheat 2.46 20
Starch 1.86 17

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%.
  • The most starch you can use in your sausages is 25%.
  • 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.1 Answer

3.1.1 Problem Definition

First, we need to translate the problem in a mathematical way. Let’s define the following variables

  • \(c\) is for the chicken
  • \(w\) is for the wheat
  • \(s\) is for the starch
  • \(e\) is for economy sausage
  • \(p\) is for premium sausage

Then, we set our objective function as follows \[Cost = 4.32(c_e + c_p) + 2.46(w_e + w_p) + 1.86(s_e + s_p)\]

The constraints can be set in the following ways: \[\begin{eqnarray} c_e + c_p &\leq& {30}\\ w_e + w_p &\leq& {20}\\ s_e + s_p &\leq& {17}\\ c_e &\geq& 0.4 (c_e + w_e + s_e)\\ c_p &\geq& 0.6 (c_p + w_p + s_p)\\ s_c &\geq& 0.25 (c_e + w_e + s_e)\\ s_p &\geq& 0.25 (c_e + w_e + s_e)\\ c_e + w_e + s_e &=& 350 × 0.05\\ c_p + w_p + s_p &=& 500 × 0.05 \end{eqnarray}\]

4 Question 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

4.1 Answer

  • How coordinate descent works
    • It can minimize function successively minimizing each of the individual dimensions of function in a cyclic fashion, while holding the values of function in the other dimensions fixed. This approach is sometimes referred to as cyclic coordinate descent.
  • How Steepest descent works
    • The method of steepest descent, also called the gradient descent method. 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 represent a kind of steepest descent approach “with a twist”. With steepest descent, we begin our minimization of a function \(f\) starting at \(x_0\) by traveling in the direction of the negative gradient \(−f′(x_0)\). In subsequent steps, we continue to travel in the direction of the negative gradient evaluated at each successive point until convergence.