We know the secret of your success
PAPER TITLE: OPTIMIZATION
EXAM DATE: MONDAY 11, JUNE 2018
COURSE CODE: M373/J
Question 1
Consider the function
.
(a) Show that f(x) is monotonically decreasing in the interval [1.6, 2].
(Note: [1.6, 2] ⊂ [ , π .)
Hence prove that there is exactly one root of f(x) = 0 in the interval [1.6, 2].
(b) Consider the iterative scheme . for finding roots of f(x) = 0.
(i) Show that the scheme satisfies the conditions for a contraction mapping on the interval [1.6, 2].
(ii) Starting from x0 = 1.8, evaluate the first two iterates of this scheme.
(iii) What stopping criterion would be needed to determine the root correct to four significant figures?
(c) Starting from x0 = −1.8, perform two iterations of the add-nx method to find a root of f(x) = 0 in [−2, −1.6]
ANSWERS(Purchase full paper to get all the solutions):
1a)
Since this show that the function is decreasing
To find the root
F(c) =
The root c =
1bi)
And
It satisfies the condition, and it converges.
1bii)
1st iteration
2nd iteration
1biii)
The stopping criteria should be 0.8177
1c)
Question 2
(a) Consider the system of equations Ax = b, where
and b = [3, −8, 6]T .
(i) The LU decomposition of A is given by
A = LU = .
Use this decomposition to find the solution of the system Ax = b.
(ii) Given that
determine the absolute condition number and an upper bound on the relative condition number for the system Ax = b with respect to small changes in the right-hand sides of the equations. Comment on the absolute and relative conditioning of the problem.
(b) Consider the following system of equations
x1 + 3x2 − x3 = −3
6x1 − x2 + 3x3 = −1
x1 + 5x2 − 7x3 = 2.
(i) Reorder the equations to obtain a system of equations for which the Gauss-Seidel method is guaranteed to converge. Explain why convergence is guaranteed.
(ii) Perform two iterations of the Gauss-Seidel method with the starting value of x(0) = [0, 0, 0]T , to find an approximation to the solution of the equations.
Question 3
(a) The equation has a root x = 0.906651 (to six decimal places) when c = 9.72.
(i) When c is subject to small changes about the value 9.72, determine whether the problem of finding the root is absolutely ill-conditioned and/or relatively ill-conditioned.
(ii) When c = 9.77, the root of the equation is x = 0.910375, correct to six decimal places. Find the absolute and relative changes to the root of f(x, c) when c is changed from 9.72 to 9.77 and comment on your findings with respect to your answers to part (i).
(b) Consider the system of linear equations Ax = b with
and .
Using five-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 =.
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.
Question 4
The non-linear system of equations
where x = [x1, x2]T , has one root near [3, 0.6]T and another near [0.7, 2.1]T .
(a) (i) Write down the Gauss-Seidel iteration scheme for this system of equations in the order given.
(ii) Show that the Gauss-Seidel iteration scheme is a contraction mapping on the region
(iii) Perform two iterations of the Gauss-Seidel scheme to refine the approximation of the solution near [3, 0.6]T .
(b) 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.7, 2.1]T .
Question 5
A supermarket chain wishes to build a store to serve two towns, A and B, which are 10 kilometres apart. They need to determine at which point between the two towns they should build the store so as to maximise their average weekly income. They surveyed the residents of A and B to find how many shoppers would visit the store weekly, how far they would be prepared to travel, and how much their average weekly spend would be. For town A, the number of shoppers, a, prepared to travel to the store if it were situated x km from A could be modelled by
where k is a positive constant.
For town B, with a smaller population than town A, the number of shoppers, b, prepared to travel to the store if it were situated x km from A could be modelled by
where k is the same constant as before. When questioned about how much they would spend, it was found that a shopper from B would spend on average 10% more than a shopper from A. The supermarket chain wishes to construct a mathematical model to help them solve their problem.
(a) State the purpose of the mathematical model.
(b) Show that the total average weekly income of the new store can be modelled by
where K is a positive constant.
(c) State clearly the assumptions made in deriving the above model.
(d) Use the model to find the optimum position for the store.
Question 6
Consider the following linear programming model:
maximize z = 3x1 + 2x2 + x3
subject to
−2x1 − x2 + 2x3 ≤ 8
4x1 + 3x2 − 3x3 ≤ 6
x1, x2, x3 ≥ 0.
(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. 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 = [6.5, 4.0]T . Reduced cost vector d = [0, 3.5, 0, 6.5, 4.0]T . Optimum z = 76.0 found at x = [18.0, 0, 22.0, 0, 0]T . By how much would the coefficient of x2 in the objective have to change for it to bring about a change in the solution?
Question 7
maximize z = 8x1 − 5x2 + 4x3
subject to 4x1 − x3 ≥ 6
2x1 − x2 + 4x3 ≤ 12
6x1 − 2x2 − 3x3 = 4
x1, x2,,x3 ≥ 0 .
(a) Express 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 Maxima, which produced the following solution and ranging information, rounded to two decimal places.
optimal vertex xT = [2.05 0.86 2.19 0 0]
reduced costs dT = [0 0 0 1.29 1.86]
optimal value z = 20.86
shadow price vector wT = [−1.29 1.86 1.57]
optimal basis list = 2 3 1
inverse basis matrix B−1 =
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 cost coefficient of x3 changed from 4 to 7?
(ii) What would be the effect on the solution if the right-hand side of the first constraint changed from 6 to 5?
Question 8
A small workshop assembles two types of bike, racing bikes and mountain bikes, built from kits. The kits arrive in a batch each morning and at the end of the day the finished bikes are moved to a local wholesale showroom, to be sold on to cycle retailers. Once assembly of a bike 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 floorspace of 80m2, the total amount of money available to buy kits, which is £2250 per day, and the total number of working hours of the employees, which is 45 hours per day. The following table gives for each type of bike: the workshop floor space required, the purchase price of each kit, the number of person-hours required to assemble that bike, and the profit from selling it.
(a) Formulate an integer programming model for maximizing the workshop’s 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 the number of kits of each type that 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 from part (a), using one or more 0 – 1 variables, to help determine whether or not the workshop should stop assembling racing bikes and instead assemble ”Electrobikes” (electrically assisted hybrid bikes), which have more costly kits and which take more production resources but have a higher profit value. The assembly of an Electrobike requires 20m2 of floor space, and each kit costs £600, takes 10 person-hours of assembly time and generates a profit of £360. You are not expected to solve this extended model.
Question 9
A gemstone producer prepares three types of gemstone for use in jewellery, starting from the rough stones. There are three processes which must be carried out in the following order: rough grinding, cutting and polishing, each of which takes place in its own specially designed machine. Each machine can treat just one stone at a time, though all three machines can operate at once. The times taken for each process for each type of gemstone are as follows.
The manufacturer wants to produce sets of three gemstones, one of each type, in the shortest possible time.
(a) Formulate the manufacturer’s problem as an integer programming model.
(b) Determine a feasible point for the model, giving values of all the variables introduced in (a). Describe the manufacturing schedule given by your feasible point.
Question 10
f(x) = x3 + 4x2 − 5x
which is unimodal in [−3, 3].
(a) Use the interval location method, beginning from x0 = 0 and with an initial step size of 0.2, to find an interval containing the local minimizer.
(b) Starting with the interval [0, 1], perform two iterations of the golden section search method to reduce the size of the interval containing the local minimizer.
(c) How many iterations and function evaluations would be required to determine the local minimizer correct to three decimal places, starting from the interval [0, 1], using the golden section search method?
(d) What are the advantages and disadvantages of the golden section search method compared to the Newton-Raphson method for locating a local minimizer? Which of these two methods would be preferred for locating the local minimizer of a function of 50 variables, and why is it to be preferred?
Question 11
where x = (x1, x2)T .
(a) Determine, analytically, the location of the stationary point of f, and show that this point is a local minimizer of f.
(b) Perform one iteration of the rank one method, starting from x(0) = 0, to find an improved approximation to the local minimizer of f. Determine the line minimizer analytically. What is the updated Hessian matrix needed for the next iteration?
(c) How does the BFGS method differ from the rank one method? What are the advantages and disadvantage of the rank one method compared to BFGS?
Question 12
Consider the following constrained minimization problem: minimize
c1(x1, x2) = x1 + 3 ≥ 0
c2(x1, x2)=2x2 − 3 ≥ 0.
(a) Determine the Karush-Kuhn-Tucker points of the problem at which at most one of the constraints is active, and the corresponding Lagrange multipliers.
(b) Determine whether any of the Karush-Kuhn-Tucker points obtained in (a) are constrained local minimizers.
Question 13
It has been proposed that a new high-speed rail-line is to be built linking two large cities. Due to the terrain between these cities, it is expected that various elevated sections of track will be needed, to cross wide rivers and span boggy ground. The line will also need to take into consideration other obstacles such as lakes, small towns and sites of particular scientific or historical importance along its route. It is intended that the route for the rail-line will be planned with the aid of mathematical modelling, with a view to trying to find the best route at a reasonable cost. Outline the process, from a simple initial model through various revisions to a final model, that you would foresee as being necessary. Suggest the type of model that is likely to be created at each stage of the process. Also indicate which method you might use to solve the model created at each stage, giving reasons for your choice, and indicate how you would determine any initial starting values and stopping criteria needed in each case. Indicate what the outcome of the modelling process might be. Note that you are not expected to give details of the models you might suggest, merely an outline of their form.
Purchase full paper by adding to cart
Last updated: Sep 02, 2021 11:04 AM
Your one-stop website for academic resources, tutoring, writing, editing, study abroad application, cv writing & proofreading needs.
