90-722: Man Sci I, Final Exam (MORNING), Spring 2017Do not turn the page until you are told to do so. Write your answers below each question.Note how much each problem is worth and budget your time. Total points possible: 129Name: ______________________________Q1: _________ out of 15 possible pointsQ2: _________ out of 20 possible pointsQ3: _________ out of 20 possible pointsQ4: _________ out of 10 possible pointsQ5: _________ out of 36 possible pointsQ6: _________ out of 28 possible pointsTotal Possible Points: 1291Question #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 the number(s) 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? _____________2For 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.Its 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 ≤ 37510 X1 + 20 X2 + 6 X3 + 11 X4 ≤ 4000 X1 + 2 X3 + 4 X4 ≤ 1000 Xi ≥ 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. 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.3Question #3: (20 Points): Starting back with the original problem, not including the modifications made in Question #2, suppose B2B 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 deviationfrom these two targets.4Question #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”. 5Question #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 customer lives 332 miles east and 393 miles north of that corner or “origin”.Likewise, Cells E2:E3 indicate that the first of the nine candidate locations where a facility couldbe built is 25 miles east and 84 miles north of that southwest corner. (Screen shot on facing page. 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.67Question #6: (28 Points): I have pasted on the facing page the node-arc incidence representationof a transshipment problem. (It happens to be the one we solved in recitation.)a) (4 points) What does the 17 in Cell F15 mean?b) (4 points) Is this problem balanced? Give a yes/no answer and a very brief explanation for your answer.c) (4 points) Write the algebraic expression for the flow balance constraint on node #3.d) (8 points) How would you modify this spreadsheet to determine what is the shortest path from node #2 to node #7? e) (8 points) How would you modify this spreadsheet if each arc only delivered 95% as much flow at its end as entered that