We know the secret of your success
PAPER TITLE: OPTIMIZATION
EXAM DATE: FRIDAY 14, JUNE 2013
COURSE CODE: M373/J
Question 1
Consider the equation
(a) By drawing a sketch show that there are exactly two roots in the interval [1.5, 5]. State approximate values for these roots, to one decimal place.
(b) Show that the iterative scheme
satisfies the conditions for a contraction mapping on the interval [1.5, 2].
(c) Starting with your approximation to the root in [1.5, 2], use the iterative scheme in (b) to determine the root correct to four decimal places. Justify the stopping criterion used.
(d) Explain why the same iterative scheme would not be suitable to use to try to find the other root in [1.5, 5].
ANSWERS(Purchase full paper to get all the solutions)
1a)
1.5
2
2.5
3
3.5
4
4.5
5
0.16
-0.04
-0.11
-0.08
-0.003
0.03
From the graph
The root = 1.86 and 4.75
1b)
The fixed point x0 = 1.75
at x = 1.5
at x = 2
Since
This means that
1c)
2nd iteration
The stopping criteria = 0.0245
1d)
the iterative scheme will not be suitable to use to try to find the other root in [1.5, 5] because the scheme does not fit into the original formular, and thus may not converge at the interval
Question 2
(a) The LU decomposition of A is given by
(Use this to find the solution of the equation Ax = b, where b = [1, 3, 10]T
(b) Consider the following system of equations
3x1 - 5x2 + x3 = -1
2x1 − 3x2 + 7x3 = 2
10x1 + x2 -x3 = 8.
(i) By reordering the equations, obtain a system of equations for which the Gauss–Seidel method is guaranteed to converge. Explain why convergence is guaranteed.
(ii) Use the Gauss–Seidel method with the starting value x(0) = [0, 0, 0]T to find the solution of the equations to an accuracy of three decimal places. Use a stopping criterion of ε = 5 × 10−4.
Question 3
(a) The equation
has a root at 9.995 441 (to six decimal places) when c = 0.1. When c is subject to small changes about the value 0.1, determine whether or not the problem of finding the root is
(i) absolutely ill-conditioned,
(ii) relatively ill-conditioned.
(b) Use the Newton–Raphson method to find the root of the equation 1x - = 0 correct to six decimal places.
(c) Use your result from (b) to find the absolute and relative changes to the root when c is changed from 0.1 to 0.11 and compare your results with your conclusions in (a).
Question 4
The system of equations
has a root near [−1, −1]T .
a(i) Write down the Jacobi iteration scheme for this system of equations in the order given.
(ii) When attempting to find the root near [−1, −1]T the Jacobi iteration scheme diverges. Show why convergence could not be guaranteed.
(b) Use the add-Nx method to determine the root correct to two decimal places.
Question 5
A supermarket chain wishes to build a store to serve two towns, A and B, which are 10 kilometres apart. They need to determine at which point between the two towns they should build the store so as to maximise their average weekly income. They surveyed the residents of A and B to find how many shoppers would visit the store weekly, how far they would be prepared to travel, and how much their average weekly spend would be. For town A, the number of shoppers, a, prepared to travel to the store if it were situated x km from A could be modelled by
where k is a positive constant.
For town B, with a smaller population than town A, the number of shoppers, b, prepared to travel to the store if it were situated x km from A could be modelled by
where k is the same constant as before. When questioned about how much they would spend, it was found that a shopper from B would spend on average 10% more than a shopper from A. The supermarket chain wishes to construct a mathematical model to help them solve their problem.
(a) State the purpose of the mathematical model.
(b) Show that the total average weekly income of the new store can be modelled by
where K is a positive constant.
State clearly the assumptions made in deriving the above model.
(C) Use the model to find the optimum position for the store.
Question 6
Consider the following linear programming model in standard form:
maximize z = 2x1 − x2 + x3
subject to 2x1 + 2x2 − 3x3 ≤ 4
x1 + x2 + x3 ≤ 10
2x1 − x2 + x3 ≤ 8
x1, x2, x3 ≥ 0 .
(a) Write down the model in matrix canonical form and show that the all-slack point is feasible. [3] (b) Solve the model using the simplex method starting from the all-slack point. [Note: at most three iterations of the simplex method are required to find the solution.] You may find the following useful:
Question 7
The UK Government must formulate a long-term electrical power policy which takes account of the consumer demand, costs, greenhouse gas emissions, and reliability. In this simplified model, five power sectors are considered: nuclear power, coal, gas and two renewables: onshore and offshore wind. The following table gives, for each power sector, the average annual generation costs (incorporating capital construction and decommissioning costs) in £Million per TWh (terawatt hour) and the contribution to greenhouse gas emissions in Mt (mega tonnes) of CO2 equivalent per TWh (including the carbon footprint of construction etc).
The Government imposes the following constraints on annual energy generation:
1. Capacity: The total energy generated shall be at least 350 TWh.
2. Nuclear: Nuclear power generation cannot exceed more than 70 TWh, because of public concerns over nuclear safety.
3. Variability: At least 245 TWh must be generated by nuclear, coal and gas to ensure consistency of supply.
4. Onshore: Onshore wind generation cannot exceed 35 TWh, because of pressure-group campaigns against windmills in the countryside.
5. CO2 emissions: Greenhouse gas emissions from electricity generation cannot exceed 160 Mt of CO2 equivalent, due to continued international commitments.
6. Coal: At least 70 TWh must be generated by coal, to support the UK’s coal industry.
7. Renewables: Renewables must provide at least 70 TWh, to conform to EU Directive 3.14159/2.71828.
The Government wishes to obtain the optimal electricity generation for each sector so as to minimize the total annual cost of electricity generation.
(a) Formulate the Government’s model as a linear programme, writing down the model in canonical form. What is the all-slack point? Is it feasible? If not, what pseudo-objective and initial pricing vector should be used for the first iteration of Phase 1 of the two-phase simplex method, starting from the all-slack point?
(b) Perform one iteration of the two-phase simplex method and find a new basic point. Is this new basic point feasible? Write down the objective or pseudo-objective function for the second iteration of the two-phase simplex method.
(c) The problem was solved using a Mathcad worksheet, which produced the solution and ranging information below, rounded to two decimal places.
Use this Mathcad output to answer the following questions (there is no need to re-solve the problem if the basis list needs to be changed).
(i) What would be the effect on the optimal cost if the amount of energy permitted from Nuclear (b2) was increased from 70 TWh to 150 TWh ?
(ii) What would be the effect on the optimal solution if the cost (c5) of 1 TWh of Offshore wind reduced from £Million 180 to £Million 120 ?
Variable name list (only first five shown): [ “Nuclear”, “Coal”, “Gas”, “Onshore Wind”, “Offshore Wind”, . . . ]T
Optimal vertex x = [70, 70, 140, 35, 35, 0, 0, 35, 0, 20.35, 0, 0]T
Reduced costs d = [0, 0, 0, 0, 0, 95, 5, 0, 85, 0, 30, 85]T
Optimal value z = −37975
Shadow prices w = [−95, 5, 0, 85, 0, −30, −85]T
Question 8
To feed her hungry dog, Mrs Hubbard uses her spare room to make Little Red Riding Hood and Cinderella dolls to sell each week at the town fair. The manufacture is an elaborate process for which each doll must be allocated its own workspace. The total workspace available is 40m2. Mrs Hubbard has £52 to buy materials and she and her husband work 9 hours on the dolls between them. The following table shows t8ihe workshop space required for each doll, the purchase cost of material for each doll, the number of person-hours required for each doll’s manufacture and the profit obtained from the sale of each doll.
(a) Formulate Mrs Hubbard’s problem as an integer programming model, given that she wishes to maximise her profit, assuming she can sell all the dolls she makes.
(b) Solve the model using the branch-and-bound method, stating clearly the branching strategy used, and hence determine how many dolls of each type should be manufactured. Solve each continuous sub-problem graphically and show the details of the solution in a table of the following kind.
(c) Extend your model in (a) using a 0-1 variable so that Mrs Hubbard can determine whether or not she should replace Cinderella dolls by Snow White dolls. The manufacture of a Snow-White doll requires a work space of 6m2, material costing £9, and 1.5 person-hours, and gives a profit of £5. You are NOT required to solve this extended model.
Question 9
Consider the primal linear programming model:
maximize z = cT x
subject to Ax ≤ b, x ≥ 0 and its dual model:
minimize z = bT w subject to AT w ≥ c, w ≥ 0 .
(a) Show that if x and w are feasible points of the primal and dual models respectively,
then cT x ≤ bT w .
(b) Deduce from part (a) that if x∗ and w∗ are feasible points of the primal and dual models respectively and cT x∗ = bT w∗, then x∗ and w∗ are solutions of the primal and dual models respectively.
(c) Show that if the primal model is unbounded (so that the optimal value of the objective z is ∞), then the dual model is infeasible. What is the corresponding statement for an unbounded dual model? No proof is required.
Hint: Recall that for any matrices or vectors P, Q for which the expressions make sense: (PQ)T = QTPT , (PT )T = P, and, if PTQ is scalar, then PTQ = QTP
a = k(1.01 - 0.01e0.4x), (0 ≤ x ≤ 10)
b = k (0.52 - 0.02e0.2(10-x) , (0 ≤ x ≤ 10)
I = K (1.582 - 0.01e0.4x - 0.022e0.2(10-x)
Question 10
Consider the function
which is unimodal in the interval [−2, 2]
(a) Use an interval location method, with h = 0.1 and x0 = 0, to determine an interval containing the local minimizer.
(b) Perform three iterations of the grid search with three internal points to reduce the size of the interval located in part (a).
(c) How many iterations and function evaluations would be required to determine the local minimizer correct to three decimal places starting with the interval located in part (a).
(d) Name a more efficient interval reduction method and determine how many iterations and function evaluations would be required to find the local minimizer correct to three decimal places starting with the interval located in part (a).
Question 11
(a) Find and classify the stationary point of f.
(b) Why is x(0) = [0, 0]T not suitable as a starting point for the Newton–Raphson method without line searches, applied to finding a local minimizer of f?
(c) Perform two iterations of the Newton–Raphson method without line searches, starting with x(0) = [−1, 0]T . Why does the method break down at this point?
(d) How could the Newton–Raphson method be modified to overcome the difficulties in parts (b) and (c)?
Question 12
Consider the following model:
(a) Write down the Lagrangian function L(x, μ) and hence derive the first-order necessary conditions for a constrained local minimizer.
(b) Show that α = [2, −1]T is a constrained stationary point of the model and determine the value of the corresponding Lagrange multiplier. Show further that α is a constrained local minimizer.
Question 13
Compare and contrast the following three methods for solving unconstrained minimization problems (i) Newton–Raphson method with line searches
(ii) The Rank One method
(iii) The BFGS method. Your answer should outline how each method works together with its strengths and weaknesses.
Purchase full paper by adding to cart
Last updated: Sep 02, 2021 10:56 AM
Your one-stop website for academic resources, tutoring, writing, editing, study abroad application, cv writing & proofreading needs.
