0
$\begingroup$

I have the following graph for a minimal cost flow problem. Usually in this type of problem the demand = supply. However here we have 30 of supply and only 16 of demand.

I'm tasked with adding a node to the graph to make sure that the surplus of the supply is absorbed by this node. However, I'm not sure how to do that. It must not change an optimal solution to the problem. My instinct is to just add a node linked to all three suppliers. Each edge will have a maximum capacity of 6 like all the other edges in the graph.

enter image description here

$\endgroup$
1
  • $\begingroup$ It´s not obvious what the meanings of the numbers at the edges and nodes are. Please explain. $\endgroup$ – callculus Nov 9 '20 at 21:05
1
$\begingroup$

Yes, add a dummy sink node with demand 14. (Your figure shows supply 40 and demand 10, though.) Yes, add links from suppliers to the dummy sink node, but you do not need any capacities or costs for the dummy links.

$\endgroup$
1
  • $\begingroup$ I made a mistake in my figure sorry! $\endgroup$ – WindBreeze Nov 9 '20 at 21:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.