SEC

NETWORK FLOWS

NAME Rachit Kumar

COURSE B.Sc. Programme with chem.
SEMESTER 5
SUBMITTED TO Dr. Jaspreet Kaur Ma’am

1
 INDEX

S.No. PRACTICAL Page No.

1 Solving LPP using Graphical Method 3-5
2 Solving LPP using Simplex Method 6-8
3 Transportation Model 9-16
4 Assignment Problems 17-26
5 Shortest Path Problem 27-32
6 Minimum Spanning Tree 33-35
7 Maximum Flow Problem 36-39
8 Critical Path Method 40-46

2
 PRACTICAL-1
Graphical Method

QUESTION-1

Solve the following LPP using Graphical method.

Max z=3x+4y
subject to the constraints:
2x+2y≤80
2x+4y≤120
x,y≥0

Conclusion:
Comparing the value of z at all the corner points we find that the optimal solution is (20,20) with
the optimal value as 140.

3
 QUESTION-2

Solve the following LPP using Graphical Method.

Max z=3x+4y
Subject to the constraints:
2x+2y<=80
2x+4y<=120
x,y>=0

The optimal value is 140 and the optimal solution is x=20 and y=20.

4
 QUESTION-3

Solve the following LPP using Graphical Method

Min z=11x+3y
subject to.
4x+y>=12
2x+2y<=18
4x-5y<=0
x,y>=0

The value of the optimal value is 33.5 and the optimal solution is x=2.5 and y=2.

5
 PRACTICAL-2
Simplex Method

QUESTION-1

Solving LPP with more than two variables using Simplex method

Max F=3x+2y-z
Subject to the constraints
x+3y+z<=9
2x+3y-z>=2
3x-2y+z>=5
x,y,z>=0

The optimal value is 27 and the optimal solution is x=9, y=0 and z=20.

6
 QUESTION-2

Solving LPP with more than two variables using Simplex method

Max 4x+3y+6z
s.t.
2x+3y+2z<=440
4x+3z<=470
2x+5y<=430
x,y,z>=0

The optimal value is 1066.67 and the optimal solution is x=0, y=42.22 and z=156.67.

7
 QUESTION-3

Solving LPP with more than two variables using Simplex method

Min w=2x1+10x2+8x3
Subject to
x1+x2+x3>=6
x2+2x3>=8
-x1+2x2+2x3>=4
x1,x2,x3>=0

The optimal value is 27 and the optimal solution is x=9, y=0 and z=20.

8
 PRACTICAL-3
TRANSPORTATION MODEL

QUESTION-1

Convert the following balanced transportation problem into a LPP and solve using excel. Also solve
the problem in TORA.

Min 5x11+8x12+4x13+6x21+6x22+3x23+3x31+9x32+6x33
s.t.
x11+x12+x13=50
x21+x22+x23=40
x31+x32+x33=60
x11+x21+x31=20
x12+x22+x32=95
x13+x23+x33=35
all xij>=0

USING TORA:
USING LINEAR PROGRAMMING OPTION:

9
TRANSPORTATION MODEL OPTION:

USING EXCEL:

10
The minimum cost is 920.

QUESTION-2
Convert the following balanced transportation problem into a LPP and solve using excel. Also solve
the problem in TORA .

Min 21x11+16x12+15x13+3x14+17x21+18x22+14x23+13x24+32x31+27x32+18x33+41x34
11
s.t.
x11+x12+x13+x14=11
x21+x22+x23+x24=13
x31+x32+x33+x34=19
x11+x21+x31=6
x12+x22+x32=10
x13+x23+x33=12
x14+x24+x34=15
all xij>=0

USING TORA:

USING EXCEL:

12
The minimum cost is 646.

13
 QUESTION-3

Solve the following unbalanced transportation problem in TORA and EXCEL.

We have to balance the unbalanced TP by introducing dummy supplier with capacity (Total
demand-Total supply=200) as in the following table.

WAREHOUSE
PLANT SUPPLY
W1 W2 W3

A 28 17 26 500

B 19 12 16 300

DUMMY 0 0 0 200

DEMAND 250 250 500

USING TORA:

14
EXCEL:

LPP:
Min 28x11+17x12+26x13+19x21+12x22+16x23
s.t.
x11+x12+x13=500
x21+x22+x23=300
x31+x32+x33=200
x11+x21+x31=250
x12+x22+x32=250
x13+x23+x33=500
all xij>=0

The minimum cost is 15650

15
 QUESTION-4

Solve the following unbalanced transportation problem in TORA and EXCEL.

We have to balance the unbalanced TP by introducing dummy destination with capacity (Total
supply-Total demand=20) as in the following table.

TORA:

16
EXCEL:

LPP:
Min 4x11+8x12+8x13+16x21+24x22+16x23+8x21+16x22+24x23
s.t.
x11+x12+x13+x14=76
x21+x22+x23+x24=82
x31+x32+x33+x34=77
x11+x21+x31=72
x12+x22+x32=102
x13+x23+x33=41
x14+x24+x34=20
all xij>=0

17
The minimum cost is 2424

PRACTICAL-4
ASSIGNMENT PROBLEMS

QUESTION-1

SOLVE THE FOLLOWING PROBLEMS IN TORA AND EXCEL

18
USING EXCEL:

LPP:

Min

7x11+9x12+8x13+13x14+16x21+16x22+15x23+11x24+16x31+19x32+10x33+15x34+16x41+17x42+14x43+16x44

s.t.

x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
x11+x21+x31++x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
x14+x24+x34++x44=1

all xij>=0

19
USING TORA:

ANSWER:
X→A, Y→D, Z→C,W→B
The total minimum cost is Rs.45.

20
 QUESTION-2

USING EXCEL:
LPP:
Min 10x11+12x12+19x13+11x14+5x21+10x22+7x23+8x24+12x31+14x32+13x33+11x34+8x41+15x42+11x43+9x44
s.t.
x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
x11+x21+x31++x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
x14+x24+x34++x44=1
all xij>=0

21
USING TORA:

ANSWER

= Rs. 38

QUESTION-3

Solve the following assignment problem in TORA and EXCEL.

22
USING EXCEL:

LPP:

Min 9x11+26x12+15x13+13x21+27x22+6x23+35x31+20x32+15x33+18x41+30x42+20x43

s.t.

x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
x11+x21+x31++x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
x14+x24+x34++x44=1
all xij>=0

23
USING TORA:

ANSWER:

24
 QUESTION-4

As Total no. of persons are greater than Total no. of work so insert a dummy work to solve the
problem. (Here A,B,C,D,E,F refers to persons and 1,2,3,4,5 refers to work)

A B C D E F
I 6 2 7 6 9 4
II 2 5 8 2 3 7
III 5 8 6 3 8 4
IV 2 7 9 4 9 6
V 6 7 8 5 7 8
DUMMY 0 0 0 0 0 0

USING EXCEL:

25
USING TORA:

ANSWER:
A → IV, B → I, C → dummy , D → V, E → II , F → III
The total minimum cost is Rs.16.

26
 QUESTION-5

We use the opportunity cost table and solve the problem

USING EXCEL:

LPP:
Min 3x11+7x12+1x13+4x14+0x21+6x22+4x23+1x24+5x31+1x32+6x33+5x34+3x41+2x42+3x43+5x44
s.t.
x11+x12+x13+x14=1
x21+x22+x23+x24=1
x31+x32+x33+x34=1
x41+x42+x43+x44=1
x11+x21+x31++x41=1
x12+x22+x32+x42=1
x13+x23+x33+x43=1
x14+x24+x34++x44=1
all xij>=0

27
USING TORA:

Answer:
We will get our answer from the original table by taking into account the corresponding entries that
we got from the opportunity costs table.

Total efficiencies= 30

28
 PRACTICAL-5
SHORTEST PATH PROBLEM
QUESTION-1

Use TORA to answer the following questions.

What is the shortest path between (i) 0 to 6 (ii) 0 to 4

SOLUTION

ANSWER:
Shortest path between 0 and 6 is 0 → 1→ 3 → 4 →6 of length 19.

Shortest path between 0 and 4 is 0 → 1→ 3 → 4 of length 17.

29
 QUESTION-2

Solve the shortest route problem for the following directed graph using TORA

SHORTEST ROUTES OPTION:

30
Dijkstra Algorithm option:

 The shortest route option shows shortest distance and path between all node pairs.
 The Dijkstra's Shortest Route Algorithm displays the Shortest distance from the source node
to all other nodes and the Shortest path (sequence of nodes) from the source node to each
node.

31
 QUESTION-3

Find the shortest path between node A and node F using EXCEL solver.

SOLUTION:

ANSWER:

A →C → E → D→ F is the shortest path of length 20.

QUESTION-4
32
Find the shortest route between node 1 and node 5 using EXCEL.

SOLUTION:

ANSWER:

1 →3 → 5 is the shortest path of length 90.

Alternative solution is 1 →3 → 4 →5

33
 QUESTION-5

Find the shortest route between node A and node E for the following directed graph using EXCEL.

SOLUTION:

ANSWER:

A →C → E is the shortest path of length 18.

34
 PRACTICAL-6
MINIMUM SPANNING TREE

QUESTION-1
Find minimal spanning tree from the following network using TORA.

SOLUTION:

ANSWER:

The minimum spanning tree is highlighted above in the figure and its length is 16.
QUESTION-2

35
Find the minimum spanning tree of the following network in EXCEL using Kruskal’s Algorithm.

SOLUTION:

ANSWER:

The minimum spanning tree is highlighted above in the figure and its length is 37.

QUESTION-3

36
Find the minimum spanning tree of the following undirected graph in EXCEL using Kruskal’s
Algorithm.

SOLUTION:

ANSWER:

The minimum spanning tree is highlighted above in the figure and its length is 17.

PRACTICAL-7
MAXIMUM FLOW PROBLEM
37
 QUESTION-1

Find Maximal flow from Source A to Sink Z in the following network using TORA.

SOLUTION:

The maximum flow in network is 13.

QUESTION-2

38
Use TORA to find Maximal flow from Source 0 to Sink 5 in the following network

SOLUTION:

The maximum flow in network is 23.

QUESTION-3

39
Find the maximal flow using EXCEL for the following network.

SOLUTION:

The maximum flow in network is 13.

QUESTION-4

40
Find the maximal flow using EXCEL for the following network.

SOLUTION:

The maximum flow in network is 23.

PRACTICAL-8
CRITICAL PATH METHOD

41
 QUESTION-1

Find Critical Path, minimum completion time, critical activities and non-critical activities for the
below project diagram in TORA.

SOLUTION:

42
The critical path is C → F → J →L
The minimum completion time is 47.
Critical Activities are C, F, J and L.
Non-Critical Activities are A, D, G, K, B, E, H and I.

43
 QUESTION-2

SOLUTION:

Network:

44
The critical path is A → D → F →H
The minimum completion time is 18 days.

45
 QUESTION-3

SOLUTION:

Network:

Here, X,Y,Z,U,V,P and Q are dummy activities.

46
The critical path is A→C→D→X(dummy)→G→H→I→U(dummy )→K→L→M→P(dummy)→O
The minimum completion time is 23.
Critical Activities are A, C, D, X(dummy), G, H, I, U(dummy), K, L, M ,P(dummy) and O.
Non-Critical Activities are E, F, J, N and B.

47