Introduction to Optimization Recitation 9 - Solutions

Introduction to Optimization Problem 1 a) The graph is as follows: 5 4 3 Integer Solutions (C1) 4x + 6y <= 24 (C2) -x + y <= 1 2 1 0 0 1 2 3 4 5 6 7 The feasible area for the LP relaxation is between the two lines, and the integer solutions are indicated by blue dots. b) The first constraint (from the final tableau) is: x + .1 s1 – .6 s2 = 1.8 or x + .1 s1 + (-1 + .4) s2 = 1 + .8 Now, focusing on the fractional parts, we add the constraint which can be rewritten as .1 s1 + .4 s2 ≥ .8 s1 + 4 s2 ≥ 8. (Incidentally, if we start with the second constraint, we get the same result.) This excludes the current fractional optimal solution (which has s1 = s2 = 0). However, it does not exclude any of the integer solutions. This is because any integer solution that satisfies the new constraint will have x integral. Thus the fractional part of the RHS (the .8) Page 1 of 4 must come from s1 and s2. It can be verified that none of the integer points plotted in part a) get excluded by the new constraint. c) Note that the new constraint can be rewritten in terms of x and y as: s1 + 4 s2 ≥ 8 ⇒ (24 – 4x – 6y) + 4 (1 + x – y) ≥ 8 ⇒ y ≤ 2 If we add this line to our graph of part a), we can see that the new solution to the LP relaxation is the point (1,2), which is integral. d) Yes! The new cut was so good that we achieved an integer solution after adding it. Problem 2 a) It is important to choose variables carefully in this part of the problem, to model the various different possibilities. One way to solve it is to let: xi = 1 if gymnast i enters both events, and 0 otherwise yi = 1 if gymnast i enters only the balance beam, and 0 otherwise zi = 1 if gymnast i enters only the floor exercise, and 0 otherwise The integer program then can be formulated as: max 16.7 x1 + 17.7 x 2 + ... + 17.7 x 6 + 8.8 y1 + ... + 9.1y 6 + 7.9 z1 + ... + 8.6 z 6 s.t. x1 + x 2 + x3 + x 4 + x5 + x 6 = 3 (1) y1 + y 2 + y 3 + y 4 + y 5 + y 6 = 1 z1 + z 2 + z 3 + z 4 + z 5 + z 6 = 1 (2) (3) xi + y i + z i ≤ 1 for i = 1,...6 xi , y i , z i ∈ {0,1} for i = 1,...6 (4) Constraint (1) ensures that exactly three people are entered in both events; constraints (2) and (3) guarantee that exactly one person is entered in only the balance beam and floor exercise. Constraint (4) says that each person can be assigned to at most one of these situations. b) If gymnasts 2 and 4 do not both wish to perform in the floor exercise, we can model this event by introducing the constraint x2 + z2 + x4 + z4 ≤ 1. c) We wish to say that if gymnast 5 participates in any event, then gymnast 6 must also participate in some event. There are multiple ways to do this, but the easiest way is to introduce the constraint x5 + y5 + z5 = x6 + y6 + z6 Page 2 of 4 Problem 3 a) We set up a minimum cost flow problem as follows. We let the nodes correspond to the cities IBM ships to, and we add an arc for every transportation possibility. The cost of arcs exiting the Boston and Raleigh nodes reflects both the cost of producing the computers and of transporting them. The cost of arcs exiting nodes other than Boston and Raleigh is equal to only the transportation cost. We set a supply of 400 at Boston and 300 at Raleigh, and a demand of 400 at Los Angeles and 300 at Austin. The graph looks like: The costs are indicated on the arcs. The capacity of each arc is infinity. b) If at most 200 units can be shipped through Chicago, we alter the network as follows: Here we have added a new node Chicago’, and new arcs (Boston, Chicago’) and (Raleigh, Chicago’). We have deleted the old arcs (Boston, Chicago) and (Raleigh, Chicago). We have added a new arc (Chicago’, Chicago) of cost 0 and capacity 200. All other arcs stay the same. The effect of the arc (Chicago’, Chicago) is that at most 200 units can enter into the node Chicago’. This is the same as limiting the number of units that can be shipped through Chicago in the original network. Page 3 of 4 Problem 4 a) The payoff matrix for this game is: Row Player Rock Paper Scissors Column Player Paper -1 0 1 Rock 0 1 -1 Scissors 1 -1 0 The payoffs are in terms of profit to the row player. b) Let x1 be the probability that the row player plays rock, x2 be the probability of playing paper, and x3 the probability of playing scissors. We can find the row player’s optimal strategy by solving the following linear program: max v s.t. v ≤ x 2 − x3 v ≤ − x1 + x3 v ≤ x1 − x 2 (1) (2) (3) x1 + x 2 + x3 = 1 (4) x1 , x 2 , x3 ≥ 0 The constraint (1) addresses the case where the column player plays rock, the constraint (2) addresses the case where the column player plays paper, and the constraint (3) addresses the case where the column player plays scissors. The constraint (4) requires that all of the probabilities sum to 1. c) Let y1 be the probability that the column player plays rock, y2 be the probability of playing paper, and y3 the probability of playing scissors. The column player’s objective is to guarantee the lowest possible payoff to the row player. Accordingly, the column player computes the expected payoff using these probabilities, for every possible choice the row player could make. The column player then tries to minimize the maximum amount the row player can win. This gives the linear program: min w s.t. w ≥ − y 2 + y3 w ≥ y1 − y 3 w ≥ − y1 + y 2 (1) (2) (3) y1 + y 2 + y 3 = 1 (4) y1 , y 2 , y 3 ≥ 0 d) The optimal payoff to the row player is the negative of the optimal payoff to the column player. In other words, the optimal values of the two LPs listed above are the same! Page 4 of 4