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

enter image description here

With the LP as follow :

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

Incidence Matrix :

enter image description here
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.

Thanks in advance.

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}

  • $\begingroup$ Do you understand how to apply Simplex here? How would you do it? What have you tried? $\endgroup$ – dhasson May 28 at 18:14
  • 1
    $\begingroup$ The last row of your incidence matrix is incorrect. Note that each column should one $1$ and one $-1$, with the other entries $0$. $\endgroup$ – RobPratt May 28 at 18:54
  • $\begingroup$ @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. $\endgroup$ – JirenOppaik May 28 at 23:07
  • $\begingroup$ @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 $\endgroup$ – JirenOppaik May 28 at 23:08
  • $\begingroup$ Your arc 5 and matrix column 5 do not match. Your matrix row 2 and constraint 2 do not match. $\endgroup$ – RobPratt May 29 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.