DSCI 3870: Management Science Exam # 3 SAMPLE Date: 12/15/2009 Time: 2 hours (1:30 p.m. – 3:30 p.m.) Name: Student ID #: Please read this carefully This sample exam consists of 44 (T/F and multiple-choice) questions. (Your final exam will likely have between 40-44 questions). Please answer on the scantron sheet provided. I will not be responsible for lost sheets that are turned in unstapled. Please note that you have to enter you name and Student ID number in the above area. Failure to do so will result in a grade of zero on the part of the exam in which the relevant details have not been entered. On the exam the following acronyms may have been used: LP - Linear Program/Programming IP – Integer Program/Programming ILP – Integer Linear Program/Programming (used synonymously with IP) NLP – Non-linear Program/ Programming MILP – Mixed Integer Linear Program/ Programming QP – Quadratic Program/Programming An “(s)” appended to these acronyms denotes the plural. This is an open book exam. Be sure to allocate your time wisely. Best of luck!! 1. In a transshipment problem, shipments a. cannot occur between two origin nodes. b. cannot occur between an origin node and a destination node. c. cannot occur between a transshipment node and a destination node. d. can occur between any two nodes.* 2. Consider a shortest route problem in which a bank courier must travel between branches and the main operations center. When represented with a network, a. the branches are the arcs and the operations center is the node. b. the branches are the nodes and the operations center is the source. c. the branches and the operations center are all nodes and the streets are the arcs.* d. the branches are the network and the operations center is the node. 3. Let x1 , x2 , and x3 be 0-1 binary variables whose values indicate whether the projects are not done (0) or are done (1). Which constraint below indicates that at least two of the projects must be done? a. x1 + x2 + x3 ≥ 2* b. x1 + x2 + x3 ≤ 2 c. x1 + x2 + x3 = 2 d. x1− x2 = 0 4. Modeling a fixed cost problem as an integer linear program requires a. adding the fixed costs to the corresponding variable costs in the objective function. b. using 0-1 variables.* c. using multiple-choice constraints. d. using LP relaxation. 5. The maximal flow problem can be formulated as a capacitated transshipment problem. a. True* b. False 6. The shortest-route problem is a special case of the transshipment problem. a. True* b. False 7. Is it possible that an LP relaxation of the original IP yields a feasible region and an optimal LP solution, but the IP itself is infeasible and therefore has no solution? a. Yes* b. No c. The question compares “apples and oranges” and can’t be answered. 8. If x1 + x2 ≤ 500 y1 and y1 is binary 0-1, then if y1 is 0, x1 and x2 will be 0. a. True* b. False 9 . If the optimal solution to the LP relaxation problem is integer, it is the optimal solution to the integer linear program. a. True* b. False 10. The interpretation of the dual price for nonlinear programming models is different than that for linear programming models. a. True b. False* 11. A function is quadratic if its nonlinear terms have a power of 4. a. True b. False* 12. In the LP formulation of a maximal flow problem, a conservation-of-flow constraint ensures that an arc's flow capacity is not exceeded. a. True b. False* The next two questions refer to the following case: I recently decided to go on a camping trip and bought a nice tent and backpack from REI in Dallas. I wanted to carry a number of items in my backpack, but its weight limit was 14 lbs. The table below lists the items by their weight (in lbs.) and their perceived benefit; with a larger number representing more benefit than a smaller one. Item 1 2 3 4 Description Ultrabrite Flashlight Energy snack Map Camera Let xi = 1 if I decide to pack item i, 0 if not where, i = 1,2,3,4 13. The appropriate model formulation is given as: a. Min. 25 x1 + 20 x2 + 8 x3 + 12 x4 St. 12x1 + 5x2 + 3x3 + 7x4 ≤ 14 b. Max. 25 x1 + 20 x2 + 8 x3 + 12 x4 * St. 12x1 + 5x2 + 3x3 + 7x4 ≤ 14 c. Min. 12x1 + 5x2 + 3x3 + 7x4 St. 25 x1 + 20 x2 + 8 x3 + 12 x4 ≤ 65 d. Max. 25/12 x1 + 20/5 x2 + 8/3 x3 + 12/7 x4 St. 12x1 + 5x2 + 3x3 + 7x4 ≤ 27 e. Min. 12/25 x1 + 5/20 x2 + 3/8 x3 + 7/12 x4 St. 12x1 + 5x2 + 3x3 + 7x4 ≤ 14 14. The above problem is popularly referred to as: a. The backpack problem b. The utility maximization problem c. The binary knapsack problem* d. The camping problem e. The binary weight to benefit problem. Weight 12 5 3 7 Benefit 25 20 8 12 The next three questions are based on the following case: Consider the problem faced by a summer camp recreation director who is trying to choose activities for a rainy day. Information about possible choices is given in the table below. (Popularity rating numbers indicate that higher is better). Category Activity Art 1 − Painting 2 − Drawing 3 − Nature craft 4 − Rhythm band 5 − Relay races 6 − Basketball 7 − Internet 8 − Creative writing 9 − Games Music Sports Computer Time (minutes) 30 20 30 20 45 60 45 30 40 Popularity with Campers 4 5 3 5 2 1 1 4 1 Popularity with Counselors 2 2 1 5 1 3 1 3 2 Let xi = 1 if activity i is chosen, 0 if not, for i = 1, ... , 9 15. The most appropriate objective function is: a. Max. 4x1 + 5x2 + 3x3 + 5x4 + 2x5 + 1x6 + 1x7 + 4x8 + 1x9* b. Min. 4x1 + 5x2 + 3x3 + 5x4 + 2x5 + 1x6 + 1x7 + 4x8 + 1x9 c. Max. 2x1 + 2x2 + 1x3 + 5x4 + 1x5 + 3x6 + 1x7 + 3x8 + 2x9 d. Min. 2x1 + 2x2 + 1x3 + 5x4 + 1x5 + 3x6 + 1x7 + 3x8 + 2x9 16. Which constraint captures the restriction that no more than two computer activities can be done? a. x7 + x8 + x9 = 2 b. x7 + x8 + x9 > 2 c. x7 + x8 + x9 ≤ 2* d. x8 + x7 + x9< 2 17. That the overall counselor popularity rating should be no higher than 10 is captured by the constraint: a. 2x1 + 2x2 + 1x3 + 5x4 + 1x5 + 3x6 + 1x7 + 3x8 + 2x9 > 10 b. 2x1 + 2x2 + 1x3 + 5x4 + 1x5 + 3x6 + 1x7 + 3x8 + 2x9 ≤ 10* c. 4x1 + 5x2 + 3x3 + 5x4 + 2x5 + 1x6 + 1x7 + 4x8 + 1x9 > 10 d. 4x1 + 5x2 + 3x3 + 5x4 + 2x5 + 1x6 + 1x7 + 4x8 + 1x9 ≤ 10 The next four questions are based on the following case: Consider the Excel implementation and subsequent Sensitivity Analysis for a typical portfolio optimization model below. Let x, y and z represent the fraction invested in stocks AT&T, GM and USS respectively. Please answer the four questions that follow based upon the information provided. Portfolio Model Average Return Covariance Matrix AT&T GM USS Decision: Stock % Requirements Expected Return AT&T -30.0% 10.3% -21.6% -4.6% -7.1% -5.6% 14.9% 26.0% 41.9% -7.8% 16.9% -3.5% 2.48% GM 22.5% 29.0% 21.6% -27.2% 14.4% 10.7% 3.8% -8.9% -9.0% 8.3% 3.5% -17.6% 4.26% USS 32.1% 30.5% 19.5% 19.0% -7.2% 71.5% 13.3% 23.2% 2.1% 13.1% 0.6% 10.8% 19.04% Year 1 2 3 4 5 6 7 8 9 10 11 12 AT&T 0.0376 -0.0125 -0.0110 GM -0.0125 0.0269 0.0079 USS -0.0110 0.0079 0.0377 Total 29.25% <=75% 0.73% 14.87% <=75% 0.63% 55.88% <=75% 10.64% 100% =100% 12% Sensitivity Analysis Adjustable Cells Cell $C$19 $D$19 $E$19 Name Decision: Stock % AT&T Decision: Stock % GM Decision: Stock % USS Final Value 29.25% 14.87% 55.88% Reduced Gradient 0.00% 0.00% 0.00% Name Decision: Stock % Total Expected Return Total Final Value 100% 12% Lagrange Multiplier 0% 19% Constraints Cell $F$19 $F$21 Portfolio Variance 0.0122 >=12.0% 18. The appropriate objective function is given as: a. Max. 0.0376x2 +0.0269 y2 + 0.0377 z2 - 0.0645 x y + 0.0753 x z - 0.0646 y z b. Min. 0.0376x2 +0.0269 y2 + 0.0377 z2 - 0.0645 x y + 0.0753 x z - 0.0646 y z c. Max. 0.0376x2 +0.0269 y2 + 0.0377 z2 - 0.0125 x y + 0.011 x z - 0.0079 y z d. Max. 0.0376x2 + 0.0269 y2 + 0.0377 z2 + 0.0125 x y + 0.011 x z + 0.0079 y z e. Min. 0.0376x2 +0.0269 y2 + 0.0377 z2 - 0.025 x y - 0.022 x z + 0.0158 y z* 19. One of the explicit constraints in the problem would be: a. 0.0376x +0.0269 y + 0.0377 z = 1.0 b. 0.0376x +0.0269 y + 0.0377 z <= 0.75 c. 2.48 x + 4.26 y + 19.04 z >= 12* d. 0.0248 x + 0.0426 y + 0.1904 z <= 0.12 e. 2.48 x + 4.26 y + 19.04 z = 12 20. It will be lucrative to invest in AT&T stock, if its average return increases to at least: a. 5% b. 6% c. 8% d. 10% e. No increase needed. AT&T stock is already invested in.* 21. If the required return is increased to 13% and assuming that its feasible to achieve this higher return, what would be a good estimate of the new portfolio variance?. (Note: Formula cells have 12% actually embedded as 0.12 and so on) a. 0.0141* b. 0.019 c. 0.19 d. 0.31 e. 0.0153 Read the following case and answer the five questions that follow: A University Police Department had decided to install emergency telephones at select locations on campus. The department wants to install the minimum number of telephones provided that each of the main campus streets is served by at least one telephone. The figure below maps the principal streets (A to K) on campus. It is logical to place the telephones at intersections of streets so that each telephone will serve at least two streets. Figure 1 shows layout of the streets and the telephone locations (encircled numbers). Let, xj = 1-if a telephone is installed at location j, 0-if a telephone is not installed at location j 22. The minimum number of constraints (excluding non-negativity) for the most concise IP formulation of the above problem would be: a. 8 b. 9 c. 10 d. 11* e. 19 23. If the optimal solution to the problem is to place telephones at locations 1, 2, 5 and 7, then how many streets receive more than the minimum required coverage? a. 8 b. 6 c. 4 d. 2 e. 1* 24. The appropriate objective function for the problem is: a. Max.. x1 - x8 b. Min. x1+ 2 x2 + 3 x3 +4 x4 + 5 x5 + 6 x6 + 7x7 + 8 x8 c. Min. x1+ x2 + x3 + x4 + x5 + x6 + x7 + x8* d. Min. x1+ x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 e. Cannot be stated as the distances between locations have not been provided. 25. The constraint x2 + x4 ≥ 1 represents the constraint for: a. Location 2 b. Location 4 c. Street H d. Street I * e. Streets B, I and C 26. The formulation for this problem may be best classified as a, a. Max. Covering Model b. Additional Covering Model c. Set Covering Model* d. Traveling Salesman Model e. Minimum Cost Location Analysis Model The next two questions are based upon the following case: Consider the picture below which shows a feasible region and the objective function contour. Answer the next two questions based on this picture. Max. 3X1 + 5 X2 St. X1 < 4 9 X12 + 5 X22 < 216 Xi > 0 ∀ i 6 4 Feasible Region 2 2 4 27. The optimal solution will likely result in: a. 1 binding constraint* b. 2 binding constraints c. 3 binding constraints d. no binding constraints e. the concept of a binding constraint does not exist in such cases. 28. The optimal solution will likely occur: a. at a corner point b. at two corner points c. on the boundary of the feasible region* d. in the interior of the feasible region e. outside the feasible region Read the following case and answer the four questions that follow: Starbucks coffee company makes two types of Coffee: Arabian Mocha Java and Decaf Espresso Roast. These two types of coffees are made by blending three varieties of coffee beans, Plantation X, Plantation Y and Plantation Z. Further, the coffee beans are flavored by an ingredient called chicory and the coffees must meet restrictions on chicory content. Too much chicory content spoils the taste of coffee. The three varieties of coffee beans are shipped, mixed together in two delivery trucks to the retail center. Plantation X, is shipped in truck 1, Plantation Z is shipped in truck 2, and Plantation Y is shipped in truck1 and/or truck 2. No more than 2000 pounds of Arabian Mocha Java and 1000 pounds of Decaf Espresso Roast may be sold. Using the data in the table below, we want to formulate a profitmaximizing non-linear program. Table COFFEE Arabian Mocha Java Decaf Espresso Roast SALES PRICE per POUND ($) 28 32 CHICORY CONTENT (%) NO MORE THAN 5 NO MORE THAN 7.5 COST PER POUND ($) Plantation X Plantation Y Plantation Z 20 26 15 6 3 9 Assume the following: X = pounds of Plantation X purchased Y1, Y2 = pounds of Plantation Y purchased and shipped in trucks 1 and 2 respectively Z = pounds of Plantation Z purchased TS1, TT1 = pounds of beans from truck 1 blended into Arabian Mocha Java and Decaf Espresso Roast respectively TS2, TT2 = pounds of beans from truck 2 blended into Arabian Mocha Java and Decaf Espresso Roast respectively TC1, TC2 = chicory content percentage of beans in trucks 1 and 2, respectively 29. The objective function can be represented as: a. Max. 32 (TS1+TS2) + 28(TT1+TT2) b.Max. 32(TS1+TS2)+ 28(TT1+TT2)– 7.5 TC1 – 5 TC2 c. Max. 28(TS1+TS2)+ 32(TT1+TT2)– 9X – 3(Y1 + Y2) – 6Z d.Min. 28(TS1+TS2)+ 32(TT1+TT2)– 20X – 26(Y1 + Y2) – 15Z e. Max. 28(TS1+TS2)+ 32(TT1+TT2)– 20X – 26(Y1 + Y2) – 15Z* 30. The constraint on chicory percentage of beans in Truck 2 is given as: a. TC2 = (0.09Z + 0.03Y2) / (Z + Y2)* b. TC2 = 0.09Z + 0.03Y2 c. TC2 = (0.09Z + 0.03Y) / (Z + 2Y) d. TC2 = 0.12 (Z + Y2) / (Z + Y2) e. TC2 = (0.09Z + 0.03Y) / (Z + Y) 31. The coffee shipped in Truck 1 satisfies which of the following constraints: a. Y2 + Z = TS2 + TT2 b. Y + Z = TS1 + TT1 c. Y1 + X = TS2 + TT2 d. Y1 + X = TS1 + TT1* e. Z + X = TS1 + TT1+Y1 32. The restriction on chicory content for Decaf Espresso Roast is captured by the constraint: a. TT1 TC1 + TT2 TC2 >= 0.075 b. TT1 TC1 + TT2 TC2 <= 0.075 (TT1+TT2)* c. (TT1 (0.06X + 0.03Y1) / (X + Y1) + TT2 (0.09Z + 0.03Y2) / (Z + Y2)) <= 0.075 d. (TT1 TC1 + TT2 TC2) <= 0.075 X e. (TT1 (0.06X + 0.03Y1) / (X + Y1) + TT2 (0.09Z + 0.03Y2) / (Z + Y2)) <= 0.05 33. Consider the shaded feasible regions shown below: Region B Region A a. b. c. d. e. both regions are convex Region A is convex and Region B is concave Region A is non-convex and Region B is convex Region A is convex and Region B is non-convex* both regions are non-convex The next three questions are based on the following case: Eastborne Realty has $2 million available for the purchase of a new rental property. After an initial screening, Eastborne reduced the investment alternatives to townhouses and apartment buildings. Each townhouse can be purchased for $282,000 and five are available. Each apartment building can be purchased for $400,000 and the developer will construct as many buildings as Eastborne wants to purchase. Eastborne’s property manager can devote up to 140 hours per month to these new properties; each townhouse is expected to require 4 hours per month, and each apartment building is expected to require 40 hours per month. The annual cash flow, after deducting mortgage payments and operating expenses, is estimated to be $10,000per townhouse and $15,000 per apartment building. Eastborne’s owner would like to determine the number of townhouses and the number of apartment building to purchase to maximize annual cash flow. Let, T = number of townhouses purchased A = number of apartment buildings purchased As seems practical, the optimal number of townhouses and apartment buildings cannot be fractional quantities. Eastborne’s problem can be solved graphically. Please find below the LP relaxation solution of the problem along with the IP feasible points. A 4 Funds Availab Manager's Townhouses Payoff: 10.00 Tim A T 3 2 1 0 0 1 2 3 Optimal Decisions(T,A): (2.48, 3.25) Funds Available ($000) : 282.00T + 400.00A <= 2000.00 Manager's Time (hours) : 4.00T + 40.00A <= 140.00 Townhouses Available : 1.00T + 0.00A <= 5.00 4 5 T 34. 35. 36. If Eastborne Realty were to simply round off the LP relaxation solution of their IP model to the nearest feasible integer point, what is the annual cash flow that they could expect? a. $62000 b. $70000 c. $76000 d. $65000* e. $73574 What is the optimal number of townhouses and apartment buildings that Eastborne Realty should buy in order to maximize their annual cash flow? a. 2.48 townhouses and 3.25 apartment buildings b. 2 townhouses and 3 apartment buildings c. 4 townhouses and 2 apartment buildings* d. 5 townhouses and no apartment buildings e. 3.25 townhouses and 2.48 apartment buildings In order to solve Eastborne Realty’s problem by complete enumeration, we would have to calculate the objective function value, a. 1 time b. 4 times c. 5 times d. 19 times e. 20 times* Read the following case and answer the three questions following it. Sandalo Petroleum Refineries, Inc. (SPR) produces petroleum at plants in Vermont a n d Edward Island. Refined petroleum products are shipped by rail to SPR’s warehouses in San Diego and New York and then distributed to regional distributors in Connecticut, Sacramento, Denver and Dallas. The two warehouses can also transfer small quantities between themselves using company trucks. The task is to plan SPR’s distribution over the next month. Each plant can ship up to 3300 barrels during this period and none are presently in Connecticut, Sacramento, Denver and Dallas. Connecticut, Sacramento, Denver and Dallas Distributors require 2400, 1200, 1400 and 1600 barrels respectively. Transfers between warehouses are limited to 40 Barrels but no cost is charged. The network flow diagram is given below. Vermont 1 San Diego 3 5 Connecticut 6 Sacramento 2 4 7 Edward New York Denver 8 Dallas Unit costs (cij) of the flow (Fij) on arc (i, j) are detailed in the following tables: From/To 1. Vermont 2. Edward 3. SanDiego 13 8 From/To 5. Connecticut 3. SanDiego 8 4. New York 12 4. New York 21 11 6. Sacramento 41 7 7. Denver 3 29 8.Dallas 7 2 37. Which of the following represent the objective function? a. Min. 13F31+21F41+8F32+11F42+8F53+41F63+3F73+7F83+12F54+7F64+29F74+2F84 b. Min. F13+F14+F23+F24+F35+F36+F37+F38+F45+F46+F47+F48 c. Min.13F13+21F14 +8F23+11F24+8F35+41F36+3F37+7F38+12F45+7F46+29F47+2F48* d. Max. F13+F14+F23+F24+F35+F36+F37+F38+F45+F46+F47+F48 e. None of the above. 38. The constraint at New York is given as: a. +F14+24+F34–F43–F45–F46–F47–F48 < 0 b. –F14–F24–F34=F43+F45+F46+F47+F48 c. +F14+F24+F34–F43–F45–F46–F47–F48 > 0 d. –F14–F24–F34+F43+F45+F46+F47+F48=0* e. Both b and d are equivalent. 39. The constraint at Denver may be written as: a. –F37–F47=1400 b. +F37+F47= –1400 c. –F37+F47=1400 d. –F37–F47= –1400* e. – F37– F47=140 Read the following case and answer the five questions that follow: A 400-meter medley relay involves four different swimmers, who successively swim 100 meters of the Backstroke, Breaststroke, Butterfly, and Freestyle. A coach has 4 very fast swimmers whose expected times (in seconds) in the individual events are given in the following table. The coach wants to assign the swimmers to events so that his chances of winning are maximized. Event Breaststroke Backstroke Butterfly Freestyle Swimmer 67 73 61 59 Smith 65 72 65 58 Johnson 68 70 69 55 Paul 71 69 71 57 Edwin DSCI 3870.001 Exam 3 SAMPLE 12/15/2009 Let Breaststroke be represented by 1, Backstroke by 2, Butterfly by 3 and Freestyle by 4 and the swimmers be referred to by the first alphabet of their names i.e. Smith is S etc. Let Xij represent swimmer “i”(S,J,P or E) assigned to event “j”(1,2,3 or 4). 40. The objective function is best represented by: a. Max: 67 XS1 + 73 XS2 + 61 XS3 + 59 XS4 + 65 XJ1 + 72 XJ2 + 65 XJ3 + 58 XJ4 + 68 XP1 + 70 XP2 + 69 XP3 + 55 XP4 + 71 XE1 + 69 XE2 + 71 XE3 + 57 XE4 b. Max: XS1 + XS2 + XS3 + XS4 + XJ1 + XJ2 + XJ3 + XJ4 + XP1 + XP2 + XP3 + XP4 + XE1 + XE2 + XE3 + XE4 c. Min: XS1 + XS2 + XS3 + XS4 + XJ1 + XJ2 + XJ3 + XJ4 + XP1 + XP2 + XP3 + XP4 + XE1 + XE2 + XE3 + XE4 d. Min: 67 XS1 + 73 XS2 + 61 XS3 + 59 XS4 + 65 XJ1 + 72 XJ2 + 65 XJ3 + 58 XJ4 + 68 XP1 + 70 XP2 + 69 XP3 + 55 XP4 + 71 XE1 + 69 XE2 + 71 XE3 + 57 XE4* e. All of the above. 41. The constraint for event ‘Breaststroke’ is given by: a. 67XS1+65XJ1+68XP1+71XE1 = 1 b. XS1+XJ1+XP1+XE1 < 1 c. XS1+XJ1+XP1+XE1 =1* d. X11+X21+X31+X41 = 1 e. X11+X12+X13+X14 = 1 42. The constraint for swimmer ‘Paul’ is given by: a. XP1+XP2+XP3+XP4 < 1 b. X21+X22+X23+X24 = 1 c. X1P+X2P+X3P+X4P = -1 d. XP1+XP2+XP3+XP4 =1* e. both a. & c. are valid constraints 43. Using the Greedy Heuristic discussed in class, what would be the assignment of swimmers to events? a. S → 1, J → 3, P → 2, E → 4 b. S → 3, J → 1, P → 4, E → 2* c. S → 3, J → 1, P → 2, E → 4 d. S → 1, J → 2, P → 3, E → 4 e. S → 2, J → 1, P → 4, E → 3 44. If you were to solve this assignment problem by complete enumeration, then you would have to compare a total of, a. 6 feasible solutions b. 8 feasible solutions c. 16 feasible solutions d. 24 feasible solutions* e. 36 feasible solutions -----Happy Holidays!------1

© Copyright 2020