Solving
the network optimization problem
The objective
of the problem is the identification of the appropriate flow values xij
in the network that minimize the total transportation cost, namely:
minimize
c x = Σcij
xij
The mathematical constraints
are a) the continuity equations at each node of the digraph and
b) the capacity constraints at at each arc of the digraph. The
continuity equations can be written in the matrix form:
A
x = y
where A is
the incidence matrix of the digraph, describing the topology of
the network (i.e., the connections between the nodes and the arcs and,
moreover, the flow directions). The elements of A take their values
from the set {1, -1, 0}. The
capacity constraints can be written in the matrix form:
0
<= x <= u
The above
optimization model, also known as the transshipment problem, can
be very easily and quickly solved via trivial methods, like the simplex
algorithm.
|
Home
page 
greek pages
