DSCI 3870.001: Management Science
Uncategorized
DSCI 3870.001: Management Science
Sample
Name:
Student ID #:
Please read this carefully
This exam consists of 28 (T/F and multiplechoice) 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 your 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 – Nonlinear Program/ Programming
MILP – Mixed Integer Linear Program/ Programming
An “(s)” appended to these acronyms denotes the plural.
This is an open book exam. Be sure to allocate your time wisely. All the best.
Answer the next six questions based on the case given below:
Tower Engineering Corporation is considering undertaking several proposed projects for the next fiscal year. The projects, the number of engineers and the number of support personnel required for each project, and the cost for each project are summarized in the following table:

Project 



1 
2 
3 
4 
5 
6 
7 
8 
Engineers Required 
40 
29 
35 
44 
45 
35 
28 
32 
Profit ($1,000,000s) 
12 
9 
10 
11 
13 
8 
7 
9 
Formulate an integer linear program that maximizes Tower’s profit, subject to constraints, which will be stated in the questions that follow.
Let P_{i} = 0 or 1, indicate if project i will not be undertaken or will be undertaken respectively.
 The most appropriate objective function(s) for Tower Engineering Corporation is:
 Min. 12P_{1} + 9P_{2} + 10P_{3} + 11P_{4} + 13P_{5} + 8P_{6 }+ 7P_{7 }+9P_{8}
 Max. 40P_{1} + 29P_{2} + 35P_{3} + 44P_{4} + 45P_{5} + 35P_{6 }+ 28P_{7 }+32P_{8}
 Max. 12P_{1} + 9P_{2} + 10P_{3} + 11P_{4} + 13P_{5} + 8P_{6 }+ 7P_{7 }
 Max. 12P_{1} + 9P_{2} + 10P_{3} + 11P_{4} + 13P_{5} + 8P_{6 }+ 7P_{7 }+9P_{8}*
 None of the above.
 At least half of the projects must be undertaken. The constraint that captures this is:
 P_{4} > 4
 P_{1} + P_{2} + P_{3} + P_{4} + P_{5} + P_{6 }+ P_{7 }+ P_{8 }< 4
 P_{1} + P_{2} + P_{3} + P_{4} + P_{5} + P_{6 }+ P_{7 }+ P_{8 }> 4*
 P_{1} + P_{2} + P_{3} + P_{4} + P_{5} + P_{6 }+ P_{7 }+ P_{8 }> 0.5*( P_{1} + P_{2} + P_{3} + P_{4} + P_{5} + P_{6 }+ P_{7 }+ P_{8})
 Both c and d could work.
 Projects 2 can only be undertaken if at least two out of Projects 1, 4 and 6 are completed. This requirement is represented by:
 P_{2} < (P_{1} + P_{4} + P_{6})/2
 P_{2} < 2*(P_{1} + P_{4} + P_{6})/3
 P_{2} > (P_{1} + P_{4} + P_{6})/2
 P_{2} < P_{1} + P_{4} + P_{6} – 2
 Both a and b could work.*
 There are 150 engineers available. The constraint that captures this is:
 40P_{1} + 29P_{2} + 35P_{3} + 44P_{4} + 45P_{5} + 35P_{6 }+ 28P_{7} + 32P_{8 }< 150*
 40P_{1} + 29P_{2} + 35P_{3} + 44P_{4} + 45P_{5} + 35P_{6 }+ 28P_{7} + 32P_{8 }= 150
 40P_{1} + 29P_{2} + 35P_{3} + 44P_{4} + 45P_{5} + 35P_{6 }+ 28P_{7} + 32P_{8 }> 150
 12P_{1} + 9P_{2} + 10P_{3} + 11P_{4} + 13P_{5} + 8P_{6 }+ 7P_{7} + 9P_{8 }< 150
 None of the above.
_{ }
 The management of Tower Engineering stipulates that if project 8 is NOT completed, then at least two of projects 3, 5 and 7 must be completed. This restriction is captured by:
 2*P_{8} < P_{3 }+ P_{5} + P_{7}
 2P_{8} < P_{3 }+ P_{5} + P_{7 }
 2(1P_{8}) < P_{3 }+ P_{5} + P_{7}*
 P_{8} < P_{3 }+ P_{5} + P_{7 }– 2
 None of the above.
 If only projects 1, 3, 5 and 6 are completed, all of the four previously listed constraints would be satisfied.
 True b. False*
 Suppose that there are 15 locations, including cities A, B and C. You want to go from city A to B and stay at B for a few days. You then want to move from city B to city C. The remaining 12 cities are located between cities A and B, as well as between B and C. You don’t necessarily want to visit these other cities but you may pass through them if required. If you want to minimize the total distance travelled, you should solve this problem as:
 Two Transshipment Problems
 One Traveling Salesperson Problem
 Two Maximal Flow Problems
 Two Shortest Route Problems*
 One Set Covering Problem
 In a typical Set Covering Problem, it is possible that the optimal solution would lead to all locations being covered twice or more.
 True
 False*
For the next two questions, consider the network below.
Consider the LP for finding the shortestroute path from node 1 to node 7. Bidirectional arrows («) indicate that travel is possible both ways. Let X_{ij} = 1 if the route from node i to node j is taken and 0 otherwise.
 Which of the following represents the constraint for Node 5?
 X_{25} – X_{45} – X_{35 }+ X_{54 }+ X_{53 }+ X_{57} = 0
 X_{25} – X_{45} – X_{35 }+ X_{54 }+ X_{53 }+ X_{57} + X_{52} = 1
 X_{25} + X_{45} + X_{35 }– X_{54 }– X_{53 }– X_{57} – X_{52} = 1
 X_{25} – X_{45} – X_{35 }+ X_{54 }+ X_{53 }+ X_{57} + X_{52} < 0
 None of the above.*
 If you apply the Greedy Heuristic method, starting at Node 1, which path would you get as the solution (keep in mind that Greedy Heuristic solution may not be optimal)?
 1à2à4à5à7*
 1à2à5à4à7
 1à3à5à7
 1à2à5à7
 None of the above.
 Suppose that an allinteger problem has 5 decision variables and each variable can take on 4 different values. Then, the maximum number of feasible combinations for this problem would be
 20
 3125
 9
 1024*
 None of the above.
 Which of the following can be typically modelled as an allbinary problem?
 Transshipment Problem
 Shortest Route Problem
 Assignment Problem
 Transportation Problem
 Both b and c can be modelled as an allbinary problem.*
 13. A maximization Linear Programming (LP) model with two decision variables x1 and x2 has an optimal solution with the objective function value of 31.5. If we restrict only x1 to be an integer, which of the following COULD be the new optimal objective function value?
 5 b. 32 c. 30 d. either (a) or (b) e. either (a) or (c)*
Read the following case and answer the four questions that follow:
A professor has been contacted by notforprofit agencies that are willing to work with student consulting teams. The agencies need help with such things as budgeting, information systems, coordinating volunteers, and forecasting. Although each of the five student teams could work with any of the agencies, the professor feels that there is a difference in the amount of time it would take each group to solve each problem. The professor’s estimate of the time, in days, is given in the table below.

Projects 
Team 
Budgeting 
Information 
Volunteers 
Forecasting 
A 
24 
28 
32 
36 
B 
35 
31 
39 
33 
C 
46 
41 
35 
30 
D
E 
22
29 
38
27 
21
29 
33
29 
Let X_{ij} denote if team i (A=1,B=2,C=3,D=4, E=5) is assigned to project j (Budgeting =1, Information = 2, Volunteers =3, Forecasting = 4)
 The most appropriate constraint for Team D is given as:
 X_{41} + X_{42} + X_{43} + X_{44} =1
 X_{41} + X_{42} + X_{43} + X_{44} > 1
 X_{41} + X_{42} + X_{43} + X_{44} < 1*
 X_{14} + X_{24} + X_{34} + X_{44 }< 1
 Both a and c are valid constraints
 The constraint for the Information project is given as:
 X_{12} + X_{22} + X_{32} + X_{42} > 1
 X_{12} + X_{22} + X_{32} + X_{42} + X_{52} > 1*
 X_{12} + X_{22} + X_{32} + X_{42} + X_{52} < 1
 X_{21} + X_{22} + X_{23} + X_{24} + X_{25} = 1
 Both b and c are valid constraints
 Using the Greedy Heuristic discussed in class, the assignment would be:
 A → Budgeting, B → Forecasting, D → Volunteers, E → Information
 A → Information, B → Budgeting, C → Volunteers, D → Forecasting
 A → Forecasting, C → Volunteers, D → Budgeting, E → Information
 A → Budgeting, C → Forecasting, D → Volunteers, E → Information *
 None of the above.
 If a team can be assigned to more than one project, then, in the optimal assignment, which team(s) would be used more than once?
 A
 D
 E
 Both D and E. *
 No team would be used more than once.
For the next six questions, consider the following: Burnside Marketing Research conducted a study for Barker Foods on some designs for a new dry cereal. Three attributes were found to be most influential in determining which cereal had the best taste: ratio of wheat to corn in the cereal flake, type of sweetener (sugar, honey, or artificial), and the presence or absence of flavor bits. Nine children participated in taste tests and provided the following partworths for the attributes:
Wheat/ Corn 
Sweetener 

Flavor Bits 
Child Low High Sugar Honey Artificial Present Absent
1 35 25 40 30 35 20 26
2 38 40 35 42 30 26 21
3 45 40 40 42 35 26 21
4 25 30 50 45 45 16 28
5 35 20 50 45 30 18 14
6 15 25 50 55 45 19 16
7 39 41 25 40 30 30 31
8 30 35 35 40 45 28 26
9 30 18 50 55 40 26 16
Assume that the overall utility (sum of partworths) of the current favorite cereal is 100 for each child. Your job is to design a product that will maximize the share of choices for the nine children in the sample.
 Suppose that the optimal solution indicates a cereal with high wheat/corn ratio, sugar and flavor bits. Then, Child #4 will choose this optimal cereal.
 True b. False*
 Suppose Child #2 prefers a particular combination. Then, which of the following children will also DEFINITELY prefer this combination?
 Child #3* Child #4 c. Child #6 d. Child #7 e. No such kid exists.
 Which child would definitely NOT switch from his/her current favorite cereal?
 All of the children may switch, given the appropriate options.
 Child #1
 Child #4
 Child #6*
 Child #9
 If Child #5 switches from his/her current favorite cereal for a particular combination, how many children would NOT switch?
 2 b. 3 c. 4 d. 5 e. 6*
 If Child #3 does NOT switch from his/her current favorite cereal for a particular combination, how many children would actually switch?
 1 b. 2 c. 3* d. 4 e. 0
 If the Greedy Heuristic solution (for each attribute, choose the option favored by the largest number of children) is implemented, how many children would switch?
 5 b. 4* c. 3 d. 2 e. 1
Answer the next three questions based on the case given below:
Hansen Controls has been awarded a contract for a large number of control panels. To meet this demand, it will use its existing plants in San Diego and Houston, and consider new plants in Tulsa, St. Louis, and Portland. Finished control panels are to be shipped to Seattle, Denver, and Kansas City. Pertinent information is given in the table.
Sources 
Construction
Cost 
Shipping Cost to Destination: 
Capacity 
Seattle
1 
Denver
2 
Kansas
City
3 
1 San Diego 
— 
5 
7 
8 
12,000 
2 Houston 
— 
10 
8 
6 
16,000 
3 Tulsa 
450,000 
12 
6 
3 
8,000 
4 St. Louis 
500,000 
12 
4 
2 
7,000 
5 Portland 
540,000 
4 
10 
11 
9,000 

Demand 
17,000 
12,000 
9,000 

We develop a transportation model as an LP that includes provisions for the fixed costs (construction costs in this case) for the three new plants. The solution of this model would reveal which plants to build and the optimal shipping schedule.
Let 
x_{ij} = the number of panels shipped from source i to destination j 

y_{i} = 1 if plant i is built, = 0 otherwise (i = 3, 4, 5) 
 The constraint for supply from Portland is given as:
 x_{51} + x_{52} + x_{53} < 9,000
 x_{51} + x_{52} + x_{53} < 9,000 + y_{5}
 x_{15} + x_{25} + x_{35} < 9,000 y_{5}
 x_{51} + x_{52} + x_{53} < 9,000 y_{5}*
 y_{51} + y_{52} + y_{53} < 9,000 x_{5}
 The constraint for demand at Denver is given as:
 x_{12} + x_{22} > 11,000
 x_{12} + x_{22} + x_{32 }+ x_{42} + x_{52} < 12,000
 x_{12} + x_{22} + x_{32 }+ x_{42} + x_{52} > 12,000*
 x_{12} + x_{22} + x_{32 }+ x_{42} + x_{52} > 12,000 y_{2}
 Both c and d are correct.
 Suppose that Hanson is not able to build any new plants due to funding issues and needs to meet as much of the demand as posible using its two existing plants in San Diego and Houston. If we apply the Greedy Heuristic method, only Kansas City’s demand would be fully satisfied.
 True * b. False
 27. If a transshipment problem has 6 supply points, 4 intermediate points and 10 destinations (all supply points can ship to all intermediate points and all intermediate points can ship to all destinations), then the number of arcs/routes would be
 20 b. 64* c. 240
 28. The 2D (i.e. (x,y)) graph of a problem, which requires x to be an integer less than or equal to 6 and y to be a binary integer problem has a feasible region _________.
 of twelve dots.
 of two horizontal stripes.
 of infinitely many dots.
 of two vertical stripes.
 of fourteen dots.*