Exxo 76 is an oil company that operates the pipeline network shown below,where each pipeline is labeled with its maximum flow rate in million cubic feet (MMcf)per day.A new oil well has been constructed near A.They would like to transport oil from the well near A to their refinery at G.Formulate and solve a network optimization model to determine the maximum flow rate from A to G.

Question

Quizplus · Accepted Answer

The Answer is This is a maximum flow problem.Associated with each pipe in the network will be an arc (or,for pipes which might flow in either direction,two arcs,one in each direction).To set up a spreadsheet model,first list all of the arcs as shown in B5:C19,along with their capacity (F5:F19).Then list all of the nodes as shown in H5:H11.All the transshipment nodes (every node except the start node A and the end node G)will be constrained to have net flow = 0 (Supply/Demand = 0).The start node (A)and end node (G)are left unconstrained.We want to maximize the net flow out of node A.

This is a maximum flow problem.Associated with each pipe in the network will be an arc (or,for pipes which might flow in either direction,two arcs,one in each direction).To set up a spreadsheet model,first list all of the arcs as shown in B5:C19,along with their capacity (F5:F19).Then list all of the nodes as shown in H5:H11.All the transshipment nodes (every node except the start node A and the end node G)will be constrained to have net flow = 0 (Supply/Demand = 0).The start node (A)and end node (G)are left unconstrained.We want to maximize the net flow out of node A. The changing cells are the amount of flow to send through each pipe (arc).These are shown in Flow (D5:D19)below,with an arbitrary value of 0 entered for each.The flow through each arc is capacitated as indicated by the <= in E5:E19. For each node,calculate the net flow as a function of the changing cells.This can be done using the SUMIF function.In each case,the first SUMIF function calculates the flow leaving the node and the second one calculates the flow entering the node.For example,consider the A node (H5).SUMIF(From,Nodes,Flow)in I5 sums each individual entry in Flow (the changing cells in D5:D19)if that entry is in a row where the entry in From (B5:B19)is the same as in the entry in that row of Nodes are rows 5 and 6,the sum in the ship column is only over these same rows,so this sum is D5+D6. The goal is to maximize the amount shipped from A to G.Since nodes B through F are transshipment nodes (net flow = 0),any amount that leaves A must enter G.Thus,maximizing the flow out of A will achieve our goal.Thus,the formula entered into the objective cell MaximumFlow (D21)is =I5. The Solver information and solved spreadsheet are shown below. Thus,Flow (D5:D19)indicates how to send oil through the network so as to achieve the Maximum Flow (D21)of 34 thousand gallons/hour.

The changing cells are the amount of flow to send through each pipe (arc).These are shown in Flow (D5:D19)below,with an arbitrary value of 0 entered for each.The flow through each arc is capacitated as indicated by the <= in E5:E19.

For each node,calculate the net flow as a function of the changing cells.This can be done using the SUMIF function.In each case,the first SUMIF function calculates the flow leaving the node and the second one calculates the flow entering the node.For example,consider the A node (H5).SUMIF(From,Nodes,Flow)in I5 sums each individual entry in Flow (the changing cells in D5:D19)if that entry is in a row where the entry in From (B5:B19)is the same as in the entry in that row of Nodes are rows 5 and 6,the sum in the ship column is only over these same rows,so this sum is D5+D6.

The goal is to maximize the amount shipped from A to G.Since nodes B through F are transshipment nodes (net flow = 0),any amount that leaves A must enter G.Thus,maximizing the flow out of A will achieve our goal.Thus,the formula entered into the objective cell MaximumFlow (D21)is =I5.

The Solver information and solved spreadsheet are shown below.

Thus,Flow (D5:D19)indicates how to send oil through the network so as to achieve the Maximum Flow (D21)of 34 thousand gallons/hour.

Exxo 76 Is an Oil Company That Operates the Pipeline