Premium Resources

PAPER TITLE: OPTIMIZATION

EXAM DATE: FRIDAY 19, OCTOBER 2007

COURSE CODE: M373/W

Question 1

The concentration c of a certain chemical in a factory t hours after its container starts to leak is well modelled as

 

It is considered hazardous to enter the factory while this concentration is in excess of 0.05.

(a) Show that the range of times when c(t) ≥ 0.05 can be found by solving the equation

 

(b) By drawing a suitable sketch, or otherwise, show that the equation in (a) has exactly two real roots and state their approximate values to one decimal place.

(c) Show that the iterative scheme

 

satisfies the conditions for a contraction mapping on [0, 1].

(d) Starting from the approximate value obtained in (b), use the iterative scheme in (c) with a suitable stopping criterion, to find the smaller root correct to three decimal places.

(e) Starting from the approximate value for the larger root, obtained in (b), use the Newton–Raphson method to find the larger root correct to four decimal places.

(f) Interpret your solutions.

ANSWERS(Purchase full paper to get all the solutions):  

1a)

 

at c(t) = 0.05

  

 

Divide all through by 0.05

 

 

1b)

To make  

Using Rolle’s theorem

 

 

 

 

This means the two value of 

1c)

 

The fixed point t₀ = 0.5

 

 

at t = 0

 

 

at t = 1

 

 

Since   

 

1d)

 

at t = 1.3

 

 

1e)

 

 

 

 

 

 

1f)

The value obtained is very large, and the difference is much.

Question 2

(a) The LU decomposition of A is given by

 

(Use this to find the solution of the equation Ax = b, where b = [-2, 5, -2]^T

(b) Consider the following system of equations

2x₁ +11x₂ + 3x₃ = 30

-2x₁ + 5x₂ + 40x₃ = 40

50x₁ + 4x₂ - x₃ = 20.

(i) Explain why the Gauss-Seidel method, when used with these equations in the order given, is not guaranteed to converge. Reorder the equations to obtain a system for which the Gauss-Seidel method is guaranteed to converge.

(ii) Write down the Gauss-Seidel method and use it, with the starting value x⁽⁰⁾ = [0, 0, 0]^T , to find the solution of the reordered equations to an accuracy of three decimal places. Comment on the stopping criterion used.

Question 3

(a) The equation  has a root at x = 7.128 227 (to six decimal places) when c = −0.0006. When c is subject to small changes about the value −0.0006, determine whether or not the problem of finding the root is

(i) absolutely ill-conditioned,

(ii) relatively ill-conditioned.

(b) Consider the system of linear equations Ax = b given by

 

Using three-figure arithmetic and the Gaussian elimination method with partial pivoting, the approximate solution is

x = [−21.7, 7.74, 4.15]^T .

(i) Use the full accuracy of your calculator to compute the residual vector r.

(ii) One iterative refinement gives the new solution

x_new = [−25.3, 9, 4.86]^T .

Use this information and your result from (i) to comment on the absolute and relative conditioning of the problem with respect to small changes in the right-hand sides of the equations.

(iii) 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 your results.

Question 4

Consider the system of non-linear equations

  

 

(a) By drawing a sketch, show that there is a root near [3,0.5]^T

 (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  [3, 0.5]^T , use the Gauss–Seidel method, with an appropriate stopping criterion, to determine the root in R to three decimal places.

Question 5

Jill has an extension built on the side of her house. The extension is of constant height and has a flat roof of constant width. It runs the complete length of the side of the house. Jill wants to buy a ladder to get up on to the roof of the extension. She doesn’t want to lean the ladder against the extension as she feels that it may damage the guttering, so she needs one long enough that will reach from the ground, over the extension, and lean against the wall of the house. She needs to know the minimum length of ladder required. 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 (you may find it helpful to draw a diagram and to label as θ the angle the ladder makes with the ground).

(c) Show that, if the extension is 3 m high and its width is 2 m, then, when the length of the ladder is a minimum, the angle θ which it makes with the ground satisfies the equation

2 sin³θ − 3 cos³θ = 0.

(d) Verify that, for the data in (c), θ lies between 0.82 radians and 0.9 radians. Use the bisection method to find its value correct to one decimal place, and hence determine the minimum length of ladder required.

Question 6

A small theatre needs to refurbish its seats. The management decides to install a mix of standard seats and deluxe ones. A standard seat will cost £84 and a deluxe one £105 to install and the theatre has a budget of £44 100 for the refurbishment. If the theatre only used standard seats, they could install 600 seats and if they only used deluxe seats, they could install 400 seats. Fire regulations forbid the theatre to have an audience in excess of 500. Market research indicates customers would be prepared to pay £10 for a standard seat and £14 for a deluxe seat for a performance.

(a) Formulate the theatre’s problem as a linear programming model in standard form, given that they wish to maximise their income from customers attending a performance.

(b) Determine graphically the solution to the problem.

(c) The theatre subsequently discover they can apply for a grant from the Arts Council to increase their budget. Is this worth doing? If so, how much grant should the theatre ask for? Give a reason for you answer.

(d) Extend your model in (a) using 0–1 variables so that it can be used to determine whether or not to abandon the installation of standard seats in favour of budget seats which cost £70 to install. If the theatre only used budget seats, they could install 650 seats and customers would be prepared to pay £8 for a budget seat. You are not required to solve this extended model.

Question 7

Consider the following linear programming model:

minimize z = 2x₁ − 5x₂ + 6x₃ + 15

subject to

 

 

 

 

(a) Write down the model in canonical form, including any artificial variables where appropriate. 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 = [4, 5.5294, 2.8235]^T

Reduced costs d = [0.1471, 0.5147]^T

Optimal value z = −2.7059

Shadow price vector w = [0.1471, −0.5147, −0.5735]

where ±1 × 10³⁰⁷ (the Mathcad value for infinity) has been replaced by ∞. 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 solution if the right-hand side of the second constraint changed from 2 to 3?

(ii) What would be the effect on the solution if the cost coefficient of x₂ changed from −5 to −6?

Question 8

(a) Consider the following integer programming model:

maximize z = 8x₁ + 5x₂

subject to

2x₁ + x₂ ≤10

3x₁ + 4x₂ ≤24

x₁, x₂ ≥0

x₁, x₂ integer

(i) Use the branch-and-bound method to find an integer solution to the model. Solve each of the subproblems graphically. State clearly which branching strategy you are using. Your solution should include a table showing each step of the solution process.

(ii) Draw a tree diagram summarizing the solution process.

(b) A cottage industry company is considering making elderflower press’s in addition to its normal range of cider and apple juice. For this it needs lemons and elderflowers (apart from sugar for which it has a supplier). Elderflowers can be picked from the hedgerows for free. Tangy sells lemons in 5 kg cartons at a price of £6. Zesty sells lemons in any quantity at £0.8 per kg but adds a carriage charge of £2 to each order. The company estimates that it requires 13 kg of lemons. Formulate this as a minimization problem, defining any variables that you introduce.

Question 9

In a paint shop there are two processes. First each object to be painted is cleaned in an acid bath and second the object is sprayed by a spraying machine. Each process can only be applied to one object at a time, though the processes can run in parallel. The paint shop has an order to paint four wrought iron pieces of garden furniture: a chair, a table, a gate and a sundial. The paint shop needs to paint all four objects in the shortest possible time. The times in minutes taken for each process on each object are as follows.

(a) Assuming the paint shop is initially unoccupied, formulate the paint shop’s problem as a linear programming model. (You need not write out all the constraints that involve 0–1 variable but you should give at least 2 such constraints for each process)

(b) There are several optimum solutions to this problem but all of them involve spraying the chair last. Explain why this is the case.

(c) Determine an optimum solution for the model, giving values of all the variables introduced in (a) and their meanings in terms of the original problem.

Question 10

Consider the function

 

(a) Perform one iteration of the alternating variables method, starting from x(0) = [1, 0]T , and using s⁽⁰⁾ = [1, 0]^T , to find a local minimizer of f. Carry out the line search analytically.

(b) Repeat (a), but starting with s⁽⁰⁾ = [0, 1]^T . Compare your improved estimate x⁽¹⁾ with that found in (a).

(c) Determine the initial search direction for the steepest descent method, starting with x⁽⁰⁾ = [1, 0]^T . Comment on this search direction.

(d) More generally, compare the steepest descent method and the alternating variables method for finding a local minimizer.

Question 11

Consider the following system of non-linear equations.

 

 

(a) Explain briefly why this system may be solved by minimizing the function

 . What is the name given to this technique for solving a system of equations?

(b) Apply one iteration of the rank one method to the function f in (a), starting from x⁽⁰⁾ = 0, to determine an approximation to a root of the system of equations. Determine the line minimizer analytically and compute the next search direction.

(c) Name two advantages that the rank one method has, compared with the Newton–Raphson method, and one disadvantage, compared with the BFGS method.

Question 12

Consider the following constrained minimization model.

minimize  

subject to

 

(a) Convert the inequality-constraint model into an equivalent equality-constraint model by introducing a non-negative surplus term

 

(b) Write down an expression for the augmented Lagrangian function, ψ(x, µ, σ), corresponding to the equality-constraint model obtained in (a). Determine expressions for the gradient ∇ψ(x, µ, σ) and the Hessian matrix G(x, µ, σ) of the augmented Lagrangian function ψ, both with respect to x only.

(c) Verify that, for µ = 48, the point x = [1, 0]^T is a stationary point of the augmented Lagrangian function. By evaluating the Hessian matrix G obtained in (b) at x = [1, 0]^T , state for what values of σ, if any, this point is a local minimizer of the augmented Lagrangian function. Hence, or otherwise, determine whether it corresponds to a constrained local minimizer of the original model, and, if it does, specify the value of that constrained local minimizer.

Question 13

(a) Discuss the advantages and disadvantages of the following methods for solving unconstrained non-linear optimization models:

(i) the Newton–Raphson method with line searches.

(ii) the BFGS method.

(iii) the Fletcher–Reeves method.

(b) Describe the effects of using inexact line searches, both on the implementation and on the efficiency of the above methods.

(Purchase full paper by adding to cart)

Last updated: Sep 02, 2021 10:51 AM

add to cart ← Back