90-722: Management Science I: Optimization and Multi-CriteriaDecision Making Final Exam Solution, Spring Term 2004Short 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?Objective function is a linear function of the decision variables.Constraints are a linear function of the decision variables.Decision variables are all continuous.2) In what sense does integer programming (IP) generalize LP?In an IP, it is allowed to have discrete (e.g., binary) decision variables, and continuous decision variables are also allowed. In an LP, only continuous decision variables are permitted.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?GP allows one to consider multiple goals or objectives simultaneously.5) 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.Horizontal axis is size of the problem (e.g., number of nodes and/or arcs in a network problem; number of constraints and/or decision variables in a more general type of optimization problem). Vertical 1axis is how long it takes an algorithm to find the optimal solution. For an NP-complete problem, the best known algorithm’s running time grows faster than a polynomial (e.g., exponentially) in the size of the problem. For problems that are not NP-complete, a polynomial time algorithm exists.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?The greater the tolerance, the easier it is for the branch and bound algorithm to bound branches and so the faster one expects Solver to return a solution.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*?Z* must be at least 100 and not more than 110.7) How many constraints and how many decision variables are there ina classic, balanced transportation problem with 8 sources and 4 sinks? 32 decision variables and 12 constraints.Problems #8 - #10 refer to this network.28) 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.)There are only two odd-degree nodes and they are separated by an arc of length 1, so the minimal matching is trivial (just add that arc) and the length of an optimal tour is 56+1 = 57.9) How long is the minimal spanning tree (MST) for this network? 1910) 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? Add a pseudo arc from node #7 back to Node #1, so would have 11+1=12 decision variables and 7 constraints. Section 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 dollars3273869831315476245However, 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).Let T, P, and C be non-negative decision variables indicating how much is spent on treatment, prevention, and CHOWs, respectively, in millions. Max 250 T + 200 C + 100 P s.t.T + C + P = 5T  0.4 (T + P) (or, equivalently, 0.6 T – 0.4 P 0)P  0.4 (T + P) (or, equivalently, 0.6 P – 0.4 T 0)T  0.5C  0.5P  0.5(Could but literally need not add three non-negativity constraints, one for each decision variable.)Question #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