Question A4. Ignoring the xij = 0 or xij = 1 restriction in the linear programming problem presentation of the
assignment problem, an assignment problem can be viewed as a special case of balance
transportation problem in which each supply point has a supply of ___________________
unit(s) and each demand point has a demand of ___________________ unit(s).
A. infinity; infinity
B. finity; finity
C. 0; 0
D. 1; 1
E. None of the above
F. All of the above
G. Uncertain
Question A5. The (___________________) defines the shortest route between the origin and the destination;
the (___________________) defines the maximum length that can be transported from a given
source to a given sink; while the (___________________) problem defines the minimum path
between each pair of nodes.
A. (shortest-path problem) ; (maximum flow problem) ; (minimum spanning tree)
B. (shortest-path problem) ; (minimum spanning tree) ; (maximum flow problem)
C. (minimum spanning tree) ; (shortest-path problem) ; (maximum flow problem)
D. (minimum spanning tree) ; (maximum flow problem) ; (shortest-path problem)
E. (maximum flow problem) ; (shortest-path problem) ; (minimum spanning tree)
F. (maximum flow problem); (minimum spanning tree) ; (shortest-path problem)
G. All of the above
H. None of the above
I. Uncertain
Question A6. Given three nodes i, j, and k, it is shorter to reach j from i passing through k if dik + dkj < dij and
in that case, it is optimal to replace the direct route from i → j with the indirect route i → k →
j. This defines the triple operation exchange applied in the (___________________) to the
distance matrix to reach the shortest route when solving shortest path problem.
A. Prim’s algorithm
B. Dijkstra’s algorithm
C. Kruskal’s algorithm
D. Floyd’s algorithm
E. Recursive computation algorithm
F. All of the above
G. None of the above
H. Uncertain
Page 3 of 12
Question A4. D. 1; 1
Question A5. B. (shortest-path problem) ; (minimum spanning tree) ; (maximum flow problem)
Question A6. D. Floyd’s algorithm