For LastMinute Tutor

profilesajhal-1
Tutorial.NetworkFlowProgrammingandOptimization.pdf

Networks Flow Programming and Optimization

In graph theory, a flow ne twork (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is

called a ne twork, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source , which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a road system, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

Network Flow

The term network flow program describes a type of model that is a special case of the more general linear program. The class of network flow programs includes such problems as the

transportation problem, the assignment problem, the shortest path problem, the maximum flow problem, the pure minimum cost flow problem, and the generalized minimum cost flow problem. It is an important class because many aspects of actual situations, particularly in

Logistics and Supply chains, are readily recognized as networks and the representation of the model is much more compact than the general linear program. When a situation can be entirely

modeled as a network, very efficient algorithms exist for the solution of the optimization problem, many times more efficient than linear programming in the utilization of computer time and space resources.

Network flow

We shall first consider the general network flow problem and then show how a number of common practical problems are variants of this general problem.

General problem

To illustrate the general network flow problem consider the diagram below where we have a

number of sources of material and a number of sinks (or demand points) for material. Typically each source has an upper limit on the amount of material it can supply and each demand point has an associated number indicating the amount of material it needs.

Between the sources and the sinks are intermediate nodes through which material can be shipped (flows) to other intermediate nodes or to the sinks. We also have arcs (essentially directed from the sources to the sinks) where each arc has associated with it:

 an upper limit (or capacity) on the amount of material which can flow down the arc; and

 a cost per unit of material sent down the arc.

An Intermediate node

Between the sources and the sinks are intermediate nodes through which material can be shipped (flows) to other intermediate nodes or to the sinks. We also have arcs (essentially directed from

the sources to the sinks) where each arc has associated with it:

 an upper limit (or capacity) on the amount of material which can flow down the arc; and  a cost per unit of material sent down the arc.

Hence the problem is one of deciding how to supply the sinks from the sources at minimum cost.

This problem is known as the minimum cost network flow problem.

Ford and Fulkerson developed an algorithm (called the " out of kilter" algorithm) for this problem in the early 1960's and this original algorithm has been revised and improved since then. Algorithms for minimum cost network flow are widely available on computers. The minimum

cost network flow problem is a linear program with a special structure. As such specialised algorithms can solve very large problems.

Any problem which can be represented in the form of a picture such as shown above can be

regarded as a minimum cost network flow problem (and hence easily solved).

Below we consider the practical problems which can be regarded as minimum cost network flow problems.

Assignment problem

Consider the table below which shows the cost of allocating 5 jobs to 5 machines Machine Job A B C D E

1 22 30 26 16 25 2 27 29 28 20 32

3 33 25 21 29 23 4 24 24 30 19 26 5 30 33 32 37 31

Which jobs should be allocated to which machines so as to minimize the total cost?

It is clear that this problem can be viewed as a minimum cost network flow problem as below where:

 each source (job) can supply one unit  each sink (machine) demands one unit  each arc has a capacity of one unit of flow and a cost taken from the table above.

Problems of this type are called assignment problems since they involve the assignment of n (in this case n=5) distinct entities to another n distinct entities. For example in the area of production planning we might be interested in assigning operators to machines, or in assigning operators to

jobs, or (as above) in assigning jobs to machines.

This problem was solved using the package (1)

, the input being shown below.

The output is shown below.

Transportation problem

Three factories can supply any of six customers with a particular product. The demand for this

product from each of the customers 1, 2, 3, 4, 5 and 6 is 40, 35, 25, 20, 60 and 30 tons respectively. Maximum production at factories A, B and C is 60, 70 and 80 tons respectively.

The variable production cost per ton is 11.3, 11.0 and 10.8 ($) at factories A, B and C respectively and the transportation cost per ton from each factory to each customer is as shown below.

From Transportation cost ($) per ton to customer

Factory 1 2 3 4 5 6 A 1.5 1.8 3.1 4.2 2.5 3.0 B 2.2 4.6 3.5 2.4 1.8 4.0

C 3.6 4.8 1.6 4.4 2.8 2.0

Determine the quantity of product to be supplied from each factory to each customer so as to minimize total costs.

In order to treat this problem as a minimum cost network flow problem we need first to find the

cost for each factory/customer pair of producing and transporting one ton from the factory to the customer. These costs are obtained by adding the variable production costs to the transportation

costs and are tabulated below.

From Production and trans portation cos t ($) pe r ton to customer factory 1 2 3 4 5 6

A 12.8 13.1 14.4 15.5 13.8 14.3

B 13.2 15.6 14.5 13.4 12.8 15.0 C 14.4 15.6 12.4 15.2 13.6 12.8

It is now clear that this problem can be viewed as a minimum cost network flow problem as

below where:

 each source (factory) can supply as much as the factory can produce  each sink (customer) has demand equal to the associated customer demand  each arc has a capacity equal to the demand of the customer it goes to and a cost taken

from the table above of combined production and transportation costs.

Problems of this type are called transportation problems and typically involve minimising the

cost of transporting goods from production facilities to customers.

Note here that:

 imposing a limit on the amount supplied from a particular factory to a particular customer is merely a matter of setting an arc capacity appropriately

 arcs can be deleted to ensure that particular factories do not supply particular customers.

This problem was solved using the package (1)

, the input being shown below.

The output is shown below.

Note here that customer 1 receives shipments from both A and B. This is normal in solving transportation problems. If we wish each customer to be sourced (supplied) from just a single

factory then the problem becomes a much more difficult problem (in fact it becomes an integer programming problem).

Transshipment problem

Frequently goods are not transported directly from factories to customers but are shipped (transshipped) via intermediate locations (such as depots or warehouses). For example suppose we take the problem we considered above and add the additional information that a new depot

has become available where:

 the depot has a cost per ton of throughput of £0.7  the cost of shipping from factories A, B and C to the depot is 0.1, 0.3 and 0.7 (£ per ton)

respectively  the cost of shipping from the depot to customers 1, 2, 3, 4, 5 and 6 is 0.7, 0.9, 1.1, 0.8, 0.6

and 0.9 (£ per ton) respectively.

This depot can be incorporated into the network flow representation as below .

Here we have added to the graph shown before:

 two new nodes (labelled D1 and D2 below) - D1 representing goods in to the depot (the "front door") and D2 representing goods out of the depot (the "back door")

 an arc between D1 and D2 with capacity equal to the total factory capacity (representing

the maximum amount of throughput that can reach the depot from the factories) and cost 0.7 (representing the cost of throughput)

 arcs from the sources (factories) to D1 of capacity equal to the factory production capacity and cost equal to the combined production and transportation (factory to depot)

cost, i.e. o arc A,D1 capacity 60 cost 11.3 + 0.1 = 11.4

arc B,D1 capacity 70 cost 11.0 + 0.3 = 11.3 arc C,D1 capacity 80 cost 10.8 + 0.7 = 11.5

 arcs from D2 to the customers of capacity equal to the customer demand and cost equal to

the cost of shipping from the depot to the customer, i.e. o arc D2,1 capacity 40 cost 0.7

arc D2,2 capacity 35 cost 0.9 arc D2,3 capacity 25 cost 1.1 arc D2,4 capacity 20 cost 0.8

arc D2,5 capacity 60 cost 0.6 arc D2,6 capacity 30 cost 0.9

Problems of this type are called transhipment problems since they involve the transhipment of

goods via intermediate locations rather than directly from factories to customers.

This problem was solved using the package (1)

. The input is shown below. Note here that this problem is entered as a network flow problem.

The output is shown below.

It can be seen that 155 units flows through the depot (from D1 to D2). If we (for example) restrict that to say 100 units (because the depot cannot cope with more than that) we merely need

to edit the Flows Bounds in the package appropriately. The solution with this capacity limit imposed is shown below.

Comment

As both the transportation and transshipment problems are (computationally) easy to solve "what-if" questions can be asked and answered relatively rapidly, both at the strategic level and

at the tactical level. For example:

 what if the capacity of a factory is substantially increased, how will this affect the overall production and transportation cost?

Increasing factory capacity is a strategic decision and presumably an increase in factory capacity

reduces the variable costs involved in production and transportation. Hence this variable cost reduction should be set against the capital required to increase the factory capacity (a typical

investment decision, balance cost savings against capital investment)

 any tactical changes e.g. in arc costs/capacities or in customer demands can be easily incorporated and the problem resolved.

Both the transportation problem and the transshipment problem are quite widely used for

planning bulk distribution, especially in the USA where the (road) distances travelled are large.

Maximum flow problem

A variation on the general minimum cost network flow problem is the problem of finding the maximum flow that can be sent between a single source and a single sink (as in the diagram

below) where each arc has a capacity (shown in the diagram below next to the arc) which limits the amount of flow which can be sent down it (there being no cost associated with using the arc).

An algorithm for solving this problem was developed by Ford and Fulkerson in the mid 1950's

(i.e. before they developed their "out of kilter" algorithm for solving the minimum cost network flow problem). Problems of this type are called maximum flow problems and appear, for

example, in communication network planning and pipeline (gas/oil/water) network planning.

The problem shown above was solved using the package (1)

, the input being shown below.

The output is shown below.

We can see from that output that the maximum flow that can be sent between the source and the

sink is 7. Note here that there is a theorem (the min-cut max-flow theorem) that says that the

maximum flow possible is equal to the capacity of the minimum cut disconnecting the source and the sink (i.e. a cut that disconnects source and sink and has the minimum (smallest) possible

capacity over all such cuts). In the above problem the min-cut corresponds to the arcs (1,2), (3,2), (3,6) and (4,5) - removing these disconnects the source and the sink (see below) and their

total capacity is 7.

(1). Software details. Previous versions of OR-Notes (since their inception in 1996) have made use of a variety of software pack ages: The Dos version of his software was called "QSB+ Quantitative systems for business

plus" (version 2.1) by Yih-Long Chang and Robert S. Sullivan published by Prentice-Hall. The Windows based version of these pack ages is called WinQSB (also by Yih-Long Chang, but published by Wiley). A copy is available

for use in the course