Maximum Flow Model

It is about linking a source node and a destination node through a network.

of directed arcs. Each arc has a maximum admissible flow capacity.
The objective is to obtain the maximum flow capacity between the source and the
destination.
Characteristics:
1. All flow through a directed connected network originates at a node,
called source, and ends in another node called destination.
The remaining nodes are transshipment nodes.
3. Flow through an arch is only allowed in theaddressindicated by the
arrow, where the maximum flow amount is given by the capacity of the
arch. In the fountain, all the arches point outward. At the destination,
everyone points to the node.
4. The objective is to maximize the total amount of flow from the source to the destination.
This amount can be measured in either of the two equivalent ways,
this is, the amount that comes out of the source or the amount that goes into the
destination.

The maximum flow problem can be formulated as a problem of

programminglinear, it can be solved with ethe methodsimple and use any
software.However, there is an algorithm for augmented trajectories
much more efficient. The algorithm is based on two intuitive concepts, that of
red residual and that of increased trajectory.

Increasing trajectory algorithm for the maximum flow problem:

1. An upward trend is identified by finding some trajectory.
directed from the origin to the destination in the residual network, such that each arc over
this trajectory has strictly positive residual capacity. (If not
there is one, the assigned net flows constitute a flow pattern
optimal)
2. The residual capacity c* of this trajectory of increase is identified.
finding the minimum of the residual capacities of the arcs over
this trajectory. The flow of this trajectory increases in c*.
3. The residual capacity of each arc in this trajectory is reduced by c*.
of increase. The residual capacity of each arc is increased by c* in the
opposite direction on this trajectory. Return to step 1.
 Shortest path model

Consider a connected, undirected graph with two special nodes.

called origin and destination. Each linkage (undirected arc) is associated with a
non-negative distance. The goal is to find the shortest path (the trajectory
with the minimum total distance) from the origin to the destination.

There is a fairly simple algorithm for this problem. The

essence of theprocedureit analyzes the entire network from the origin;
successively identify the shortest path to each of the nodes in
ascending order of their distances (shortest), from the origin; the problem
it is resolved at the moment of reaching the destination node.

Shortest path algorithm:

1. Objective of the n-th iteration: to find the n-th nearest node
to the origin. (This step will be repeated for n=1,2,… until the n-th node
the closer the destination node.
2. Data for the n-th iteration: n-1 closest nodes to the origin
(found in previous iterations), including its shortest path and the
distance from the origin. (These nodes and the origin are called nodes
resolved, the rest are unresolved nodes.)
3. Candidates for the n-th nearest node: Each resolved node that
it has a direct connection through a link with one or more unresolved nodes
provide a candidate, and this is the unresolved node that has the
shorter tie. (Ties provide additional candidates.)
4. Calculation of the n-th nearest node: for each resolved node and its
candidates, the distance between them is added to the distance of the route most
cut from the origin to this resolved node. The candidate with the distance
the smallest total is the n-th nearest node (ties
they provide additional resolved nodes), and its shortest route is the one that
generate this distance.
 Network minimization model

The network minimization model or minimum spanning tree problem

expansion has to do with the determination of the branches that can connect
all the nodes of a network, such that it minimizes the sum of the lengths of the
selected branches. Cycles should not be included in the solution to the problem.

To create the minimum spanning tree, it has the following characteristics:

1. The nodes of a network are available but not the connections. Instead, they
they provide potential ligatures and the positive length for each
a yes is inserted into the network. (Alternative measures for length of
a binding includes distance, cost andtime.)
2. It is desired to design the network with enough ties to meet the
Requirement that there is a path between each pair of nodes.
3. The goal is to meet this requirement in such a way as to minimize the
total length of the ligatures inserted into the network.

A network with n nodes requires only (n-1) links to provide a

trajectory between each pair of nodes. The (n-1) bonds must be chosen in such a way
so that the resulting network forms a spanning tree. Therefore the
the problem is to find the spanning tree with the minimum total length of its
ligatures.
Algorithm to construct the minimum spanning tree:
1. Any node is selected arbitrarily and is connected (it is
to say, a link is added to the nearest different node.
2. The closest unconnected node to a connected node is identified and
these two nodes are connected (that is, a bond is added between
This step is repeated until all nodes are connected.
3. Ties: the ties for the nearest distinct node (step 1) or for
the nearest disconnected node (step 2), can be broken in shape
arbitrary and the algorithm must arrive at an optimal solution. However,
these ties are a sign that they may exist (but not necessarily)
solutionsmultiple optimizations. All those solutions can be
identify whether the other ways of breaking ties are being used
until the end.
 MINIMUM COST FLOW PROBLEM

The minimum cost flow problem has a central position among

network optimization problems; first, it encompasses aclassbroad of
applications and second, its solution is very efficient. Just like the problem of the
maximum flow, take into account a flow in a network with limited capacities in
your arches. Just like the shortest path problem, consider a cost (or
distance) for the flow through an arc. Just like the transportation problem
or the one for assignment, can handle multiple sources (source nodes) and several
destinations (demand nodes) for the flow, again withcostsassociates. From
Indeed, these four problems are special cases of the flow problem.
minimum cost.

The minimum cost flow problem is described below:

The network is a connected directed graph.
At least one of the nodes is a source node.
At least one of the nodes is a demand node.
4. The rest of the nodes are transfer nodes.
5. Flow through an arch is permitted only in the direction indicated by the
arrow, where the maximum flow is given by the capacity of the
arc. (If the flow can occur in both directions, it must be represented
for a pair of arches with opposite directions.)
The network has enough arcs as sufficient capacity to allow
that all flows generated by the source nodes reach the nodes
demand.
7. The cost of flow through the arch is proportional to the amount of that
flow, where the cost per unit is known.
The goal is to minimize the total cost of sending the available supply to.
through the network to meet the given demand. (An alternative objective
it is to maximize the total shipping profit.)
 FORMULATION OF EXAMPLES

Minimum Cost Flow Problem (Example)

The DISTRIBUTION UNLIMITED CO. will manufacture the same new one.productin two
different plants and then it will have to send it to two warehouses. The network of
available distribution for the shipping of this product is shown in the figure,
where A and B are the factories, D and E are the warehouses, and C is the center of
distribution. The quantities that must be sent from A and B are shown at the
left, and the amounts that must be received in D and E are shown to the
right. Each arrow represents a feasible shipping channel. A can send
directly to D and has three possible routes (A C E, A B C E and A
D E) for sendinggoodsFactory B has only one route to E. C
E) and one to D (B C E D). The cost per unit sent through each
the channel is shown next to the arrow. Also, next to A B and C E are
show the maximum amounts that can be sent through these channels. The
other channels have enough capacity to handle everything that the factories
they can send.
The decision to be made concerns how much to send through each channel.
distribution. The goal is to minimize the total shipping cost.
Formulation:
Minimize

Subject to:
PRACTICAL APPLICATION OF THE MINIMUM COST FLOW PROBLEM

The most important type of application of the cost flow problem

minimum is in the operation of a company's distribution network. In the
The following table shows some common types of applications of the
minimum cost flow problem:

Application Type Nodes of Nodes of

Transshipment Demand

Operation of a Sources of Warehouses Consumers

distribution network goods intermediates

Management of Source of Facilities of Fillings

solid waste solid waste processing

Operation of a Agents of Warehouses Facilities of

supply network sales intermediates processing

Coordination of plants Production of u Market of

mix of products specific product article
in plants specific

Administration of Sources of Options of Needs of

cash flow cash in investmentshort cash in
times period times
specific specific
 TRANSPORT PROBLEM(DATATOOLS)

A node is provided forresourcesfor each origin and a node of

demand for each destination but transshipment nodes are not included in the network.
All arcs are directed, from the resource node to the node of
demand, where to distribute units from origin i to destination j correspond
to a flow through the arch The cost per distributed unit it
convert it into the cost per flow unit.

FORMULATION AS A LINEAR PROBLEM

Formulation as a LP of the minimum cost flow problem

Consider a connected directed graph in which the n nodes include at least one
origin node and at least one destination node. Thevariablesof decision are:

flow through the arch , and theinformationdad includes:

cost per unit of flow through the arch ,

arc capacity ,

net flow generated at node i.

Ethe valueit depends on thenaturefrom node i, where

, if it is a source node,
, if it is a demand node,

yes, it is a transshipment node.

The goal is to minimize the total cost of sending the available resources to
through the network to meet the given demand.
Using the convention that sums are taken only over existing arcs,
the linear programming formulation of this problem is
Minimize
Subject to,

for each node i,

y

for each arc .

The first sum in the node constraints represents the total flow that
exits from node i while the second represents the total flow that enters the
node i, thus, the difference is the net flow generated at this node.

In some applications, it is necessary to have a lower bound. for the

flow that passes for each arc When this happens, a
conversion of variables , where is replaced by in everything
the model, in order to adjust the model to the previous format with non-restrictions
negativity.
It is not guaranteed that the problem has feasible solutions, it depends on
part of which arcs are present in the network and their capabilities. Of
in any case, for a reasonably designed network, the condition
the following is the most important necessary.

Property of feasible solutions: a necessary condition for a

the minimum cost flow problem has feasible solutions is that

.
That is, the total flow generated at the source nodes is equal to the total flow.
absorbed by the destination nodes.
Formulation as a PL of the shortest path problem

The LP model of the shortest path is constructed as follows:

Each variable corresponds to an arc.
2. Each constraint corresponds to a node.

Therefore, if represents the amount of flow in the arc (i,j), the model of the
the shortest path with n nodes is given as:

Minimize
Subject to:

(source)

for all k 1 or n

(destination)

for all i and j.

The first and last constraint indicates that the total flow (sum of variables) that
the output from node 1 is equal to 1 and the total flow received at node n also
is equal to 1. At any intermediate node, the total flow entering the node is
equal to the total flow that leaves the same node. Thefunctionobjective requires that it be
minimize the total distance traveled by the flow unit.