Final Exam – Optimization, Spring 2016

2
1) Find the first derivative with respect to x of the function f (x) = −3x − 32x + 100.

f'(x) = −6x − 32

2) Find the maxima and minima of f(x) = 4x3 – 22x2 + 2x – 14 (assuming no constraints). Identify each
as a global and/or local min/max point.

f'(x) = 12x2 – 44x + 2

−b ± √ b2−4 ac
Using the quadratic formula x=
2a
'
 f ( x )=0 for x 1 ≈ 3.62∧x 2≈ 0.046

Based on the graph:

- a local maxima occurs at x ≈ 0.046, and f(x) = -13.95

- a local minima occurs at x ≈ 3.62 and f(x) = -105.31.

There is no global min/max point.

3) Repeat Problem 2, but use a constraint of x ≥ 0. Again, identify each as a global and/or local
min/max point. Discuss what changed between the original unconstrained problem and the new
constrained problem.

f'(x) = 12x2 – 44x + 2

−b ± √ b2−4 ac
Using the quadratic formula x=
2a
'
 f ( x )=0 for x 1 ≈ 3.62∧x 2≈ 0.046

Given that X >= 0 [0, infinity),

Then f(0) = -14

f(3.62) = -105.31

f(0.046) = -13.95

Therefore, on [0, infinity), f(x) achieves a maximum of -13.95 at x = 0.046 and a minimum value of
-105.31 at x = 3.62:

There is global minimum point at x = 3.62.

There is no global max point.

There is a global minimum point now that the function is constrained

4) The Foundation for Ridiculously Irrelevant Research (FRIR) has received five proposals to investigate
the growth rate of tarantula’s toenails. Each proposal can be accepted for funding next year at the
level shown in the following table, or it can be rejected. A total of $1.3 million is available for the
year.

Scores represent the value of doing each body of research as estimated by FRIR’s advisory panel.

Formulate a discrete optimization model to decide which projects to accept to maximize total score
within the available budget. Use decision variables xj = 1 if proposal j is selected and xj = 0
otherwise.

a. What is the objective function for this discrete optimization model? Write the objective
function clearly using variables as well as the ‘max’ or ‘min’ qualifier.

Maximize z=85 x 1+70 x 2+62 x 3+ 93 x 4 +33 x 5

b. What is the main constraint for this problem? Again show this as an inequality with
variables if needed.

The main constraint is the budget of $1.3 Mil, such that:

$ 700,000 x 1+ $ 400,000 x 2+ $ 300,000 x 3+$ 600,000 x 4 +$ 400,000 x 5 ≤ $ 1.3 million

c. Determine by inspection (without the Solver) what the optimal solution is to this problem.
You can check your answer with the Solver. Don’t just provide the answer but explain the
thought process you used to find the answer (without the help of the Solver).

Each proposal is less than the total budget, so any proposal could form the optimal
solution, given the budget constraint. I think that Proposal 4 will be selected because it
has the highest value. The next proposal with a high value is Proposal 1 at a funding of
$700,000 and both proposals will bring a value of 178 at $1.3 Mil, which is equal to the
budget.

The next proposals to consider are 2 and 3. Both amount to a funding of Proposal 1
($700,000), but they bring a higher value than Proposal 1 {(70+62) > 85}. Therefore,
it is better to accept proposal 2 and 3 than proposal 1.

Hence, the optimal solution is x1 = 0, x2 = 1, x3 = 1, x4 = 1, x5 = 0 with a z = 1.3

million. The solution excludes proposal 1 and proposal 5.
5) Gradient Search - You are finding the maximum of the function f(x,y) = 6 - x 2 + 3xy – y4 and you will
start searching for that maximum at the point (2,2). (note that we are not actually finding the
maximum but instead just doing the first few steps of the process).
a. Identify the gradient of the function.

'
f ( x , y ) =¿)
b. Identify the direction of greatest ascent at the point (2, 2).

Given(x o , yo)=(2 , 2)
'
f ( 2 , 2 )=¿) = (2, -26)
'
Then ( x 1 , y 1 ) =( xo , yo ) +r f ( xo , yo )
= (2, 2) + r (2, -26)
= (2+2r, 2-26r)

Thus h(r1) = f(x1, y1) = f(2+2r, 2-26r)

= 6 – (2+2r)2 + 3(2+2r)(2-26r) – (2-26r)4

Using the Wolfram Alpha online tool service, then h’(r1) = 0 and r1 = 0.0323072

Therefore (x1, y1) = (2.065, 1.160), meaning y is the variable with the largest rate of
improvement and that y is decreasing.

c. Calculate how far you will travel in this direction until improvement in the objective function
value stops.

The value of y will continue to decrease until all a corner point in the solution space is
reached. At the corner point, then the value of x will change to reach an improved corner
point, until an optimum point is reached.
6) Suppose that the decision variables of a mathematical programming model are:

xi,j,t = acres of land plot i allocated to crop j in year t

where i = 1,…, 47; j = 1,…, 9; t = 1,…, 10. Use summation and indexed notation to write
expressions for each of the following systems of constraints in terms of these decision variables:

a. At least ¼ of the total acreage planted in year 2 must be in corn (crop j = 4).

Sum (0.25xi,4,2) > 0

b. Exactly 5,000 acres must be devoted to soybeans (crop j = 2) each year.

Sum( Xi,2,t ) = 5000

7) An agricultural equipment company sells its main product at the rate of 8 units per week. Due to the
large setup cost of $4,500, the product is manufactured every few weeks in fixed sized lots. The
holding cost of finished products is $200 per week. The company wishes to choose their fixed lot
size to minimize the average inventory and setup cost per week assuming the demand occurs
smoothly at the given rate. Formulate a 1-variable unconstrained NLP to choose an optimum lot size.
Describe how you created the objective function. Be sure to include information about the decision
variable(s) you are using, identify how you calculated the average inventory, the setup cost, etc.
Your solution should include a function as well as a paragraph or two describing your reasoning.

Holding cost: $200 / week

Units produced: 8 / week

Cost of holding each unit = $25

Minimize Z = 25x
8) The table that follows shows the activities required to construct a new computer laboratory, along
with their estimated durations (in weeks) and predecessor activities. Show all calculations for these
problems.

a. Construct the corresponding CPM project network.

b. What is the critical path?
c. What is the earliest possible time for the project to finish?

See the image below:

9) In the Bridges of Konigsberg problem that you did in class this semester, you identified that we
would need to add 2 bridges to allow us to make a round-trip. Unfortunately the Konigsberg city
council will only allow a total of 7 bridges in town. Identify a possible solution allowing a round-trip
to be made while still having only 7 bridges. (Hint: One solution might include moving a bridge; or
tearing one down and rebuilding it elsewhere)

Describe your solution by including a new picture of the town after the construction. Identify what
the round trip path is and any characteristics about locations A, B, C, and D that helped you arrive at
this result.

The original bridges, when represented as a network, with nodes representing the sections and arcs
representing the bridges, results in an odd number of arcs incident onto each node. Since a desired
solution cannot be constructed with odd number of arcs, my idea was to reconstruct the network
(demolish and rebuild a bride elsewhere) such that the number of arcs incident onto each node is
even. See the images below:

Figure 1: Network with odd incident arcs

Demolishing the arc between C and D, results in an even number of arcs incident onto each node as
shown below:
Figure 2: Network with even incident arcs

With the new setup, the path is as shown below, and the path starts from B.
10) Life Cycle Assessment – Suppose that you are an Engineering Manager at an architectural firm in
Platteville. You are asked to generate an LCA scope document for two competing floor coverings,
granite tile from Italy and wood flooring produced in Canada. Write a scope that includes the stages
of the LCA, the functional unit, and any other pertinent information one might need.

The goal of this study is to conduct a comparative assessment of the environmental impacts of two
competing floor coverings: granite tile from Italy and wood flooring produced in Canada. The study
covers the following life cycle stages for both floor covering systems:

1) Raw Material Acquisition

2) Manufacturing
3) Use / Reuse / Maintenance
4) Recycle / Waste Management

The functional unit for this study is 1 square foot of flooring over a 100 year period. The time period
was chosen based on the life expectancy of both systems found at nachi.org/life-expectancy.htm.

This study excludes the:

- Human health impacts that may result from the natural aging of both systems and the aging as
a result of use. The study also excludes:
- Environmental impacts of the different cleaning detergents used to clean each flooring system.
- Acquisition of the raw materials used for packaging both flooring systems

The study also assumes: that the emissions of the electric energy production in Italy is relative to
the Canadian energy system; and the transportation impact in Italy is relative to the Italian
transportation system.

11) Describe what sensitivity analysis is and how it can be used. As part of your solution, give an
engineering situation where sensitivity analysis can be used and be sure to clearly describe how it
would be used. You don't need to discuss the mechanics of how one performs the analysis but
instead why it would be used and what a manager might look for.

A sensitivity analysis be used to demonstrate the effectiveness of a proposed model, to provide

information regarding what happens to the optimum when parameters of a linear programing model
are changed. Sensitivity analysis is a study of the how sensitive a solution is to changes in the data
(parameters of the linear programming model).

One application is in the field of radiation therapy treatment planning (cancer treatment) when
deciding how much dose to deliver to a tumor. Suppose an Oncologist prescribes 30 MUs to
structure A, 10 MUs to structure B (which happens to be a critical structure), 50 MUs to structure D
and 60 MUs to a tumor. A Dosimetrist then creates a plan as requested by the Oncologist and uses
radiation therapy planning software to create an optimum solution. A sensitivity analysis of the plan
could be used to provide information about how dose prescribed to one structure (the tumor) is
dependent on the dose prescribed to another structures. Specifically, how much the critical structure
could be spared from the effects of radiation dose, if dose prescribed to the tumor is increased or
reduced.
12) What are Monte Carlo simulations and can you think of a way to use these simulations to
approximate the value of pi? Write several sentences to provide clear answers to these two
questions and clearly describe how the simulations would produce the numerical value of pi.

Monte Carlo simulation is a modeling tool used approximate or forecast stochastic or deterministic
parameters based on random sampling; it is a simulation tool that uses random numbers to perform
simulation or approximate a solution to a problem.

Suppose you have a circle with a unit square, then the ratio of the area of the circle and the square
is as follows:

Ac π∗r∗r π
= =
As 4∗r∗r 4

Ac
 π=4
As
Suppose a dart player is attempting to throw darts inside the unit square. Some darts will fall inside
the circle and some darts will fall outside the circle (inside the square). The ratio of the darts that fell
inside the circle and those that fell outside the circle is can be used to represent the ration of the
area of the circle and the square.

To demonstrate the randomness of the modeling tool, if the player throws 100 darts and 80 of them
fall inside the circle, then π will be estimated as 4*0.8 = 3.2