90-722: Man Sci I, Final Exam Solution (MORNING), 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) keep track of multiple solutions at each stage? _____________b) is/are the best for solving large LPs? _____________c) is/are used for NLPs with 10+ DVs? _____________d) is/are not practical for professional work? _____________e) can usefully be implemented with a data table for 2 variable NLPs? _____________Solution:a) #3b) #1c) #3, #6, #7d) #2e) #9For Questions #2 - #4: Recall the Backpacks to Beyond (B2B) problems you worked for HW. Here is the spreadsheet after the optimization in HW #2, Problem #10.1Its algebraic formulation is:Letting the subscripts denote the backpack types, i = 1, 2, 3, 4Maximize 30 X1 + 12 X2 + 50 X3 + 80 X4 s.t.X1 + X2 + X3 + X4 ≤ 375 10 X1 + 20 X2 + 6 X3 + 11 X4 ≤ 4000 X1 + 2 X3 + 4 X4 ≤ 1000Xi ≥ 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 different of these problems. Indeed, we’d encourage you to reuse the letter Y (perhaps with subscripts) to denote auxiliary binary variables in each problem part. Question #2: (20 Points): Add constraints that ensure that (a) if B2B wants to produce any of a particular model of backpack, it will produce at least 30 of them, and (b) B2B produces at least two types of backpacks.Solution:Introduce four auxiliary binary variables Yi, one for each model of backpack, which indicate whether B2B will produce any of that model and a suitably large “Big M” constant denoted byM. Add the constraintsa) For all i, Xi ≤ M Yib) For all i, Xi ≥ 30 Yic) Y1 + Y2 + Y3 + Y4 ≥ 2Question #3: (20 Points): 2B2B wants to both maximize profit and maximize the amount of labor used (since labor used = jobs provided). Suppose its targets for these two goals are $22,000 and 3900 hours, respectively.Augment the formulation so B2B 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 = $22,000 and t2 = 3,900 Min Qs.t.d2+¿t 2d2−¿t 2;Q ≥¿d1+¿t 1;Q ≥ ¿d1−¿t 1;Q ≥¿Q ≥¿30 X1 + 12 X2 + 50 X3 + 80 X4 +¿=t 1−¿−d1¿+d1¿10 X1 + 20 X2 + 6 X3 + 11 X4 +¿=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 laboruse (big numbers are good again) the smiley face goes in the upper right. The efficient frontier will slope downward and at an increasing rate (concave). The “infeasible” label goes to the frontier’s upper right. The “suboptimal” label goes to its lower left. 4Question #5: (36 Points): I used Solver to find the lowest cost set of facility locations that could “cover” 26 customers who are scattered around on a 500 X 500 grid, where a customer is considered covered if a facility is built within 150 miles (according to a Euclidean distance metric or, less formally, “as the Crow flies”). Locations are measured as distances to the east andnorth of the southwest corner, whose location is defined as (0,0). For example, Cells C8:D8 indicate that the first of the 26 customers lives 332 miles east and 393 miles north of that southwest corner or “origin”. Likewise, Cells E2:E3 indicate that the first of the nine candidate locations where a facility could be built is 25 miles east and 84 miles north of that southwest corner. (The accompanying map may help you visualize the situation.)a) What kind of optimization problem is this? (Be specific)b) How many facilities would be built following the solution indicated in the screen shot?c) How many decision variables are there and what do they mean or stand for?d) Write the algebraic expression for the constraints guaranteeing that customers #1, #8, and#15 are covered. (Do not use summation notation.)e) How many such constraints are there?f) What is the Excel formula behind Cell N9?g) Suppose that for legal reasons a facility could only be built at site #4 if one is also built atsite #7. Write the algebraic expression for the constraint enforcing that restriction.h) What would you change in the spreadsheet if you wanted to make sure there were two facilities built within 150 miles of Customer #12? i) Fill in the Solver dialog box as I did to solve this problem.56Solution:a) Set covering problem. (Just saying it is an IP is not sufficient)b) 6c) 9. Yj is a binary DV indicating whether a facility is built at site j (Yj = 1 for yes, = 0 for no)d) Y2 + Y6 ≥ 1; Y8 + Y9 ≥ 1; Y1 ≥ 1.e) 26, one for each customer.f) =SUMPRODUCT(E9:M9,E$5:M$5)g) – Y4 + Y7 ≥ 0h) Change Cell O19 from a 1 to a 2. [BAD QUESTION. NOT GRADED. I HADN’T NOTICED THERE WAS ONLY ONE ‘1’ IN THE ROW OF CONSTANTS FOR ATOM 12]i) Question #5: (28 Points): I have pasted below the node-arc incidence representation of a transshipment problem. (It happens to be the one we solved in recitation.)7a) (4 points) What does the 17 in Cell F15 mean?b) (4 points) Is this problem balanced? Give a