We know the secret of your success
PAPER TITLE: OPTIMIZATION
EXAM DATE: TUESDAY 11, JUNE 2019
COURSE CODE: M373/C
Question 1
Consider the function
The equation f(x) = 0 has three real roots: one at x = 0, one in the interval [0.1, 0.8] and one in the interval [2.5, 3.5].
Consider also the iterative scheme where ,
for finding roots of f(x) = 0.
(a) Show that the solutions to f(x) = 0 are the same as the solutions to g(x) = x.
(b) Show that the scheme satisfies the conditions for a contraction mapping on the interval [0.1, 0.8].
(c) Starting from evaluate the first two iterates of this scheme.
(d) What stopping criterion would be needed to determine the root in the interval [0.1, 0.8] correct to five significant figures?
(e) Explain why the same iterative scheme would not be suitable to use to try to find the solution to f(x) = 0 in [2.5, 3.5].
ANSWERS(Purchase full paper to get all the solutions):
1a)
If g(x) = x
Simplifying
Cross multiply
Recall f(x) =
Hence, both have the same solution because the functions are equal
1b)
The interval = [0.1, 0.8].
Using newton Raphson rule
This shows that the schemes satisfies the condition because the root lies in the interval
1c)
1st iteration
2nd iteration
1d)
The 1st iteration = 0.46014
The 2nd iteration = 0.46467
The tolerance = 0.00453
1e)
The interval = [2.5, 3.5].
The iteration scheme will not be suitable for the interval because the interval does not lie between 0 and 1, and the degree of the polynomial is less than the initial and final value of the interval
Question 2
(a) (i) Find the LU decomposition of the matrix
.
ii) Use this decomposition to find the solution of the equation Ax = [0, 2, −2]T .
(b) Consider the following system of equations
0.26x1 − 0.23x2 + 0.21x3 = 0.14
0.09x1 + 2.5x2 − 0.13x3 = −0.15
−0.11x1 + 0.72x2 + 0.28x3 = 0.067.
(i) Obtain a system of equations for which the Jacobi method is guaranteed to converge, by scaling by a power of 10. Call the scaled variable , so that for some integer a.
Explain why convergence is guaranteed.
(ii) Write down the Jacobi iterative scheme when applied to the scaled system of equations.
(iii) The solution to the scaled system of equations is to two significan
Question 3
Consider the system of linear equations Ax = b with
A = -and b = .
(a) Using four-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 = [−9.000, −36.67, −2.667]T .
Use this information and your result from (a)(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.
(b) Using the Gaussian elimination method with partial pivoting and full computer accuracy, the approximate solution is
When b is changed to b1 = [11.2, 0.9, −3.2]T the approximate solution is (renaming the variable x to x1 for clarity)
x1 =
Use this to calculate the absolute and relative changes to the solution resulting from these changes in the right-hand sides of the equations. Hence 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 with respect to small changes in the right-hand sides of the equations. What does this tell you about the absolute conditioning of the system, and how does it compare to your results from parts (a) and (b)?
Question 4
The non-linear system of equations
where has one root near .
(a) (i) Write down the Gauss–Seidel iteration scheme for this system of equations in the order given. (ii) Show that convergence to the root near cannot be guaranteed for the Gauss–Seidel iteration scheme.
(b) (i) Perform one iteration of the Newton–Raphson iteration scheme (for two-dimensional problems) needed to find the root of this non-linear system of equations near [−0.5, −0.5]T .
(ii) State appropriate stopping criteria for the Newton–Raphson scheme, to determine the root to two significant figures. Hence check whether your single iteration in part (b)(i) is sufficient to stop iterating. Note that you do not need to perform any more iterations.
Question 5
A wicker basket manufacturer has received a specification from a customer for a new basket. The basket is to be cylindrical in shape and must contain a volume of 0.5 m3. The open end of the cylinder is strengthened by an additional wicker rim of the same radius as the cylinder and with height 0.05 m, as shown in the following diagram.
In order to make the basket sufficiently strong for this customer’s requirements, the base will cost three times as much to manufacture per square metre, and the rim twice as much to manufacture per square metre, as the cost of manufacturing the side. The basket manufacturer wants to minimize the cost of manufacturing each basket and requires a mathematical model to determine the radius of the circular base in order to do so.
(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 you use.
Show that the optimal radius of the circular base, r, must satisfy the equation
(c) Using an initial estimate of 0.35 for the radius, perform one iteration of the method to find the optimal radius. (One iteration is sufficient to give the optimal radius correct to two significant figures in this case.)
Question 6
Consider the following linear programming model:
subject to
(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 enough of the next iteration of the simplex method to enable you to decide if the feasible point you found in part (b) is a solution to the model. Explain how you can tell whether or not you have found a solution.
(d) Continuing the process with further iterations produces the following optimal solution: Shadow price vector w = [0.0, 1.5]T . Reduced cost vector d = [2.0, 5.0, 0, 0, 1.5]T . Optimum z = 18.0 found at x = [0, 0, 6.0, 4.0, 0]T . If the value of the coefficient of x2 in the objective function is changed, what is the smallest value of this coefficient that would bring about a change in the solution?
Question 7
A farming co-operative in the Caribbean produces organic tropical produce for the UK market, specifically okra, peppers, and chillies. The following table summarises the cost of seedlings and organic fertiliser, the land 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 seedlings/fertiliser is $25 000, while the maximum number of labour days available per year is 3 300. The co-operative wishes to allocate these resources appropriately to each type of crop in order to achieve an annual profit of at least $30 000 while minimizing the area of land required.
(a) Let x1, x2, x3 be the numbers of okra, pepper and chilli plants respectively, in units’ of 1000 plants. Formulate this problem as a linear programming model in standard form.
(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 peppers 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, 5.65, 1.41]T
shadow price vector [52.17, 58.70, 0.00]T
Use these results to answer the following questions.
(i) What is the minimum area of land required? Give your answer to the nearest square metre.
(ii) How many pepper plants are required? Give your answer to the nearest thousand.
Question 8
A small workshop makes two types of tables: standard rectangular tables and de luxe circular tables. Both types are made from the same wood and after the wood has been cut each table has to go through three processes: joinery, sanding and finishing. At the end of the day the finished tables are moved to a local wholesale showroom, to be sold on to furniture retailers. Once production of a table has been started, it must be completed the same day so that the workshop can be cleared and left empty to start on the next batch in the morning. The limitations for the workshop are the total amount of specialist labour time per day available for each process. The following table shows the time required for each process for each type of table, and the total labour time available per day for each process. It also shows the profit from selling each type of table.
(a) Formulate an integer programming model for maximizing the workshop’s daily profit, assuming it can sell all the tables it assembles.
(b) Solve the model using the branch-and-bound method, stating clearly the branching strategy used, and hence determine the number of tables of each type that should be produced 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 from part (a), using one or more 0–1 variables, to help determine whether or not the workshop should stop assembling rectangular tables and instead assemble larger conference tables, which take more production resources but have a higher profit value. The production of a conference table requires 4 hours of joinery, 1.5 hours of sanding and 6 hours of finishing and generates a profit of £250. You are not expected to solve this extended model.
Question 9
Mr O’Connell lives in London and has inherited 40 acres of agricultural land in Ireland from his great-uncle Seamus. To escape the rat-race, he intends to start a new life in Ireland, raising animals of traditional breeds – pigs, sheep and goats – which he will buy when the animals are very young and sell for a profit after six months. He consults his Irish cousins for information about costs in euros (AC). He estimates that each pig will cost AC62 and will sell for AC142, with feed costing AC20 for six months. Each pig will require 0.6 acres of land and 15 hours of his time over six months. He expects that each sheep will cost him AC80 and will sell for AC180, with feed costing AC30 for six months. Each sheep will require 0.9 acres of land and 20 hours of his time over six months. Each goat will cost him AC10 and will sell for AC30, with feed costing AC2 for six months. Each goat will require 0.1 acres of his land and 10 hours of his time over six months. He has AC2000 to spend on livestock and can spend 200 hours per month looking after them and up to AC70 per month on feed. In addition, he can borrow money from the local bank to buy extra animals (but not food) at a simple interest rate of 1% per month, he can rent extra land from neighbouring farmers at AC15 per acre per month, and he can employ part-time assistance at AC10 per hour up to a maximum of 60 hours per month. If any of his land is not used for livestock, then he can rent this spare land to neighbouring farmers at AC12 per acre 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.
(a) Using appropriate meaningful variable names, formulate Mr O’Connell’s problem as a linear programming model with a view to maximizing his profit over six months.
(b) A solution to this problem generated using Maxima gave output including the following: Optimum z = 4182.3529 at x = [10.588235, 0, 104.11765, ...]T. Reduced costs = [0, 17.317647, 0, ...] T . You can assume that the first three variables in each list correspond to the numbers of pigs, sheep and goats respectively.
(i) Interpret this solution, to explain what Mr O’Connell should do to maximize his profit and how much that profit would be. Discuss any problems with these non-integer optimal values and how to deal with this.
(ii) Using the above Maxima results, calculate how much the profit per sheep would need to be in order to give a different optimal solution for the numbers of each animal. Give your answer in euros to two decimal places.
Question 10
where x = [x1, x2]T .
(a) Find and classify all the stationary points of f(x).
(b) Perform one iteration of the alternating variables method, starting from x(0) = [0, −2]T , to find an approximation to the local minimizer of f. Determine the line minimizer analytically.
(c) For those stationary points you classified as local minimizers in part (a), estimate the absolute and relative condition numbers for the problems of
(i) finding the local minimizer
(ii) finding the corresponding local minimum when the coefficient of x3 1 is subject to small changes in value.
Question 11
(a) Consider the function
(i) Perform one iteration of the Newton–Raphson method with line searches, starting from x(0) = [0, 1]T , to find an approximation to the local minimizer of f. Determine the line minimizer analytically.
(ii) Why would it not be advisable to start this search for the minimizer of f from x(0) = [0, 0]T ?
(iii) If you were required to start the search from x(0) = [0, 0]T , how would you need to modify the method?
(b) What are the advantages of using the BFGS method over the Newton–Raphson method for this problem?
Question 12
Consider the following constrained minimization problem:
(a) Write down the Lagrangian function for this problem.
(b) Show that α = [−1, −2]T 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
(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.
figures. What is the solution to the original system of equations?
Purchase full paper by adding to cart
Last updated: Sep 02, 2021 10:54 AM
Your one-stop website for academic resources, tutoring, writing, editing, study abroad application, cv writing & proofreading needs.
