Given:

c =

[[0, 3, 4, 0, 0],

[0, 0, 1, 0, 2],

[0, 0, 0, 5, 0],

[0, 0, 0, 0, 6],

[1, 1, 0, 0, 0]]

s = 0

t = 4

if c(i, j) = 0, then the graph has no edge from vertex i to vertex j

Question: Model the above problem in such a way that, we can use scipy.linprog() to solve it.

Exercise 4 (Linear Programming #2) In the maximum flow problem, we are given a network, and our goal is to route the maximum amount of flow from a source node to a sink node, without exceeding the capacity on any edge of the network. MAXIMUMFLOW Input: A directed graph G- (V,E), a source node s EV, a sink node tEV and a capacity ce on each edge e e E Output: A flow fe for each edge e E E with the following properties . For each edge e E E, we have 0S fe (i.e., the flow is less than the capacity) . For all nodes v EV except s and t, the flow entering v equals the flow exiting v: (v,w) (u,v)EE ,u)EE . The total flow from s to t is maximum. Since all flow exits s, this can be written as f(sa) (s,u) maximize Exercise 4 (Linear Programming #2) In the maximum flow problem, we are given a network, and our goal is to route the maximum amount of flow from a source node to a sink node, without exceeding the capacity on any edge of the network. MAXIMUMFLOW Input: A directed graph G- (V,E), a source node s EV, a sink node tEV and a capacity ce on each edge e e E Output: A flow fe for each edge e E E with the following properties . For each edge e E E, we have 0S fe (i.e., the flow is less than the capacity) . For all nodes v EV except s and t, the flow entering v equals the flow exiting v: (v,w) (u,v)EE ,u)EE . The total flow from s to t is maximum. Since all flow exits s, this can be written as f(sa) (s,u) maximize