We know the secret of your success
PAPER TITLE: OPTIMIZATION
EXAM DATE: WEDNESDAY 11, JUNE 2014
COURSE CODE: M373/C
Question 1
Consider the equation
(a) Show that there is a root of this equation in the interval [−0.8, 0].
(b) Show that the iterative scheme
satisfies the conditions for a contraction mapping on the interval [−0.8, 0].
(c) Starting with x0 = −0.4 as an approximation to the root in [−0.8, 0], use the iterative scheme in (b) to determine the root correct to five decimal places. Justify the stopping criterion used.
(d) Use the add-nx method to find another root of the equation near x = 1.5 correct to five decimal places.
ANSWERS(Purchase full paper to get all the solutions):
1a)
Using the M.V.T
1b)
The fixed point x0 = -0.4
at x = −0.8
at x = 0
Since
This means that
1c)
x0 = -0.4
The stopping criteria = -0.00482
1d)
Question 2
(a) (i) Find the LU decomposition of the matrix
(ii) Use this decomposition to find the solution of the equation
Ax = b where b = [-1, -4, 6]T .
(b) Consider the following system of equations
3x1 - x2 + x3 = 2
x1 + 8x2 - x3 = 3
4x1 + x2 - 9x3 = 1.
(i) Explain why the Gauss–Seidel method is guaranteed to converge for this system of equations.
(ii) Use the Gauss–Seidel method with the starting value x(0) = [0, 0, 0]T to find the solution of these equations to an accuracy of three decimal places. Use a stopping criterion of ε = 5 × 10−4.
Question 3
The equation
f(x, c) =
has a root at 0.841 260 (correct to six decimal places) when c = 0.996.
(a) Explain why the Newton–Raphson method, with initial value x0 = 1, fails to find this root.
(b) When c is subject to small changes about the value 0.996, determine whether or not the problem of finding the root is
(i) absolutely ill-conditioned,]
(ii) relatively ill-conditioned.
(c) Use the Newton–Raphson method, with initial value x0 = 0.8, to find the root of the equation
correct to six decimal places.
(d) Use your result from (c) to find the absolute and relative changes to the root when c is changed from 0.996 to 0.995 and compare your results with your conclusions in (b).
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.4]T , use the Gauss–Seidel method, with an appropriate stopping criterion, to determine the root in R to three decimal places.
Question 5
Jack wishes to make a small flower bed in his garden. He has five strips of straight edging, each of length 1 m, to put round the edges of the flower bed. In addition, he can use the wall of his house as one of the edges. He had thought of making the flower bed 1 m wide and 3 m long, as in the diagram below, which would give him an area of 3 m2.
He wondered if he changed the design to that in the diagram below if he could get a greater area.
A mathematical model is required to solve the problem.
(a) State the purpose of the mathematical mode.
(b) (i) Create a mathematical model to solve the problem.
State clearly any assumptions that you make and identify any variables that you use.
(ii) Show that the area of the flower bed is given by
A = 1 + 2 sin θ + (1 + sin θ) cos θ
(iii) Show that if the area is to be a maximum, then
,
where x = cos θ.
(c) Show that the equation in (b)(iii) has a root in [0.52, 0.60]. Use the bisection method to find this root to an accuracy of two decimal places. Hence find the corresponding value of θ and the maximum area which can be obtained.
Question 6
The Replica Company manufactures three types of table: Tudor, Jacobean and Georgian. The table top and legs are manufactured separately. The times (in hours) required for each process for each table are shown in the following table, together with the maximum time available for each process and the profit made on each type of table.
The objective is to maximise the monthly profit. Assume that the sales market can only absorb up to four Tudor tables per month.
(a) Formulate this problem as a linear programming model in canonical form (without scaling the equations).
(b) Complete two iterations of the simplex method for this model, starting from the all-slack solution, and proceed as far as the basis list at the end of the second iteration.
(c) The following solution was found Objective function 9300
State the dual problem for the linear programming model you obtained in (a) and use the above information to deduce the solution to the dual model correct to five decimal places.
Question 7
Consider the following linear programming model:
maximize z = 5x1 +2x2 + 6x3 + 2x4
subject to
4x2 +x3 +6x4 ≤12
-2x1 +5x2 + 7x4 ≥10
3x1 +3x2 − x3 + 2x4 = 16
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 first constraint changed from 12 to 15?
(ii) What would be the effect on the solution if the cost coefficient of x3 changed from 6 to 8?
Question 8
(a) Consider the following linear programming model:
minimize z = 4x1 + 5x2
subject to 5x1 + 3x2 ≤ 21
4x1 + 7x2 ≤ 30
x1, x2 ≥ 0 x1, x2 integer.
Solve the model graphically using the branch-and-bound method, stating clearly the branching strategy used. Record your results in a table.
(b) Use 0–1 variables to formulate the constraints required to ensure that the solution to a linear programming model satisfies the following constraints
5x1 + 3x2 ≤ 25 for 0 ≤ x1 ≤ 2
4x1 + 3x2 ≤ 25 for 3 ≤ x1
where x1, x2 ≥ 0.
Question 9
Fred, a washing-machine service engineer must visit 5 clients today scattered across his region, with the mileages shown in the following diagram.
Fred would like to minimize his time on the road and to end up back at A, where he started. Formulate Fred’s problem as an integer programming model
Question 10
Consider the function
(a) Perform one iteration of the steepest descent method, starting from x(0) = [2.5, 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 the line minimizers are determined numerically using a grid search.
Question 11
(a) Determine, analytically, the stationary point 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. Comment on your solution.
(c) How many iterations of the rank one method would be needed to find a local minimizer of f using exact arithmetic?
(d) Name two advantages and one disadvantage that the rank one method has, compared with the Newton–Raphson method.
Question 12
Consider the following constrained minimization model minimize
(a) Use the Lagrangian function to show that α = [1, 1]T is a constrained local minimizer of f.
(b) If the constant in the constraint changes from 8 to 8.1 estimate the change in the minimum value of f, and the new minimum value of f
Question 13
Outline and discuss the branch and bound method for solving integer programming problems. Pay particular attention to the branching strategy. Illustrate the steps of the method using simple graphs.
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.
