6
$\begingroup$

I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know how to do is to solve this for maximum flow using the simplex method of linear programming.

I know that I would need to put values into a matrix which I could then pass through the R function rref() which puts the matrix into row reduced echelon form, but what I am not sure about is what values need to be put into this matrix. What would such a matrix look like?

enter image description here

I have tried to follow Oguz Toragay's advice but I must be doing something wrong because my matrix is clearly not correct. I made a LHS matrix which was all the inflows for each node, and a RHS list that was all the outflows for each node, then binded them together to make A, but the sides clearly do not equal each other. I have written the following code:

#LHS 
#from      1   2   3   4   5   6   7
node1 = c( 0,  0,  0,  0,  0,  0,  0)
node2 = c(20,  0,  0,  0, 15,  0,  0)
node3 = c(15,  0,  0, 13,  0,  0,  0)
node4 = c( 0, 10, 13,  0,  0,  0,  0)
node5 = c( 0, 15,  0, 10,  0,  7,  0)
node6 = c( 0,  0, 15,  0,  7,  0,  8)
node7 = c( 0,  0,  3, 12,  0,  8,  0)
node8 = c( 0,  0,  0,  0, 10,  8, 10)
LHS = rbind(node1,node2,node3,node4,node5,node6,node7,node8)

#RHS
#to           1   2   3   4   5   6   7   8
node1o = sum( 0, 20, 15,  0,  0,  0,  0,  0)
node2o = sum( 0,  0,  0, 10, 15,  0,  0,  0)
node3o = sum( 0,  0,  0, 13,  0, 15, 10,  0)
node4o = sum( 0,  0, 13,  0, 10,  0, 12,  0)
node5o = sum( 0, 15,  0,  0,  0,  7,  0, 10)
node6o = sum( 0,  0,  0,  0,  7,  0,  8,  8)
node7o = sum( 0,  0,  0,  0,  0,  8,  0, 10)
node8o = sum( 0,  0,  0,  0,  0,  0,  0,  0)
RHS = c(node1o,node2o,node3o,node4o,node5o,node6o,node7o,node8o)

A = cbind(LHS, RHS)

# Calling A returns:
                          RHS
node1  0  0  0  0  0 0  0  35
node2 20  0  0  0 15 0  0  25
node3 15  0  0 13  0 0  0  38
node4  0 10 13  0  0 0  0  35
node5  0 15  0 10  0 7  0  32
node6  0  0 15  0  7 0  8  23
node7  0  0  3 12  0 8  0  18
node8  0  0  0  0 10 8 10   0
```
$\endgroup$

1 Answer 1

5
$\begingroup$

Here is a link that includes all the information that you need. The matrix should include all the capacity limitations on all the connections between nodes. Actually, for your example, it should be a $8\times8$ matrix with all the coefficients. Each row represents one of the constraints in your LP model. In other words for each row, you consider one of the nodes in the network and write a constraint which implies that:

$$\text{All incoming flow} = \text{All outgoing flow}$$

Also in this the matrix for a given simple network extracted from the linear model, which I think would be helpful for your problem.

$\endgroup$
4
  • $\begingroup$ Thank you that helps a lot. However I am still unsure about what to do with the values of some of the arcs because this model allows flow in both directions whereas all the ones in that link do not. For instance, would the arc with flow 15 going from 5 to 2 simply be an outflow of 5 and the arc from 2 to 5 with flow 15 be an outflow of 2? @Oguz Toragay $\endgroup$
    – Jacob Myer
    Oct 9, 2019 at 1:20
  • $\begingroup$ @JacobMyer yes exactly, putting it in that way, the model decided to choose one of the directions, either from 5 to 2 or 2 to 5. If I remember correctly both of the flows can not be positive simultaneously. $\endgroup$ Oct 9, 2019 at 1:27
  • $\begingroup$ I edited my post because I ran into a problem and must have misunderstood something about what you were saying. Could you take a look at my matrix A and tell me what I could change? $\endgroup$
    – Jacob Myer
    Oct 9, 2019 at 2:50
  • $\begingroup$ @JacobMyer look at the link below from Matlab documentation, in which the same Matlab function called rref() has been used to solve a system of equation. In linear programs the procedure is almost the same. Link: mathworks.com/help/matlab/ref/rref.html#description $\endgroup$ Oct 9, 2019 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.