answer all questions
Full Name: Student Number: TOTAL POINTS: /30 Trent University MATH 3350 - Linear Programming Instructor: Aras Erzurumluoğlu Final Exam (due 23:59 pm on April 18, 2022 Monday) Show all your work. You may use your notes, but you are not allowed to copy solutions from one another or from elsewhere (not even partially). Please familiarize yourself with Trent University’s policies on academic in- tegrity. Make sure that your solutions are well-written and follow the terminol- ogy and notation as we have seen in class. Problem 1) (5 points) Solve the transportation problem where C (cost matrix) = 5 6 7 42 9 7 5 8 5 8 7 , s = 7550 60 , and d = 45 50 25 50 . Problem 2) (4 points) Consider a hallway at Trent with 15 offices num- bered 101 through 115. The distance from office i to office j (101 ≤ i, j ≤ 115) is |j − i|. One desk from each one of the offices 102, 105, 108, 109, and 113 need to be moved to one of the offices 106, 107, 112, 114, and 115. Each one of the offices 106, 107, 112, 114, and 115 need exactly one desk, and it does not matter which desk goes to which office. Use a method from class to find an assignment of the desks that mini- mizes the total distance over which the desks would need to be moved. 1 Problem 3) (4 points) For the LP problem given below, first find the extreme points of the set of feasible solutions and then find an optimal so- lution if it exists. Maximize z = 3x− y subject to 4x− y ≤ 8 2x + y ≥ 4 x + 2y ≤ 6 x ≥ 0, y ≥ 0. Problem 4) (3 points) You have 6 favourite songs, and there are a total of 10 CD’s at a store that contain some of these songs. Each one of these 6 songs is in at least one of the 10 CD’s. Suppose that the ith CD costs ci dollars. Let aij = 1 if the ith CD contains the jth song (i = 1, . . . , 10; j = 1, 2, . . . , 6); aij = 0 otherwise. Write an integer programming model that you could use to determine the cheapest selection of CD’s to while guaranteeing that you will get each one of your favourite songs in at least one CD. Problem 5) (2 points) In the transportation problem (as defined at the bottom of p. 184 in the lecture notes where total supply equals total de- mand), show that taking xij = sidj∑m i=1 si satisfies all constraints of the form∑n j=1 xij = si (for i = 1, . . . ,m). Problem 6) (2 points) Use one iteration of the simplex method to obtain the next tableau from the given tableau below. x1 x2 x3 x4 x2 1 1 5 0 4 x4 -1 0 2 1 6 -3 0 -2 0 7 2 Problem 7) (4 points) Apply the two-phase method to the following prob- lem. to find an optimal solution if it exists. (If no optimal solution exists, express why.) Maximize z = 2x1 + 5x2 − x3 subject to −4x1 + 2x2 + 6x3 = 4 6x1 + 9x2 + 12x3 = 3 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Problem 8) (4 points) Suppose that x1 = 2, x2 = 0, x3 = 4 is an optimal solution to the LP problem given as follows: Maximize z = 4x1 + 2x2 + 3x3 subject to 2x1 + 3x2 + x3 ≤ 12 x1 + 4x2 + 2x3 ≤ 10 3x1 + x2 + x3 ≤ 10 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. Find an optimal solution to the dual problem and determine the value of the dual objective function at this optimal value. (Hint: Using some appropriate techniques and theorems will reduce the required work very significantly.) Problem 9) (2 points) Suppose that the following tableau was obtained during an application of the simplex method to an LP problem in standard form. What can we conclude about the optimal solution of the LP problem? x1 x2 x3 x4 x2 2 1 -5 0 5 x4 -1 0 0 1 2 4 0 -2 0 6 3