90-722: Mgmt Science I, Afternoon 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) What is the role of the 2nd objective when addressing multiple objectives via lexicographicpreferences?b) If you use a dummy arc to convert a max flow problem to a transshipment problem, what shouldyou tell Excel is the demand at the nodes at either end of that arc?c) How many decision variables and constraints (besides non-negativity) are there in a standardmake vs. buy problem with 4 products and 3 resource constraints? d) What is the sign of the shadow price on a binding greater than or equal to constraint for an LPminimization problem? e) In the bottom 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 is nonlinear in the Chapter 8 portfolio optimization model? Solution:a) It breaks ties when there are alternative optimal solutions with respect to the first or pimarygoal.b) 0 for bothc) 8 variables and 7 constraints (4 demand constraints and 3 resource constraints)d) Non-negative. Increasing the RHS of a greater than or equal to constraint makes it morestringent, so the objective function value may get worse and in a minimization problem that isincreasing. e) Right hand sides of constraintsf) The measure of risk (or more specifically the variance or standard deviation of the return) Question #2: (18 Points):What algorithm or method that we discussed in class would be best for solving a:Capital budgeting problem: ____Branch & Bound_______________Traveling Salesman Problem (TSP): ___Evolutionary/Genetic_______________________Equipment Replacement Problem: _(Transportation/Transshipment version of) Simplex___Make vs. Buy problems as discussed in Chapter 3: ____ Simplex_____________Convex nonlinear optimization problem: ____GRG__________________General Nonlinear optimization with two decision variables: _____2D Data Table__________1Question #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) What are the tightest bounds you can provide on the optimal solution value to the original problem?Minimization#8#5 & #6110 ≤ ZIP* ≤ 150Question #4: (20 points): Suppose you need to acquire 6,000 units of something (e.g., hot tubs) from amixture of ten suppliers (e.g., “factories”). Each source has its own fixed and variable cost. E.g., if youordered 100 units from Supplier #1 the cost would be $900 + 28 * $100. Suppliers have limitedcapacities and none will accept an order of fewer than 100 units.Formulate an integer linear program to minimize the cost of obtaining the 6,000 items subject to twoconstraints:#1: At least 2,000 are obtained from preferred suppliers#2: At least seven sources are used (in order to avoid being too dependent on a few suppliers)You are strongly encouraged to use summation notation and to use the following parameter definitions(which you do not need to rewrite)2FCi = fixed cost of ordering any from supplier i,VCi = variable cost per item ordered from supplier i, andCi = maximum number that can be ordered from supplier i,Solution:Let Xi = the amount obtained from supplier i for i = 1, 2, 3, …, 10.Let Yi be binary variables indicating whether any is obtained from supplier i.Min Z = ∑i=110(FCiYi+VCiXi)s.t. ∑i=110Xi≥ 6,000∑i=13Xi≥ 2,000∑i=110Yi≥7For all I, 100 Yi ≤ Xi ≤ Ci Yi Question #5: (17 points) Explain how you would extend that algebraic formulation if you have three goals:#1: Minimize the cost of obtaining the 6,000 units.#2: Obtain 3,150 units from the first three suppliers who are preferred.#3: Source from all ten suppliers to diversify sources and associated risks. In particular, write the algebraic expressions for what you would add to create a linear integer goalprogram that minimizes the maximum undesirable percent deviation from these targets, using softconstraints with both undershoot and overshoot deviational variables. You may use summation notationto sum over suppliers but not for the goals. Write numerical values for targets, rather than writing ti, forthe goals for which target values are given. 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, with 1 being the cost goal, 2 being the local production goal, and 3 being the diversity of suppliers goal.Min Qs.t.d3−¿10d2−¿3150; Q≥ ¿d1+¿t1;Q ≥ ¿Q≥ ¿3+¿=t1−¿−d1¿∑i=110(FCiYi+VCiXi)+d1¿X1 + X2 + X3 +¿=3,150−¿−d2¿+d2¿∑i=110Yi +¿=10−¿−d3¿+d3¿+¿ ≥ 0−¿ ,d3¿+¿, d3¿−¿ ,d2¿+¿, d2¿−¿ ,d1¿Q , d1¿in addition to all of the constraints from the original problem.Question #6: (11 Points): 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. Its algebraic formulation was:Max 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,4I solved an extended version of that problem in which: (a) Howie must make at least two types ofHot Tubs, (b) if he makes any of a model he must make at least 50 of that model, (c) 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. The screen shot isshown below, after solving to optimality.4Show how the Solver dialog box was filled in to solve this problem, including every entry or change that needed to be made. Solution: (dollar signs not necessary in Solver dialog box):5Question #7: (10 points) Suppose someone were optimizing the food they ordered at a restaurant suchas Wendy’s with the twin goals of minimizing cost and minimizing fat in the food purchased, whilemeeting other