Student number Semester 1 Assignment 1, 2021 School of Mathematics and Statistics MAST20018 Discrete Mathematics and Operations Research Submission deadline: This assignment consists of 3 pages (including this page) Instructions to Students • If you have a printer, print the assignment. Writing • This assignment is individual. • Write your answers on A4 paper. Page 1 should only have your student number, the subject code and the subject name. Write on one side of each sheet only. Each question should be on a new page. The question number must be written at the top of each page. Scanning • Put the pages in question order and all the same way up. Use a scanning app to scan all pages to PDF. Scan directly from above. Crop pages to A4. Make sure that you upload the correct PDF file and that your PDF file is readable. Submitting • Go to the Gradescope window. Choose the Canvas assignment for this assignment. Submit your file. Get Gradescope confirmation on email. c©University of Melbourne 2021 Page 1 of 3 pages Do not place in Baillieu Library MAST20018 Discrete Mathematics and Operations Research Semester 1, 2021 Question 1 A company produces chairs and tables. Each table requires twice as much labour time as each chair. If only chairs are produced, the company can produce a total of 400 chairs a day. The market limits daily sales of chairs to a maximum of four times the sales of tables in the same period. The company obtains a profit of $80 per table and $50 per chair. Formulate a linear program to determine the number of tables and chairs the company should produce in order to maximise its profit. Clearly explain the meaning of your variables and constraints. (Do not solve the program). Question 2 A student is preparing for their final exams in subjects A, B and C. Each subject assessment is composed only by a mid-term and a final exam. The percentage of the final mark due to the mid-term exam in each subject and the marks the student obtained in these exams are listed in the table below: Subject % of final mark due to mid-term exam Student’s mark (out of 100) A 20 80 B 30 70 C 50 30 The student has 40h to dedicate to their studies and evaluates that they will obtain 10, 6 and 4 additional points in the final exam for each extra hour he dedicates to exams A, B and C, respectively (capped at 100). For example, they estimate that if they study 10h for subject C, they will obtain a mark of 40 in its final exam. The student wants to pass in all subjects (obtaining a final mark of at least 50 in each one of them) while obtaining the maximum possible sum of marks for all subjects combined. Formulate a Linear Program to help the student plan his studies. Clearly define your variables and explain each one of the constraints you define. Question 3 Using the definition of convex set, show that the set of solutions of the linear system of equalities Ax = b is a convex set. Question 4 Recall that an ILP (integer linear program) is a linear program where the decision variables are constrained as integers. Now consider the following ILP: max 1.00x1 + 0.64x2 such that 50x1 + 31x2 ≤ 250 3x1 − 2x2 ≥ −4 x1, x2 ≥ 0 and integer. (a) By using the graphical method, solve the linear program that results by ignoring the integer constraints (this is called the linear programming relaxation of the ILP). (b) One potential method for solving an ILP is to solve the corresponding linear pro- gram before rounding the answers to the nearest integer. Do you think this is an effective method? Give reasons for your answer. End of Assignment Page 2 of 3 pages
欢迎咨询51作业君
