Math 339 Solutions to Review Questions, Exam 1

Solutions to Review Questions, Exam 1 1. What are the four possible outcomes when solving a linear program? Hint: The first is that there is a unique solution to the LP. SOLUTION: • No solution - The feasible set is empty. • A unique solution (either with or without an unbounded feasible set). • An unbounded solution - The feasible set is unbounded. • An infinite number of solutions - Either by an unbounded set or the isoprofit lines are coincident with a boundary at the optimum. 2. The following are to be sure you understand the process of constructing a linear program: (a) Draw a production process diagram and set up the LP for Exercise 6, p. 98 (Sect. 3.9) SOLUTION: See the figure below. 1 (b) Exercise 2, 31 Chapter 3 review SOLUTIONS: Be sure you can do these graphically. • Solution to exercise 2: The optimal value is 69/7, where we have 36/7 chocolate cake and 66/7 vanilla (yes, the “divisibility” assumption is violated here). • Solution to exercise 31: The LP is unbounded (no solution). (c) Exercise 6, 18 Chapter 3 review (A ton is 2000 lbs) SOLUTIONS: Be sure you introduce your variables! 6. Let x1 be the pounds of Alloy 1 used to produce one ton of steel and x2 be the pounds of Alloy 2. Then the objective function is: min z = 190/2000x1 + 200/2000x2 With: – Carbon constraints: 0.03x1 + 0.04x2 ≥ (0.032)(2000) 0.03x1 + 0.04x2 ≤ (0.035)(2000) – Silicon: 0.02x1 +0.025x2 ≥ (0.018)(2000) 0.02x1 +0.025x2 ≤ (0.025)(2000) – Lastly, nickel: 0.01x1 + 0.015x2 ≥ 18 0.01x1 + 0.015x2 ≤ 24 – Tensile strength: 42, 000x1 + 50, 000x2 ≥ 45, 000 2, 000 – Relationship between variables: x1 + x2 = 2000 – Non-negative: x1,2 ≥ 0. • An interesting application of “blending”- The solution is in the back of the text. (d) Exercise 22, Chapter 3 review. Hint: Consider using a triple index on your variables. SOLUTION: Let xijk is the units of product 1, machine i, month j, for sale in month k. Let yijk is the units of product 2, machine i, month j, for sale in month k. In order to simplify things, we note some quantities that are useful: • • • • Amount Amount Amount Amount of of of of Product Product Product Product 1 2 1 2 for for for for sale sale sale sale in in in in 2 Month Month Month Month 1: 1: 2: 2: x111 + x211 y111 + y211 x112 + x212 + x122 + x222 y112 + y212 + y122 + y222 Then we have the objective function to maximize: 55(x111 +x211 )+12(x112 +x212 +x122 +x222 )+65(y111 +y211 )+32(y112 +y212 +y122 +y222 ) For constraints, here are Machine 1 hour constraints (for Months 1, 2): 4(x111 + x112 ) + 7(y111 + y112 ) ≤ 500 4x122 + 7y122 ≤ 500 Similarly, for Machine 2: 3(x211 + x212 ) + 4(y211 + y212 ) ≤ 500 3x222 + 4y122 ≤ 500 Sales constraints (Month 1, then Month 2): x111 + x211 ≤ 100 x112 + x212 + x122 + x222 ≤ 190 y111 + y211 ≤ 140 y112 + y212 + y122 + y222 ≤ 130 Also, all variables are non-negative. (e) Exercise 47, 53 in Chapter 3 review. SOLUTIONS: For Exercise 47, see the back of the book. SOLUTION, Exercise 53: Here is a list of the variables: • T1,2 : Number of Type 1 and 2 Turkeys that are purchased • D1,2 : Pounds of dark meat used in Cutlet 1, 2 (resp) • W1,2 : Pounds of white meat used in Cutlet 1, 2 (resp) The objective function is to maximize: 4(W1 + D1 ) + 3(W2 + D2 ) − 10T1 − 8T2 Here are the constraints: • • • • • • • (Cutlet 1 demand) W1 + D1 ≤ 50 (Cutlet 2 demand) W2 + D2 ≤ 30 (Don’t use more white meat than you have) W1 + W2 ≤ 5T1 + 3T2 (Don’t use more dark meat than you have) D1 + D2 ≤ 2T1 + 3T2 (70% white meat) W1 /(W1 + D1 ) ≥ 0.7 (60% white meat) W2 /((W2 + D2 ) ≥ 0.6 T1,2 , D1,2 , and W1,2 are all non-negative. 3. Convert the following LP to one in standard form. Write the result in matrix-vector form, giving x, c, A, b (from our formulation). min z = 3x − 4y + 2z st 2x − 4y ≥ 4 x + z ≥ −5 y+z ≤1 x+y+z =3 with x ≥ 0, y is URS, z ≥ 0. SOLUTUION: Let x = [x, y + , y − , z, e1 , s1 , s2 ]T . Then  2 −4 4 0 −1 0 0  −1 0 0 −1 0 1 0 c = [3, −4, 4, 2, 0, 0, 0]T A=  0 1 −1 1 0 0 1 1 1 −1 1 0 0 0 3       4  5   b=  1  3 4. Consider again the “Wyndoor” company example we looked at in class: min z = 3x1 + 5x2 st x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 ≤ 18 with x1 , x2 both non-negative. (a) Rewrite so that it is in standard form. SOLUTION: Define the extra variables x3 , x4 , x5 . Using the extra variables in order, the constraints become: x1 + x3 2x2 + 3x1 + 2x2 + x4 x5 =4 = 12 = 18 And from this, it is easy to read off the coefficient matrix A. (b) Let s1 , s2 , s3 be the extra variables introduced in the last answer. Is the following a basic solution? Is it a basic feasible solution? x1 = 0, x2 = 6, s1 = 4, s2 = 0, s3 = 6 Which variables are BV, and which are NBV? SOLUTION: The matrix A has rank 3. If the solution has n − m = 5 − 3 = 2 zeros (and it is a solution), then it is a basic solution: Yes, this is a basic solution. It is also a basic feasible solution since every entry of the basic solution is non-negative. The variables x2 , x3 and x5 are the basic variables (BV) and the variables x1 and x4 are NBV. (c) Find the basic feasible solution obtained by taking s1 , s3 as the non-basic variables. In this case, we can row reduce the augmented matrix (remove columns 3 and 5 from the original):     1 0 0 4 1 0 0 4  0 2 1 12  −→  0 1 0 3  3 2 0 18 0 0 1 6 In this case, we have the (full) solution: x1 = 4, x2 = 3, x3 = 0, x4 = 6, x5 = 0 5. Consider Figure 1, with points A(1, 1), B(1, 4) and C(6, 3), D(4, 2) and E(4, 3). • Write the point E as a convex combination of points A, B and C. SOLUTION: First we’ll find the point
of intersection between line AE and BC. 58 43 Call it E 0 . We found it to be E 0 13 , 13 (Sorry about the fractions!). By the time we’re done, you should have:          2 1 13 4 1 9 6 4 + + = 3 15 1 15 13 4 13 3 4 • Can E be written as a convex combination of A, B and D? If so, construct it. SOLUTION: No. The point E is above the convex hull of A, B and D (which is the triangle whose vertices are at A, B, D). • Can A be written as a linear combination of A, B and D? If so, construct it. SOLUTION: Obvious typo there- I meant to say E can be written ... Using E, we can set up the matrix and solve:   1 1 4 4 ⇒ 1 4 3 2 If the coefficients for the linear combination are c1 , c2 , c3 , we find them to be: C1 = 14 − 13 C 3 3 3 C2 = − 23 + 13 C3 C3 = C3 Therefore, there are an infinite number of ways to make this linear combination (which was expected, since three vectors in IR2 are not linearly independent). 6. Draw the feasible set corresponding to the following inequalities: x1 + x2 ≤ 6, x1 − x2 ≤ 2 x1 ≤ 3, x2 ≤ 6 with x1 , x2 non-negative. (a) Find the set of extreme points. SOLUTION: (0, 0), (0, 6), (2, 0), (3, 3), (3, 1). (b) Write the vector [1, 1]T as a convex combination of the extreme points. SOLUTION: Since I get to choose, let’s make it easy:             2 0 1 3 0 2 3 1 + +0 +0 +0 = 6 0 1 1 3 3 3 0 Or, a little more complex:             1 0 1 2 1 0 1 3 3 = + + +0 +0 1 3 1 6 6 2 0 3 0 Figure 1: Figure for the convex combinations, Exercise 5. 5 Figure 2: Figure for Question 10 (c) True or False: The extreme points of the region can be found by making exactly two of the constraints binding, then solve. SOLUTION: If we follow this recipe, we will get extreme points, but we’ll also get non-feasible points (for example, the point (3, 6)). Therefore, FALSE. (d) If the objective function is to maximize 2x1 + x2 , then (a) how might I change that into a minimization problem, and (b) solve it. SOLUTION: For part (a), we convert it by minimizing −z, or min −2x1 − x2 . For part (b), solve it graphically to get that the maximum occurs at (3, 3) and the maximum is 9. 7. Consider the unbounded feasible region defined by x1 − 2x2 ≤ 4, −x1 + x2 ≤ 3 with x1 , x2 non-negative. Consider the vector p = [5, 2]. (a) Show that p is in the feasible region. SOLUTION: Substitute the values into the constraints to see that they are both valid. (b) Set up the system you would solve in order to write p in the form given in Theorem 2 (provide a specific vector d). SOLUTION: Directions of unboundedness can have “slopes” between 1/2 and 1, so we could choose d = [1, 1]T . But then [5, 2]T − [1, 1]T is not in the convex hull of the vertices, so we can make d = [2, 2]T . Therefore,           5 2 4 0 0 = + σ1 + σ2 + σ3 2 2 0 2 0 And we could go ahead and solve “by inspection”, getting σ1 = 3/4, σ2 = 0 and σ3 = 1/4. 8. Finish the definition: Two basic feasible solutions are said to be adjacent if: SOLUTION: Two basic feasible solutions are adjacent if they share all but one basic variable. 6 9. Let d be a direction of unboundedness. Using the definition, prove that this means that rd is also a direction of unboundedness, for any constant r ≥ 0. SOLUTION: We assume an LP in standard form, so our set S = {x|Ax = b}. Then, d 6= 0 is a direction of unboundedness for S if x + λd ∈ S for all x ∈ S and λ ≥ 0. Therefore, in what is given, we can let u = rd and show that u is a direction of unboundedness: Let x be any point of S and λ ≥ 0. Then: x + λu = x + (λr) d which must be in S since d was a direction of unboundedness. 10. If C is a convex set, then d 6= 0 is a direction of unboundedness for C iff x + d ∈ C for all x ∈ C (Use the definition of unboundedness). SOLUTION: We have two directions• d 6= 0 is a direction of unboundedness for C implies x + d ∈ C is trivially true, since we can just make λ = 1. • We now show that, if x+d ∈ C for all x ∈ C, then d is a direction of unboundedness for C: Let x0 be any point in S, and λ ≥ 0. Then show that x0 + λd ∈ S. Let λ = N + α, where N is a non-negative integer, and 0 ≤ α < 1. Then x0 + λd = x0 + (N + α)d = (x0 + d) + ((N − 1) + α)d Now, since x1 = x0 + d, then x1 ∈ C, we can write this as: x1 + d + ((N − 2) + α)d and so on. Therefore, we have that x0 + N d ∈ S Finally, since x0 + N d + d ∈ C, then because C is convex, so will the vector x0 + N d + αd ∈ C. 11. For an LP in standard form (see above), prove that the vector d is a direction of unboundedness iff Ad = 0 and d ≥ 0. Solution: • Show that if Ad = 0, with d ≥ 0, then d is a direction of unboundedness. Note that this means we have to show that y = x + λd ∈ S for every λ. Let x be in the feasible set, x ∈ S so that x ≥ 0. Now, Ay = A (x + λd) = Ax + λAd = b + 0 = b Wait! We’re not done- Check that y ≥ 0 (it is since λ, x, d ≥ 0). • Now go in the reverse: Suppose that we know that d is a direction of unboundedness. We show that Ad = 0 and d ≥ 0. 7 Let x be in the feasible set. One path we could take is to suppose that, by way of contradiction, that Ad 6= 0. Then A (x + λd) = Ax + λAd = b + λk 6= b But then x + λd is not an element of S (contradiction). The other part: Is d ≥ 0? If not, then at least one coordinate di < 0. But then it is possible to find λ so that the ith coordinate of x + λd is negative (contradiction). 12. Show that the set of optimal solutions to an LP (assume in standard form) is convex.  SOLUTION: Define S = x|Ax = b, cT x = L Now, let y1 , y2 ∈ S. We show that all points on the line segment between them is also in S. Let y be a point between- Then there is a 0 ≤ t ≤ 1 so that: y = ty1 + (1 − t)y2 Now, y is also feasible, since Ay = tAy1 + (1 − t)Ay2 = tb + (1 − t)b = b And y will give the same optimal value, cT y = tcT y1 + (1 − t)cT y2 = tL + (1 − t)L = L 13. Let a feasible region be defined by the system of inequalities below: −x1 + 2x2 ≤ 6 −x1 + x2 ≤ 2 x2 ≥ 1 x1 , x2 ≥ 0 The point (4, 3) is in the feasible region. Find vectors d and b1 , · · · bk and constants σi so that the Representation Theorem is satisfied (NOTE: Your vector x from that theorem is more than two dimensional). SOLUTION: Graphing the region in 2-d, we see that the extreme points are:       0 0 2 b1 = , b2 = , b3 = 1 2 4 And d can be any vector pointing outwards with a slope between 0 and 1/2. The easiest method to get the representation is to “aim backwards” at an extreme point, but using a vector that will be an allowable d. In this case, we can write:       4 0 4 = + 3 2 1 Using the matrix A from the LP in standard form (with variables in order: x1 , x2 , s1 , s2 , e1 ), we have:   −1 2 1 0 0 0  A =  −1 1 0 1 0 1 0 0 −1 8 From this, it is easy to solve for the remaining dimensions: Ax = b s1 = 6 + x1 − 2x2 s 2 = 2 + x1 − x2 e1 = −1 + x2 ⇒ And for the vector in the null space, replace (6, 2, 1) by (0, 0, 0). Therefore,       4 0 4  3   2   1         4 = 2 + 2         3   0   3  2 1 1 14. Let a feasible region be defined by the system of inequalities below: −x1 + x2 ≤ 2 x1 − x2 ≤ 1 x1 + x2 ≤ 5 x1 , x2 ≥ 0 The point (2, 2) is in the feasible region. Find vectors d and b1 , · · · bk and constants σi so that the Representation Theorem is satisfied (NOTE: Your vector x from that theorem is more than two dimensional). SOLUTION: The point given is between two extreme points, [0, 2]T and [3, 2]T . Therefore, in two dimensions we have       1 2 0 3 =t + (1 − t) ⇒ t= 2 2 2 3 We also get the matrix A in standard form, with column variables (in order): x1 , x2 , s1 , s2 , s3 , and   −1 1 1 0 0 s 1 = x1 − x2 + 2   1 −1 0 1 0 s2 = −x1 + x2 + 1 A= ⇒ 1 1 0 0 1 s3 = −x1 − x2 + 5 From which we get:       0 3 2  2   2   2    1  2   2 =  0 +  3    3  3   3   0   1  3 0 1 15. Suppose that λ1 ≤ λ2 ≤ · · · λn , and let σ1 , · · · , σn be non-negative constants so that n X σi = 1. Show that i=1 λ1 ≤ σ1 λ1 + σ2 λ2 + · · · σn λn ≤ λn SOLUTION: σ1 λ1 + σ2 λ2 + · · · σn λn ≤ σ1 λn + σ2 λn + · · · σn λn = (λn ) X i (A similar proof works the other way, too) 9 σi = λn 16. Show that, if x is in the convex hull of vectors b1 , · · · bk , then for any constant vector c,  cT x ≤ max cT bi i SOLUTION: If x is in the convex hull of the vectors bi , then we can write x as a convex combination of them: x = α1 b1 + · · · + αk bk Taking the dot product of both sides with c, we have: cT x = α1 (cT b1 ) + · · · αk (cT bk ) which is the set up to the previous problem with λj = cT bj . By that exercise, we know that  cT x = α1 (cT b1 ) + · · · αk (cT bk ) ≤ max cT bi i SIDE REMARK: Notice that this is a key element of the fundamental theorem of linear programming- The maximum and minimum of the objective function are attained at extreme points. 17. True or False, and explain: The Simplex Method will always choose a basic feasible solution that is adjacent to the current BFS. SOLUTION: That is true. It is because we will only replace one of the current basic variables with a new variable, therefore, the new BFS will keep all but one of the current set of basic variables. 18. Given the current tableau (with variables labeled above the respective columns), answer the questions below. x1 x 2 s 1 s2 rhs 0 −1 0 2 24 0 1/3 1 −1/3 1 1 2/3 0 1/3 4 (a) Is the tableau optimal (and did your answer depend on whether we are maximizing or minimizing)? For the remaining questions, you may assume we are maximizing. ANSWER: This tableau is not optimal for either. If we were minimizing, we could still pivot using s2 . If we were maximizing, we could still pivot in x2 . (b) Give the current BFS. ANSWER: The current BFS is x1 = 4, x2 = 0, s1 = 1 and s2 = 0. (c) Directly from the tableau, can I increase x2 from 0 to 1 and remain feasible? Can I increase it to 4? ANSWER: From the ratio test, x2 can be increased to 3 in the first, and 6 in the second. However, increasing it to 4 would violate the first constraint. Summary: I can increase x2 from 0 to 1, but not to 4. (d) If x2 is increased from 0 to 1, compute the new value of z, x1 , s1 (assuming s2 stays zero). SOLUTION: 10 2 z = 25 x1 = s1 = 3 3 10 (e) Write the objective function and all variables in terms of the non-basic (or free) variables, and then put them in vector form. SOLUTION: For the current tableau, z = 24 + x2 − 2s2 , with       x1 = 4 − 2/3x2 − 1/3s2 −2 −1 4  0  x2  1  s 2  0  x2 = x2      ⇒ x=  1  + 3  −1  + 3  1  s1 = 1 − 1/3x2 + 1/3s2 s2 = s2 0 0 0 11