IELM3010'17 Tutorial 7 Nov. 29 & 30 1. The board of directors of General wheels Co. is considering six large capital investments. Each investment can be made only once. These investments differ in the estimated long-run profit(net present value) that they will generate as well as in the amount of capital required, as shown by the following table (in units of millions of dollars): Estimated profit Capital required 1 15 2 12 38 33 Investment opportunity 3 4 16 18 39 45 5 9 6 11 23 27 The total amount of capital available for these investments is $100 million. Investment opportunities 1 and 2 are mutually exclusive, and so are 3 and 4. Furthermore, neither 3 nor 4 can be undertaken unless one of the first two opportunities is undertaken. There are no such restrictions on investment opportunities 5 and 6. The objective is to select the combination of capital investments that will maximize the total estimated long-run profit (net present value). Formulate a BIP model for this problem. 2. Use the BIP branch-and bound algorithm to solve the following problem. Maximize Z 2 x 1 x 2 5 x 3 3 x 4 4 x 5 IELM3010'17 Tutorial 7 Nov. 29 & 30 Subject to 3 x1 2 x 2 7 x 3 5 x 4 4 x 5 6 x1 x 2 2 x 3 4 x 4 2 x 5 0 and x j is binary, for j=1, 2,..., 5. Optimal solution is (0, 0, 1, 1, 1), Z=6 3. A college student has 7 days remaining before final examinations begin in her four courses, and she wants to allocate this study time as effectively as possible. She needs at least 1 day on each course, and she likes to concentrate on just one course each day, so she wants to allocate 1,2,3 or 4 days to each course. Having recently taken an OR course, she decides to use dynamic programming to make these allocations to maximize the total grade points to be obtained from the four courses. She estimates that the alternative allocations for each course would yield the number of points shown in the following table: IELM3010'17 Tutorial 7 Estimated Grade Points Course 2 3 5 2 5 4 6 7 9 8 Study Days 1 3 5 6 7 1 2 3 4 Nov. 29 & 30 4 6 7 9 9 Let Xn be the number of study days allocated to course n, Let Pn(Xn) be the number of grade points expected when Xn days are spent on course n. Let Sn be the number of study days not yet allocated. P n ( X n ) f n* 1 ( S n X n ) Then f n* ( S n ) max 1 x n min( s n , 4 ) Number of stages = 4 S4 1 2 3 4 \\ X3 S3\\ \\ 2 3 4 5 \\ X2 S2\\ \\ 3 4 5 6 X4* * f 4 (S 4 ) 6 7 9 9 1 2 3 4 f 3 ( S 3 , X 3 ) P3 ( X 3 ) f 4 ( S 3 X 3 ) * 1 8 9 11 11 2 --10 11 13 3 ----13 14 ------14 8 10 13 14 * 13 15 18 19 2 --13 15 18 3 ----14 16 X * 3 4 f 2 ( S 2 , X 2 ) P2 ( X 2 ) f 3 ( S 2 X 2 ) 1 * f3 (S 3 ) * f 2 (S 2 ) 1 2 3 3, 4 X 4 ------17 13 15 18 19 1 1 1 1 * 2 IELM3010'17 \\ X1 S1\\ \\ 7 Tutorial 7 Nov. 29 & 30 * f1 (S 1 ) * X1 f 1 ( S 1 , X 1 ) P1 ( X 1 ) f 2 ( S 1 X 1 ) * 1 22 2 23 3 21 Optimal solution: (X1*, X2*, X3*, X4*) = (2, 1, 3, 1) The estimated total points to be obtained is 23. 4 20 23 2