Question

(a) The Assignment Problem can be modeled as a Transportation Problem: yes no it depends Explanation: (b) The Transportation Problem can be modeled as a Generalized Network Flow Problem: yes no it depends Explanation: (c) The Generalized Network Flow Problem with multiple source and sink nodes can be converted to a Generalized Network Flow Problem with only one source and one sink node: yes no it depends Explanation: (d) Negative arc weights in the Shortest Path Problem can never occur in real life: yes no Explanation:

Answer 1

(a)

Yes

Reason - The assignment problem is a special case of the transportation problem. It deals with assigning n origins (workers, for instance) to n destinations (jobs or machines, for instance,) with the goal of determining the minimum cost assignment. Each origin must be assigned to one and only one destination, and each destination must have assigned one and only one origin. cij represents the cost of assigning the origin Oi to the destination Dj , i, j = 1, . . . , n.

(b)

Yes

Reason - The term network flow program describes a type of model that is a special case of the more general linear program. The class of network flow programs includes such problems as the transportation problem, the assignment problem, the shortest path problem, the maximum flow problem, the pure minimum cost flow problem, and the generalized minimum cost flow problem.

(c)

Yes

Reason - Multiple-sources multiple-links problem can be converted to a single-source and single-sink problem by Introducing a dummy source node that is connected to the original source nodes with infinite capacity links (or) Introducing a dummy sink node that is connected with the original sink nodes with infinite capacity links

(c)

No

Reason - Dijkstra relies on one simple fact that if all weights are non-negative, adding an edge can never make a path shorter. By this statement we can say that if there are negative weights we can get the shortest path can occur in real life and hence NO for this statement.