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?
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
```