PRACTICAL FILE

NETWORK FLOWS

NAME: NEERAV JAIN

ROLL NO. 25/1017
SEMESTER: 1ST
BA(H) BUSINESS ECONOMICS
CS
 Introduction to Network Flows

A network flow model represents movement of a commodity (goods, data, people)

through a directed graph where nodes are locations and arcs are routes. Each arc
has a capacity limiting how much can flow through it, and flow must satisfy
conservation at intermediate nodes (what comes in goes out) except at source(s) or
sink(s).

In operations research, many allocation or transportation problems can be framed as

minimum-cost network flows: given supplies at some nodes and demands at
others, assign flows across arcs (with cost per unit) so that total cost is minimised
while respecting capacities and supply/demand constraints.

The classic models—like the transportation problem (multiple supply nodes →

multiple demand nodes) and the assignment problem (each agent to exactly one
task)—are special cases of network flows. This framework allows visualising
problems as networks, writing them in terms of flows, costs, and constraints, and
thus applying systematic solution approaches.
s

goods, data, people)

e routes. Each arc
must satisfy
xcept at source(s) or

ms can be framed as
and demands at
cost is minimised

e supply nodes →
gent to exactly one
s visualising
constraints, and
 1. Balanced Transportation Problem
Scenario: A company has three factories (F1, F2, F3) producing identical widgets,
and three regional warehouses (W1, W2, W3) that demand those widgets.
Data:
Supplies: F1 = 50 units, F2 = 70 units, F3 = 80 units (total supply = 200).
Demands: W1 = 60 units, W2 = 90 units, W3 = 50 units (total demand = 200).
Shipping cost per unit:

W1 W2 W3
F1 4 7 9
F2 5 6 8
F3 3 4 7

2. Unbalanced Transportation Problem

Scenario: A logistics firm must ship goods from four plants (P1, P2, P3, P4) to three
markets (M1, M2, M3). The total supply exceeds total demand.
Data:
Supplies: P1 = 40, P2 = 60, P3 = 50, P4 = 30 (total supply = 180).
Demands: M1 = 50, M2 = 70, M3 = 40 (total demand = 160).
Shipping cost per unit:

M1 M2 M3
P1 6 5 8
P2 7 4 6
P3 5 9 3
P4 4 6 7

3. Prohibited Cell Transportation Problem

Scenario: A manufacturer ships products from two warehouses (A and B) to four stores (S
S2, S3, S4). One route is not feasible (prohibited) because store S3 cannot be served by
warehouse B due to contract restrictions.
Data:
Supplies: A = 70 units, B = 90 units (total supply = 160).
Demands: S1 = 30, S2 = 50, S3 = 40, S4 = 40 (total demand = 160). Balanced in this
case.
Shipping cost per unit:

S1 S2 S3 S4
A 5 8 6 7
B 6 7 — 5

Note: “—” means it’s prohibited for B → S3 (no shipping allowed).

ng identical widgets,
ose widgets.

pply = 200).
demand = 200).

P3, P4) to three

nd B) to four stores (S1,

annot be served by

. Balanced in this
 Question 1: Balanced Assignment Problem
Scenario: A company has four salespersons (S1, S2, S3, S4) and four sales territori
(T1, T2, T3, T4). The cost (in thousands of rupees) of assigning each salesperson to
each territory is given below:

T1 T2 T3 T4
S1 8 5 9 6
S2 7 4 8 5
S3 9 6 7 8
S4 6 3 5 4

Question 2: Unbalanced Assignment Problem

Scenario: A firm has five interns (I1, I2, I3, I4, I5) and three projects (P1, P2, P3).
Each intern can be assigned to at most one project; each project needs exactly one
intern. The cost (in thousands of rupees) of assigning each intern to each project is:

P1 P2 P3
I1 4 7 5
I2 6 3 8
I3 5 9 4
I4 8 6 7
I5 3 8 6

Question 3: Assignment Problem with Prohibited (Restricted) Assignments

Scenario: A small hospital needs to assign four nurses (N1, N2, N3, N4) to four
different wards (W1, W2, W3, W4). However, nurse N3 cannot be assigned to ward
W2 (maybe for medical/specialisation reasons). The cost (in thousands of rupees) o
assigning each nurse to each ward is:

W1 W2 W3 W4
N1 5 7 6 4
N2 4 6 5 3
N3 7 — 8 6
N4 3 5 4 2

(Here “—” indicates that N3 → W2 is forbidden/prohibited.)

nd four sales territories
g each salesperson to

ects (P1, P2, P3).

ct needs exactly one
rn to each project is:

cted) Assignments
N3, N4) to four
be assigned to ward
ousands of rupees) of
1. What is the shortest path problem?
In simple terms: given a graph (a network of nodes/vertices and arcs/edges) where each
has an associated weight (cost, distance, time, etc.), the shortest path problem is the task
finding a path between two nodes such that the sum of the weights of the arcs in the p
is minimised.

The graph may be directed (each arc has a direction) or undirected (arcs can be used in
either direction).

The weights on arcs could represent distance, time, cost, or more abstract “effort”. For
example: in a road map intersection = node, road-segment = arc, weight = length of the
road.

A “path” is a sequence of nodes connected by arcs (respecting directions if directed). The

“cost” of a path is the sum of the weights of those arcs. The goal is the path from a source
node to a target node (or to all other nodes) with the minimal cost.

2. Why is it useful / where is it used?

Navigation and routing: finding the fastest or shortest route from Point A to Point B (vehic
pedestrians, data packets).

Network design & data communication: shortest path algorithms help with efficient data
routing, minimising delay or cost.

Logistics & operations research: even in supply‐chain or transportation problems, the idea
“cheapest route” mirrors shortest‐path thinking (though those problems often add
supply/demand, capacities etc).
Graph theory / algorithms: as a core problem that helps develop algorithmic skills (greedy
dynamic programming, graph traversal).

3. Variants of the problem

There are several common variants:
Single‐source shortest paths: From a given source node to all other nodes. (E.g., find

Single‐pair shortest path: From one specified node 𝑠to another specified node 𝑡.
shortest cost from node S to each other node in the graph.)

All‐pairs shortest paths: For every pair of nodes (𝑢ⓜ,𝑣)find the shortest path. (E.g., wha
the shortest distance between any two cities in a network.)

4. Key properties & considerations

If the graph has non-negative weights on all arcs, some algorithms become efficient (e
Dijkstra’s Algorithm).

If the graph has negative weight arcs, more care is needed — e.g., the Bellman‑Ford
Algorithm can handle negative weights (and detect negative cycles).

If the graph contains a negative cycle reachable from the source, a “shortest path” migh
not be well‐defined because you can loop around the negative cycle infinitely and keep
reducing cost.

The problem of shortest path is simpler (in structure) than many more complex network fl
or transport problems: typically you just care about a path cost, not supply/demand at nod
or capacities. But it shares the same “network + cost” paradigm.
If the graph contains a negative cycle reachable from the source, a “shortest path” migh
not be well‐defined because you can loop around the negative cycle infinitely and keep
reducing cost.

The problem of shortest path is simpler (in structure) than many more complex network fl
or transport problems: typically you just care about a path cost, not supply/demand at nod
or capacities. But it shares the same “network + cost” paradigm.
 /edges) where each arc
h problem is the task of
s of the arcs in the path

(arcs can be used in

bstract “effort”. For

ight = length of the

ons if directed). The

e path from a source

t A to Point B (vehicles,

with efficient data

n problems, the idea of

ms often add

rithmic skills (greedy,

er nodes. (E.g., find

ecified node 𝑡.
rtest path. (E.g., what is

become efficient (e.g.,

the Bellman‑Ford

“shortest path” might

nfinitely and keep

e complex network flow

upply/demand at nodes
“shortest path” might
nfinitely and keep

e complex network flow

upply/demand at nodes
 Practical File
Case Study: Shipping Wood to Market

Alabama Atlantic is a lumber-company that obtains raw wood from three sources and
supplies finished or semi-finished wood (board-feet) to five market destinations. In the
past, Alabama Atlantic used rail transport exclusively, but because shipping costs by
rail have been increasing, management is investigating the alternative of using water
(ship) transport along certain routes. This involves additional capital investment in
ships for the water routes. (Data adapted from Hillier & Lieberman, Case 8.1
“Shipping Wood to Market”.)

Data Sources:
Source 1: Annual availability = 15 million board-feet
Source 2: Annual availability = 20 million board-feet
Source 3: Annual availability = 15 million board-feet
Markets (destinations):
Market 1: Demand = 11 million board-feet
Market 2: Demand = 12 million board-feet
Market 3: Demand = 9 million board-feet
Market 4: Demand = 10 million board-feet
Market 5: Demand = 8 million board-feet
Shipping costs by route (in thousands of dollars per 1 million board-feet):
By rail: for each source-market pair there is a cost (e.g., Source 1 → Market 1 = $61k,
→ Market 2 = $72k, etc)
By ship (when feasible): for each source-market pair where water transport is feasible
there is a cost (e.g., Source 1 → Market 1 by ship = $31k, etc)

Capital investment requirement: For using ship transport on a given route, there
is a capital investment cost (in thousands of dollars per 1 million board-feet annually)
for ships required for that route. Considering the useful life and time value of money,
the annual equivalent is one-tenth of those investment amounts.

Problem Statement
Alabama Atlantic must decide how to allocate shipments from the three sources to
the five markets so that:
Each source’s supply is not exceeded.
Each market’s demand is met.
The overall annual cost (which includes transportation cost by rail or ship, plus the
annualised investment cost if ship transport is used) is minimised.
They are considering three policy options:
Continue shipping exclusively by rail.
Use exclusively water (ship) transport on routes where feasible (otherwise rail).
For each route choose the mode (rail or ship) that gives the lowest cost, subject to
feasibility.
The decision should also factor in expected future cost changes (e.g., rail cost
increases, ship investment amortisation, fuel cost changes, etc).
increases, ship investment amortisation, fuel cost changes, etc).

Key Considerations
Feasibility of ship transport: Not all source-to-market routes may be feasible by
ship (e.g., due to geography, lack of port access, waterway limitations).
Fixed investment cost: If ship transport is used on a route, the capital investment
must be carried regardless of volume (though in this simplified case the investment is
modelled per million board-feet).
Mode choice trade-off: While ship transport may have lower per-unit variable cost
on some routes, the fixed investment cost may offset that advantage unless volumes
are sufficient.
Supply–demand balance: Total supply = 15 + 20 + 15 = 50 million board-feet; total
demand = 11 + 12 + 9 + 10 + 8 = 50 million board-feet. Thus supply equals demand
in this case (a “balanced” transportation/assignment/flow problem).
Future cost dynamics: Management must anticipate how costs may evolve: e.g., if
rail cost continues rising faster than ship cost, then ship might become more
favourable; conversely, if ship fuel, maintenance or port fees increase significantly,
the advantage may vanish.
Analysis Outline
Here is how you could approach analysing this case:

Cost calculation:
For each route (i,j), compute cost per million board-feet by rail and by ship (if feasible)

Sum over all shipments 𝑥_𝑖𝑗multiplied by the appropriate cost to get total cost.
+ amortised investment (for ship) and compare.

Option evaluation:
For Option 1: set all shipments to rail. Compute total cost.
For Option 2: set all feasible shipments to ship mode. Compute total cost (including
investment amortisation).
For Option 3: for each route pick whichever mode (rail or ship) gives the lower cost;
compute total cost.
Compare the costs of the three options; assess under what circumstances one option
becomes superior (for example, if rail cost rises by x %, or ship investment
amortisation falls by y %).

Learning Points
This case illustrates the transportation/flow model in operations research: shipping
from multiple sources to multiple destinations under cost minimisation.
It introduces mode choice and fixed investment cost into a transportation
problem, extending beyond the simple cost-per-unit model.
It underscores strategic decision-making: not just the current optimal plan, but how
future cost changes and investment amortisation affect long-term strategy.
It reinforces the importance of supply–demand balancing, capacity constraints, and
cost structure (variable vs fixed).
It invites discussion of real-world complications: route feasibility, infrastructure
constraints, risk, environment, dynamic cost changes, and scenario/sensitivity
analysis.
et

ree sources and

estinations. In the
hipping costs by
ve of using water
nvestment in
ase 8.1

d-feet):
Market 1 = $61k,

nsport is feasible

ven route, there

rd-feet annually)
value of money,

ee sources to

ship, plus the

rwise rail).
ost, subject to

rail cost
 be feasible by
s).
ital investment
he investment is

nit variable cost

unless volumes

n board-feet; total
y equals demand

y evolve: e.g., if
me more
e significantly,

y ship (if feasible)

total cost.

cost (including

the lower cost;

nces one option

tment

esearch: shipping
n.
portation

plan, but how

ategy.
y constraints, and

astructure
ensitivity