90-722: Man Sci I, Final Exam (MORNING), Spring 2019Do 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: 100Name: _________________________________ Section: __________Q1: _________ out of 12 possible pointsQ2: _________ out of 18 possible pointsQ3: _________ out of 12 possible pointsQ4: _________ out of 18 possible pointsQ5: _________ out of 18 possible pointsQ6: _________ out of 6 possible pointsQ7: _________ out of 6 possible pointsQ8: _________ out of 10 possible pointsTotal Possible Points: 1001Question #1: (12 points). Provide short, clear, and neatly written answers to these questions. Correctideas poorly communicated will not receive credit. Think before you write. a) Can the optimal solution value to an integer programming problem be non-integer? Explain whyor why not.b) If you use a dummy supply node to balance a transportation problem, and label it as node 0, whatdoes the variable X07 stand for?c) How many decision variables and constraints (besides non-negativity) in a standard assignmentproblem for which there are 10 individuals being assigned to jobs? d) What is the sign of the reduced cost of a decision variable that is at a binding upper bound in anLP maximization problem?e) In the top half of Solver’s LP sensitivity report, what is it that can change within the rangespecified by the allowable increase and decrease? That is, what variable, parameter, or conceptdoes that allowable range apply to?f) What do the two decision variables in an EOQ model stand for? (Hint: We denoted them by Qand x.)2Question #2: (18 Points): For any 6 or the 9 statements below, give the name of the algorithm we discussed in class that best fits the concept. (Write neatly) a) Works well for the traveling salesman problem.b) Has a magical ability to produce integer valued solutions on certain problems even if you don’t explicitly ask it to.c) Solves LP relaxations as one part of its overall solution process.d) Can work well on nonlinear optimization problems even if their response surface is jagged, with lots of little bumps. e) Works well on convex nonlinear optimization problems f) Works well on nonlinear optimization problems that have a moderate number of hills each of which is smooth.g) Yields sensitivity reports with shadow prices and reduced costs.h) Is extremely fast for solving max flow problem that have been augmented by a pseudo return arc.i) Makes extensive use of randomness.3Question #3: (12 Points): Consider the branch and bound tree depicted below.a) Is the problem a maximization or minimization problem?b) Which subproblem(s) cannot contain the optimal solution?c) Which additional subproblem(s) could be bounded if the tolerance parameter were set at 10%?d) Suppose the solution to subproblem #6’s LP relaxation had X3* = 7.5. What constraints would you add to form subproblems #9 and #10 branching off from subproblem #6?4Background information for Questions #4 and #5:The midterm asked questions based on an augmented version of Howie’s Hot Tub problem in which he can make two additional models, the deluxe Vortices and the cut rate Sink Holes. The screen shot for that LP is shown below, after solving to optimality.Its algebraic formulation isMax Z = 350 X1 + 300 X2 + 625 X3 + 99 X4s.t. X1 + X2 + 2 X3 + X4 ≤ 2009 X1 + 6 X2 + 12 X3 + X4 ≤ 156612 X1 + 16 X2 + 40 X3 + X4 ≤ 2880Xi ≥ 0 for i=1,2,3,4Question #4: (18 Points). Provide the algebraic formulation, including definitions of relevant decision variables and parameters, that would augment the formulation above if: - Howie wanted to be sure he made at least two types of hot tubs, - If he makes any of a model he must make at least 50 of that model, - There are fixed costs of $15,000 if he produces any Aqua Spas, $12,000 if he produces any Hydroluxes, $9,000 if he produces any Vortices, and $1,000 if he produces any Sink Holes, and- He can only produce Hydroluxes if he makes Aqua Spas. 5Question #5: (18 Points): Again start with the augmented Howie problem from the midterm (i.e., without the things you added for the previous problem). Explain how you would extend that algebraic formulation if Howie cared about both maximizing profit and minimizing labor hours used, with target values of $66,000 and 1200 respectively. In particular, suppose Howie wanted to minimize the maximum weighted percent deviation, for unfavorable deviations, placing twice as much weight on the profit goal as on the labor hours goal. Use the standard notation from class, write out each constraint explicitly (not using summation/index notation), and use specific numbers for the targets, not ti’s. 6Question #6: (6 Points): Show all changes you would make to the options part of the Solver dialog box below if you were solving an integer programming problem and wanted to allow solutions that were within 5% of optimality and did not want the computer to run for more than 20 seconds. 7Question #7: (6 points). The graph below shows an efficient frontier created with goal programming.Goal #2 is a minimization goal. Indicate by circling whether Goals #1 and #3 are maximization orminimization.Goal #1: Maximization MinimizationGoal #3: Maximization Minimization8Question #8: (10 points). Sketch total cost as a function of volume shipped, out to 10 units shipped, if thealgebraic representation of that cost relation is:Cost = 5 X1 + 2 X2 + 10 Y14 Y2 ≤ X1 ≤ 1000 Y1X2 ≤ 1000 Y2where X1 = # of units shipped at an initial higher variable cost per unit and X2 = # of units shipped at alower cost available for amounts beyond a certain threshold quantity. Label the origin and the points at both ends of the cost curve for positive quantities, as well as any kinksin between when the slope of the curve changes. E.g., if the cost of shipping 17 were $3 you’d write (17,$3) next to that point.