Hi, I need solutions to the linear programming problem on page 4 please
School of Mathematics Level I Semester 1 & 2RCA Supplementary Examinations Instructions • Answer all questions for modules for which you are registered and which appear in this booklet. • You have a maximum period of time to complete and upload your solutions of 12+ 12q hours, where q is the number of full questions that you are required to complete. Any solutions submitted after your personal deadline will not be marked. • This assessment is not intended to need the full time period you have available; the time period indicates only the timescale within which you need to complete this assessment. The available time period automatically takes into account an adjustment for those stu- dents with Reasonable Adjustment Plans (RAPs) or individual personal circumstances. • Solutions must be neatly handwritten; typed solutions will not be marked. • Make sure that you read and follow the instructions for each module, in particular the page limit for your answers. Solutions will only be marked up to the specified page limit. • Solutions to each question should be uploaded to Canvas individually as a single PDF document and may be submitted at any point within the time period available. Solutions may be re-uploaded, however incorrectly submitted solutions, i.e. uploaded to the wrong question, may not be marked. It is your responsibility to ensure that your solutions have successfully uploaded to Canvas by your personal deadline. • Whilst you may use your notes and other materials available to you, submitted answers should be your own. The School of Mathematics has enhanced processes in place to identify any instances of plagiarism or collusion. There is no reduction in the threshold for plagiarism associated with this assessment. Appropriate University penalties will be applied to any individual found to be involved in any way with an act of plagiarism or collusion. • When your answers to each question are graded the marker will take into account a num- ber of factors to determine your awarded grade including: whether your answers are fully correct to all aspects of the question; the overall level of mathematical precision and rigor demonstrated in your arguments; the appropriateness of your mathematical explanation; and, your overall presentation of the mathematical material. The index uses hyperlinks to aid navigation and on each page there is a “Back to index” link. Page 2 Turn over Index 1 LI Algebra & Combinatorics 1 3 LI Linear Algebra & Linear Programming 5 LI Multivariable & Vector Analysis 7 LI Real & Complex Analysis 1AC2 06 27363 Level I LI Algebra & Combinatorics 1 Full marks may be obtained with complete answers to BOTH the following questions. Each answer must be no more than SIX sides of A4, any work in excess of this will not be marked. 1. You may apply results from the lecture notes, but you should clearly state which results you use and when you apply them. (a) (i) Let p,q ∈ N be distinct primes and let a ∈ Z. Suppose that p - a and q - a. Prove that there exists z ∈ Z such that az≡ 1 mod pq. (ii) Find z ∈ Z such that 17z≡ 1 mod 55. (b) Let p,q ∈ N be distinct primes and define Upq = {[a]pq ∈ Zpq : p - a and q - a}. (i) Verify that the axiom (G0) for a group holds for Upq as a group under multiplication. (ii) Show that |Upq|= (p−1)(q−1). (c) You are given that U15 is a group under multiplication. (i) Write down all elements of U15. (ii) Find all elements x ∈U15 such that x2 = [4]15. (iii) Is U15 a cyclic group? Justify your answer. (d) (i) Let f = ( 1 2 3 4 5 6 7 8 9 3 7 8 9 1 2 6 5 4 ) ∈ S9. Determine the cycle notation and the order of f . (ii) Find a permutation g ∈ S12 with order 42. (iii) Find two 3-cycles c,d ∈ S6 such that c◦d has order 2. (e) Let Ω = {−3,−2,−1,1,2,3} and let H = { f ∈ Sym(Ω) : f (−i) =− f (i) for all i ∈Ω} ⊆ Sym(Ω). Show that H is a subgroup of Sym(Ω). LI Algebra & Combinatorics 1 Turn over Page 1 Back to the index 2. You may apply results from the lecture notes, but you should clearly state which results you use and when you apply them. (a) Prove that if G is a bipartite graph with vertex classes A and B, then ∑ a∈A deg(a) = ∑ b∈B deg(b). (b) Prove that for each even n ∈ N we have (n 0 ) 2n− (n 1 ) 2n−1 + (n 2 ) 2n−2−·· ·+ (n n ) = 1. (c) Find all the possible degree sequences for a graph with 5 vertices and 5 edges. Your answer should include examples of graphs with each degree sequence in your list, and jusification that there are no other possible degree sequences than those you have listed. (d) Each day, 10 children vote on whether the theme colour for the day should be red, green or blue; the result of the vote is the triple (r,g,b), where r,g and b are the numbers of votes for red, green and blue respectively. What is the maximum possible number of days for which this can happen without the same result occurring twice? You may assume that each day all 10 children cast a valid vote for one of the three options. (e) I roll three unbiased standard six-sided dice. Calculate the probabilities of each of the following events: (i) the numbers rolled are {a,a + 1,a + 2} (not necessarily in that order) for some a ∈ {1,2,3,4}; (ii) on at least two of the rolls the numbers rolled are at most 5, and also, on at least two of the rolls the numbers rolled are at least 4. (f) Let A be the set of all ordered sequences (a1,a2,a3, . . .) such that ai ∈ {1,2,3,4} for each i ∈ N. Let ∼ be the relation on A in which (a1,a2,a3, . . .) ∼ (b1,b2,b3, . . .) if and only if there exists i ∈ N for which a j = b j for every j ≥ i. (i) Prove that ∼ is an equivalence relation. (ii) Determine, with proof, whether the set of equivalence classes A/∼ is countable or uncountable. End of LI Algebra & Combinatorics 1 Page 2 Back to the index 2LALP 06 25765 Level I LI Linear Algebra & Linear Programming Full marks may be obtained with complete answers to BOTH the following questions. Each answer must be no more than SIX sides of A4, any work in excess of this will not be marked. 1. (a) Consider the inner product space V = M2,2(R) where the inner product is given by (A,B) = tr(AtB) for A,B ∈M2,2(R). (Recall that At is the transpose of the matrix A.) (i) Compute the length |A| for A = ( 1 0 0 1 ) . (ii) Compute the angle α between this vector A and the vector B = ( 0 1 0 −1 ) . Are A and B orthogonal? (b) Let V = P2 and consider the inner product on V given by ( f ,g) = ∫ 0 −2 f (x)g(x)dx. (i) Explain why U = P1 is a subspace of P2. (ii) Use the Gram-Schmidt method to find an orthogonal basis in U starting from the standard basis {1,x}. (iii) Use the orthogonal basis of U from part (ii) to find the orthogonal projection projU(x 2− 1) of x2−1 onto U . (c) Consider a vector space V over a field F. Suppose that {v1, . . . ,vk} is a spanning set for V , that is, V = 〈v1, . . . ,vk〉. For two linear maps φ and ψ from V to V , it is known that φ(vi) = ψ(vi) for all i = 1, . . . ,k. Prove that φ = ψ , that is, φ(v) = ψ(v) for all v ∈ V . (Hint: Show that φ −ψ is a linear map. What can you say about the kernel of φ −ψ?) LI Linear Algebra & Linear Programming Turn over Page 3 Back to the index 2. (a) Consider the linear programming problem (P) Minimise −3x1−3x2−21x3, subject to 6x1 +9x2 +25x3 + x4 = 25, 3x1 +2x2 +25x3 + x5 = 20, x1,x2,x3,x4,x5 ≥ 0. and its dual problem (DP) Maximise 25u1 +20u2, subject to 6u1 +3u2 ≤−3, 9u1 +2u2 ≤−3, 25u1 +25u2 ≤−21, u1 ≤ 0, u2 ≤ 0. It is known that u∗ = (u∗1,u ∗ 2) = (− 33175 ,−114175) is the optimal solution to the dual problem (DP). Use complementary slackness conditions to find the optimal solution of the linear programming problem (P). (b) Consider the following linear programming problem: Minimise −2x1 + x2− x3, subject to x1 + x2 + x3 ≤ 6, −x1 +2x2 ≤ 4, x1, x2, x3 ≥ 0. Solve this problem by the Simplex Method. End of LI Linear Algebra & Linear Programming Page 4 Back to the index 2MVA 06 25667 Level I LI Multivariable & Vector Analysis Full marks may be obtained with complete answers to BOTH the following questions. Each answer must be no more than SIX sides of A4, any work in excess of this will not be marked. 1. (a) For the function, f (x,y,z) = xy+ yz+ zx at the point P = (1,2,3): (i) Find the directional derivative for f at P in the direction from P to Q = (2,0,1). (ii) Find the direction and rate of change of steepest decent for f at P. (iii) Write the equation for a level surface passing through P and having the normal vector5 f (1,2,3). (iv) Write the equation for the tangent plane to the level surface at P obtained in (iii). (b) Calculate the triple integral I in (i) using any coordinates. Express the triple integral L in (ii) as repeated integrals using Cartesian coordinates, cylindrical coordinates and spherical coordinates, respectively, and calculate it using any coordinates. (i) I = ∫∫∫ S ydxdydz, where S is the domain bounded by the planes x = 0 and x = y+ z, and the surfaces z = y2 and z = 2y− y2. (ii) L = ∫∫∫ D 1( x2 + y2 + z2 )dxdydz, where the domain D is in the first octant (where x,y,z≥ 0) and lies above the cone surface z = √ x2 + y2 and below the spherical surface x2 + y2 +(z−1)2 = 1. LI Multivariable & Vector Analysis Turn over Page