University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

212

Pages:

3
Author:

Isabell Velasquez

Introduction to Optimization Problem 1 Formulating a Piece Wise Linear IP Formulate the following as an IP. Do not solve your IP: A petrochemical company wants to maximize profit on an item that sells for $0.30 per gallon. Suppose that increased temperature increases output according to the graph in the Figure 1 below. Assuming that production costs are directly proportional to temperature at $9.50 per degree centigrade, how many gallons of the item should be produced? Formulate as an IP. (The function has three linear pieces.) Gallons vs. Temperature C° 70 Temperature C° 60 50 40 30 20 10 0 0 200 400 600 800 1000 Gallons Figure 1. Problem 2 Radio Days A radio station schedules radio commercials in 60 second blocks. This hour, they have sold commercial time for commercials of 15, 16, 20, 25, 30, 35, 40, 45, 50, and 55 seconds. Formulate an integer program to that can be used to determine the minimum number of 60-second blocks of commericals that must be scheduled to fit in all the current hour’s commercials. Problem 3 IP Formulation with Logical Constraints As the leader of an oil-exploration drilling venture, you must determine the least-cost selection of 5 out of 10 possible sites. Label the sites S1, S2, . . ., S10, and the exploration costs associated with each as c1, c2, . . . , c10. Regional development restrictions are such that: i) Evaluating sites S2 and S7 will prevent you from exploring site S6 and S9. ii) Evaluating site S3 or S4 prevents you from assessing site S6. iii) Of the group S3, S6, S7, S8, at most two sites may be assessed. Formulate an integer program to determine the minimum-cost exploration scheme that satisfies these restrictions. Try to develop a model in which the only variables are x1, … , x10, where xj is 1 or 0 according as site j is explored or not. (For example, the constraint “Evaluating sites S2 and S7 will prevent you from exploring site S6” can be expressed as x2 + x6 + x7 ≤ 2 because the only binary solutions prohibited have x2 = x6 = x7 = 1.) Problem 4: What in the world does fathomed mean? 1. Define Fathomed 2. What are the three different cases in which a node is fathomed? 3. Solve the following problem While running a branch and bound algorithm, eventually one gets to the following node; Node 27. Corresponds to the problem minimize c1x6 + c2x7 + 15 subject to a1x6 + a2x6 ≥ 15 x6∈ {0,1}, x7 ∈ {0,1} The current incumbent has an objective value of 34. Note that the objective is to minimize. In the following, give example values for the parameters c1, c2, a1, and a2 that satisfy the conditions given (assume integer values for all parameters). a. Give conditions on the parameters so that node 27 of the tree is fathomed because of infeasibility. b. Give conditions on the parameters so that node 27 of the tree is fathomed because of integrality. c. Give conditions on the parameters so that node 27 of the tree is fathomed because of the bound. d. Give conditions of the parameters so that node 27 of the tree is not fathomed. Problem 5 Branch and Bound Use branch-and-bound to solve the following IP: max z = 4x1 + 5x2 s.t. 3x1 + 2x2 ≤ 10 x1 + 4x2 ≤ 11 3x1 + 3x2 ≤ 13 x1, x2 ≥ 0; x1, x2 integer Problem 6 Branch and Bound Use branch-and-bound to solve the following IP: max z = 4x1 + 3x2 s.t. 4x1 + 9x2 ≤ 26 8x1 + 5x2 ≤ 17 x1, x2 ≥ 0; x1, x2 integer