90-722: Management Science I: Optimization and Multi-CriteriaDecision Making Final Exam, Spring Term 2004Do not turn the page until you are told to do so. Write your answersbelow each question.Note how much each problem is worth and budget your time. Totalpoints possible: 100Section I: Short Answer Problems (50 points total)Q1: _________ out of 14 possible pointsQ2: _________ out of 8 possible pointsQ3: _________ out of 4 possible pointsQ4: _________ out of 4 possible pointsQ5: _________ out of 5 possible pointsQ6: _________ out of 5 possible pointsQ7: _________ out of 5 possible pointsQ8: _________ out of 5 possible pointsSection II: Formulation Problems (50 points total)Q9: _________ out of 15 possible pointsQ10: _________ out of 10 possible pointsQ11: _________ out of 15 possible pointsQ12: _________ out of 10 possible pointsName or SSN: ________________________________Mailbox or other way of returning exam: __________________________1Questions on Basic Concepts (35 points total)1) 14 points; 2 points for each answer.For each problem in Column 2 indicate which management science formulation or problem type (Column 4) could solve that problem by marking the appropriate letter from column 3 in the answer column (column 1).AnswerProblem Mgmt Sci Problem TypeFinding the least costly schedule for replacing an expensive piece of capital equipmenta Set covering problemDesigning a natural gas pipeline networkthat will connect every city in a regionb Edge covering problemDeciding where to establish polling stations to ensure that every voter is within 3 miles of a polling station c MSTDesigning a natural gas pipeline networkthat maximizes how much natural gas can be shipped from the Gulf Coast to the major metropolitan areas of the Midwest.d TSP (Traveling Salesperson Problem)Sequencing the appointments of a nurse providing prenatal home visitation services in order to minimize travel timee Steiner tree problemDesigning routes for parking enforcement officers (“meter maids”) to followf Max flow problemDesigning a LAN (local are network) g Shortest path problem2) (8 points; 2 per part)For the following alternatives-outcomes matrix:Attribute A Attribute B Attribute CAlternative #1 8 6 6Alternative #2 2 4 18Alternative #3 5 5 9Alternative #4 2 3 3a) Identify a (Pareto) dominated alternative and indicate which rowdominates it2b) Identify an alternative that is convex dominated (but not Paretodominated) and what combination of rows dominates it. 3c) Suppose the attributes were ranked in order of importance(Attribute #A is the most important, Attribute #B is the second mostimportant, etc.). Convert that rank information into cardinal attributeweights by the formula weight = 1/n, where n is the attribute rank.Given that scoring model, which alternative would be preferred andwhat is its composite score?d) Write on the spreadsheet below the formula(s) you would add tocompute the scoring model composite scores for the four alternatives?3) (4 points) Consider a multi-criteria decision-making problem withknown attribute weights but only rank information concerning thealternatives’ performance with respect to each attribute. Wediscussed two broad strategies for proceeding: pair-wise comparisonstrategies and positional rules. Each has a conspicuous weakness.What are those weaknesses?44) (4 points) What can you say about the optimal solution value for an integer programming (IP) maximization problem after solving its LP relaxation whena) The optimal solution value for the LP relaxation is 50 and the solution is all integer valued?b) The optimal solution value for the LP relaxation is 75 and the solution contains both integer-valued and non-integer elements?Questions 5 - 8 are worth 4 points each5) (5 points) Why it is useful that Solver gives you the option to “tolerate” a certain amount of sub-optimality when solving integer programming problems.6) (5 points) How many decision variables and how many constraints are there (in addition to non-negativity constraints) for a multi-period financial planning problem that involves 6 periods, 15 investment options, and the ability to leave excess funds in an interest-bearing fully liquid account (e.g., a money market account) in each period?57) (5 points) How many additional decision variables, non-negativity constraints, and other constraints do you need to add to an optimization problem when using goal programming (GP) to minimize the maximum percentage deviation with respect to four goals, rather than just optimizing a single objective? (Assume deviations in either direction from the goal are undesirable.)8) (5 points) Suppose you face a variation of a standard assignment problem. In particular, it is an unbalanced assignment problem with 5 demand nodes (tasks to be done) but only 3 source nodes (people whocan do a task). No one can do more than one task.a) Sketch the network diagram including a (single) pseudo-node that balances supply and demand; include supply and demand at each node. (You don’t have to draw every single arc as long as the general pattern of the arcs is clear.)b) If the objective function coefficients on the “real” arcs indicate the cost of assigning person i to task j, what would the objective function coefficients on the pseudo-arcs represent?6Formulation Problems (50 points total)9) 15 points total; 3 points for each partConsider the following capital budgeting problem, in which all numbersstand for thousands of dollars. Max 250 X1 + 150 X2 + 100 X3 + 325 X4s.t. 40 X1 + 45 X2 + 20 X3 + 25 X4 <= 90 (constraint forperiod #1)33 X1 + 27 X2 + 18 X3 + 15 X4 <= 140 (constraint forperiod #2)66 X1 + 37 X2 + 10 X3 + 35 X4 <= 120 (constraint forperiod #3)23 X1 + 22 X2 + 30 X3 + 28 X4 <= 85 (constraint forperiod #4)X1, X2, X3, X4 {0,1}a) What does the decision variable X3 represent?b) What is the benefit of selecting project #4?c) How much capital is available in period 3?d) Suppose that project #4 can only be undertaken if project #3 is selected. What constraint would you add to ensure the solution satisfied this condition? e) Suppose that for political reasons, either project #1 or both projects#3 and #4 must be selected. (It would be fine to have all three of these projects are selected.) What