The University of Sydney School of Mathematics and Statistics Assignment MATH2070/2970: Optimisation and Financial Mathematics Semester 2, 2021 Lecturers: Jie Yen Fan Due on Monday 20th September at 11:59pm via Canvas • Only pdf are allowed as a file format. You should submit a single pdf file. • Please make sure your submission is clear and legible. • The deadline is a hard deadline in the sense that in case of a late submission for each day (up to maximum 10 days) you will be deducted 5% of the total marks. This is non-negotiable, so make sure you submit in time; a submission on Tuesday the 21st at 12:01am will incur an automatic deduction of 5%. It is your responsibility to check that your submission was successful. • Each question is worth 10 marks. MATH2070: Do all questions except Question 5. MATH2970: Do all questions except Question 3. Copyright© 2021 The University of Sydney 1 1. Consider the following linear programming problem minimise Z = x1 − 2x2 subject to − x1 − x2 ≥ −3 − x1 + x2 ≥ −1 x1 ≥ 0, x2 ≥ 0. (a) Write the problem in standard form. (b) Solve the problem in standard form graphically. Also, • Introduce appropriate slack or surplus variables and define the boundaries of the feasible region in your graphical representation. • Indicate the shortest path to optimality. (c) Solve the problem manually using the simplex algorithm. Determine the optimal solution x∗ and the optimal value Z∗. Explain every step you make. In particular: • How do you choose certain values to enter the basis? Explain why. • How do you choose which variables should leave the basis? Explain why. • How do you decide when to stop? Explain why. 2. Consider the following linear programming problem maximise Z = 6x1 + 14x2 subject to 3x1 + 7x2 ≤ 21 7x1 + 3x2 ≤ 21 with x1 ≥ 0, x2 ≥ 0. Solve the problem manually using the simplex algorithm. Determine the optimal solution x? and the optimal value Z?. Explain every step you make. In particular, • Record which variables enter and leave the basis at each step. • Give a complete characterisation of the optimal solution(s). 3. (MATH2070 only.) Consider the following optimization problem maximise Z = −3|x1|+ x2 subject to 2x1 + x2 ≥ 2 x1 − 2x2 ≥ −10 x1 ∈ R, x2 ≥ 0. (a) Is this problem an LP problem in its current form? Explain your answer. (b) Convert this problem to an (equivalent) LP problem of the following form: Maximise Z = c>x subject to Ax = b with x ≥ 0, x ∈ Rn where c ∈ Rn, 0 ≤ b ∈ Rm and A is an m× n matrix, for some n and m. Explain every step you make. In particular, define every variable that you introduce and explain why it is needed. 2 4. A tea company sells tea under a “premium label” and an “economy label”. Both are blended from three basic grades of tea: Premium = 60%A + 30%B + 10%C Economy = 20%A + 30%B + 50%C The market prices are $1000/tonne for premium and $750/tonne for economy. Due to the limited supply, the company can only purchase up to 100 tonnes of grade A at a cost of $800/tonne. The cost of grade B is $600/tonne and the cost of grade C is $400/tonne. To meet the demand, the total production of the two blends must be at least 200 tonnes. How much of each blend should they produce to maximise their profit (not gross but net re- turns)? Formulate an LP problem to determine this. Solve the LP using two phase simplex algorithm. Remember to define all the variables clearly and explain every step. 5. (MATH2970 only.) A best approximate solution to an inconsistent set of m equations in n unknowns, n∑ j=1 aijxj = bi , i = 1, . . . ,m , can be found by minimising the sum of the absolute errors, m∑ i=1 ∣∣∣∣bi − n∑ j=1 aijxj ∣∣∣∣ , with respect to xk, k = 1, . . . , n. This L1-approximation optimisation problem is equivalent to the following LP problem with n + m decision variables xj , j = 1, . . . , n, and ei, i = 1, . . . ,m. Minimise Z = m∑ j=1 ej subject to ei + n∑ j=1 aijxj ≥ bi , i = 1, . . . ,m ; ei − n∑ j=1 aijxj ≥ −bi , i = 1, . . . ,m . (a) Write down the dual problem using dual variables yi, i = 1, . . . ,m, for the first m con- straints and wi, i = 1, . . . ,m, for the last m constraints. Show by eliminating the wi that the dual problem can be simplified to Maximise V = m∑ i=1 biyi subject to m∑ i=1 aijyi = 1 2 m∑ i=1 aij , j = 1, . . . , n ; 0 ≤ yi ≤ 1 , i = 1, . . . ,m . (b) The result in part(a) can be used to fit a straight line of the form y = ax + b to the five points (−2,−3), (−1, 2), (1, 5), (3, 10), (5, 14) by minimising the sum of the absolute errors at the five points (i.e. use L1 curve-fitting). Formulate the simplified dual LP problem of Part (a) for this curve-fitting problem. Note: you are not required to solve the LP that you formulated. 3