Deck 6: Network optimization problems

Question 1

As long as all its supplies and demands have integer values,any minimum cost flow problem is guaranteed to have an optimal solution with integer values

Answer 1

True

Question 2

In a minimum cost flow problem,the cost of the flow through each arc is proportional to the amount of that flow

Answer 2

True

Question 3

A minimum cost flow problem will have feasible solutions as long as there is a balance between the total supply from the supply nodes and the total demand at the demand nodes

Answer 3

True

Question 4

Any minimum cost flow problem where each arc can carry any desired amount of flow is a transshipment problem

Question 5

The network simplex method can aid managers in conducting what-if analysis

Question 6

In a minimum cost flow problem there can be only one supply node and only one demand node

Question 7

Any node where the net amount of flow generated is fixed at zero is a transshipment node

Question 8

In a feasible minimum cost flow problem,the network has enough arcs with sufficient capacity to enable all the flow generated at the supply nodes to reach all the demand nodes

Question 9

A transportation problem is just a minimum cost flow problem without any transshipment nodes and without any capacity constraints on the arcs

Question 10

The network simplex method can be used to solve minimum cost flow problems with over a million arcs

Question 11

Conservation of flow is achieved when the flow through a node is minimized

Question 12

Each node in a minimum cost flow problem where the net amount of flow generated is a fixed positive number is a demand node

Question 13

A network representation is a very specific conceptual aid and is only used in special cases

Question 14

The amount of flow that is eventually sent through an arc is called the capacity of that arc

Question 15

The objective of a minimum cost flow problem is to minimize the total cost of sending the available supply through the network even if all demand is not satisfied

Question 16

Network representations can be used for financial planning

Question 17

Minimum cost flow problems are the special type of linear programming problem referred to as distribution-network problems

Question 18

All network optimization problems actually are special types of linear programming problems

Question 19

The model for any minimum cost flow problem is represented by a network with flow passing through it

Question 20

A minimum cost flow problem may be summarized by drawing a network only after writing out the full formulation

Question 21

Which of the following can be used to optimally solve minimum cost flow problems?

A)The simplex method
B)The network simplex method
C)A greedy algorithm
D)a and b only
E)All of the above

Question 22

In a shortest path problem there are no arcs permitted,only links

Question 23

Shortest path problems are concerned with finding the shortest route through a network

Question 24

In a true maximum flow problem there is only one source and one sink

Question 25

Which of the following will have negative net flow in a minimum cost flow problem ?

A)Supply nodes
B)Transshipment nodes
C)Demand nodes
D)Arc capacities
E)None of the above

Question 26

Maximum flow problems are concerned with maximizing the flow of goods through a distribution network

Question 27

The objective of a maximum flow problem is to maximize the total profit generated by sending flow through a network

Question 28

In a shortest path problem,the lines connecting the nodes are referred to as arcs

Question 29

A shortest path problem is required to have only a single destination

Question 30

The source and sink of a maximum flow problem have conservation of flow

Question 31

Which of the following is an example of a transshipment node?

A)Storage facilities
B)Processing facilities
C)Short-term investment options
D)Warehouses
E)All of the above

Question 32

When reformulating a shortest path problem as a minimum cost flow problem,each link should be replaced by a pair of arcs pointing in opposite directions

Question 33

The source and sink of a maximum flow problem are analogous to the supply nodes and demand nodes of a minimum cost flow problem

Question 34

A network model showing the geographical layout of the problem is the usual way to represent a shortest path problem

Question 35

Network representations can be used for the following problems:

A)project planning
B)facilities location
C)financial planning
D)resource management
E)all of the above

Question 36

A maximum flow problem can be fit into the format of a minimum cost flow problem

Question 37

A minimum cost flow problem is a special type of:

A)linear programming problem
B)transportation problem
C)spanning tree problem
D)transshipment problem
E)maximum flow problem

Question 38

In a maximum flow problem,the source and sink have fixed supplies and demands

Question 39

In a maximum flow problem,flow is permitted in both directions and is represented by a pair of arcs pointing in opposite directions

Question 40

Which of the following is not an assumption of a minimum cost flow problem?

A)At least one of the nodes is a supply node
B)There is an equal number of supply and demand nodes
C)Flow through an arc is only allowed in the direction indicated by the arrowhead
D)The cost of the flow through each arc is proportional to the amount of that flow
E)The objective is either to minimize the total cost or to maximize the total profit

Question 41

Which of the following is an application of a shortest path problem?

A)I and II only
B)I,II,and III only
C)IV only
D)I,II,III,and IV
E)I,III,and IV only

Question 42

Which of the following is not an assumption of a shortest path problem?

A)The lines connecting certain pairs of nodes always allow travel in either direction
B)Associated with each link or arc is a nonnegative number called its length
C)A path through the network must be chosen going from the origin to the destination
D)The objective is to find a shortest path from the origin to the destination
E)None of the above

Question 43

What is the objective of a maximum flow problem?

A)Maximize the amount flowing through a network
B)Maximize the profit of the network
C)Maximize the routes being used
D)Maximize the amount produced at the origin
E)None of the above

Question 44

Which of the following could be the subject of a maximum flow problem?

A)Products
B)Oil
C)Vehicles
D)All of the above
E)None of the above

Question 45

In a shortest path problem,when "real travel" through a network can end at more than one node:

A)an arc with length 0 is inserted
B)the problem cannot be solved
C)a dummy destination is needed
D)c only
E)a and c only

Question 46

Which of the following problems are special types of minimum cost flow problems?

A)I and II only
B)I,II,and III only
C)IV only
D)I,II,III,and IV
E)None of the above

Question 47

For a minimum cost flow problem to have a feasible solution,which of the following must be true?

A)There is the same number of supply nodes and demand nodes
B)There is only one supply node and one demand node
C)There is an equal amount of supply and demand
D)The supply and demand must be integers
E)The transshipment nodes must be able to absorb flow

Question 48

Which of the following is not an assumption of a maximum flow problem?

A)All flow through the network originates at one node,called the source
B)If a node is not the source or the sink then it is a transshipment node
C)Flow can move toward the sink and away from the sink
D)The maximum amount of flow through an arc is given by the capacity of the arc
E)The objective is to maximize the total amount of flow from the source to the sink