90-722: Man Sci I, Final Exam Solution (AFTERNOON), Spring 2017Question #1:(15 points): Fill in the blanks below with the appropriate number or numbers corresponding to the following list of algorithms that we discussed for solving optimization problems. (Write neatly)1. Simplex2. Graphical approach to solving LPs3. Evolutionary4. Enumerating all extreme points (aka “vertices”)5. Branch & Bound6. Simulated Annealing7. GRG or “hill climbing”8. Greedy algorithm9. Brute force search over all possible values of the decision variablesWhich algorithm or algorithms …a) involve randomness? _____________b) is/are effective for smooth, convex NLPs but is/are prone to get stuck at local optima? _____________c) is/are most commonly applied to IPs? _____________d) suffer badly from a curse of dimensionality? _____________e) Produce sensitivity reports that specify shadow prices, reduced costs, and allowable increases and decreases? _____________Solution:)a) #3 & #6b) #7c) #5d) #4 & #9 at least. #5 also, to a lesser extent so fine to include it also. (It’s also fine to say #2. It’s not truly a curse of dimensionality, but certainly the graphical method doesfail for problems with more than 2 DVs.)e) #1For Questions #2 - #4: Recall that in HW #1, Problem #6, Howie’s friend Harold convinced Howie to commit to selling at least 45 “Super Bowl” kits that do-it-yourselfers (DIY) can assemble at home. I’ve pasted the spreadsheet from the optimization problem below.1Its algebraic formulation is:Letting the subscripts denote the hot tub types, i = 1, 2, 3Maximize 350 X1 + 375 X2 + 750 X3 s.t. X1 + X2 + 2 X3 ≤ 180 9 X1 + 6 X2 ≤ 1500 12 X1 + 16 X2 + 40 X3 ≤ 2400X3 ≥ 45Xi ≥ 0 for all i.Problems #2 - #3 ask you to write the algebraic formulation for various extensions of this problem. Only write down what is new or changed; do not re-write portions of the formulation that are unchanged. You are permitted to reuse the same variable names to mean different things in problems #2 and #3. Indeed, we’d encourage you to reuse the letter Y (perhaps with subscripts) to denote auxiliary binary variables in each problem. Question #2: (20 Points): Modify the formulation so that (a) Howie incurs a fixed cost of $2,500 for each model he produces, and (b) If he sells more than 20 Aqua Spas then he must sell at least 10 Hydroluxes.Solution:Introduce four auxiliary binary variables Yi, one for each model of hot tub (i=1,2,3) which indicate whether Howie will produce any of that model, Y4 indicating whether Howie sells more than 20 Aqua Spas, and a suitably large “Big M” constant denoted by M. a) Add the constraints for i=1,2,3 Xi ≤ M Yi and add to the objective function + 2,500 (Y1 + Y2 + Y3)b) Add the constraints (X1 – 25) ≤ M Y4 and Y2 ≥ 10 Y4.Question #3: (20 Points): [Start over with the 3-product Howie problem without the additions from Problem #2.] Making and selling one Aqua Spa produces 3 units of pollution, one Hydrolux procures 2 units of 2pollution, and one Super Bowl produces 1 unit of pollution. Howie wants to both maximize profit and minimize the amount of pollution produced. Suppose targets for these two goals are $50,000 and 180 units, respectively. Augment the formulation so Howie can minimize the maximum percentage deviation from these two targets.Solution: Use the usual notation for deviational variables and the maximum % deviation variable Q. The two target values are t1 = $50,000 and t2 = 180 Min Qs.t.d2+¿t 2d2−¿t 2;Q ≥¿d1+¿t 1;Q ≥ ¿d1−¿t 1;Q ≥¿Q ≥¿350 X1 + 375 X2 + 750 X3 +¿=t 1−¿−d1¿+d1¿3 X1 + 2 X2 + X3 +¿=t 2−¿−d2¿+d2¿+¿ ≥ 0−¿ ,d2¿+ ¿ , d2¿−¿ ,d1¿Q , d1¿in addition to all of the constraints from the original problem.Question #4: (10 Points): Sketch the shape of the efficient frontier that would be produced by solving the previous problemas a Goal Program. That would repeatedly minimize a weighted sum of the deviations (or percentage deviations), varying the weights between runs. On your graph, put attainment on Goals #1 and #2 on the horizontal and vertical axes, respectively. Label the axes with the actual goal (not “Goal #1” and “Goal #2”). Put a smiley face in the corner that would be ideal. Label one side of the frontier “infeasible” and the other side “suboptimal”. 3Solution: Since the horizontal axis is profit (large #’s are good) and the vertical axis is pollution (small numbers are good) the smiley face goes in the lower right. The efficient frontier will slope upward and at an increasing rate (convex). The “infeasible” label goes tothe frontier’s lower right. The “suboptimal” label goes to its upper left. PM Question #5: (32 Points): Consider a “linear city” meaning all people and facilities are strung out along one long straight road, so location is specified by a single number not a pair of numbers as with specifying a location with its longitude and latitude. This city begins at location“0” and stretches for 26 miles. So, for example, the location “10” means 10 miles along the road.There are 26 customers located at mile points 1, 2, 3, … 26. There are nine locations at which facilities could be built to serve these customers, with locations and costs as follows.Assume a customer can be considered “covered” if a facility is built 3 or fewer miles from the customer and the city wants to figure out how to cover all 26 customers at the lowest possible cost.a) What kind of optimization problem is this? (Be specific)b) How many decision variables are there and what do they mean or stand for?c) Write the algebraic expression for the constraints guaranteeing that customers #1, #8, and#15 are covered. (Do not use summation notation.)d) How many such constraints are there?e) What is the algebraic expression for the objective function?f) Suppose that for legal reasons a facility could only be built at site #4 if facilities are also built at both sites #1 and #7. Write the algebraic expression for the constraint enforcing that restriction.Solution:a) Set covering problem. (Just saying it is an IP is not sufficient)b) 9. Yj is a binary DV indicating whether a facility is built at site j (Yj = 1 for yes, = 0 for no)c) Y1 + Y2 ≥ 1; Y3 + Y4 ≥ 1; Y5 + Y6 + Y7 + Y8 ≥ 1.d) 26, one for each customer.4e) Min∑j=19∑ijCjYj, where C 1=$91, C 2=$ 60, etc .f) – 2