Question

1. Linear programming can be used to calculate the maximum flow in a network from the source s, to the sink t. Which of the following statements below gives the correct objective function, and number of constraints for applying a linear program for computing maximum flow in the following graph? In this graph, the maximum capacity of each edge is given as the number next to the corresponding edge. The flow along an edge eſi, j) is denoted by fij. Here we only consider variables fij when there the edge eſi,j) exists. 3 3 3 N 3 2 15 marks] A. Objective function is: max (f5,1-fs.2) and the number of constraints are: 10 B. Objective function is: max (f.,1+f3.2) and the number of constraints are: 20 C. Objective function is: max (f1 + fs.2) and the number of constraints are: 14. D. Objective function is: max (3,1 + f2 - $3,1 - $1,1) and the number of constraints are: 20

Answer 1

SOLUTION:-

The objective function contain the variables showing the flow from the source node. So the objective function is, $\small \boldsymbol{max(f_{s,1}+f_{s,2})}$

There are 8 capacity constraints, each $\small \boldsymbol{f_{i,j}}$ less than or equal to the capacity given in the edge $\small \boldsymbol{e_{i,j}}$ .

There are four flow conservation constraints showing that the inflow = out flow for each node except the source and destination nodes. (there are total 4 nodes other than source and sink).

To complete into a linear programming we introduce a dummy edge from destination to source and include the conservation constraints on these two nodes.

Thus the required linear programming conversion is: $\small \boldsymbol{max(f_{s,1}+f_{s,2})}$ with a total 8+4+2=14 constraints.

Hence option is C