We know the secret of your success
PAPER TITLE: OPTIMIZATION
EXAM DATE: MONDAY 19, JUNE 2009
COURSE CODE: M373/L
Question 1
A sketch of the function
shows that there is a minimum point at x = 1.2 approximately and a maximum point at x = 2.5 approximately.
(a) Show that the exact positions of these turning points satisfy the equation
(b) Show that the iterative scheme
satisfies the conditions for a contraction mapping on [2, 3].
(c) Starting with the initial approximation x0 = 2.5, use the iterative scheme in (b), with an appropriate stopping criterion, to find the x-coordinate of the turning point in [2, 3] correct to three decimal places.
(d) Explain why the same iterative scheme would not be suitable to use to try to find the turning point in the interval [1, 2].
ANSWERS(Purchase full paper to get all the solutions):
1a)
At the truing point 0
Divide all through by
Divide by
1b)
The fixed point x0 = 2.5
4
at x = 2
at x = 3
Since
1c)
The x-coordinate of the turning point = 2.514 ( to 3 decimal place).
1d)
The iterative scheme will not be useful in the interval (1,2) because it will not give the maximum and the minimum value, respectively.
Question 2
(a) The LU decomposition of A is given by
(Use this to find the solution of the equation Ax = b, where b = [5, -5, 8]T
(b) Given that
determine the absolute condition number and an upper bound on the relative condition number for the system with respect to small changes in the right-hand sides of the equations. Comment on the absolute and relative conditioning of the problem
(c) Reorder the equations in the system
Ax = [6, −6, 10]T
so that the Gauss–Seidel method is guaranteed to converge. Use the Gauss–Seidel method to find the solution of these equations to an accuracy of two decimal places. You should use your results from (a) and (b) to choose a suitable starting vector and use a stopping criterion of ε = 5 × 10−3.
Question 3
(a) The largest root of the equation
is at x = 9.666 328 (to six decimal places) when c = 0.001. When c is subject to small changes about the value 0.001, determine whether or not the problem of finding the largest root is
(i) absolutely ill-conditioned,
(ii) relatively ill-conditioned.
(b) Use the Newton–Raphson method to find the root of the equation 1x3-1x5-0.0009= 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.001 to 0.0009 and compare your results with your conclusions in (a).
Question 4
Consider the system of non-linear equations
(a) By drawing a sketch, show that there are two roots of this system of equations in the region
(b) Write down the Jacobi iteration scheme for this system of equations in the order given.
Show that it is a contraction mapping on the region
.
(c) Starting with the initial approximation x0 = [0.1, 0.4]T , use the Gauss–Seidel method, with an appropriate stopping criterion, to determine the root in R to three decimal places.
Question 5
John wishes to construct a circular pond in his garden. The pond is to have a volume of 20m3 and is to be of uniform depth. The base of the pond is to be covered with plastic sheeting. The side of the pond is to be constructed from small tiles. These tiles are also to be used to construct a path on the ground, half a metre wide, round the edge of the pond. The cost, per square metre, of putting the tiles on is 20 times that for laying the plastic sheeting on the base. John wishes to know what dimensions the pond should have to keep its overall cost of construction to a minimum. A mathematical model is required to solve the problem.
(a) State the purpose of the mathematical model.
(b) Create a mathematical model to solve the problem. State clearly any assumptions that you make and identify any variables that you use. Show that the radius r of the pond should satisfy the equation
(c) Verify that r lies between 3.10 m and 3.18 m. Use the bisection method to find its value correct to two decimal places. Calculate the corresponding depth of the pond.
Question 6
Consider the following linear programming model:
maximize z = 3x1 + x2 + 4x3
subject to
4x1 + x2 + 2x3 ≤ 12
2x1 + 3x2 + 2x3 ≤ 14
x1, x2, x3 ≥ 0
(a) Express the model in canonical form and show that the all- slack point is feasible.
(b) Perform one iteration of the simplex method for this model starting from the all-slack solution. State the new basis list and the new feasible point.
(c) Perform the next iteration of the simplex method. Comment on your solution. If a solution has been found, state it.
(d) By how much would the coefficient of x1 in the objective have to change for it to bring about a change in the solution.
Question 7
A family sell their handmade jewellery at various craft fairs. Each week they make earrings, pendants and brooches for sale. The family have available between them 80 person-hours per week to make items of jewellery. They have 0.12m3 of storage in their portable display case and they budget £100 per week for buying raw material. They also have an agreement with a local souvenir shop to supply 20 brooches per week. The amount of profit, labour and storage space in their portable display case is given in the following table together with the cost of raw materials for each item of jewellery.
(a) Formulate the family’s problem as a linear programming model in standard form, given that they wish to maximize their weekly profit.
(b) State the dual of the model.
(c) Show that the primal problem has a feasible solution involving only brooches. Find a feasible solution to the dual model. Deduce that the primal model has an optimal solution.
(d) If the optimal solution to the primal model is to make 20 pendants and 20 brooches use the complementary slackness principle to determine the optimal solution to the dual model.
Question 8
A small assembly factory produces televisions and DVDs. Production involves three processes: assembly, testing and delivery to the wholesalers. The following table gives the time in person-hours for each process, the total number of person-hours available per week and the profit for each appliance.
(a) Formulate the factory’s problem as an integer programming model, given that the factory wishes to maximize its weekly profit.
(b) Solve the model using the branch-and-bound method, stating clearly the branching strategy used, and hence determine the quantity of each appliance which the factory should produce. Solve each continuous sub-problem graphically and show the details of the solution in a table of the following kind.
(c) The wholesaler requires the factory to produce at least 4 DVDs a week or it will use another supplier. Write down the extra constraints needed to the model in (a) to ensure that if the factory assembles DVDs then it must produce at least 4 per week to satisfy the wholesaler.
Question 9
Mr Harris is a volunteer driver for the local community. Each Monday morning, he walks to the community centre to collect its vehicle in order to drive around the neighbouring villages to collect three elderly people from their homes to take them to their weekly luncheon club at the community centre. The following table gives the distance in miles between the homes and the centre.
(a) Formulate Mr Harris’s problem as an integer programming model using 0–1 variables with the objective of minimizing the number of miles he must drive on Monday mornings. Explain carefully how each constraint in the model has been derived.
(b) Determine a feasible point for the model you derived in (a).
(c) Suggest a strategy for solving this problem which does not require a complete formulation of the model.
(d) Miss Jones likes to be picked up first so she can have a longer drive in the surrounding countryside. How would the model change if Mr Harris agrees to her request?
Question 10
Consider the function
(a) Find and classify the stationary points of f.
(b) For those stationary points you have classified as local minimizers, determine the absolute and relative conditioning of the problems of finding that local minimizer and the corresponding local minimum when the coefficient of x13 is subject to small changes in value.
Question 11
(a) Consider the function
Perform one iteration of the Newton–Raphson method with line searches, starting from x(0) = [0, 0]T , to find an approximation to a local minimizer of f. Determine the line minimizer analytically.
(b) Explain why, when using the Newton–Raphson method with line searches to obtain a local minimizer of a function f, you might need to use a matrix of the form G(x(r) ) + νI where G is the Hessian matrix for f, x(r) is the current iterate, I is an identity matrix and ν is a number.
Explain also how the matrix G(x(r) ) + νI is used and how you might obtain a suitable value for ν.
(c) Explain how inexact line searches are implemented and how they can help improve the efficiency of the Newton–Raphson method with line searches.
Question 12
Consider the following model:
(a) Determine the KKT points of the model at which at most one of the constraints is active, and the corresponding Lagrange multipliers.
(b) Determine whether any of the KKT points you obtained in (a) are constrained local minimizers.
Question 13
Two large towns are separated by a mountain range, through which it is desired to construct a road linking the towns. Because of the height of the mountains, it is expected that it will be necessary to construct one or more tunnels. The road will also need to take account of other obstacles such as lakes and rivers and of the contours of the mountain range. It is intended that the route for the road will be planned with the aid of mathematical modelling, with a view to trying to find the best route at reasonable cost. Outline the process, from simple initial model through various revisions to final model, that you would foresee as being necessary. Suggest the type of model that is likely to be created at each stage of the process. Also indicate which method you might use to solve the model created at each stage, giving reasons for your choice, and indicate how you would determine starting values and stopping criteria in each case. Indicate the outcome of the process. Note that you are not expected to give details of the models you suggest, merely an outline of their form.
Last updated: Sep 02, 2021 10:55 AM
Your one-stop website for academic resources, tutoring, writing, editing, study abroad application, cv writing & proofreading needs.
