Deck 5: Transportation, Assignment, and Network Models

Question 1

In a maximal flow problem,each node in the network is associated with a decision variable.

Answer 1

False

Question 2

Which of the following is NOT a network flow model?

A)Transportation model
B)Assignment model
C)Product mix model
D)Shortest-path model
E)Minimal-spanning tree model

Answer 2

C

Question 3

Use the information below to answer the following questions.
Consider the following shortest path problem where node 1 is the starting node and node 6 is the destination node.

Refer to the figure.What is the constraint associated with node 6?

A)X₆₄ + X₆₅ - X₄₆ - X₅₆ = +1
B)X₆₄ + X₆₅ - X₄₆ - X₅₆ = 0
C)X₄₆ + X₅₆ - X₆₄ - X₆₅ = +1
D)-X₆₄ - X₆₅ = -1
E)-X₄₆ + X₅₆ = 0

Answer 3

C

Question 4

What is the constraint associated with job A for the following assignment problem?
$$\begin{array} { l l l l l } & & { \text { Machine } } \\& & { 1 } & { 2 } & { 3 } \\& \text { A } & \$ 3 & \$ 4 & \$ 2 \\\text { Job } & \text { B } & \$ 1 & \$ 3 & \$ 5 \\& \text { C } & \$ 6 & \$ 4 & \$ 2\end{array}$$
Let X?? = 1 if job i is assigned to machine j,otherwise 0.

A)3XA? + 4XA? + 2XA? = 1
B)3XA? + 4XA? + 2XA? = 0
C)3XA? + 4XA? + 2XA? = -1
D)XA? + XA? + XA? = -1
E)-XA? - XA? - XA? = -1

Question 5

Use the information below to answer the following questions.
Consider the following shortest path problem where node 1 is the starting node and node 6 is the destination node.

Refer to the figure.Excluding the non-negativity constraint,this model has:

A)6 decision variables
B)7 decision variables
C)8 decision variables including the dummy arc
D)5 decision variables
E)none of the above

Question 6

Consider the following transshipment problem.The shipping cost per unit between nodes 1 and 2 is $10,while the shipping cost per unit between nodes 2 and 3 is $12.What is the objective function?

A)Min X₁₂ + X₂₃
B)Max X₁₂ + X₂₃
C)Min 10X₁₂ + 12X₁₃
D)Min -10X₁₂ - 12X₁₃
E)Max 10X₁₂ + 12X₂₃

Question 7

Which of the following statements concerning the transshipment model are False?

A)A supply node is one where the total flow into the node is less than the total flow out of the node.
B)A transshipment node is one where the total flow into the node equals the total flow of the node.
C)The flow balance for a demand node should show a positive RHS value.
D)The flow balance for a transshipment node should show a negative RHS value.
E)The flow balance for a supply node should show a negative RHS value.

Question 8

Use the information below to answer the following questions.
Consider the following shortest path problem where node 1 is the starting node and node 6 is the destination node.

Refer to the figure.What is the constraint associated with node 1?

A)X₂₁+ X₃₁ - X₁₂ - X₁₃ = -1
B)X₂₁ + X₃₁ - X₁₂ - X₁₃ = +1
C)X₂₁ + X₃₁ - X₁₂ - X₁₃ =0
D)X₁₂ + X₁₃ = 0
E)-X₁₂ + X₁₃ = -1

Question 9

Use the information below to answer the following questions.
Consider the following maximal flow problem where node 1 is the source and node 6 is the destination.

Refer to the figure.What is the constraint associated with node 2?

A)X₁₂ - X₂₄ = 0
B)X₁₂ - X₃₂ - X₂₄ = 0
C)X₁₂ + X₃₂ - X₂₄ = 1
D)X₁₂ - X₃₂ + X₂₄ = 0
E)X₁₂ + X₃₂ - X₂₄ = 0

Question 10

In an unbalanced transportation problem where total supply exceeds total demand,the supply constraints will typically have "≥" inequalities.

Question 11

Which of the following models determines the path through the network that connects all the points?

A)Transportation model
B)Assignment model
C)Product mix model
D)Shortest-path model
E)Minimal-spanning tree model

Question 12

Use the information below to answer the following questions.
Consider the following maximal flow problem where node 1 is the source and node 6 is the destination.

Refer to the figure.What is the objective function?

A)Max X₁₆
B)Min X₁₆
C)Max X₆₁
D)Min X₆₁
E)Max X₂₆ + X₅₆

Question 13

In an unbalanced transportation problem where total demand exceeds total supply,the demand constraints will typically have "≤" inequalities.

Question 14

In a maximal flow problem,if node 1 is the source and node 2 is the destination,the objective function of the LP problem is to maximize the flow along arc X₁₂ .

Question 15

In a maximal flow problem,the right-hand side of the flow balance constraints equals 1.

Question 16

Use the information below to answer the following questions.
Consider the following maximal flow problem where node 1 is the source and node 6 is the destination.

Refer to the figure.What is the constraint associated with node 1?

A)-X₁₂ - X₁₃ = 1
B)X₆₁ - X₁₂ - X₁₃ = -1
C)X₆₁ - X₁₂ - X₁₃ = 1
D)X₆₁ - X₁₂ - X₁₃ = 0
E)X₆₁ - X₁₂ - X₁₃ = ∞

Question 17

What is the constraint associated with machine 2 for the following assignment problem?
$$\begin{array} { l l l l l } & & { \text { Machine } } \\& & { 1 } & { 2 } & { 3 } \\& \text { A } & \$ 3 & \$ 4 & \$ 2 \\\text { Job } & \text { B } & \$ 1 & \$ 3 & \$ 5 \\& \text { C } & \$ 6 & \$ 4 & \$ 2\end{array}$$

Let X?? = 1 if job i is assigned to machine j,otherwise 0.

A)XA? + XB? + XC? = +1
B)XA? + XB? + XC? = 0
C)XA? + XB? + XC? = -1
D)4XA? + 3XB? + 4XC? = +1
E)4XA? + 3XB? + 4XC? = -1

Question 18

Use the information below to answer the following questions.
Consider the following maximal flow problem where node 1 is the source and node 6 is the destination.

Refer to the figure.What is the constraint associated with node 6?

A)X₄₆ + X₅₆ = 0
B)X₄₆ + X₅₆ = 1
C)X₄₆ + X₅₆ - X₆₁ = 1
D)X₄₆ + X₅₆ - X₆₁ = -1
E)X₄₆ + X₅₆ - X₆₁ = 0

Question 19

All supply and demand quantities in an assignment model equal one unit.

Question 20

Use the information below to answer the following questions.
Consider the following maximal flow problem where node 1 is the source and node 6 is the destination.

Refer to the figure.What is the maximum capacity associated with arc X₆₁?

A)+1
B)-1
C)0
D)+∞
E)-∞

Question 21

In a maximal flow problem,all the net flows are typically zeros.

Question 22

Use this information for the following questions.
The following network describes the hourly volume of traffic that can flow between various communities in Dover County.Assume traffic can flow in both directions between each community at the same rate.What is the maximum flow of cars between Communities 1 and 6 in one hour?

Refer to the network above.Formulate this problem as a linear programming problem.

Question 23

Use this information for the following questions.
Neki Sports Company manufacturers treadmills in factories located in Pittsburgh and Kansas City.These are shipped to regional distribution centers in Chicago,Phoenix,and Philadelphia.Ultimately they are delivered to supply houses in New York and Los Angeles.The available supplies at the factories,demands at the final destinations,and shipping costs are illustrated in the table below.

Refer to the information above.Formulate this problem as a linear programming problem.

Question 24

The starting node of the shortest path problem has a supply value of -1.

Question 25

Use this information to answer the following questions.
Bob Jenkins needs to drive from City 1 to City 7 and would like to find the shortest route between the two.The road system with the distance in miles between cities is shown in the network below.What cities should he travel through to minimize his distance?

Refer to the following Excel spreadsheet model.

Refer to the network above and its associated spreadsheet.
a.What equation should be entered in cell B23?
b.What equation should be entered in cell B27?
c.What equation should be entered in cell I4?

Question 26

In a maximal flow problem,the flow capacity on the dummy arc connecting the destination node to the source node should be set to a very large value.

Question 27

Use this information for the following questions.
The following network describes the hourly volume of traffic that can flow between various communities in Dover County.Assume traffic can flow in both directions between each community at the same rate.What is the maximum flow of cars between Communities 1 and 6 in one hour?

Refer fo the network above and its associated Excel solution shown below.

What values would you enter in the Solver Parameter dialog box for the Excel spreadsheet model?
Set Target Cell:
By Changing Cells:
Subject to the Constraints:

Question 28

The addition of constraints other than supply and demand constraints may cause the optimal solution in network flow models to no longer be integers.

Question 29

It is possible to solve small assignment problems by enumerating all possible outcomes rather than modeling them as linear programming problems.

Question 30

Use this information for the following questions.
The following network describes the hourly volume of traffic that can flow between various communities in Dover County.Assume traffic can flow in both directions between each community at the same rate.What is the maximum flow of cars between Communities 1 and 6 in one hour?

Refer fo the network above and its associated Excel solution shown below.

a.What equation should be entered in cell H4?
b.What equation should be entered in cell B10?
c.What equation should be entered in cell B25?

Question 31

The objective function of an assignment problem may be either maximization or minimization.

Question 32

In a transshipment problem,nodes are considered as either pure supply nodes or pure demand nodes.

Question 33

An assignment model has three jobs and four machines.This problem would be referred to as a balanced assignment problem.

Question 34

The ending node of the shortest path problem has a demand value of +1 associated with it.

Question 35

Use this information to answer the following questions.
Bob Jenkins needs to drive from City 1 to City 7 and would like to find the shortest route between the two.The road system with the distance in miles between cities is shown in the network below.What cities should he travel through to minimize his distance?

Refer to the following Excel spreadsheet model.

Refer to the network above and its associated spreadsheet.What values would you enter in the Solver Parameter dialog box for the Excel spreadsheet model?
Set Target Cell:
By Changing Cells:
Subject to the Constraints:

Question 36

Every node in a network flow problem has a decision variable associated with it.

Question 37

Use this information for the following questions.
Neki Sports Company manufacturers treadmills in factories located in Pittsburgh and Kansas City.These are shipped to regional distribution centers in Chicago,Phoenix,and Philadelphia.Ultimately they are delivered to supply houses in New York and Los Angeles.The available supplies at the factories,demands at the final destinations,and shipping costs are illustrated in the table below.

Refer to the information above. Using Excel, determine how many units should be shipped for all possible origin and destination points (final or intermediate) in the distribution network in order to minimize shipping costs.