We know the secret of your success
PAPER TITLE: OPTIMIZATION
EXAM DATE: FRIDAY 3, JUNE 2016
COURSE CODE: M373/G
Question 1
Consider the equation
(a) By drawing a suitable sketch, or otherwise, show that there are exactly two solutions of this equation in the interval [0, π]. Hint: You should see that the solutions are 0.5 and 2.4 correct to one decimal place.
(b) Show that the iterative scheme
satisfies the conditions for a contraction mapping on the interval [0.4, 0.6].
(c) Starting with x0 = 0.5 as an approximation to the solution in [0.4, 0.6], use the iterative scheme in part (b) to determine the solution correct to four decimal places. State the stopping criterion used. (d) Explain why the same iterative scheme would not be suitable to use to try to find the other solution in [0, π].
ANSWERS(Purchase full paper to get all the solutions):
1a)
Both lie within the interval [0,
1b)
The fixed point x0 = 0.5
Since 0 and 0 0<0.4<0.5
This means that
1c)
x0 = 0.5
The stopping criteria = 0.0055
1d)
It will not be useful to find other solution because the iterative schemes will not converge
Question 2
(a) The LU decomposition of a matrix A is given by
A =
Use this to find the solution of the equation Ax = b, where b = [8, −1, −4]T
(b) Consider the following system of equations
10x1 + 10x2 − x3 = 8,
−20x1 + 5x2 + 10x3 = 12,
220x1 + 5x2 − 10x3 = 6.
(i) Scale x1 by an appropriate factor of 10 and reorder the equations to 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.4, 0.8, 0.9]T to find the solution of your equations to an accuracy of three decimal places. Use a stopping criterion of
.
Hint: You should not need to perform more than four iterations of the Gauss–Seidel method. Write down the solution of the original equations to an accuracy of three decimal places.
Question 3
(a) The equation
has a root at 5.937 324 (to six decimal places) when c = 0.5. When c is subject to small changes about the value 0.5, 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 with starting value x0 = 6 to find the root of the equation correct to six decimal places.
(c) Use your result from part (b) to find the absolute and relative changes to the root when c is changed from 0.5 to 0.55 and compare your findings with your answers to part (a).
Question 4
The system of equations
has a root near [−0.5, 0.8]T .
(a) (i) Write down the Jacobi iteration scheme for this system of equations in the order given.
(ii) Show that convergence to the root near [−0.5, 0.8]T cannot be guaranteed for the Jacobi iteration scheme.
(b) Use two iterations of the add-Nx method to determine the root correct to two decimal places. You should verify that the relevant stopping criterion (which you should state clearly) has been satisfied.
Question 5
Gwilym wishes to construct a pond in his garden. The pond must have a volume of 25 m3 and be of uniform depth, with a square base. The base of the pond is to be covered with plastic sheeting. The sides of the pond are to be lined with mosaic tiles. These tiles are also to be used to construct a path on the ground, around the edge of the pond, one metre wide. (The path consists of four rectangular sections, each one along one of the edges of the pond, and four quarter-circles, one at each corner of the pond.)
The cost, per square metre, of putting the tiles on is 10 times that for laying the plastic sheeting on the base. Gwilym 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 length x of the side of the pond should satisfy the equation
(c) Verify that x lies between 4.50 m and 4.58 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 = 2x1 − x2 + 3x3
subject to
3x1 + x2 + x3 ≤10
2x1 + x2 + 2x3 ≤12
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 point. 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 x2 in the objective have to change for it to bring about a change in the solution?
Question 7
maximize z = 8x1 − 5x2 + 4x3 + 3x4
7x1 − x3 + 3x4 ≥6
5x1 − x2 − 4x3 − x4 ≤5
7x1 − 2x2 − 3x3 + 4x4 = 4
x1,...,x4 ≥0.
(a) Write the model in canonical form, including any artificial variables where appropriate. Show that the all-slack point is infeasible, and hence write down the pseudo-objective and initial pricing vector for the first iteration of phase I of the two-phase simplex method when applied to this model.
(b) Perform one iteration of the two-phase simplex method and find the new basic point. Determine whether this new basic point is feasible and hence write the objective or pseudo-objective for the second iteration of the two-phase simplex method.
(c) The problem was solved using a Maxima worksheet which produced the following solution and ranging information, rounded to two decimal places.
Ranging information
Ranges of values for which the optimal basis list remains optimal. right-hand side vector b
Use these results to answer the following questions.
(i) What would be the effect on the solution if the right-hand side of the second constraint changed from 5 to 6?
(ii) What would be the effect on the solution if the cost coefficient of x2 changed from −5 to −7?
Question 8
A small assembly factory produces mobile phones and cameras. Production involves three processes: assembly, testing and packaging. 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 an integer programming model for maximizing the factory’s weekly profit.
(b) Solve the model using the branch-and-bound method, stating clearly the branching strategy used, and hence determine the number of kits of each type that should be assembled each day. 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 part (a) using one or more 0-1 variables so that the factory can determine whether or not it should replace mobile phones by GPS devices. The assembly of a GPS device takes 9 person-hours, testing takes 9 person-hours, and packaging takes 5 person-hours. The profit per GPS device is 42
Question 9
A family business makes three kinds of bicycle parts: water bottle cages, stands and mud guards. The production of these items involves three processes in the following order: first Amy moulds each item, then Boris paints each item and finally Catrin varnishes each item. Each process can only be applied to one item at a time, but the team can work on different objects at the same time. The times in minutes to complete each process are as follows:
The business wants to produce sets of three items, one of each type, in the shortest possible time. (a) Formulate the business’s problem as an integer programming model.
(b) Determine a feasible point for the model you derived in part (a).
(c) By considering the total time to process the water bottle cage, find a lower bound for T, the total time to process all three objects. Hence determine whether your solution to part (b) is optimal.
Question 10
Consider the function
(a) Perform one iteration of the steepest descent method, starting from x(0) = [0, 0]T , to find an approximation to a local minimizer of f. Determine the line minimizer analytically. Determine the search direction for the second iteration.
(b) Find, and classify, all the stationary points of the function.
(c) Describe briefly how you might have determined the starting vector in part (a), had it not been given.
Question 11
(a) Determine analytically the global minimizer of f.
(b) Perform one iteration of the rank one method, starting from x(0) = [0, 0]T and with H(0) = I, to find an approximation to a local minimizer of f. Determine the line minimizer analytically. Determine the updated approximate inverse Hessian matrix H(1).
(c) What is the maximum number of iterations required for the convergence of the rank one method for this function?
(d) State two advantages of the rank one method over the Newton–Raphson method. State one disadvantage of the rank one method over the BFGS method.
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 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
(a) Describe the basic steps in a line-search method for the unconstrained minimization of a function f of n variables.
(b) Discuss the advantages and disadvantages of the following methods for performing the line search in the procedure that you described in part (a):
(i) the Newton–Raphson method.
(ii) the grid search method.
(c) Explain how inexact line searches are implemented and how they can improve the efficiency of a line-searching method.
Purchase full paper by adding to cart
Last updated: Sep 02, 2021 11:02 AM
Your one-stop website for academic resources, tutoring, writing, editing, study abroad application, cv writing & proofreading needs.
