Exam # 3, Version  Green

Date

December 12^{th},2013

Allotted Time

120 Min

Name


SID


Please read this carefully
The questions, which you attempt today, consist of True/False and multiplechoice questions worth 133 points total. Some of these questions are based on descriptive cases. There are a total of 37 questions.
Please answer all the questions on the scantron sheet provided in the order that they appear. After you are done, please turn in the scantron and this question booklet.
Please note that you have to enter your name and Student ID Number (SID#) in the above area and on the scantron. Failure to do so will result in a grade of zero.
This is an open book, open notes exam. Laptop computers are also allowed.
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
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!!

In an allinteger linear program,

all variables must be integer.

all objective function coefficients and righthand side values must be integer.

all objective function coefficients must be integer.

all righthand side values must be integer.

The objective of the transportation problem is to

identify one origin that can satisfy total demand at the destinations and at the same time minimize total shipping cost.

minimize the number of origins used to satisfy total demand at the destinations.

minimize the cost of shipping products from several origins to several destinations.

minimize the number of shipments necessary to satisfy total demand at the destinations.

The assignment problem constraint x_{31} + x_{32} + x_{33} + x_{34} < 2 means

agent 3 can be assigned to 2 tasks.

agent 2 can be assigned to 3 tasks.

a mixture of agents 1, 2, 3, and 4 will be assigned to tasks.

there is no feasible solution.

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

portfolio average return.

portfolio minimum return.

portfolio variance.

portfolio standard deviation.

We assume in the maximal flow problem that

the flow out of a node is equal to the flow into the node.

the source and sink nodes are at opposite ends of the network.

the number of arcs entering a node is equal to the number of arcs exiting the node.

None of the alternatives is correct.

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

True B. False

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

True B. False

In a model, x_{1} > 0 and integer, x_{2} > 0, and x_{3} = 0, 1. Which solution would not be feasible?

x_{1} = 5, x_{2} = 3, x_{3} = 0

x_{1} = 4, x_{2} = .389, x_{3} = 1

x_{1} = 2, x_{2} = 3, x_{3} = .578

x_{1} = 0, x_{2} = 8, x_{3} = 0
The next two questions are based on the following case:
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
4
5
6
7
Wisconsin
Newark
Peoria
Fresno
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:
From/To

3. Memphis

4. Pittsburgh

1. Wisconsin

7

8

2. Alabama

4

7

From/To

5. Fresno

6. Peoria

7. Newark

3. Memphis

25

5

17

4. Pittsburgh

29

8

5
 
The overall flow constraint at Memphis is given as:

– F13 – F23 – F43 + F34 + F35 + F36 + F37 = 0

+F13 + F23 + F43 – F34 – F35 – F36 – F37 <= 0

–F13 – F23 – F43 = F34 + F35 + F36 + F37

+F13 + F23 + F43 – F34 – F35 – F36 – F37 >= 0

Which of the following represents the objective function?

Max. 7F_{31} + 8F_{41} + 4F_{32} + 7F_{42} + 25F_{53} + 5F_{63} + 17F_{73} + 29F_{54} + 8F_{64} + 5F_{74}

Min. 7F_{31} + 8F_{41} + 4F_{32} + 7F_{42} + 25F_{53} + 5F_{63} + 17F_{73} + 29F_{54} + 8F_{64} + 5F_{74}

Min. F_{13} + F_{14} + F_{23} + F_{24} + F_{35} + F_{36} + F_{37} + F_{45} + F_{46} + F_{47}

Min. 7F_{13} + 8F_{14} + 4F_{23} + 7F_{24} + 25F_{35} + 5F_{36} + 17F_{37} + 29F_{45} + 8F_{46} + 5F_{47}
Read the following case and answer the three questions that follow:
FixIt 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 fixit 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.
Worker #
Car

1

2

3

4

5

A

25

30

28

27

24

B

31

25

24

22

19

C

18

35

31

32

19

D

20

22

25

24

22


The constraint for person 5 is given as:

25X_{A5} + 31X_{B5} + 18X_{C5} + 20X_{D5} =1

25X_{A5} + 31X_{B5} + 18X_{C5 }+ 20X_{D5} ≤ 1

X_{A5} + X_{B5} + X_{C5 }+ X_{D5} ≥ 1

X_{A5 }+ X_{B5} + X_{C5} + X_{D5} ≤ 1

The constraint for Aston Martin is given as:

X_{A1} + X_{A2} + X_{A3} + X_{A4} =1

X_{A1} + X_{A2} + X_{A3} + X_{A4} ≤ 1

X_{A1} + X_{A2} + X_{A3} + X_{A4} + X_{A5} =1

25X_{A1} + 30X_{A2 }+ 28X_{A3} + 27X_{A4 }+ 24X_{A5} ≥ 1

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

Aston Martin5, Bentley1, Carrera2, Daimler4

Aston Martin5, Bentley2, Carrera3, Daimler4

Aston Martin3, Bentley5, Carrera1, Daimler4

Aston Martin3, Bentley1, Carrera2, Daimler4

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?

25

22

19

3
The next three 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. 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.
Average Return

0.47%

7.61%

33.76%



Covariance Matrix

AT&T

GM

USS



AT&T

0.0014

0.0016

0.0006



GM

0.0016

0.0355

0.0141


Portfolio

USS

0.0006

0.0141

0.0244

Total

Variance

Decision: Stock %

65.00%

5.78%

29.22%

100%

0.0029

Requirements

<=65%

<=75%

<=70%

=100%


Expected Return

0.30%

0.44%

9.86%

10%

>=10.0%













Sensitivity Analysis
Adjustable Cells






Final

Reduced


Cell

Name

Value

Gradient


$C$19

Decision: Stock % AT&T

65.00%

0.75%


$D$19

Decision: Stock % GM

5.78%

0.00%


$E$19

Decision: Stock % USS

29.22%

0.00%






Constraints






Final

Lagrange


Cell

Name

Value

Multiplier


$F$19

Decision: Stock % Total

100%

1%


$F$21

Expected Return Total

10%

2%


The appropriate objective function is given as:

Max. 0.65x^{2} + 0.0578 y^{2} + 0.2922 z^{2}

Min. 0.0014x^{2} +0.0355 y^{2} + 0.0244 z^{2} 0.0032 x y 0.012 x z + 0.0282 y z

Min. 0.65x^{2} + 0.0578 y^{2} + 0.2922 z^{2} 0.0016 x y 0.006 x z + 0.0141 y z

Max. 0.0014x^{2} +0.0355 y^{2} + 0.0244 z^{2} 0.0016 x y 0.006 x z + 0.0141 y z

One of the constraints in the problem would be:

0.65x + 0.0578 y + 0.2922 z = 1.0

0.65x + 0.0578 y + 0.2922 z ≤ 0.75

0.003 x + 0.0044 y + 0.0986z = 0.1

0.0047 x + 0.0761 y + 0.3376 z ≥ 0.1

If the investor demands one percent more return, then the additional risk that
he/she will have to bear would be approximately:

0.0002

1.0029%

0.0129

0.02
Consider the shaded feasible regions shown below:
Region A
Region B

Which of the following items is correct?

both regions are nonconvex

both regions are convex

Region A is convex and Region B is concave

Region A is nonconvex and Region B is convex
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.
1
2
3
4
5
6
7
12
8
10
12
6
3
4
9
7
3

Which of the following represents the constraint for Node 5?

X_{25} X_{35} X_{45 } X_{75 }+ X_{52 }+ X_{53 }+ X_{57} = 0

X_{25} X_{35} X_{45 } X_{75 }+ X_{52 }+ X_{53 }+ X_{57} = 1

X_{25} 7X_{35} 3X_{45 }+ 8X_{52 }+ 7X_{53 }+ 3X_{54 }+ 4X_{57} = 0

X_{25} X_{35} X_{75 }+ X_{52 }+ X_{53 }+ X_{54 }+ X_{57} = 0
Read the following case and answer the three questions that follow:
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

Let x_{i} = 1 if activity i is chosen, 0 if not, for i = 1, …, 9

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

Max 4x_{1} + 5x_{2} + 3x_{3} + 5x_{4} + 2x_{5} + 1x_{6} + 1x_{7} + 4x_{8} + 1x_{9}

Max 30x_{1} + 20x_{2} + 30x_{3} + 20x_{4} + 45x_{5} + 60x_{6} + 45x_{7} + 30x_{8} + 40x_{9}

Max 2x_{1} + 2x_{2} + x_{3} + 5x_{4} + 1x_{5} + 3x_{6} + 1x_{7} + 3x_{8} + 2x_{9}

Min 4x_{1} + 5x_{2} + 3x_{3} + 5x_{4} + 2x_{5} + 1x_{6} + 1x_{7} + 4x_{8} + 1x_{9}

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

4x_{1} + 5x_{2} +3 x_{3} 1

2x_{1} + 2x_{2} + x_{3 } 1

x_{1} + x_{2} + x_{3} 1

30x_{1} + 20x_{2} + 30x_{3} 1

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

x_{6} 5x_{4}

60x_{6} 20x_{4}

5x_{6 } x_{4}

x_{6} x_{4}
Max. 54X_{1}  9X_{1}^{2} + 78X_{2} 13 X_{2}^{2}
_{ } St. X_{1} < 4
2 X_{2 }< 12
3 X_{1} + 2 X_{2} < 18
X_{i} > 0 i
Feasible Region
2
4
6
4
2
Z = 189
Z = 162
Z = 117
The next two questions are based upon the following case:
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.

The optimal solution will likely result in:

1 binding constraint

2 binding constraints

no binding constraints

3 binding constraints

The optimal solution will likely occur:

in the interior of the feasible region

at a corner point

at two corner points

on the boundary of the feasible region
The next three questions are based upon the following case:
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

Let P_{i} = the number of hoses produced on machine i and U_{i} = 1 if machine i is used, = 0 otherwise

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

Min 1.25P_{1} + 1.5P_{2} + P_{3} + 2P_{4}

Min750U_{1} + 500U_{2} + 1000U_{3} + 300U_{4}

Min750U_{1} + 500U_{2} + 1000U_{3} + 300U_{4} + 1.25P1 + 1.5P2 + P3 + 2P4

Min500U_{2} + 300U_{4} + 1.25P_{1} + 1.5P_{2} + P_{3} + 2P_{4}

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

Total amount of production

Minimum amount of production

Maximum amount of production

Minimum required contracted amount

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

Machine 1 and machine 4 should be used.

If machine 4 is used, machine 1 cannot be used and vice versa.

Machine 1 and machine 4 should be used together.

Neither machine 1 nor machine 4 should be used.
The next four questions are based upon the following case:
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:

Project


1

2

3

4

5

6

Engineers Required

20

55

47

38

90

63

Support Personnel Required

15

45

50

40

70

70

Profit ($1,000,000s)

1.0

1.8

2.0

1.5

3.6

2.2


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

P_{4} + P_{6} ≥1

P_{4}+P_{6} = 0

P_{4} P_{6} ≥ 0

P_{4} P_{6} = 0

What is the meaning of the constraint “P_{1} P_{2} ≥ 0”?

Project 2 can be undertaken only if project 1 is undertaken.

If either project 2 or project 1 is undertaken, both must be undertaken

If project 2 is undertaken, then project 1 cannot be undertaken.

If project 1 is undertaken, then project 2 cannot be undertaken.

What is the meaning of the constraint “P_{3} + P_{5} ≥ 1”?

If either project 3 or project 5 is undertaken, both must be undertaken

Either project 3 or 5 must be undertaken.

If project 5 is undertaken, project 3 must not be undertaken and vice versa

If project 3 is undertaken, then project 5 cannot be undertaken.

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”

P_{4} + P_{6} ≥ P_{2} and P_{4} ≥ P_{2}, P_{6} ≥ P_{2}

P_{4} ≥ P_{2}, P_{6} ≥ P_{2} and P_{4} + P_{6} – 1 ≤ P_{2}

P_{4} + P_{6}≤ P_{2} and P_{4} ≥ P_{2}, P_{6} ≥ P_{2}

P_{4} ≥ P_{2}, P_{6} ≥ P_{2} and P_{4} + P_{6} ≤ 2 P_{2}

Consider a mapbased solution of the salesrep 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.

10

5

3

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

If the objective function were to be minimized, then the linear programming
relaxation of the problem would yield an objective function value:

slightly more than 11

exactly the same as the integer program

slightly less than 11

slightly less than 18

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

24

25

26

26.1

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

Traveling Salesman Game

Transportation Game

Shortest Path Game

Max Flow Game

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 _________.

Shortest Path Model

Multicommodity Network Flow Model

Traveling Salesman Model

Spanning Tree Model

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.

5

4

3

2
