90-722: Management Science I: Optimization and Multi-CriteriaDecision Making Final Exam Solution, Spring Term 2005Questions 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).Answer Problem Mgmt Sci Problem TypegFinding the least costly schedule for replacing an expensive piece of capital equipmenta Set covering problemeDesigning a natural gas pipeline network that will connect every city in a regionb Edge covering problemaDeciding where to establish polling stations to ensure that every voter is within 3 miles of a polling station c MSTfDesigning a natural gas pipeline network that 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)dSequencing the appointments of a nurse providing prenatal home visitation services in order to minimize travel timee Steiner tree problembDesigning routes for parking enforcement officers (“meter maids”) to followf Max flow problemcDesigning 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 31a) Identify a (Pareto) dominated alternative and indicate which rowdominates itAlternative #4 is dominated by Alternative #3 (and also by #1and #2)b) Identify an alternative that is convex dominated (but not Paretodominated) and what combination of rows dominates it. Alternative #3 is convex dominated by an equally weightedcombination of Alternatives #1 and #2.c) 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?Alternative #1 is best with a composite score of 8 * 1 + 6 *(1/2) + 6 * (1/3) = 13. (Alternative #2’s score of 2 * 1 + 4 *(1/2) + 18 * (1/3) = 10 is lower.)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?Pair-wise comparison strategies can yield differentrecommendations depending on the sequence in which thecomparisons are made (unless there is a Condorcet winner).Positional rules are not invariant with respect to irrelevantalternatives.4) (4 points) What can you say about the optimal solution value for an integer programming (IP) maximization problem after solving its LP relaxation when2a) The optimal solution value for the LP relaxation is 50 and the solution is all integer valued?Z*IP = 50b) The optimal solution value for the LP relaxation is 75 and the solution contains both integer-valued and non-integer elements?Z*IP  75Questions 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.The running time of Excel’s Branch & Bound algorithm for solving IP is greatly improved when one only demands that solution values be within a certain percentage of the optimum solution value. This “tolerance” allows more branches to be “bounded” (cut-off) more quickly, eliminating them further consideration (and, hence further computations). It is not uncommon when facing NP-hard problems to settle for a good solution produced by a heuristic, rather than insisting on an optimal solution, particularly when the performance of that heuristic can be bounded as in this case.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?Seven balance of flow constraints (one for today and one for each of the 6 future periods).There are 21 decision variables, one for each of the 15 investment options plus one for each of the six one-period longarcs representing money kept in the liquid account. One couldalso say 22 if the objective function value (Z) is included.(Partial credit was given for answers that presumed each of the 15 investment options was available in each of the 6 periods, leading to 90 decision variables of that type.)7) (5 points) How many additional decision variables, non-negativity constraints, and other constraints do you need to add to an 3optimization 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.)One had four more soft constraints plus eight constraints of the form Q greater than or equal to a percentage deviation, fora total of 12 new constraints.There are 8 more deviational decision variables (one undershoot and one overshoot for each of the four soft constraints, 2 * 4 = 8) plus the Q variable, for a total of 9.There are eight more non-negativity constraints (one for each of the deviational variables).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