Question

How many constraints are there in a transshipment problem that has n nodes and m arcs (ignoring any upper or lower bounds on the decision variables)?

a) n
b) m
c) n + m
d) n * m

Answer 1

In a transshipment problem with n nodes and m arcs, there will be n constraints representing the flow balance at each node, making the correct answer a) n.

Step-by-step explanation:

In a transshipment problem, which is a type of network flow problem in optimization, the number of constraints is dictated by the number of nodes in the network. Each node has a constraint representing the balance between incoming and outgoing flows, ensuring that the amount shipped to a node either stays there or continues to another node. Therefore, for a transshipment problem with n nodes and m arcs, ignoring any bounds on decision variables, there will be exactly n constraints.

These constraints ensure the conservation of flow at each node, which means the sum of inflows minus the sum of outflows must equal the supply or demand at that node. As such, having m arcs only affects the number of possible paths or decisions, not the number of constraints. So the correct answer is: a) n.