2-504-09 Lecture Notes - Lecture 9: Row And Column Vectors, Hazardous Waste, Slack Variable
2-604-15 Lecture notes
1"
4. Network flow models
Jacques Desrosiers and Jean Bertrand Gauthier (December, 2015)
Management problems structured around network flow models are legion; see the following web
site for several examples: web network.
https://www.google.ca/search?q=web+network&biw=1000&bih=603&tbm=isch&imgil=lyHiJ2gl-
8jn6M:;7AHUN4K6krspNM;http://www.cugelman.com/online-research/united-nations-web-
network/&source=iu&pf=m&fir=lyHiJ2gl-8jn6M:,7AHUN4K6krspNM,_&usg=__lCySzDFNd-_dBh-
7LDJsrvjT1QU=&ved=0ahUKEwjEif_bgK7JAhXJbiYKHR_zCMIQyjcIQQ&ei=u-
9WVoTAAsndmQGf5qOQDA#imgrc=KLZjMuNpCmmjhM:&usg=__lCySzDFNd-_dBh-7LDJsrvjT1QU=
This chapter aims to present a unified modeling structure for five classical models: minimum cost
flow, shortest path, maximum flow, transportation, and assignment. Figure 1 illustrates the logical
relations between these problems, the most general one serving as an umbrella at the top. Section
4.1 serves as an introduction for network flows while Section 4.2 presents the terminology. In the
following Sections 4.3—4.7, we dive into specific network models following the ordered logical
relations listed prior.
Figure 1. Logical relations between network flow problems
find more resources at oneclass.com
find more resources at oneclass.com
2-604-15 Lecture notes
2"
4.1 Introduction
The transportation and logistics industries might be the most prominent examples of network flow
models applications. For instance, Figure 2 displays a simplified representation of a natural gas
pipeline delivery network (Source: CEPA – Canadian Energy Pipeline Association (2013).
Natural gas pipelines. Available online at: http://www.cepa.com/about-pipelines/types-of-
pipelines/natural-gas-pipelines.)
Figure 2. Simplified representation of a natural gas pipeline delivery network
In this system, the natural gas is being transported from one location to another using the pipeline
delivery network. Among these locations one may distinguish the following purposes:
1. Producing wellheads where raw natural gas is extracted.
2. Underground storage facility.
3. Processing plant where raw natural gas is cleansed.
4. Compressor stations where pressurizing techniques are applied to push gas into the pipelines.
5. City gate corresponding to a local distribution center.
6. Consumers, for example, residual customers or commercial customers like a power station.
Furthermore, each pipeline has its own specificities. Think in particular of the different diameters
depending on where they lead thus impacting the amount of natural gas they can carry at any given
time. The very physical aspect of this applied problem can actually be abstracted using
mathematical objects. Each location may be defined as a node, a pipeline as an arc and finally the
natural gas as the flow. This paves the way for mathematical programming models but let us first
define additional terminology.
find more resources at oneclass.com
find more resources at oneclass.com
2-604-15 Lecture notes
3"
4.2 Terminology
In an optimization model, whether it is a number of people or email transferred, or a quantity of
cars or like in the preceding example the amount of natural gas, the flow circulating on each arc is
an unknown value that we aim to determine through optimization. Observe that an arc links a tail
node ! to a head node " thus meaning it is explicitly directed, an assumption silenced from now.
Let A be the set of arcs and let the non-negative flow associated with the arc !# " $ % be captured
by the arc variable &'(. This variable is always contained between a lower bound and an upper
bound, i.e., )'( * &'( * +'(, both bounds being known parameters. Recall for instance the diameter
of a pipeline for the upper bound, giving a practical meaning of capacity for the latter.
Furthermore, each flow unit passing on the arc ,!# "- contributes to the objective function
proportionally to the coefficient .'(, another known parameter.
Let N be the set of nodes. A node also conveys meaning in the network. For example, a node
associated with a producing wellhead introduces raw natural gas flow units in the network
according to the production level. Likewise, a node associated with a residual customer extracts
flow units from the network according to the demand. In this respect, given a node identified by
index / $ 0, a supply 123 4 is associated with a source node and a demand 523 4 is associated
with a destination (or sink) node. Finally, a transshipment node refers to a node where there is
neither supply nor demand. By combining all of these components, one obtains a directed network
defined by the sets of arcs % and the set of nodes 0. Take a look at Figure" 3 that puts all of this in
practice for the first example.
Figure"3.""Network"for"Example(1"
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Jacques desrosiers and jean bertrand gauthier (december, 2015) Management problems structured around network flow models are legion; see the following web site for several examples: web network. https://www. google. ca/search?q=web+network&biw=1000&bih=603&tbm=isch&imgil=lyhij2gl- This chapter aims to present a unified modeling structure for five classical models: minimum cost flow, shortest path, maximum flow, transportation, and assignment. Figure 1 illustrates the logical relations between these problems, the most general one serving as an umbrella at the top. 4. 1 serves as an introduction for network flows while section 4. 2 presents the terminology. In the following sections 4. 3 4. 7, we dive into specific network models following the ordered logical relations listed prior. The transportation and logistics industries might be the most prominent examples of network flow models applications. For instance, figure 2 displays a simplified representation of a natural gas pipeline delivery network (source: cepa canadian energy pipeline association (2013). Simplified representation of a natural gas pipeline delivery network.
