Flow Distribution Network with Triangular Intuitionistic Fuzzy Number as EDGE Weight

Flow Distribution Network with Triangular Intuitionistic Fuzzy Number as EDGE Weight

B. Rajesp,

1Assistant Professor, Department of Mathematics,

University College of Engineering Pattukkottai,- 614 701, India.

S. Ismail Mohideen2

2 Associate Professor,

PG and Research Department of Mathematics, Jamal Mohamed College,

Tiruchirappalli- 620 020. India.

J. Prassanna3

3Assistant Professor (SG),

School of Computing Science and Engineering, VIT, Chennai.

Abstract This paper deals with flow distribution of a network. The objective of flow distribution network is to maximize the flow subject to the edge capacities. In this paper an algorithm is proposed to find the path with maximum flow from source node to all other nodes of a network where edge weights are considered as triangular intuitionistic fuzzy number.

Keywords Maximal flow, Network, Label Setting Method, Intuitionistic Fuzzy Number.

1. INTRODUCTION

   Network is a graph consisting of a finite non-empty set of vertices (V), a set of edges (E) connecting the vertices (E V x V) and a set of associated weights of the edges. Maximum flow problem for a given network with flow capacities on the edge weight is to determine the maximum possible flow from source node to destination node, with

   respect to the edge capacity. The first maximum flow

   1. A is normal, (i.e.) there exists an element x0 such that

      A (x0) = 1

   2. A is fuzzy convex, (i.e.)

      A [x1 + (1 )x2]

      A (x1)A (x2), x1, x2 R, [0,1]

   3. A is upper continuous and

   4. SuppA is bounded, where Supp A = {x R:A (x) > 0}.

   2.2 Intuitionistic Fuzzy Number

   Let A = {(x, A (x), A (x)), xX} be an intuitionistic fuzzy set, then the pair (A (x), A (x) is refered here as an intuitionistic fuzzy number.

   2.3. Triangular Intuitionistic Fuzzy Number

   A triangular intuitionistic fuzzy number A in R, written as (a1, b1, c1 ; a1, b1, c1) where a1 a1 b1 c1 c1 has the membership function

   algorithm, was proposed by Ford and Fulkerson [5] in 1956. The concept of flow problems was discussed by Andrew Goldberg &Tarjan [1]. Time varying cost flow problems was

   x a1

   b1 a1

   x c1

   a1 x b1

   discussed by Cai et al. [2]. Applications of flow problem were given by Foulds [6]. The notion of fuzzy numbers was introduced by Dubois and Prade [3].In 2010, Deng Feng Li et al. [4] proposed a ranking method for triangular intuitionistic fuzzy number. In 2009, fuzzy quantities and relations in multi objective flow problem were analyzed by Mehdi Ghatee and

   A (x) = b1 c1 b1 x c1

   0 othererwise

   {

   and non-membership function of A is given by

   b x

   Mehdi Hashemi [7].

   In this paper an algorithm is proposed to find a path

   1

   b1 a1

   a1 x b1

   with maximum flow of a network with triangular intuitionisticfuzzy number as edge weight. The concept of label setting is used in this method. In Label Setting Method,

   A (x) =

   x b1

   c1 b1

   b1 x c1

   there are two types of nodes, permanent labeled nodes and temporary labeled nodes. In this method, once a node gets permanent labeled, it continues to be permanent in further iterations.

2. PRELIMINARIES

   2.1 Fuzzy Numbers

   A fuzzy subset of the real line R with membership function is called a fuzzy number if

   1 othererwise.

   {

3. ALGORITHM

   Following is the algorithm to find the path with maximum flow capacity from source node to all other nodes of a network where triangular intuitionistic fuzzy number is considered as weight of the edges.

   Step 1:

   Let N be the set of all nodes and be the source node.

   Let be the set of temporary labeled nodes and be the set of permanently labeled nodes.

   Let = and = {}.

   Let represent the capacity of the path with maximum flow from source node to node i at kth iteration. Let

   Step 9:

   Let = + 1

   If = 0, then

   {Path = < s > Path

   If , go to step 6 Else Terminate}

   Else go to step 7.

   0 = (0, 0, 0 ; 0, 0, 0). Let be the weight of the edge (, )

   and = (0, 0, 0 ; 0, 0, 0), if(, ) . Let = 0.

   Step 2:

   For all , (, ) , 0 =

   Step 3:

   The value of the membership function of the triangular

4. NUMERICAL ILLUSTRATION

   Consider a simple directed network given in figure 4.1 with seven vertices and twelve edges. Here triangular intuitionistic fuzzy numbers are considered as weight of the edges and is given in table 4.1. The problem is to find a path with maximum flow capacity from node 1 to all other nodes.

   intuitionistic fuzzy number = ( , , ; , , ) 2 5

   1 1 1 1 1 1

   and = (2, 2, 2 ; 2, 2, 2) is calculated as follows:

   If () > () then >

   If () < () then <

   1 4 7

   If () = () then = , where

   () = (1, 1, 1 ; 1, 1, 1) = (1 + 41+ 1)/6.

   Step 4:

   Using step 3, select a node y from, such that is

   3 6

   Figure 4.1 Network

   maximum. Tie can be broken arbitrarily Let +1 =

   Let = {} and = {}

   If = { }, then

   Edge	weight of the edge
   (1, 2)	(75,80,86; 70,80,90 )
   (1, 3)	(70,76,80; 60,76,85)
   (2, 3)	(30,32,36; 28,32,38)
   (2, 4)	(48,52,56; 40,52,58)
   (2, 5)	(30,36,42; 26,36,46)
   (3, 4)	(64,70,74; 50,70,80)
   (3, 6)	(20,26,30; 17,26,33)
   (4, 5)	(60,64,68; 50,64,70)
   (4, 6)	(48,50,54; 40,50,56)
   (5, 6)	(22,25,28; 20,25,30)
   (5, 7)	(28,33,35; 26,33,38)
   (6, 7)	(75,80,85; 70,80,88)

   Edge	weight of the edge
   (1, 2)	(75,80,86; 70,80,90 )
   (1, 3)	(70,76,80; 60,76,85)
   (2, 3)	(30,32,36; 28,32,38)
   (2, 4)	(48,52,56; 40,52,58)
   (2, 5)	(30,36,42; 26,36,46)
   (3, 4)	(64,70,74; 50,70,80)
   (3, 6)	(20,26,30; 17,26,33)
   (4, 5)	(60,64,68; 50,64,70)
   (4, 6)	(48,50,54; 40,50,56)
   (5, 6)	(22,25,28; 20,25,30)
   (5, 7)	(28,33,35; 26,33,38)
   (6, 7)	(75,80,85; 70,80,88)

   {For all ,+1 =

   Table 4.1 Edge weights of the Network for figure 4.1

   Let = + 1and go to step 6}, otherwise go to step 5.

   Step 5:

   For all , if (, ) compute +1 =

   Max[ , min( , )]

   Else, if (, ) then +1 = .

   For all , +1

   Let = + 1

   Go to step 4

   =

   Step 6: (Determination of path from source node s to node i)

   Select a node x arbitrarily from PLN. Let = {}

   Let = 0 and Path= < x >

   Step 7:

   Node i	Path with maximum flow from node 1 to node i	Maximum flow of the path
   2	1-2	(75,80,86; 70,80,90)
   3	1-3	(70,76,80; 60,76,85)
   4	1-3-4	(64,70,74; 50,70,80)
   5	1-3-4-5	(60,64,68; 50,64,70)
   6	1-3-4-6	(48,50,54; 40,50,56)
   7	1-3-4-6-7	(48,50,54; 40,50,56)

   Node i	Path with maximum flow from node 1 to node i	Maximum flow of the path
   2	1-2	(75,80,86; 70,80,90)
   3	1-3	(70,76,80; 60,76,85)
   4	1-3-4	(64,70,74; 50,70,80)
   5	1-3-4-5	(60,64,68; 50,64,70)
   6	1-3-4-6	(48,50,54; 40,50,56)
   7	1-3-4-6-7	(48,50,54; 40,50,56)

   If = (+1) then go to step 9

   Applying the algorithm, one of the paths with maximum flow capacity from node 1 to all other nodes is computed and is given in table 4.2.

   Otherwise go to step 8

   Step 8:

   Path = < > Path

   Let =

   Go to step 7.

   Table 4.2 Path and its maximum flow

5. CONCLUSION

In this paper a new method is proposed to find a path with maximum flow from source node to all other nodes with triangular intuitionistic fuzzy numbers as edge weights. An example is provided to illustrate the method.

REFERENCES

1. Andrew V. Goldberg., Tarjan, R. E., A new approach to the maximal flow problem, Journal of the association for computing machinery, Vol. 35, No 4, Oct 1988, 921-940.

2. Cai, X., Sha, D., Wong, C. K., Time varying minimum cost flow problem, European Journal of Operations research 131 (2001) 352- 374.

3. Dubois, D., and Prade, H., Operations of Fuzzy Numbers, Internat.J.Systems Sci. 9(6), 1978, 613-626.

4. Deng Feng Li., Jiang Xia Nan. and Mao Jun Zhang., A Ranking Method of Triangular Intuitionistic Fuzzy Numbers and Applications to Decision Making, International Journal of Computational Intelligence Systems, Vol.3, No.5, Oct 2010, 522-530.

5. Ford, L. R., JR., and Fulkerson, D.R., Maximal Flow through a network, Can. J. Math, 8(1956), 399-404.

6. Foulds, L. R., Graph Theory Appications, Springer-Verlag New York, Inc,1992, 234-236.

7. Medhi Ghatee and Medhi Hashemi, S., Fuzzy sets and systems, 60(2009), 3263-3289.