Adding slack nodes to min cost network flows

Question

I have the following question. I want to clarify couple of points.

As you can see, total demand and total supply does not match, we do not have enough demand. What I want to ask is:

1. Do we need to add a slack node to provide that gap? If yes, would adding one slack node be enough? I mean, if we had a gap in supply I believe we had to, but for this case, I could not be sure.

2. If we add a slack node, what cost value we assign for the arc that carries the "needed" supply/demand?

3. Does adding a slack node change anything about the other arcs, do we need to remake our calculations?

I am asking for both insufficient demand and supply cases.

My attempt: I am not very sure about my model as I couldn't figure out how the slack node should be but, I thought $x_{12}=3$ , $x_{24}=4$ and $x_{32}=2$. ($x_{ij}=$flow from node i to node j). $z=15$.

Linear program I created is as follows:

$Min$ $x_{12}+3x_{13}+4x_{24}-2x_{32}+3x_{34}$

$s.t$ $x_{12}+x_{34}=4$

$-x_{12}+x_{24}=-1$

$x_{13}-x_{32}-x_{34}=2$

$x_{24}+x_{34}=-4$

Answer 1

Whether you need a dummy node to absorb excess flow depends on the method you are using for solving the problem. (For instance, if you are using an LP model then you do not need the dummy node.) If you do need it, one dummy node will suffice. You assign it demand = excess supply and run a zero-cost arc from each supply node to the dummy node. No other changes to the network are required.

For the excess demand case, you can do the same with a single dummy supply node (supply = excess demand) and zero cost arcs to the various demand nodes.

Caveat: The above works if there is no cost for excess supply / unmet demand or the cost of excess supply / unmet demand is constant regardless of where it occurs. That's not awesomely realistic. If excess supply is stored or disposed of, and that cost varies by supply node, then you still only need one dummy demand node, but the cost of the arc from each supply node to the dummy should equal the unit storage/disposal cost at that supply node. The case of customer-specific shortfall costs when demand exceeds supply is analogous: one dummy supply node but with the cost of the arc to each demand node equal to the unit shortfall cost.