APM261: Quiz 8. Minimal Cost Network Flows

Quiz 8. Minimal Cost Network Flows

Enter your name:

Each question has only one correct answer. The results of the quiz do not affect the final marks.

1: What is a correct definition of a tree?

A tree is a closed path in the directed connected graph
A tree is the connected graph which has a non-singular node-arc incidence matrix
A tree connects n nodes with n-1 links and may contain cycles
A tree consists of several one-link nodes and one multi-link node called the root

2: Which algorithm solves the minimal cost network flow problems?

Revised simplex algorithm
Dual simplex algorithm
Network implementation of the simplex method
Network implementation of the dual simplex method

3: Consider the minimal cost network flow for a connected graph with 100 nodes and 1001 links. What is the rank of the incidence matrix for this problem?

Rank is 99
Rank is 100
Rank is 1000
Rank is 1001

4: Consider the following network:

Sorry, you need enabled Java to see the applet.

The supply vector b has the values:

b₁ = 2, b₂ = 0, b₃ = 0, b₄ = -2

What is a legitimate initial solution to start the network algorithm?

x₁₂ = 
x₁₃ = x₂₄ = x₃₄ = 1

x₁₂ = 
x₃₄ = 2, x₁₃ = x₂₄ = 0

x₁₂ = 
x₂₄ = 2, x₁₃ = x₃₄ = 0

x₁₂ = 
x₁₃ = x₂₄ = x₃₄ = 0, x₁₄ = 2

5: Consider the following network:

Sorry, you need enabled Java to see the applet.

The supply vector b has the values:

b₁ = 5, b₂ = -2, b₃ = -2, b₄ = 0

The cost coefficients are

c₁₂ = 3, c₂₃ = -1, c₁₄ = 2, c₃₄ = 0

Give a reason why the network should be modified before the use of the network algorithm.

Some of the cost coefficients c_ij are negative. Replace negative coefficients by zeros.
The graph does not have trees. Modify links between existing nodes to transform to a proper graph.
There are two sinks with negative supplies. The network problems may have only one sink and source.
Total supply and demand are not equal. Introduce a dummy node with zero cost.

Your Results: