Premium Resources

PAPER TITLE: OPTIMIZATION

EXAM DATE: FRIDAY 13, OCTOBER 2006

COURSE CODE: M373/J

Question 1

Consider the equation

 

(a) By drawing a suitable sketch or otherwise show there are exactly two roots in the interval [0,π]. Verify that these roots are 0.9 and 3.0 correct to one decimal place.

(b) Show that the iterative scheme

 

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

(c) Starting from x₀ = 0.9 evaluate the first four iterates of the scheme in (b). What stopping criterion would be needed to determine the root to three decimal places?

(d) Starting from x₀ = 3.0, use the Newton-Raphson method to find the other root in [0, π] correct to five decimal places.

ANSWER(Purchase full paper to get the solutions):

1a)

 

 

 

Using Rolle’s theorem

 

 

 

 and

1b)

 

The fixed point x₀ = 0.925

 

 

at x = 0.85

 

 

at x = 1

 

 

Since  

This means that

 

1c)

 

 

 

4

 

 

 

3

The stopping criteria is 0.127

1d)

 Using newton Raphson

 

 

at x = 3

 

 

 

 

 

 

 

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, 9, 8]^T

(b) Consider the following system of equations

20x₁ - 3x₂ + 10x₃ = 5

-3x₁ + x₂ + 150x₃ = 50

2x₁ - 25x₂ + 40x₃ = 2.

(i) By scaling x₃ by an appropriate factor of 10 and 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.1, 0.5, 0.33]^T to find the solution of your equations to an accuracy of four decimal places. Comment on the stopping criterion used. Write down the solution of the original equations to an accuracy of four decimal places.

Question 3

(a) The equation f(x, c) = e^−x + c has a root x = 4.60517 (to five decimal places) when c = −0.01. When c is subject to small changes about the value −0.01, 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 = [5.17, 5.01, −4.00]^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 = [7.26, 6.94, −5.60]^T.

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.

(iii) Given that (to two decimal places)

 

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

The system of equations

 

.

has a root near [2, 3]^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 [2, 3]^T cannot be guaranteed for the Jacobi iteration scheme.

(b) Use the add-Nx method to determine the root correct to two decimal places.

Question 5

A hotel wishes to build a conservatory with a small fountain at its centre. For the sides of the conservatory n panels are available, each of width p m. There is also a door of width d m which is to be used as the entrance. The conservatory is to have an irregular (n + 1)-sided shape, with the door forming one side and the n panels forming the remaining n sides. The fountain should be equidistant from the joins between neighbouring panels. To be able to construct the foundations, the hotel needs to know the distance between the fountain and the joins. 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 can make and identify any variables that you use (you may find it helpful to draw a diagram and to label as θ the half angle subtended by the panel at the fountain).

(c) Show that, for seven panels of width 4 m and a door of width 2 m, the distance x from the fountain to each join satisfies the equation

.

(d) Verify that, for the data in (c), x lies between 4.6 m and 5 m, and use the bisection method to find its value correct to one decimal place.

Question 6

A small English town is opening a theatre staffed by local volunteers that will seat 400 people. The management has decided to offer tickets at three prices: £5 for standard rate customers, £4 for concessionary rate customers and £3.50 per ticket for school parties. Volunteer staff are available at each performance to either work in the foyer ushering the customers to their seats and selling ice-cream, or they work behind the bar. Six volunteers are available to work in the foyer and five behind the bar. It is thought that one volunteer in the foyer would be needed for every 50 concessionary rate customers and one for every 25 members of school parties. Each volunteer behind the bar can serve up to 20 customers. It is estimated that half the standard rate customers, one third of the concessionary rate customers and one quarter of each school party will need serving in the bar. The management is trying to find the optimum mix of tickets to sell, assuming there is sufficient demand for each type of ticket, to maximize its income from ticket sales subject to the constraints of available staff and a maximum seating capacity of 400.

(a) Formulate the management’s problem as a linear programming model in standard form.

(b) Express the problem in canonical form using matrices.

(c) Perform one iteration of the simplex method, starting from the all-slack point and state the basic feasible point after one iteration.

(d) Extend the model in (a) using one or more 0 − 1 variables to cover the extra requirement that if tickets are sold to school parties then a minimum of 25 of these tickets must be sold.

Question 7

Consider the following linear programming model:

maximize z = -x₁+2x₂ - x₃+ 3x₄

subject to

 

 

 

 

(a) Write down the model in canonical form, including any artificial variables where appropriate.

(b) What is the all-slack point? State why it is not feasible. What pseudo-objective and initial pricing vector should be used for the first iteration of Phase I of the two-phase simplex method, starting from the all-slack point?

(c) 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.

(d) The problem was solved using a Mathcad worksheet, which produced the following solution and ranging information, rounded to three decimal places.

Optimal vertex x = [0, 0, 5, 0, 8, 0]^T .

Reduced costs d = [6, 0, 0, 1.667, 0, 0.667]^T .

Optimal value z = −5.

Shadow price vector w = [0, 0.667, −2.333]^T .

Optimal (final) basis list 2 3 5 .

Use these results to answer the following questions.

(i) What would be the effect on the solution if the cost coefficient of x₄ changed from 3 to 4?

(ii) What would be the effect on the solution if the cost coefficient of x₃ changed from −1 to −3?

Question 8

The Pound stir company assembles washing machines at its two factories in Rugby and Swindon. It must make weekly deliveries to three retail outlets in Ashton, Bury St. Edmunds and Cleve don. The following table gives the distribution costs (in pounds per machine) from each factory to each outlet, together with the maximum weekly production at each factory, and the fixed weekly requirement at each outlet. Table of distribution costs (pounds per machine)

Let x_ij be the number of machines per week from factory i (i = 1, 2) to outlet j (j = 1, 2, 3).

(a) Write down constraints to ensure that:

(i) maximum production at each factory is not exceeded.

(ii) the requirement at each outlet is satisfied exactly. Complete the formulation of an integer programming model in which the objective is to minimize the distribution costs.

(b) Pound stir has decided to make all deliveries to Bury St. Edmunds from its Rugby factory. In addition, deliveries to all outlets must be made in full loads of 50 machines. Use this information to revise your model from (a). Your revision should include the elimination of the variables x₁₂, x₂₁, x₂₂, x₂₃ from the model. Write down the complete revised model. (It may help to define x11 = 50X₁, etc.)

(c) Show that the solution to the continuous problem is an integer solution and hence advise Pound stir on how to make its deliveries.

Question 9

Mr Bond has acquired 50 hectares of agricultural land in East Anglia. He intends to use it to raise free-range cattle, pigs and chickens, which he will buy when very young, and sell for a profit after six months. He estimates that each calf will cost him £240 and will sell for £960, with feed costing £18 for the six months. Each calf will require 0.5 hectares of land and 20 hours of his time over the six months. Each piglet will cost him £60 and will sell for £180, with feed costing £6. Each piglet will require 0.1 hectares of land and 4 hours of his time. Each chicken will cost him £1.20 and will sell for £3.60, with feed costing £1.20. Each chicken will require 0.001 hectares of land and 1 hour of his time. He has £12 000 available to spend on livestock, and can spend 180 hours per month looking after them. He can also spend up to £1 200 per month on feed. In addition, he can borrow money from the bank to buy extra animals (but not food), at a simple interest cost of 2% per month, he can rent land from neighbouring farmers at £24 per hectare per month, and can employ part-time assistance at £6 per hour. If any of his land is not used for livestock, he can rent it to neighbouring crop farmers at £30 per hectare per month. Any unused time cannot be used in a productive way, and any money not used to buy livestock or feed cannot produce additional income. Formulate Mr. Bond’s problem as a linear programming model with a view to maximizing his net income over six months.

Question 10

Consider the

.

(a) Perform one iteration of the steepest descent method, starting from the origin, 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

Consider the function

.

(a) Determine, analytically, the stationary point of f.

(b) Perform one iteration of the Newton-Raphson method without line searches, starting from x⁽⁰⁾ = [3, 2]^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 normally be needed to find a local minimizer of f. When would this not happen?

(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, 2]^T is a constrained local minimizer of f.  

(b) If the constant in the constraint changes from 13 to 13.1 estimate the change in the minimum value of f.

Question 13

Discuss the branch and bound method for solving integer programming problems. Pay particular attention to the branching strategy. Illustrate your solution using simple graphs.

Purchase full paper by adding to cart

Last updated: Sep 02, 2021 10:51 AM

add to cart ← Back