**Unformatted text preview:**

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 5 possible pointsQ2: _________ out of 5 possible pointsQ3: _________ out of 5 possible pointsQ4: _________ out of 5 possible pointsQ5: _________ out of 5 possible pointsQ6: _________ out of 5 possible pointsQ7: _________ out of 5 possible pointsQ8: _________ out of 5 possible pointsQ9: _________ out of 5 possible pointsQ10: _________ out of 5 possible pointsSection II: Formulation Problems (50 points total)Q11: _________ out of 15 possible pointsQ12: _________ out of 15 possible pointsQ13: _________ out of 20 possible pointsName or SSN: ________________________________1Mailbox or other way of returning exam: __________________________2Short Answer Problems (25 points total; 5 points per question)Optimization problems involve choices (coded as decision variables) and optimizing an objective subject to constraints (both written as functions of the decision variables).1) What are the three defining characteristics of a linear programming (LP) optimization problem?2) In what sense does integer programming (IP) generalize LP?3) Which of the following problems related to networks are or can easily be transformed into a transshipment problems and, hence, are types of LP’s?Yes / No Assignment ProblemYes / No Steiner Tree ProblemYes / No Shortest Path ProblemYes / No Transportation ProblemYes / No Traveling Salesman Problem4) What capability does goal programming (GP) offer that LP, IP, and network optimization as described in chapters 3, 5, and 6 do not?35) We discussed the concept of computational complexity in class. Sketch a simple graph that concisely conveys the distinction between a problem that is NP-complete and one that is not NP-complete (one curve per problem type). Be sure to label both axes.6) When solving IP’s with Excel’s Solver, one of the options was the “tolerance”.a) Suppose you solved the same moderately large IP twice, both times using the same initial values. (I.e., you re-set the initial conditions after solving it the first time, so both times you started from the same place). Suppose the first time the tolerance parameter = 5%, and the second time tolerance = 10%. Which time would you expect Solver to report its answer more quickly?b) Suppose in an IP maximization problem with tolerance = 10% Solver found a solution whose solution value was 100. Letting Z* denote the optimal solution value for this IP, what can you say about Z*?7) How many constraints and how many decision variables are there ina classic, balanced transportation problem with 8 sources and 4 sinks? 4Problems #8 - #10 refer to this network.8) What is the value of the optimal solution to the Chinese Postman Problem (CPP) for this graph? (Note: the sum of the lengths of the arcs in the graph is 56.)9) How long is the minimal spanning tree (MST) for this network? 10) Suppose you wanted to find the maximum possible flow from node#1 to node #7 by solving a transshipment problem. Assume that the arc labels represent arc flow capacities and the arcs are directional (even though they do not have arrows). Note the network has 7 nodesand 11 arcs. How many decision variables and constraints are there inthis transshipment problem, including those representing any pseudo arcs and/or pseudo nodes you might need to add? 52738698313154762456Section II: Formulation Problems (50 points total)Question #11 (15 points)The County Health Department has $5M to allocate across three programs for reducing HIV/AIDS among injection drug users (IDUs): (1)drug treatment, (2) prevention (education) programs, and (3) CHOW’s (Community Health Outreach Workers). (CHOW’s teach drug users how to clean their injection equipment.) The objective is to avert as many HIV/AIDS infections as possible, and evaluation studies report the following cost-effectiveness results: Treatment averts 250 HIV infections per million dollarsCHOW’s avert 200 HIV infections per million dollarsPrevention averts 100 HIV infections per million dollarsHowever, federal block grant funding requirements mandate that spending on drug treatment and prevention be balanced, with neither getting less than 40% of total spending on treatment and prevention. (CHOW funding is not part of this constraint.) In addition, to avoid depending too heavily on any one intervention, the Health Department feels it must to allocate at least $500,000 to each intervention.Formulate this problem as a linear program (LP).7Question #12 (15 Points; Extension of Question #6)Suppose the Health Department in Question #11 also wants to reduce Hepatitis C (HCV) among IDUs. Evaluation studies find that preventionis relatively more effective at HCV control than HIV control because HCV is more highly infectious and even occasional treatment lapses can lead to infection. In particular, Treatment averts 100 HCV infections per million dollarsCHOW’s avert 200 HCV infections per million dollarsPrevention averts 400 HCV infections per million dollars(Note: HIV is the virus that causes AIDS; HCV refers to hepatitis.)(Note #2: There are still only three interventions. Each intervention generates two benefits, a reduction in HIV infections and a reduction inHCV infections.)Suppose the County Executive has announced that the $5M in funding will be used to avert 1,000 HIV infections and 1,000 HCV infections. You realize both goals cannot be met simultaneously. Formulate a goal program (GP) whose objective is to minimize a weighted sum of deviations from these targets. (This GP can be used to generate various spending allocation alternatives for the County Executive to review.) Remember to carry forward the hard constraints from Question #11.8Question #13 (20 points)A Hospital is deciding which capital improvement projects to pursue with its limited capital budget of $25 million. The medical director in consultation with an advisory committee has rated the importance of each, and the Hospital CEO’s basic objective is to fund as many of the most important projects as possible, more specifically to maximize thesum of importance ratings of

View Full Document