Dsci 3870: Management Science

This is an open book, open notes exam. Laptop computers are also allowed.

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 Be sure to allocate your time wisely between the multiple choice and T/F questions.

Best of luck!!

1. 
   In an all-integer linear program,
   

1. 
   all variables must be integer.
   
2. 
   all objective function coefficients and right-hand side values must be integer.
   
3. 
   all objective function coefficients must be integer.
   
4. 
   all right-hand side values must be integer.
   

2. 
   The objective of the transportation problem is to
   

1. 
   identify one origin that can satisfy total demand at the destinations and at the same time minimize total shipping cost.
   
2. 
   minimize the number of origins used to satisfy total demand at the destinations.
   
3. 
   minimize the cost of shipping products from several origins to several destinations.
   
4. 
   minimize the number of shipments necessary to satisfy total demand at the destinations.
   

3. 
   The assignment problem constraint x₃₁ + x₃₂ + x₃₃ + x₃₄ < 2 means
   

1. 
   agent 3 can be assigned to 2 tasks.
   
2. 
   agent 2 can be assigned to 3 tasks.
   
3. 
   a mixture of agents 1, 2, 3, and 4 will be assigned to tasks.
   
4. 
   there is no feasible solution.
   

4. 
   The measure of risk most often associated with the Markowitz portfolio model is the
   

1. 
   portfolio average return.
   
2. 
   portfolio minimum return.
   
3. 
   portfolio variance.
   
4. 
   portfolio standard deviation.
   

5. 
   We assume in the maximal flow problem that
   

1. 
   the flow out of a node is equal to the flow into the node.
   
2. 
   the source and sink nodes are at opposite ends of the network.
   
3. 
   the number of arcs entering a node is equal to the number of arcs exiting the node.
   
4. 
   None of the alternatives is correct.
   

6. 
   Dual or shadow prices, similar to those that we get for linear programming models, are mathematically impossible to derive for integer programming models.
   

1. 
   True B. False
   

7. 
   Whenever total supply is less than total demand in a transportation problem, the LP model does not determine how the unsatisfied demand is handled.
   

1. 
   True B. False
   

8. 
   In a model, x₁ > 0 and integer, x₂ > 0, and x₃ = 0, 1. Which solution would not be feasible?
   

1. 
   x₁ = 5, x₂ = 3, x₃ = 0
   
2. 
   x₁ = 4, x₂ = .389, x₃ = 1
   
3. 
   x₁ = 2, x₂ = 3, x₃ = .578
   
4. 
   x₁ = 0, x₂ = 8, x₃ = 0
   

Optimal Ovens, Inc. (OOI) makes home toaster ovens at plants in Alabama and Wisconsin. Completed ovens are shipped by rail to one of OOI’s warehouses in Memphis and Pittsburgh and then distributed to customer facilities in Fresno, Peoria and Newark.

1

2

3

5

6

Wisconsin

Newark

Peoria

Pittsburgh

Memphis

Alabama
The two warehouses can also transfer small quantities between themselves using company trucks. The task is to plan OOI’s distribution over the next month. Each plant can ship up to 1000 units during this period and none are presently in Fresno, Peoria and Newark. Fresno, Peoria and Newark customers require 450, 500 and 610 ovens respectively. Transfers between warehouses are limited to 25 ovens but no cost is charged. The network flow diagram is given below.

Unit costs (c_ij) of the flow (F_ij)on arc (i, j) are detailed in the following tables:

9. 
   The overall flow constraint at Memphis is given as:
   

1. 
   – F13 – F23 – F43 + F34 + F35 + F36 + F37 = 0
   
2. 
   +F13 + F23 + F43 – F34 – F35 – F36 – F37 <= 0
   
3. 
   –F13 – F23 – F43 = F34 + F35 + F36 + F37
   
4. 
   +F13 + F23 + F43 – F34 – F35 – F36 – F37 >= 0
   

10. 
    Which of the following represents the objective function?
    

1. 
   Max. 7F₃₁ + 8F₄₁ + 4F₃₂ + 7F₄₂ + 25F₅₃ + 5F₆₃ + 17F₇₃ + 29F₅₄ + 8F₆₄ + 5F₇₄
   
2. 
   Min. 7F₃₁ + 8F₄₁ + 4F₃₂ + 7F₄₂ + 25F₅₃ + 5F₆₃ + 17F₇₃ + 29F₅₄ + 8F₆₄ + 5F₇₄
   
3. 
   Min. F₁₃ + F₁₄ + F₂₃ + F₂₄ + F₃₅ + F₃₆ + F₃₇ + F₄₅ + F₄₆ + F₄₇
   
4. 
   Min. 7F₁₃ + 8F₁₄ + 4F₂₃ + 7F₂₄ + 25F₃₅ + 5F₃₆ + 17F₃₇ + 29F₄₅ + 8F₄₆ + 5F₄₇
   

Fix-It shop has received four luxury cars Aston Martin (A), Bentley (B), Carrera (C) and Daimler (D) to repair. Five workers with different talents are available to repair the cars. The fix-it shop owner has an estimate of the profit if a particular worker does a particular car. The profits in dollars per hour, which are shown in the table differ because the owner believes that each worker will differ in speed and skill on these quite varied jobs. Assume that the variables are X_ij where i=A,B,C,D denote cars and j=1,2,3,4,5 denote workers, and assume that the owner wants to maximize his profits by repairing all the cars and making sure that each car is assigned to a single worker and each worker works on at most one car.

11. 
    The constraint for person 5 is given as:
    

1. 
   25X_A5 + 31X_B5 + 18X_C5 + 20X_D5 =1
   
2. 
   25X_A5 + 31X_B5 + 18X_C5 + 20X_D5 ≤ 1
   
3. 
   X_A5 + X_B5 + X_C5 + X_D5 ≥ 1
   
4. 
   X_A5 + X_B5 + X_C5 + X_D5 ≤ 1
   

12. 
    The constraint for Aston Martin is given as:
    

1. 
   X_A1 + X_A2 + X_A3 + X_A4 =1
   
2. 
   X_A1 + X_A2 + X_A3 + X_A4 ≤ 1
   
3. 
   X_A1 + X_A2 + X_A3 + X_A4 + X_A5 =1
   
4. 
   25X_A1 + 30X_A2 + 28X_A3 + 27X_A4 + 24X_A5 ≥ 1
   

13. 
    Using the Greedy Heuristic discussed in class, what would be the assignment of cars to workers?
    

1. 
   Aston Martin5, Bentley1, Carrera2, Daimler4
   
2. 
   Aston Martin5, Bentley2, Carrera3, Daimler4
   
3. 
   Aston Martin3, Bentley5, Carrera1, Daimler4
   
4. 
   Aston Martin3, Bentley1, Carrera2, Daimler4
   

14. 
    In class we saw the Max Cover problem for the state of Ohio. Based on the map of the optimal solution to such a Max Cover problem shown below, how many counties, excluding the hubs, have been covered to achieve maximum coverage?
    

1. 
   25
   
2. 
   22
   
3. 
   19
   
4. 
   3
   

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. The “Average Return” and the information in the “Covariance Matrix” represent basic statistical analysis performed on returns data provided to us for AT&T, GM and USS. The optimization model embedded in MS Excel appears below the covariance matrix.

Sensitivity Analysis

15. 
    The appropriate objective function is given as:
    

1. 
   Max. 0.65x² + 0.0578 y² + 0.2922 z²
   
2. 
   Min. 0.0014x² +0.0355 y² + 0.0244 z²  0.0032 x y  0.012 x z + 0.0282 y z
   
3. 
   Min. 0.65x² + 0.0578 y² + 0.2922 z²  0.0016 x y  0.006 x z + 0.0141 y z
   
4. 
   Max. 0.0014x² +0.0355 y² + 0.0244 z²  0.0016 x y  0.006 x z + 0.0141 y z
   

16. 
    One of the constraints in the problem would be:
    

1. 
   0.65x + 0.0578 y + 0.2922 z = 1.0
   
2. 
   0.65x + 0.0578 y + 0.2922 z ≤ 0.75
   
3. 
   0.003 x + 0.0044 y + 0.0986z = 0.1
   
4. 
   0.0047 x + 0.0761 y + 0.3376 z ≥ 0.1
   

17. 
    If the investor demands one percent more return, then the additional risk that
    

1. 
   0.0002
   
2. 
   1.0029%
   
3. 
   0.0129
   
4. 
   0.02
   

Consider the shaded feasible regions shown below:

Region A

Region B

18. 
    Which of the following items is correct?
    

1. 
   both regions are non-convex
   
2. 
   both regions are convex
   
3. 
   Region A is convex and Region B is concave
   
4. 
   Region A is non-convex and Region B is convex
   

Consider the network below. Consider the LP for finding the shortest-route 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.

1

2

3

5

6

12

8

12

6

4

9

3

19. 
    Which of the following represents the constraint for Node 5?
    

1. 
   X₂₅  X₃₅  X₄₅  X₇₅ + X₅₂ + X₅₃ + X₅₇ = 0
   
2. 
   X₂₅  X₃₅  X₄₅  X₇₅ + X₅₂ + X₅₃ + X₅₇ = 1
   
3. 
   X₂₅  7X₃₅  3X₄₅ + 8X₅₂ + 7X₅₃ + 3X₅₄ + 4X₅₇ = 0
   
4. 
   X₂₅  X₃₅  X₇₅ + X₅₂ + X₅₃ + X₅₄ + X₅₇ = 0
   

A summer camp recreation director is trying to choose activities for a rainy day. Information about possible choices is given in the table below. A higher numeric popularity rating is considered better.

Category	Activity	Time (minutes)	Popularity with Campers	Popularity with Counselors
Art	1 - Painting	30	4	2
	2 - Drawing	20	5	2
	3 - Nature craft	30	3	1
Music	4 - Rhythm band	20	5	5
Sports	5 - Relay races	45	2	1
	6 - Basketball	60	1	3
Computer	7 - Internet	45	1	1
	8 - Writing	30	4	3
	9 - Games	40	1	2

20. 
    If the objective is to keep the campers happy, what should the objective function be?
    

1. 
   Max 4x₁ + 5x₂ + 3x₃ + 5x₄ + 2x₅ + 1x₆ + 1x₇ + 4x₈ + 1x₉
   
2. 
   Max 30x₁ + 20x₂ + 30x₃ + 20x₄ + 45x₅ + 60x₆ + 45x₇ + 30x₈ + 40x₉
   
3. 
   Max 2x₁ + 2x₂ + x₃ + 5x₄ + 1x₅ + 3x₆ + 1x₇ + 3x₈ + 2x₉
   
4. 
   Min 4x₁ + 5x₂ + 3x₃ + 5x₄ + 2x₅ + 1x₆ + 1x₇ + 4x₈ + 1x₉
   

20. 
    Which of the following represents the constraint : “at most one art activity can be done.”?
    

1. 
   4x₁ + 5x₂ +3 x₃  1
   
2. 
   2x₁ + 2x₂ + x₃  1
   
3. 
   x₁ + x₂ + x₃  1
   
4. 
   30x₁ + 20x₂ + 30x₃  1
   

20. 
    Which of the following represents the constraint : “if basketball is chosen, then music must be chosen”
    

1. 
   x₆  5x₄
   
2. 
   60x₆  20x₄
   
3. 
   5x₆  x₄
   
4. 
   x₆  x₄
   

Consider the picture above/on the earlier page which shows a “Feasible Region” and several objective function contours. Answer the next two questions based on this picture.

20. 
    The optimal solution will likely result in:
    

1. 
   1 binding constraint
   
2. 
   2 binding constraints
   
3. 
   no binding constraints
   
4. 
   3 binding constraints
   

20. 
    The optimal solution will likely occur:
    

1. 
   in the interior of the feasible region
   
2. 
   at a corner point
   
3. 
   at two corner points
   
4. 
   on the boundary of the feasible region
   

The Westfall Company has a contract to produce 10,000 yards of garden hoses for a large discount chain. Westfall has four different machines that can produce this kind of hose. Because these machines are from different manufacturers and use differing technologies, their specifications are not the same.

Machine	Fixed Cost to Set Up Production Run	Variable Cost Per Hose	Capacity (yards)
1	750	1.25	6000
2	500	1.50	7500
3	1000	1.00	4000
4	300	2.00	5000

20. 
    If the company wants to minimize total cost what will be the objective function?
    

1. 
   Min 1.25P₁ + 1.5P₂ + P₃ + 2P₄
   
2. 
   Min750U₁ + 500U₂ + 1000U₃ + 300U₄
   
3. 
   Min750U₁ + 500U₂ + 1000U₃ + 300U₄ + 1.25P1 + 1.5P2 + P3 + 2P4
   
4. 
   Min500U₂ + 300U₄ + 1.25P₁ + 1.5P₂ + P₃ + 2P₄
   

20. 
    What does the constraint “P1 + P2 + P3 + P4 ≥ 10000” capture?
    

1. 
   Total amount of production
   
2. 
   Minimum amount of production
   
3. 
   Maximum amount of production
   
4. 
   Minimum required contracted amount
   

20. 
    If we add the constraint of “U1 + U4 ≤ 1”, what does the constraint capture?
    

1. 
   Machine 1 and machine 4 should be used.
   
2. 
   If machine 4 is used, machine 1 cannot be used and vice versa.
   
3. 
   Machine 1 and machine 4 should be used together.
   
4. 
   Neither machine 1 nor machine 4 should be used.
   

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 expected profits for each project are summarized in the following table:

20. 
    Which of the following captures the constraint of “If either project 6 or project 4 is undertaken, then both must be undertaken”?
    

1. 
   P₄ + P₆ ≥1
   
2. 
   P₄+P₆ = 0
   
3. 
   P₄  P₆ ≥ 0
   
4. 
   P₄  P₆ = 0
   

20. 
    What is the meaning of the constraint “P₁ P₂ ≥ 0”?
    

1. 
   Project 2 can be undertaken only if project 1 is undertaken.
   
2. 
   If either project 2 or project 1 is undertaken, both must be undertaken
   
3. 
   If project 2 is undertaken, then project 1 cannot be undertaken.
   
4. 
   If project 1 is undertaken, then project 2 cannot be undertaken.
   

20. 
    What is the meaning of the constraint “P₃ + P₅ ≥ 1”?
    

1. 
   If either project 3 or project 5 is undertaken, both must be undertaken
   
2. 
   Either project 3 or 5 must be undertaken.
   
3. 
   If project 5 is undertaken, project 3 must not be undertaken and vice versa
   
4. 
   If project 3 is undertaken, then project 5 cannot be undertaken.
   

20. 
    Which of the following captures the constraint: “project 2 cannot be undertaken unless both projects 6 and 4 are undertaken, however, when projects 6 and 4 are undertaken, then project 2 must be undertaken”
    

1. 
   P₄ + P₆ ≥ P₂ and P₄ ≥ P₂, P₆ ≥ P₂
   
2. 
   P₄ ≥ P₂, P₆ ≥ P₂ and P₄ + P₆ – 1 ≤ P₂
   
3. 
   P₄ + P₆≤ P₂ and P₄ ≥ P₂, P₆ ≥ P₂
   
4. 
   P₄ ≥ P₂, P₆ ≥ P₂ and P₄ + P₆ ≤ 2 P₂
   

32. 
    Consider a map-based solution of the sales-rep example discussed in class, which was somewhat different from the Max Cover or Set Cover problems. The map (where shaded counties are part of the optimal solution), suggests that we are optimally locating ___ sales reps.
    

1. 
   10
   
2. 
   5
   
3. 
   3
   
4. 
   2
   

The next two questions are based on the following case:

Consider the following integer programming problem and partial graphical solution which follows. Answer the next two questions based on this information.

Objective function: 3 x + 5 y

Subject to: 2 x > 3

2 x + 3 y < 16

x + 4y > 6

x > 0, y > 0

x - Integer, y - Integer

32. 
    If the objective function were to be minimized, then the linear programming
    

relaxation of the problem would yield an objective function value:

1. 
   slightly more than 11
   
2. 
   exactly the same as the integer program
   
3. 
   slightly less than 11
   
4. 
   slightly less than 18
   

32. 
    If the objective function were to be maximized, then the optimal objective function value for the integer program would be.
    

1. 
   24
   
2. 
   25
   
3. 
   26
   
4. 
   26.1
   

32. 
    Consider below a screen shot of an exercise that we did in class. This represents the ______.
    

1. 
   Traveling Salesman Game
   
2. 
   Transportation Game
   
3. 
   Shortest Path Game
   
4. 
   Max Flow Game
   

32. 
    Consider below a picture that represents an optimal solution to a network model similar to one we discussed in class and as mentioned, this is one of the few models that can be solved to optimality using simply a “greedy” approach. We call this a _________.
    

1. 
   Shortest Path Model
   
2. 
   Multicommodity Network Flow Model
   
3. 
   Traveling Salesman Model
   
4. 
   Spanning Tree Model
   

32. 
    Consider below a picture that represents an optimal solution to the “Share of Choices” model similar to the one that we discussed in class. The optimal pizza covers __ customers.
    

1. 
   5
   
2. 
   4
   
3. 
   3
   
4. 
   2