Co 250 Assignment 6 Paper

Unformatted text preview: CO 250 Assignment 1 – Winter 2015 Solutions Problem 1: Linear Algebra Review Answer each of the following questions. For questions (a)–(e), indicate if the given statements are TRUE or FALSE. Justify your answer by either providing a proof (if the statement is true) or a counterexample (if the statement is false). (a) Let x, y be vectors in Rn . In the following, we will say that x ≥ y if xi ≥ yi for all 1 ≤ i ≤ n. For any x, y ∈ Rn we either have x ≥ y, x = y or x ≤ y. Solution: FALSE. E.g., take x = (1, 0)T and y = (0, 1)T . (b) There are 4 linearly independent columns 1 8 −1 11 0 −7 0 2 1 Solution: in the following matrix: 0 108 −2 41 17 11 0 2 14 19 4 −7 1 3 0 9 −6 10 FALSE: Each column is a vector in R3 , and there do not exist 4 linearly independent vectors in R3 . (c) Let A be a matrix and y be a non-zero vector such that y T A = 0T . Then the rows of A are linearly dependent. Solution: TRUE: If y = (y1 , y2 , . . . , yn )T , and we let Ai denote the ith row in A, then y T A = y1 A1 + y2 A2 + . . . + yn An , Since y = 0 and y T A = 0, it follows that the rows of A are linearly dependent. (d) Let A be a n-by-n matrix, and Ax = b has a unique solution. Then AT x = b has a unique solution. Solution: TRUE. Since A is square and Ax = b has a unique solution, we know that A must be non-singular, and hence so is AT . Thus, (AT )−1 exists, and AT x = b ⇐⇒ (AT )−1 (AT x) = (AT )−1 (b) ⇐⇒ x = (AT )−1 b. Therefore, x = (AT )−1 b is the unique solution to AT x = b. (e) For two 2 × 2 matrices A and B, (AB)T = AT B T . Solution: FALSE. Consider, for example A= 1 1 1 1 and B = 0 0 . 1 1 (AB)T = 1 1 1 1 and AT B T = Then 1 0 2 . 0 2 (f) Let a and b be length n vectors. What is the dimension of the matrix abT ? What is its rank? Solution: Let a = (a1 , . . . , an )T and b = (b1 , . . . , bn )T . Then abT = [ab1 , ab2 , . . . , abn ] , and thus, abT is an n × n matrix. Moreover, its rank is 1 as all of its columns are multiples of a. Problem 2: LP Models I The director of the CO-Tech startup needs to decide what salaries to offer to its employees for the coming year. In order to keep the employees satisfied she needs to satisfy the following constraints: • Tom wants at least $20,000 or he will quit; • Peter, Nina, and Samir each want to be paid at least $5000 more than Tom; • Gary wants his salary to be at least as high as the combined salary of Tom and Peter; • Linda wants her salary to be $200 more than Gary; • The combined salary of Nina and Samir should be at least twice the combined salary of Tom and Peter; • Bob’s salary is at least has high as that of Peter and at least as high as that of Samir; • The combined salary of Bob and Peter should be at least $60,000; • Linda should make less money than the combined salary of Bob and Tom. (a) Write an LP that will determine salaries for the employees of CO-tech that satisfy each of these constraints while minimizing the total salary expenses. Solution: We will introduce a variable xi for i ∈ {Tom, Peter, Nina, Samir, Linda, Gary, Bob} representing the salary of i. We create one constraint for each of the constraints. • Tom wants at least $20,000 or he will quit; xTom ≥ 20000 (1) • Peter, Nina, and Samir each want to be paid at least $5000 more than Tom; We need a constraint for each of the three employees: xPeter ≥ xTom + 5000 xNina ≥ xTom + 5000 (2) xSamir ≥ xTom + 5000 (4) (3) • Gary wants his salary to be at least as high as the combined salary of Tom and Peter; xGary ≥ xTom + xPeter 2 (5) • Linda wants her salary to be $200 more than Gary; We interpret this question as “Linda wants her salary to be exactly $200 higher than that of Gary”. xLinda = xGary + 200 (6) • The combined salary of Nina and Samir should be at least twice the combined salary of Tom and Peter; xNina + xSamir ≥ 2(xTom + xPeter ) (7) • Bob’s salary is at least has high as that of Peter and at least as high as that of Samir; Once more, we need two constraints here. xBob ≥ xPeter xBob ≥ xSamir (8) (9) • The combined salary of Bob and Peter should be at least $60,000; xBob + xPeter ≥ 60000 (10) • Linda should make less money than the combined salary of Bob and Tom. There is no way that we can express this constrained linearly as we are not allowed to use strict inequalities, and since all variables are fractional (as opposed to integral). We interpret this constraint as “Linda’s salary is no more than the combined salary of Bob and Tom”. xLinda ≤ xBob + xTom (11) The entire LP now becomes: min xTom + xPeter + xNina + xSamir + xLinda + xGary + xBob s.t. (1) − (11) x≥0 (b) Write an LP that will determine salaries for the employees of CO-tech that satisfy each of these constraints while minimizing the salary of the highest paid employee. Solution: We introduce one new variable M for the maximum salary of any employee. We now add the following constraints to the LP from (a): xi ≤ M (i ∈ {Tom, Peter, Nina, Samir, Linda, Gary, Bob}) We also change the objective function to min M, and hence the new LP becomes min M s.t. (1) − (12) x≥0 3 (12) Suppose that (x, M ) is an optimal solution to the above LP. Then one of the constraints in (12) must be satisfied with equality. Why? (c) What is the relation between the solution for (a) and (b)? Solution: The objective function in (a) enforces the sum of all saleries to be small; i.e., in other words, the average salary will be small. On the other hand, in solutions to (b) that maximum salary will be small, but the sum might still be large! Problem 3: LP Models II – Multiperiod Models Waterloo’s world famous Cold Products Unlimited produces ice-cream for the entire southern part of Ontario. The following table shows the demand di (in tons) for each month i ∈ {1, . . . , 12}. Month di 1 10 2 12 3 14 4 20 5 15 6 22 7 28 8 30 9 20 10 22 11 16 12 17 The company needs to decide how much ice-cream to produce in each month so that the demand can be met. As usual we make the following assumption: ice-cream produced in month i can be consumed in month i (and later, of course). (a) Assume that producing a ton of ice-cream in month i costs pi , and that the company can store up to 15 tons of ice-cream in its freezers for an unlimited amount of time. Assume that the freezers contain 7 tons of ice-cream at the beginning of month 1. The company wants to determine how much to produce in each month in order to minimize the total production cost. Write an LP for this task. Solution: Let xi be the amount of ice-cream produced in month i, and let si be the number of tons stored at the end of the month. 12 min p i xi i=1 s.t. xi + si−1 − di = si si ≤ 15 (1 ≤ i ≤ 12) (1 ≤ i ≤ 12) s0 = 7 x, s ≥ 0 (b) Now assume that the company wants to even out production over the year in order to keep its demand for staff constant. We model this by assuming that the company incurs a cost of 50 for each ton of difference between the production quantities in any two consecutive months. As an example, assume that the company decides to produce xi tons of ice-cream in month i ∈ {1, . . . , 12}. i xi 1 23 2 21 3 26 4 28 5 32 6 32 4 7 20 8 10 9 12 10 5 11 6 12 8 The cost incurred by the company for the production plan given in the above table is: (23 − 21) + (26 − 21) + (28 − 26) + (32 − 28) + (32 − 32) + (32 − 20)+ (20 − 10) + (12 − 10) + (12 − 5) + (6 − 5) + (8 − 6) · 50. As in (a), assume that the freezers contain 7 tons of ice cream at the beginning of month 1, and that you can store up to 15 tons of ice cream at any time. The company wants to find a production schedule that minimizes the total cost incurred by production changes. Formulate the problem as an LP. Solution: As before, we let xi be the production quantity in month 1 ≤ i ≤ 12, and let si be the storage requirement at the end of month i. We want to minimize 11 |xi − xi+1 | 50. i=1 We need to linearize the absolute value in the above expression, and do this by introducing new variables zi with intended meaning |xi − xi+1 | for all i. We enforce this meaning by adding two constraints for each i: zi ≥ xi − xi+1 zi ≥ xi+1 − xi . Clearly if zi is equal to |xi − xi+1 | then it satisfies these two constraints. On the other hand, if zi is minimal and satisfies these two constraints then zi = |xi − xi+1 |. With this the new LP becomes: 11 min 50 zi i=1 s.t. xi + si−1 − di = si si ≤ 15 (1 ≤ i ≤ 12) (1 ≤ i ≤ 12) s0 = 7 zi ≥ xi − xi+1 (1 ≤ i ≤ 11) zi ≥ xi+1 − xi (1 ≤ i ≤ 11) x, s, z ≥ 0 Problem 4: Modeling Absolute Values For about two years now, residents of Winston have been plagued by an ominous noise at night. The source of the noise is unclear, but it appears to be coming from across the river that flows through town, from the city of Steeltown. What is worse, the noise seems to be getting louder every night! In order to prove this fact, the residents of Winston are taking noise measurements on a nightly basis. The following table and graph show the data for 9 consecutive measurements. day i noise ni [dB] 1 13 2 11 3 21 4 29 5 5 27 6 30 7 41 8 37 9 42 volume [dB] 60 50 40 30 20 10 day 1 2 3 4 5 6 7 8 9 The picture seems to show that the increase in noise level is linear; i.e., that there is a line (as depicted in the figure) that explains the noise developments in Winston; i.e., there are a, b ∈ R such that the noise on day i is roughly a i + b. But how do we choose a and b? A savvy resident writes down the following mathematical program for this task: 9 |(a i + b) − ni |, min (13) i=1 where ni is the measured noise level on day i, | · | denotes the absolute value function. Mathematical program (13) has two variables, a and b, and attempts to choose these such that the total absolute error for the observed data with respect to the linear function ax + b is minimized. Note that (13) is not a linear program: the absolute value function is not linear! But our savvy friend from Winston claims that one can use linear programming to formulate this problem. Can you help? Solution: First note that we can replace |(ai + b) − ni | in the objective function with a new variable yi , and the constraints yi ≤ |(ai + b) − ni | and yi ≥ |(ai + b) − ni |. Moreover, since we are trying to minimize the value of the objective function, we only need the constraints yi ≥ |(ai + b) − ni |. This gives us the more familiar looking mathematical program: 9 min yi i=1 s.t. yi ≥ |(ai + b) − ni | (1 ≤ i ≤ n). It remains to remove the absolute value expressions from the constraint set. Note that if x ≥ |α|, then x ≥ α and x ≥ − α. So we can replace yi ≥ |(ai + b) − ni | with the constraints yi ≥ (ai + b) − ni and yi ≥ −(ai + b) + ni . So our linear program is: 9 min yi i=1 s.t. yi ≥ (ai + b) − ni yi ≥ −(ai + b) + ni (1 ≤ i ≤ n) (1 ≤ i ≤ n) Problem 5: IP Models The Waterloo hotel wants to rent rooms 1, 2 and 3 for New Year’s night. Abby is willing to pay $60 for room 1, $50 for room 2 but is not interested in room 3. Bob is willing to pay $40 for room 1, $70 for room 6 2, and $80 for room 3. Clarence is not interested in room 1, but is willing to pay $55 for room 2 and $75 for room 3. Donald is willing to pay $65 for room 1, $90 for room 2, but is not interested in room 3. The information is summarized in the following table. Room number 1 2 3 Abby’s offer $60 $50 not interested Bob’s offer $40 $70 $80 Clarence’s offer not interested $55 $75 Donald’s offer 65$ $90 not interested The hotel wants fill up rooms 1,2,3 with some of the potential clients (Abby, Bob, Clarence and Donald) in a way that maximizes the total revenue. Each room is to be assigned to exactly one potential client, and each potential client is to be assigned at most one room. As an example, Room 1 could be assigned to Bob, room 2 to Abby, and room 3 to Clarence (while Donald would not get to stay in the hotel). This would yield a revenue of $40+$50+$75=$165. (a) Formulate this problem as an IP. Your solution should be easy to modify if we change the values in the table. Solution: We let oij be the offer of i ∈ {Abby, Bob, Clarence, Donald} for room j ∈ {1, 2, 3}. We then introduce one binary variable xij for all guests i and rooms j whose value is 1 if person i is assigned to room j. We obtain the following integer program: s.t. (oij xij : i ∈ {Abby, Bob, Clarence, Donald}, j ∈ {1, 2, 3}) (14) (xij : j ∈ {1, 2, 3}) ≤ 1 (i ∈ {Abby, Bob, Clarence, Donald}) (15) (xij : i ∈ {Abby, Bob, Clarence, Donald}) = 1 (j ∈ {1, 2, 3}) max (16) x ≥ 0, x ≤ 1, x integer (17) The objective function (14) simply maximizes the total revenue extracted from the guests. Constraints (17) enforce that all variables xij are between 0 and 1 and integer – thus, these variables are binary. With this, constraints (15) force each guest into at most one room, and similarly, constraints (16) enforce that each room is given to exactly one guest. (b) Abby and Bob have a history of loud and rude behavior when celebrating together. In the interest of keeping the New Year’s eve party orderly the hotel management decides that it does not wish to rent rooms to both Abby and Bob. Add a constraint to the IP in (a) that will enforce this condition (the resulting formulation should still be an IP). Solution: Notice that, for some guest i, (xij : j ∈ {1, 2, 3}) is at most 1 in any feasible solution to the IP in (a), and that it is exactly 1 if i is booked into a room. Thus we add the constraint (xAbby,j : j ∈ {1, 2, 3}) + (xBob,j : j ∈ {1, 2, 3}) ≤ 1 enforcing that at most one of Abby and Bob are assigned to a room. 7 ...
View Full Document

Please, wait while we are validating your browser

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *