Power Network

A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node $u$ may be supplied with an amount s(u) \geq 0 of power, may produce an amount 0 \leq p(u) \leq p_{\text{max}}(u) of power, may consume an amount 0 \leq c(u) \leq \min(s(u), c_{\text{max}}(u)) of power, and may deliver an amount d(u) = s(u) + p(u) - c(u) of power. The following restrictions apply: c(u) = 0 for any power station, p(u) = 0 for any consumer, and p(u) = c(u) = 0 for any dispatcher. There is at most one power transport line $(u,v)$ from a node $u$ to a node $v$ in the net; it transports an amount 0 \leq l(u, v) \leq l_{\text{max}}(u, v) of power delivered by $u$ to $v$. Let Con = \sum_u c(u) be the power consumed in the net. The problem is to compute the maximum value of $Con$.

An example is in figure. The label $x/y$ of power station $u$ shows that p(u) = x and p_{\text{max}}(u) = y. The label $x/y$ of consumer $u$ shows that c(u) = x and c_{\text{max}}(u) = y. The label $x/y$ of power transport line $(u,v)$ shows that l(u, v) = x and l_{\text{max}}(u, v) = y. The power consumed is Con = 6. Notice that there are other possible states of the network but the value of $Con$ cannot exceed $6$.