# Simplex - Network flow problem : Arc from 1 to P with infinite capacity

The Network - Maximum flow problem below aims to find the maximum flow using simplex method :

With the LP as follow :

LP : $$\begin{Bmatrix} Z(Max) = \sum_{i=1}^{m} fi \\ Af =0 \end{Bmatrix}$$

Incidence Matrix :

With arcs indexed {1,2,3,4,5} in red.

Question part

As mentioned above, I need to get the Maximum Flow using the simplex method.
Can someone please solve it, and explain to me how to they did.

Edit :

To solve this problem using the simplex method I had to add artificial variables, which gave me the following LP :

$$\begin{Bmatrix} f_{1} + f_{2} - f_{5} = 0\\ f_{1} + f_{3} = 0\\ -f_{2} + f_{4} = 0\\ -f_{3} -f_{4} + f_{5} = 0\\ \\ f_{1}\leq 4\\ f_{2}\leq 4\\ f_{3}\leq 2\\ f_{4}\leq 3 \end{Bmatrix}$$

• Do you understand how to apply Simplex here? How would you do it? What have you tried? Commented May 28, 2020 at 18:14
• The last row of your incidence matrix is incorrect. Note that each column should one $1$ and one $-1$, with the other entries $0$. Commented May 28, 2020 at 18:54
• @dhasson yes, I just added how I did proceed to solve this problem, to solve this problem using simplex method I added artificial variables which gave me the LP -I added above- which it should be solved using simplex method, and here we come to the point I where I struggle. Commented May 28, 2020 at 23:07
• @RobPratt thank you sir, I just corrected the last row of the incidence matrix and added how did I proceed to get the LP which I'm struggling to solve using the simplex method Commented May 28, 2020 at 23:08
• Your arc 5 and matrix column 5 do not match. Your matrix row 2 and constraint 2 do not match. Commented May 29, 2020 at 1:52