We know the secret of your success
PAPER TITLE: OPTIMIZATION
EXAM DATE: MONDAY 17, OCTOBER 2011
COURSE CODE: M373/M
Question 1
Consider the equation
(a) By drawing a sketch show that there are exactly two roots in the interval [0.5, 3]. 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 [2, 3].
(c) Starting with your own approximation to the root in [2, 3], use the iterative scheme in (b) to determine the root correct to six 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 [0.5, 3].
ANSWERS( Purchase full paper to get all the solution):
1a)
From the graph
The root = 0.52 and 2.2
1b)
The fixed point x0 = 2.5
at x = 2
at x = 3
Since
1c)
2nd iteration
3rd iteration
The stopping criteria = 0.000067
1d)
the iterative scheme will not be suitable to use to try to find the other root in [0.5, 3] because the scheme will contain some random error, 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, 5, 12]T
(b) Consider the following system of equations
2x1 - x2 + 20x3 = -2
5x1 − 3x2 + 4x3 = 2
10x1 + x2 +2x3 = 1.
(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−5.
Hence write down the solution of the original equations to an accuracy of three decimal places.
Question 3
(a) The equation
is at x = 0.495 538 (to six decimal places) when c = 3.81. When c is subject to small changes about the value 3.81, determine whether or not the problem of finding the smallest root is
(i) absolutely ill-conditioned,
(ii) relatively ill-conditioned.
(b) Use the Newton–Raphson method to find the root of the equation 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
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.2, 0.2]T , use the Gauss–Seidel method, with an appropriate stopping criterion, to determine the root in R to three decimal places.
Question 5
The Box Company manufactures boxes made from thin metal. They wish to design a box with a square base and rectangular sides, and which has a volume of 0.2m3. The lid of the box is to be made from a sheet of metal which is the same size as the base, but has additional strips, 10cm wide, extending on each side. These strips are then bent at 900 to form the lid. The company wishes to know the dimensions of the box so that the minimum amount of metal is used. A mathematical model is required to solve the problem
(a) State the purpose of the mathematical problem.
(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 width x of the base should satisfy the equation
10x3 + x2 – 2 = 0
(c) Use the Newton–Raphson method to solve the equation in (b) and hence give the approximate width and height of the box to an accuracy of three decimal places.
Question 6
A building contractor has bought 12,000m2 of land on the outskirts of a village for development. He intends to build three types of house on the land: Grand which requires 350m2 of land and yields a profit of £25,000; Deluxe which requires 250m2 of land and yields a profit of £20,000 and Affordable which requires 150m2 of land and yields a profit of £10,000. The local authority is concerned about the effect that extra families in the village will have on local amenities so they impose a maximum of 50 houses that the contractor may build. Also, government regulations require that at least 40% of the houses must be Affordable.
(a) Formulate the contractor’s problem as a linear programming model in standard form, given that he wishes to maximise his total profit from the sale of houses.
(b) Express the model in canonical form and show that the all-slack point is feasible. 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) Extend your model in (a) using one or more 0-1 variables to include the extra constraint that if Grand houses are to be built on the land then at least 10 must be built.
Question 7
Consider the following linear programming model:
maximise z = 12x1 + 4x2 + 5x3 − 6x4
subject to
5x1 + 4x2 − x3 + x4 ≤ 8
7x1 + 2x2 + 5x3 + 4x4 ≥ 10
7x1 − 3x2 + 8x3 − 3x4 = 4
x1, x2, x3, x4 ≥ 0
(a) Write down the model in canonical form, including any artificial variables where appropriate
(Do NOT eliminate any variables). 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 following solution and ranging information, rounded to four decimal places.
Optimal vertex x = [0, 2.3448, 1.3793, 0, 0, 1.5862]T
Reduced costs d = [1.8966, 0, 0, 5.1379, 1.6207, 0]T
Optimal value z = 16.2759 Shadow price vector w = [1.6207, 0, 0.8276]
Right-hand-side vector b range
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 value of the objective if the right-hand side of the first constraint changed from 8 to 7?
(ii) What would be the effect on the solution if the cost coefficient of x1 changed from 12 to 10?
Question 8
A small workshop assembles two types of motor bike: Racer and Screamer from kits. The kits are obtained from a wholesaler each morning and, at the end of the day, the assembled bikes are moved to a showroom for sale the next day, leaving the workshop empty overnight. Once started, an assembly must be completed the same day. The total floor space in the workshop for assembling the bikes is 80m2. The owner has £600 to buy kits each day and the employees work a total of 44 hours per day between them. The following table shows the workshop floor space required for each bike, the purchase cost of each kit, the number of person-hours required for each bike’s assembly and the profit obtained from the sale of each bike.
(a) Formulate the workshop’s problem as an integer programming model, given that the workshop wishes to maximise its daily profit, assuming it can sell all the bikes it assembles.
(b) Solve the model using the branch-and-bound method, stating clearly the branching strategy used, and hence determine how many kits of each type 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 (a) using a 0-1 variable so that it can determine whether or not to abandon the assembly of Screamer bikes in favour of the new Luxury model. The assembly of Luxury bikes requires a floor space of 18m2, each kit costs £150, requires 10 person-hours and attracts a profit of £120. You are NOT required to solve this extended model.
Question 9
Garden Plus is a small family business that gives garden furniture an annual clean and varnish. Each restoration requires three processes: first Alan prepares and cleans each item, second Bill oils each item and third Claire varnishes each item. One day they had three items to restore and Garden Plus estimate the times in minutes to complete each process as follows:
Each process can only be applied to one object at a time but the GardenPlus team can work on different objects at the same time. GardenPlus would like to know in which order to process the objects to complete the work in the shortest possible time.
(a) Formulate GardenPlus’s problem as an integer programming problem.
(b) Determine a feasible point for the model you derived in (a) that involves Alan preparing the bird table first.
(c) By considering the total time to process the bird table find a lower bound for T, the total time to process all three objects. Hence determine whether your solution in (b) is optimal.
Question 10
Consider the function
(a) Perform one iteration of the alternating variables 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 line minimizer analytically.
(b) Find, and classify, all the stationary points of the function.
(c) For those stationary points you have classified as local minimizers, determine the absolute and relative condition of the problems of finding that local minimizer and the corresponding local minimum when the coefficient of x3 1 is subject to small changes in value.
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 constrained minimization model minimize
(a) Write down the Lagrangian function for this problem.
(b) Show that the point α = [−1, 2]T is a constrained stationary point of f and determine whether it is also a constrained local minimizer.
(c) Estimate the change in the minimum value of f if the constant term is changed from −7 to −7.1.
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 10:55 AM
Your one-stop website for academic resources, tutoring, writing, editing, study abroad application, cv writing & proofreading needs.
