Introduction to Optimization Problem 1 – IP formulations Consider a production profit maximization problem with 4 production processes (running time expressed in hours) and 4 resource constraints: max 2 x1 + 3x2 + 5 x3 + 4 x4 3 s.t. x1 + x2 + 4 x3 + 4 x4 ≤ 40 (1) 4 2 x1 + x2 + 2 x3 + 3x4 ≤ 60 (2) x1 + 3x2 + 3x3 + x4 ≤ 70 3x + 2 x2 + 2 x3 ≤ 65 (3) ( 4) 0 ≤ x1 , x2 , x3 ≤ 100. Model the following additional production constraints, by introducing additional (possibly integer) variables and constraints. a) Suppose that there is an additional constraint that if process 1 is used, then process 2 cannot be used. b) Suppose that due to plant design, at least one of processes 1 and 2 has to run for at least 10 hours. c) Suppose that due to plant design, processes 1 and 2 can either run for 10 hours, or not run at all. Model the constraints that at least one of them has to run, but not both. d) Suppose that due to plant design, each process can either run for 5 hours, or not run at all. Model the constraint that at least 3 processes can run. Model the constraint that exactly 3 processes have to run. Model the constraint that at least 3 processes have to run. Page 1 of 3 e) Suppose that due to plant design, process 4 can only run for 0, 4, 10, 15 or 20 hours. Model this constraint. The following points deal with additional specifics on the resource constraints: f) Suppose that instead of having to satisfy both constraint (1) and (2), it is enough to satisfy one of these constraints (it is still ok to satisfy both at the same time). Model this situation. g) Suppose that it is enough to satisfy any 2 of the 4 constraints (it is still ok to satisfy any 3, or all 4). Model this situation. h) Suppose that constraint (3) only needs to be satisfied if constraint (2) is not satisfied. Model this situation. i) Suppose that constraint (4) only needs to be satisfied if none of the constraints (1, 2, 3) are satisfied. Model this situation. Problem 2 – Minimum Cost Flow 6 6 1 B 1 7 10 A 6 9. E 6 1 6 C 1 F 1 4 9 9 D 4 1 G 8 Page 2 of 3 H 2 The graph above represents a minimum cost flow problem. There is a supply of 10 at node A and 6 at node E. There is a demand of 6 at node B, 8 at node G and 2 at node H. There is no capacity limit on any of the arcs. The numbers next to the arcs represent the cost of shipping one unit along the arc. a) Our objective is to minimize the cost of shipping from supply nodes to demand nodes. Formulate the problem as an LP . b) Will the decision variables ALL be integral in the optimal solution? Problem 3. The Ultimate Relay Team Carol, Jim, Margret and Mike are all outstanding swimmers and they are competing together in 4x100m IM relay. (In an IM relay, one swimmer swims backstroke, one breaststroke, one butterfly and one freestyle). The following table shows their best times in each stroke. backstroke breaststroke butterfly freestyle Carol 57.8 01:01.0 56.2 55.3 Jim 56.2 59.9 55.7 54.6 Margret 59.3 01:05.7 59.6 57.2 Mike 56.8 01:00.3 55.9 55.7 Carol, Jim, Margret and Mike want to put together the fasted relay team possible – who should swim what stroke? a) An example of what type of problem is the Relay Team Problem? b) Formulate the problem as an LP Page 3 of 3