We know the secret of your success
PAPER TITLE: OPTIMIZATION
EXAM DATE: FRIDAY 9, JUNE 2017
COURSE CODE: M373/K
Question 1
This question concerns the equation e2x cos x – 2 = 0.
(a) By drawing a suitable sketch, or otherwise, show that there are exactly two roots in the interval [0, 2].
(b) Consider the iterative scheme
(i) Show that the scheme satisfies the conditions for a contraction mapping on the interval [0, 0.5].
(ii) Starting from x0 = 0.35, evaluate the first two iterates of this scheme.
(iii) What stopping criterion would be needed to determine the root to three decimal places?
(c) Starting from x0 = 1.4, perform two iterations of the Newton–Raphson method to find the other root in [0, 2].
ANSWERS(Purchase full paper to get all the solution):
1a)
Using Rolle’s formular
f(x) = e2x cos x – 2 = 0
recall
These two value of x lie in the interval [0,2]
1bi)
The fixed point x0 = 0.25
Since 0 and
This means that
1bii)
Iteration 1, starting with 0.35
Iteration 2
1biii)
The stopping criteria = 0
1c)
1st iteration
2nd iteration
Question 2
(a) (i) Find the LU decomposition of the matrix
(ii) Use this decomposition to find the solution of the equation Ax = [2, 5, 0]T .
(b) Consider the following system of equations
8x1 + 3x2 + 2x3 = 2
4x1 − x2 + 4x3 = 1
2x1 + 5x2 + x3 = 1.
(i) 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) Perform two iterations of the Gauss–Seidel method with the starting value of x(0) = [0, 0, 0]T , to find an approximation to the solution of the equations.
Question 3
(a) The equation has a root x = 0.658991 (to six decimal places) when c = 8.22.
When c is subject to small changes about the value 8.22, determine whether the problem of finding the root is
i) absolutely ill-conditioned
ii) relatively ill-conditioned.
(b) Consider the system of linear equations Ax = b with
and .
Using three-figure arithmetic and the Gaussian elimination method with partial pivoting, the approximate solution is
x = .
(i) Calculate the residual vector r (use full calculator accuracy).
(ii) One iterative refinement gives the new solution
xnew = .
Use this information and your result from (i) to comment on the absolute and relative conditioning of the system with respect to small changes in the right-hand sides of the equations.
(c) Given that
A−1 =
determine the absolute condition number and an upper bound on the relative condition number of the system with respect to small changes in the right-hand sides of the equations. What does this tell you about the absolute and relative conditioning of the system?
Question 4
The system of non-linear equations
where x = [x1, x2]T , has one root near [-1, 0.5]T and another near [2, -2]T .
(a) (i) Write down the Jacobi iteration scheme for this system of equations in the order given.
(ii) Show that the Jacobi iteration scheme is a contraction mapping on the region
.
(iii) Perform two iterations of the Jacobi scheme to refine the approximation of the solution near [-1, 0.5]T .
(b) State the particular add-Nx iteration scheme needed to find the root near [2, −2]T ?
Question 5
A packaging company wishes to make cylindrical tubes, closed at one end, and lids to fit on the open end of the tube. The tube and lid are to be made from thin metal. The lid is formed from a circular disc, of the same radius as the tube, with strip of width 2 cm attached to the circumference of the disc, and fixed perpendicular to the disc. The company needs the tube to contain a volume of 750 cm3 and wishes to choose the dimensions of the tube so as to minimise the amount of metal used. You have been consulted to form a mathematical model 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 tube must satisfy the equation
πr3 + πr2 − 375 = 0.
(c) Verify that the above equation for r has one solution between r = 4 and r = 5 and use the bisection method to find the radius to one decimal place. Hence find the corresponding height of the tube.
Question 6
Consider the following linear programming model:
maximize z = 4x1 + 2x2 − x3
subject to
2x1 + x2 + 2x3 ≤10
4x1 + 3x2 + 3x3 ≤16
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 x3 in the objective have to change for it to bring about a change in the solution?
Question 7
A market gardening company produces tomatoes, lettuce and cucumber for the UK market, using greenhouses to ensure a long growing season. The following table summarises the annual seed/fertiliser costs, the greenhouse area required, the labour time needed and the profit, all per year for 1000 plants for each type of crop.
The total annual budget for seed and fertiliser is £20 000, while the maximum number of labour days available per year is 3 000. The market gardener wishes to allocate these resources appropriately to each type of crop in order to achieve an annual profit of at least £30 000 while minimising the area of greenhouse space required.
(a) Formulate this problem as a linear programming model in standard form. Let x1, x2, x3 be the numbers of tomato, lettuce, and cucumber plants respectively, in units’ of 1000 plants.
(b) State the dual of this model. Why is the dual model of interest for solving this problem?
(c) Show that the primal model has a feasible point that only involves lettuces and that the dual model has a feasible point at the origin. What does this tell you about the primal model and why?
(d) The dual problem was solved using a computer which converged to a solution with the following results (to two decimal places):
optimal point [0.00, 1.31, 0.80]T
shadow price vector [41.38, 53.79, 0.0]T
Use these results to answer the following questions.
(i) What is the minimum area of greenhouse required? Give your answer to the nearest square metre.
(ii) How many tomato plants are required? Give your answer to the nearest thousand.
Question 8
A small pottery produces replica historic vases of two types, either Chinese style or Greek style. There are three processes involved: throwing (i.e. shaping the raw clay), decorating and firing. Vases are fired in a kiln which must be filled for the heat to circulate properly, with each firing taking a number of days. So vases are always made in a batch, which is a standard number of vases for each type, and fractions of batches are not possible. The following table gives the time in person-days or days for each process, the total number of person-days or days available per month and the profit for a batch of each type of vase.
(a) Formulate an integer programming model for maximizing the pottery’s monthly profit.
(b) Solve the model using the branch-and-bound method, stating clearly the branching strategy used, and hence determine the number of batches of each type that the pottery should produce. Solve each continuous sub-problem graphically and show the details of the solution in a table of the following kind.
(c) Extend your model from part (a), using one or more 0-1 variables, so that the pottery can determine whether or not it should replace Chinese vases by Roman style vases which take more production resources but have a higher profit value. The throwing of a batch of Roman vases takes 9 person-days, decorating also takes 9 person-days and firing takes 5 days. The profit per batch is £1100. You are not expected to solve this extended model.
Question 9
A farm, F, is introducing a small-scale vegetable box delivery service. There are currently 4 customers, A, B, C and D, who wish to have boxes delivered to their homes on a particular day. The following table gives the distances in miles between the customers’ homes and the farm.
The farm would like to choose the delivery order such that the total distance travelled is minimized, whilst beginning and ending the route at the farm.
(a) Formulate the problem as an integer programming model.
(b) Customer C keeps chickens and sells the eggs through the farm’s delivery service. Customers A and B wish to buy eggs. How should the model be changed to ensure the farm delivery vehicle visits C (to collect the eggs) before visiting A and B (to deliver the eggs)?
Question 10
Consider the function
(a) Perform one iteration of the alternative variables method, starting from x(0) = [0, 0]T and using the initial search direction s(0) = [1, 0]T , to find a local minimizer of f. (Perform the line search analytically.).
(b) Perform one iteration of the steepest descent method, again starting from x(0) = [0, 0]T , to find a local minimizer of f. (Perform the line search analytically.)
(c) Briefly explain why the minimizers found in (a) and (b) differ.
(d) Explain what is meant by an inexact line search and how this might improve the efficiency of numerical optimization methods.
Question 11
(a) Determine, analytically, the location of the stationary point of f, and show that this point is a local minimizer of f.
(b) Perform one iteration of the Newton–Raphson method without line searches, starting from x(0) = [0, 0]T , to determine an approximation to a local minimizer of f.
(c) With reference to your results in parts (a) and (b), comment on the accuracy of the approximation found in (b) and whether this should be expected.
(d) Outline one situation in which it would not be suitable to use the Newton–Raphson method from a particular starting point and describe how the method could be modified to overcome this.
Question 12
Consider the following constrained minimization problem:
(a) Write down the Lagrangian function for this problem.
(b) Show that the point is a constrained local minimizer of f.
(c) Estimate the change in the minimum value of f if the constraint is changed to
Question 13
Compare and contrast the following three methods for solving unconstrained minimization problems.
(i) The 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 11:02 AM
Your one-stop website for academic resources, tutoring, writing, editing, study abroad application, cv writing & proofreading needs.
