NETWORK FLOW MODELS
ISL323E- OPERATIONS RESEARCH
DR. AZİZ KEMAL KONYALIOĞLU
15th Dec, 2025
konyalioglua@[Link]
Class Hours: Monday 14.30/17.30
Tuesday 14.30/17.30
CONTENT FOR TODAY
¡ Why is it important?
¡ General formulation of network-flow models
¡ Examples
NETWORK FLOW MODELS
¡ Proctor & Gamble makes and markets over 300 brands of consumer goods worldwide.
¡ In the past, P & G had hundreds of suppliers, over 60 plants, 15 distributing centers, and over 1000 consumer
zones.
¡ Managing item flows over the huge supply network is challenging!
¡ An LP/IP model helps.
¡ The special structure of network transportation must also be utilized.
¡ $200 million are saved after an OR study!
NETWORK FLOW MODELS
¡ A lot of operations are to transport items on a network.
¡ Moving materials from suppliers to factories.
¡ Moving goods from factories to distributing centers.
¡ Moving goods from distributing centers to retail stores.
¡ Sending passengers through railroads or by flights.
¡ Sending data packets on the Internet.
¡ Sending water through pipelines and many more.
¡ A unified model, the minimum cost network flow (MCNF) model, covers many network operations.
¡ It has some very nice theoretical properties.
¡ It can also be used for making decisions regarding inventory, project management, job assignment, facility location, etc.
NETWORK FLOW MODELS
¡ A network (graph) has nodes (vertices) and arcs (edges/links).
¡ A typical interpretation: Nodes are locations and arcs are roads.
¡ Arcs may be directed or undirected.
¡ For an arc from u to v: (u, v) if directed and [u, v] if undirected.
¡ In this lecture, all arcs are directed.
¡ A network is directed if its arcs are directed.
¡ An undirected network is also called a graph (by some people).
¡ A path (route) from node s to node t is a set of arcs
¡ (s, v1), (v1, v2), ..., (vk−1, vk), and (vk, t) such that s and t are connected.
¡ ) A cycle (equivalent to circuit in some textbooks) is a path whose destination node is the source node.
¡ ) A path is a simple path if it is not a cycle.
¡ ) A network is an acyclic network if it contains no cycle.
NETWORK FLOW MODELS
Flows, weights, capacities
¡ A flow on an arc is the action of sending some items through the arc.
¡ The number of units sent is called the flow size.
¡ A network flow is the collection of all arc flows.
¡ A network flow is just a plan for making flows on all arcs.
¡ An arc may have a weight.
¡ A weight may be a distance, a cost per unit flow, etc.
¡ A weighted network is a network whose arcs are weighted.
¡ An arc may have a capacity constraint.
¡ There may be an upper bound and/or an lower bound (typically 0) for its flow size.
¡ A network is capacitated if there is an arc having capacity limits.
NETWORK FLOW MODELS
NETWORK FLOW MODELS
m!n mol!gette g!t
demand
object!ve func
.
eepes!!md!yet
te - Xe 2
≤ 12
θ X13[20
4Xe2 + 3xez + ----o 亠 X
λ 23
24 ≤ 12
≤ 2o
s t
X
-
^ 25
ç!za-g!ren
\
×
z4
M
X
X
12 + X13
- 0 = 25 demand
35
X 45
_
ー
10 X53
445
-
*
y34
=
+ -
84
_
MINIMUM COST NETWORK FLOWS
+ 1
-
9
=
ottrassh!pment danad el!m!zde yönlü , kapas!tel! ve ağırlıklı b!r ağ var .
G =
(0 , E)
25> o
t
=d!s!ns
supply
denand E =
yaylar ,
kanalar
Duğum türler!
b! s o
tsupply node
b! < O- demand node
25 =
( ot (
b!= o - transh!pmentnode
Y
problem freas!ble
Ʃ b! = o
yaylar :
(v!j ,
< !j) ! EO
dd
Kopos!te b!r!m mal!yet
l!st sur) toplan arzz toplan talep
örnez : (1 + 2) 15
:
, $) '
)
r -
<$
>(: 20 ,
3 )
2 + 3) : 10 e
∞
dec!s!on var!ables
X!j = (! >-
j) yayı üzer!ndek! akış m!ktarı
tüm (!jj) & E !ç!n tanımlanır .
amaç fonks!yonu
4X12 -X 13 + 2x 23 +2x +3X
m!n
24 25
+
2x34 +14
25
+
2x45 4X38 +
5 katsayılar b!r!m mal!yetler .
model!n tom matemat!ksel formu
m! Gx 12 + Bx 1y + 2x2y + 2x24 + 2x25 + 2x34 + X35 + 2x45 + Gx5]
s!t
Kapos!te surler
X12 + X13 = 25
o X!j[V!j & X12[15 -
X12 +
x23 +
x24
+
X25 = 0
×5 0
× t
434 t × } =
X13[20
-
13 423 35
- -
X 5315
×
2みー × 3み ← ×
み5
ニー (O
35 *
-
+ x =
17
-
Flow Bolance Constra!nts 45 5z
kurd Çıkan akış akış b! O X!jV!j (! , EE
gene g!ren
-
d!sum (transsh!pment bod dujum 5 (demand b5 15)
d!sum 1/ supply , b , 25) 3 , = -
= ,
·
*5 + X 53 15
*
85435
-
-
= -
+ X
125 × 13
*
13 x + X
x5z = 0
-
23 34 35
-
X
-
= 25
duğum G (demand -10)
·
d!sum 2 ( transsh!pment , be = o) , bu =
x24
-
-
x34 +
Xe = -
10
-
X12 + X23 + X24 +
y25 =
0
一
MINIMUM COST NETWORK FLOWS
'
MINIMUM COST NETWORK FLOWS
MINIMUM COST NETWORK FLOWS
ASSIGNMENT PROBLEMS
TRANSSHIPMENT PROBLEMS
SHORTEST PATH PROBLEMS
MAXIMUM FLOW PROBLEMS
AN OVERVIEW
AN EXAMPLE (SHORTEST ROUTE)
!zer!nde
sen!n
X!j
31 efe phetestpoth
=
1
m!nz =
Ec!px!s
d
_
Cost- '
g!o! \
düşün
1
m!nz = 100 x12 + 30x13 + 20 x23 + 1034 +
15x42 + 68x35 + 5045 ←
· r!r !
source
exte trassn!pment g!rel = G!zen
nodes +
X12 +
113 = 1 b!r! seç!len
- 2
yolda
&
Rode2 +
X12 + X12 =
X2 + 1 + hade oldağo
!ç!p
1
!nputs g!ren-alken =
mode3 - X13 + X23 = X34 + X35 >
- hedel değ"l -
g!ren = alde
mode 4 Xu2
->
Xzu = + X
+5
nodes =
Xg5 + Xu5 =
0 g!ren = sl!e - O
L!ndgee
AN EXAMPLE (TRANSSHIPMENT)
supp □
θ
%* We denends
>
-
Horp
ง, I
≠
tümem
% 0
β
0000000000
melt
J el!m!zbekenstme!nt !
y frels
akan
- zeraa
g!ren
>
- zerana g!ren çıka
] g!ver
replen deverd!
-
kers " enel
"
จั๋
MAXIMUM FLOW
!ntere
↑
=
ab!z
& at!f!c!al
o
top!e ,
dovete
s!ndle g!ve
dd
sourcecenter
Xo
=
QO nebel
b!z!m Xo
ara nodeler 1-2-3
∞
nodef
X80 , X 1
S = X
2+ ,3
m!ktarı g!ren alzan
S03 borudan
geçen petrol
source
S!- s!nz
X!j >
rode 2
]
XS0 , 2 ≤2
Kop ps!te
en fazla kon !ş * + X
c, 2 s012 =
X25!
göndereb!l!r!m
1
y ,
34 sınırsanı node3
X3 s! [1 X2 3
,
X3 , s!
1
=
,
Xo = X50 , 1 + Xso , 2 toplan G!ze
X3 ,
s! +
X2 , s! = Xo - toplan g!ren
REFERENCES
¡ Taha, H. A. (2013). Operations research: an introduction. Pearson Education India.
¡ Hillier, F. S., & Lieberman, G. J. (2015). Introduction to operations research. McGraw-Hill,.
¡ Bazaraa, M. S., Jarvis, J. J., & Sherali, H. D. (2011). Linear programming and network flows. John Wiley & Sons.
¡ Massachusetts Institute of Technology, Mathematics Department, Operations Research Class Notes
¡ DELFT University of Technology, Mathematics Department, Operations Research Class Notes
¡ Taiwan Technical University, Ling-Chieh Kung’s Class Notes