Problem $3(40$ points$).$ Consider the max flow problem on the directed graph below with the orange

node being the source node $($node $s)$ and the green node being the terminal node $($node $t).$ The number on

each arc denotes the capacity of the arc. Do the following based on the lecture slides.

$(1).$ Please formulate the max flow problem as a linear program and solve it$.($You can solve the problem

with matlab cvx toolbox, or excel, and any other software, no codes needed.$)$

$(2).$ Formulate the dual of this problem and solve it$.($Please follow the dual problem on the lecture note.

In order to get $0-1$ solution for $y_i\text{'}$s in the slides, please add the constraint $0y_{i}1$ for each $y_i$

variable. You can solve the problem with matlab cvx toolbox, or excel, and any other software, no codes

needed.$)$

$(3).$ Find the corresponding maximum flow and minimum cut of the graph.