90-722: Mgmt Science I, Morning Final Exam Solution, Spring 2019Question #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.)Solution:a) Yes. IP only requires decision variables to be integral, but the objective function coefficientsneed not be.b) The extent to which customer #7’s demand is shortedc) 100 variables and 20 constraintsd) Non-negative. If it were negative you could improve the objective function by reducing thevalue of that decision variable, which is possible if it is bumped up against an upper bound(but, implicitly, not a lower bound). e) Objective function coefficientsf) Q = size of an order. x = amount by which backorders are accumulated before the next orderarrivesQuestion #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. 1e) 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.Solution:a) Genetic/evolutionary algorithmsb) Network/transportation/transshipment simplex algorithm (just saying simplex is also fine)c) Branch and boundd) Simulated annealinge) GRG/hill climbing/best feasible gradient searchf) Multistart forms of GRG/hill climbing/best feasible gradient search g) Simplexh) Network/transportation/transshipment simplex algorithm (just saying simplex is also fine)i) Simulated annealing or Genetic/evolutionary algorithmsQuestion #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?Maximization#8#4 & #5X3* ≤ 7 and X3* ≥ 8, respectively.2Background 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, andHe can only produce Hydroluxes if he makes Aqua Spas. Solution:Introduce binary variables Yi that are 1 if Howie produces any of model i and 0 otherwise. Change the objective function to Max Z = 350 X1 + 300 X2 + 625 X3 + 99 X4  $15,000 Y1  $12,000 Y2 $9,000 Y3  $1,000 Y4Add the constraints 50 Yi ≤ Xi ≤ M Yi for i=1,2,3,4 and some suitably large big M such asM=200Add the constraints Y1 + Y2 + Y3 + Y4 ≥ 2 and Y2 ≤ Y1.Question #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 3wanted 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. Solution: Use the usual notation for deviational variables and the maximum % deviation variable Q, meaning di- is the undershoot on goal i and di+ is the corresponding overshoot. Letthe two target values for the two goals be denoted t1 and t2, with 1 being the profit goal and 2 being the labor hours goal.Min Qs.t.d2+¿1200d1−¿66,000;Q≥ ¿Q ≥2 ¿350 X1 + 300 X2 + 625 X3 + 99 X4 +¿=$ 66,000−¿−d1¿+d1¿9 X1 + 6 X2 + 12 X3 + X4 +¿=1200−¿−d2¿+ d2¿+¿ ≥ 0−¿ ,d2¿+ ¿ , d2¿−¿ ,d1¿Q , d1¿in addition to all of the constraints from the original problem.Question #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