Dynamic Programming of Optimum Flows in Lossy Communication Nets

This paper deals with assignments of optimum flows in lossy communication nets. In a lossy communication net, each edge
e
has an edge efficiency factor
\alpha_e (0 \leq \alpha_e \leq 1)
as well as an edge capacity
C_e
. If edge
e
is an edge from node
x
to node
y
, then the flow
\psi(e, x)
entering into node
x
is not only limited by the edge capacity
(0 \leq \psi(e, x) \leq C_e)
but also suffers a loss of
(1 - \alpha_e) \cdot \psi(e, x)
in passing through
e
, consequently,
\alpha_e \cdot \psi (e, x)
emerges from
e
at node
y
. A flow
\psi
with the sending flow value
\hat{t}
at the source and the receiving flow value
\underbrace{t}
at the sink is said to be optimum if there is no flow which has less sending flow value value than
t
while having the same receiving value
\underbrace{t}
. Necessary and sufficient conditions are described for the optimality of flows in Theorem 1 and Theorem 2. Based on these characterizations, dynamic programming of optimum flows in a lossy communication net is devised and demonstrated by an example.