Question

Explain how the maximum flow problem can be cast as a linear programming problem...

Answer 1

Formulation of Flow Maximization Problem as an L.P.P

Let S is the source and D is the target in the directed or undirected graph G = (V, E) and the path under consideration for flow between S and D are k, these paths are not necessarily all disjointed.

P1, P2, P3…, Pk are the paths between S and D and flow along these paths are F1, F2, F3, …,Fk, respectively.
It is possible to transform the flow maximization problem in to a linear programming problem with the objective of maximization of total flow between S and D with the restriction of the edges capacities that is the flow value in an edge cannot exceed the capacity of the edge and the total flow cost cannot be higher than the given budget.
The problem as L.P.P. can be formulated as

The constraints indicate that the sum of flow on an edge e must be bounded by u suffix e.

Numerical example:

​​

Since all delta j > 0, the optimality condition satisfied. Hence, the optimal flow value components are given by
F1=3, F2=1, F3=4, total flow = 8(max flow)
F(max) = 8(maximum flow).