ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Decomposition of network part 2 bk

•
•
Bansi Kansagara
Bansi Kansagara

The Barkley and Motard algorithm converts a digraph into an equivalent signal flow graph (SFG) by interchanging nodes and edges. It then decomposes the network by tearing or cutting nodes in the SFG. The algorithm proceeds by (1) eliminating nodes with a single precursor and replacing them, (2) cutting any self-loop nodes and assigning them to the cut-set, (3) handling any two-way edges by assigning one node to the cut-set, and (4) if needed, selecting the node with the most output edges to cut. When the SFG is fully reduced, the cut-set of tear streams is identified.

1 of 5
Download to read offline
Chapter 4 Partioning And Tearing Bansi_Kansagra 1 THE BARKLEY AND MOTARD ALGORITHM:- Barkley and Motard (B&M) (1972) suggest an alternate representation of a digraph by interchanging nodes and edges known as a ‘signal flow graph (SFG)’. It contains as nodes what are the edges in a digraph and vice versa. The decomposition procedure is then applied on the SFG by tearing or cutting nodes in place of edges on a digraph. The following steps are involved in decomposition of a network using theB&M algorithm: Step 1 Convert the digraph into an equivalent SFG. Step 2 Eliminate any node with asingle precursor, sinceit belongs to that precursor. Replace such a node whenever it appears as a precursor by its header node. Step 3 If any self-loops appear, cut those nodes and assign them to the cut-set. Eliminate such nodes, which may render the graph reducible again, i.e., nodes may now appear with a single precursor. Step 4 Two-way edges can also prevent complete reduction of the SFG. A two- way edge is shown in Figs 12.3 and 12.4. In the figure, the situation presented is for the jth node. Before the SFG is totally reduced, two-way edges as shown below may appear; in such a situation, assign either the ith or the yth node to the cut-set. Fig. 12.3 Simple two-way edge Fig. 12.4 Compound two-way edges
Chapter 4 Partioning And Tearing Bansi_Kansagra 2 Step 5 If all other conditions fail to appear, select the node with the maximum number of output edges for cutting. Step 6 When SFG is totally reduced, the cut-set is found. Illustration 12.1 Using the Barkley and Motard (1972) method (B&M algorithm) for the decomposition of a maximal cyclic net (MCN), find out the streams that are to be teared (i.e., cut-set) for the digraph (Fig. 12.1) of a process: (decomposition is by a minimum number of tear streams, all of them assigned unit weight). Solution First reduction Eliminate any node with a single precursor, since it belongs to that precursor. Then, replace such a node whenever it appears as a precursor by its header node.
Chapter 4 Partioning And Tearing Bansi_Kansagra 3 Note Replace the nodes which are eliminated with their precursors. In the above table, (1) eliminate each node with only one precursor (i.e., remove nodes 1, 3, 5, 8 since these belong to that precursor) and (2) replace such nodes in all their occurrences in the list of precursors by their precursors, i.e., we need to replace node 3 with its precursor 2. Similarly, we replace node 5 with its precursor 7, node 1 with its precursor 2, and node 8 with its precursor 7. The remaining nodes are 2, 4, 6, and 7. (If nodes 1, 3, 5, 8 are removed.) The remaining nodes are shown above in which two ‘self- loops’ are formed at nodes 2 and 7. Now cut these nodes, remove them from the above table and repeat the same procedure. As a result, the SFG is totally reduced and the cut-set found consists of nodes 2 and 7 (where self-loops are formed) or equivalent streams 2 and 7 in the digraph of Fig. 12.1
Bansi_Kansagra 4 THE BASIC TEARING ALGORITHM:- This is also based on the concept of SFG. Pho and Lapidus (1973a, 1973b) presented an alternative algorithm which offers the advantage of assigning any arbitrary weights (weigh each stream with a number reflecting the probable degree of difficulty that can be encountered in an iterative procedure to converge) to the edges or streams of a digraph. It locates the cut-set of tear streams by minimizing the sum of their weights. This is equivalent to finding minimum weights of tear streams when all of them are assigned unit weights. The features of the basic tearing algorithm (BTA) are as given below: 1. The reduced digraph (one that excludes feed and product streams) is first converted into an equivalent SFG. 2. Information on the SFG is provided to the algorithm in the form of an adjacent matrix. 3. Ineligible nodes arefound according tothefollowing criterion: If theweight of node i is greater than or equal to the sum of weights of non-zero elements in the first rows of the matrix, then that node is ineligible. 4. The reduction of ineligible node I is performed as follows: Shift the elements of column I to those columns in row I containing non-zero elements forming a Boolean sum. Make row I and column I null. 5. Primarily the cut node is found by locating a self-loop. 6. If no ineligible nodes are found, then two-way edges are searched. 7. When all attempts fail, the branch and bound method is ultimately applied to totally reduce the SFG. The algorithm is shown in Fig. 12.5.
Bansi_Kansagra 5

More Related Content

Decomposition of network part 2 bk

  • 1. Chapter 4 Partioning And Tearing Bansi_Kansagra 1 THE BARKLEY AND MOTARD ALGORITHM:- Barkley and Motard (B&M) (1972) suggest an alternate representation of a digraph by interchanging nodes and edges known as a ‘signal flow graph (SFG)’. It contains as nodes what are the edges in a digraph and vice versa. The decomposition procedure is then applied on the SFG by tearing or cutting nodes in place of edges on a digraph. The following steps are involved in decomposition of a network using theB&M algorithm: Step 1 Convert the digraph into an equivalent SFG. Step 2 Eliminate any node with asingle precursor, sinceit belongs to that precursor. Replace such a node whenever it appears as a precursor by its header node. Step 3 If any self-loops appear, cut those nodes and assign them to the cut-set. Eliminate such nodes, which may render the graph reducible again, i.e., nodes may now appear with a single precursor. Step 4 Two-way edges can also prevent complete reduction of the SFG. A two- way edge is shown in Figs 12.3 and 12.4. In the figure, the situation presented is for the jth node. Before the SFG is totally reduced, two-way edges as shown below may appear; in such a situation, assign either the ith or the yth node to the cut-set. Fig. 12.3 Simple two-way edge Fig. 12.4 Compound two-way edges
  • 2. Chapter 4 Partioning And Tearing Bansi_Kansagra 2 Step 5 If all other conditions fail to appear, select the node with the maximum number of output edges for cutting. Step 6 When SFG is totally reduced, the cut-set is found. Illustration 12.1 Using the Barkley and Motard (1972) method (B&M algorithm) for the decomposition of a maximal cyclic net (MCN), find out the streams that are to be teared (i.e., cut-set) for the digraph (Fig. 12.1) of a process: (decomposition is by a minimum number of tear streams, all of them assigned unit weight). Solution First reduction Eliminate any node with a single precursor, since it belongs to that precursor. Then, replace such a node whenever it appears as a precursor by its header node.
  • 3. Chapter 4 Partioning And Tearing Bansi_Kansagra 3 Note Replace the nodes which are eliminated with their precursors. In the above table, (1) eliminate each node with only one precursor (i.e., remove nodes 1, 3, 5, 8 since these belong to that precursor) and (2) replace such nodes in all their occurrences in the list of precursors by their precursors, i.e., we need to replace node 3 with its precursor 2. Similarly, we replace node 5 with its precursor 7, node 1 with its precursor 2, and node 8 with its precursor 7. The remaining nodes are 2, 4, 6, and 7. (If nodes 1, 3, 5, 8 are removed.) The remaining nodes are shown above in which two ‘self- loops’ are formed at nodes 2 and 7. Now cut these nodes, remove them from the above table and repeat the same procedure. As a result, the SFG is totally reduced and the cut-set found consists of nodes 2 and 7 (where self-loops are formed) or equivalent streams 2 and 7 in the digraph of Fig. 12.1
  • 4. Bansi_Kansagra 4 THE BASIC TEARING ALGORITHM:- This is also based on the concept of SFG. Pho and Lapidus (1973a, 1973b) presented an alternative algorithm which offers the advantage of assigning any arbitrary weights (weigh each stream with a number reflecting the probable degree of difficulty that can be encountered in an iterative procedure to converge) to the edges or streams of a digraph. It locates the cut-set of tear streams by minimizing the sum of their weights. This is equivalent to finding minimum weights of tear streams when all of them are assigned unit weights. The features of the basic tearing algorithm (BTA) are as given below: 1. The reduced digraph (one that excludes feed and product streams) is first converted into an equivalent SFG. 2. Information on the SFG is provided to the algorithm in the form of an adjacent matrix. 3. Ineligible nodes arefound according tothefollowing criterion: If theweight of node i is greater than or equal to the sum of weights of non-zero elements in the first rows of the matrix, then that node is ineligible. 4. The reduction of ineligible node I is performed as follows: Shift the elements of column I to those columns in row I containing non-zero elements forming a Boolean sum. Make row I and column I null. 5. Primarily the cut node is found by locating a self-loop. 6. If no ineligible nodes are found, then two-way edges are searched. 7. When all attempts fail, the branch and bound method is ultimately applied to totally reduce the SFG. The algorithm is shown in Fig. 12.5.