Introduction to Optimization Recitation 2 - Solutions

Problem 1 We will solve the problem in couple of discrete steps. When you become familiar with these transformations you might reformulate in a single step. The following figure shows x and |x| and the feasible region (the constraints are the black thin lines, the feasible region is shown as grey) First we introduce a new variable z and let z = |x| and introduce z = |x| as a constraint. As a result, the problem looks somewhat different, but in reality nothing has changed yet – as the following figure shows. minimize subject to Page 1 of 9 z z = |x| -3 ≤ x ≤ 2 Because we are minimizing z, we can change z = |x| to z ≥ |x|, thus yielding the problem minimize z subject to z ≥ |x| -3≤x ≤2 and our picture of the feasible region changes to Recall that the definition of |x| is |x| ={-x, for x ≤ 0 and x, for x≥0}=max{x,-x} Therefore, if we require z to be greater than or equal to both –x and x it is going to be greater than or equal to max{x,-x}, hence greater than or equal to |x|. Hence, we obtain the following program which is a linear program. Page 2 of 9 minimize subject to z z ≥ -x z≥x -3 ≤ x ≤ 2 And our final plot looks like Note that the only difference is that instead of the V-shaped constraint z ≥ |x|, we have two linear constraints. Problem 2 We start by drawing the feasible region (where constraints are thin black lines, and the feasible region is grey) Page 3 of 9 We let z = max{2x-4, |x|} and obtain minimize subject to z z = max{2x-4, |x|} -3≤ x ≤6 The plot does not change much Next, we make use of the fact that we are minimizing z to replace z = max{2x-4,|x|} with z ≥ max{2x-4,|x|}, and obtain Page 4 of 9 minimize subject to z z ≥ max{2x-4,|x|} -3≤x ≤6 The corresponding plot follows We have z ≥ max{2x-4,|x|} if and only if z ≥ 2x-4 and z ≥ |x|, hence we obtain minimize subject to z z ≥ 2x-4 z ≥ |x| -3≤x ≤6 The final step is to replace z ≥ |x| with two linear constraints, z ≥ -x and z ≥ x, and we then obtain minimize subject to z z ≥ 2x-4 z≥x z ≥ -x -3≤x ≤6 The following figure provides geometric interpretation for the obtained problem. Page 5 of 9 ii) Solution with 2 variables An alternative way to proceed is to introduce a new variable z2 in the following way: We proceed as before and obtain minimize subject to z z ≥ 2x-4 z ≥ |x| -3≤ x ≤6 We then let z2 = |x| and obtain the following problem minimize subject to z z ≥ 2x-4 z ≥ z2 z2=|x| -3≤x ≤6 And then we get rid of the absolute value as before minimize z subject to z ≥ 2x-4 z ≥ z2 z2≥x z2≥-x -3≤x ≤6 Page 6 of 9 This is identical to the previous solution once we notice that z ≥ z2, z2 ≥ x, z2≥-x ↔ z ≥ x, z ≥ -x Problem 3 First, we let z1=|x1| and z2=|x2|. The problem becomes: minimize subject to z 1 + z2 z1 = |x1| z2=|x2| 6≤ x ≤8 x1≤ x2 Since we are minimizing z1+z2 we can replace z1 = |x1| and z2=|x2| as we have done in previous problems. This gives us Minimize subject to z1+z2 z1 ≥ |x1| z2 ≥ |x2| 6≤x≤8 x1≤ x2 By replacing zi ≥ |xi| with zi ≥ -xi and zi ≥ xi as before we obtain the final solution: minimize subject to z1+z2 z1 ≥ -x1 z1≥ -x1 z2≥ -x2 z2≥ x2 6≤x≤8 x1 ≤ x2 Problem 4 – Introduction to SolverTable -See Excel Sheet Problem 5 From Excel – CyTools we get -3 4 1 3 10 20 1 0 -0.33333 4.333333 -3.33333 33.33333 1 0 0 1 -0.76923 7.692308 Page 7 of 9 And we see that -0.769 times the first vector plus 7.692 times the second vector gives us the last vector. See Excel sheet for more information Problem 6 - Portfolio Selection Let XA be the amount ($M) invested in bond A : XE be the amount ($M) invested in bond E Maximize z = 0.043xA + 0.027xB + 0.025xC + 0.022xD + 0.045xE Subject to (1) x A + x B + x C + x D + x E ≤ 10 (2) x B + xC + x D ≥ 4 (3) 2 x A + 2 x B + xC + x D + 5 x E ≤ 1.4 x A + x B + xC + x D + x E (4) 9 x A + 15 x B + 4 xC + 3x D + 2 x E ≤5 x A + x B + xC + x D + x E Rewrite constraints (3) and (4) as (3) 0.6 x A + 0.6 x B − 0.4 xC − 0.4 x D + 3.6 x E ≤ 0 (4) 4 x A + 10 x B − xC − 2 x D − 3x E ≤ 0 And don’t forget non-negativity: (5) x A , x B , xC , x D , x E ≥ 0 In the case where we can borrow: Let y be the amount of money borrowed at 5.5% New Objective is: Maximize z = 0.043xA + 0.027xB + 0.025xC + 0.022xD + 0.045xE – 0.055y Rewrite constraint (1) as: (1’) x A + x B + xC + x D + x E ≤ 10 − y Page 8 of 9 And add a constraint to limit the amount we can borrow: (6) y ≤1 See Excel for Solver Table Page 9 of 9